CSD203 -> Phần 2 | Quizlet

What is value of the Shift Folding Hash Function if K = 23-45-89-2 and TSize = 100?

A. 66

B. 23

C. 89

D. 59

D. 59

(a + b + c) / 100%

Consider the following 2 definitions about graph:

An undirected graph is called connected when there is a path between any two vertices of the graph.

If every node u in undirected graph G is adjacent to every other node v in G, a graph is said to be complete.

Which of the following statements is correct:

A. None of the other options

B. The complete graph is always connected and vise versa.

C. The connected graph is always complete.

D. The complete graph is always connected.

D. The complete graph is always connected.

In the worst case, quick sort is____

A. O(nlogn)

B. O(n^2)

C. O(n)

D. O(1)

B. O(n^2)

Run length encoding is a lossless compression method in which repeated

occurrences of a symbol are replaced by one occurrence of the symbol followed by the number of occurrences

A. True

B. False

A. True

Dijkstra's Algorithm cannot be applied on

a. Directed and weighted graphs

b. Graphs having negative weight

c. Unweighted graphs

d. Undirected and unweighted graphs

b. Graphs having negative weight

Given a raw message 'XXXXUUUUUXXXXUUXXXXXUU' (without single quote).

Run the run-length encoding algorithm for that message, what is the output?

Select one:

a. 4X5U4X2U5X2U

b. 4X4U3X2U5X2U

c. 4X5U4X3U5X2U

d. 4X5U3X2U5X2U

a. 4X5U4X2U5X2U

In the best-case, quicksort is_____

A. O(nlogn)

B. O(n)

C. O(1)

D. (n^2)

A. O(nlogn)

Linked lists allow easy insertion and deletion of information because such

operations have a local impact on the list.

True

False

True

State True or False: "Recursion bears substantial overhead. Each time the program calls a method, the system must assign space for all of the method's local variables and parameters. This can consume considerable memory and requires extra time to manage the additional space".

False

True

True

Specify the correct statement about open addressing method for handling collision

Select one:

A. Each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys

B. The collision is resolved by finding an available table entry other than the position to which the colliding key is originally hashed

C. The collision is resolved by open an address to store any collision

D. An address is opened for storing keys

B. The collision is resolved by finding an available table entry other than the position to which the colliding key is originally hashed

Select the correct statement.

Suppose T is a binary tree with 9 nodes. What is the minimum possible height

of T?

(Note: In a tree the height of root is 1)

A. 5

B. 3

C. 4

D. 2

C. 4

Select the most correct statement about complexity of quicksort.

Select one:

A. The best case is O(n), the average case is O(nlogn), and the worst case is O(n^2)

B. Both best and average cases are O(nlogn), the worst case is O(n^2)

C. The best case is O(n), and the worst case is O(n^2)

D. Both best and worst cases are O(n^2)

B. Both best and average cases are O(nlogn), the worst case is O(n^2)

In the array implementation, enqueuing can be executed in constant time O(1)

Select one:

True

False

True

Partitioning is a technique used in quicksort. The following is a partition pseudocode:

partition the array a from index low to index up

x:= a[low], i=low,j=up

do

increase i and stop at i, where a[i]>x

decrease j and stop at j, where a[j]<=x

if(i

D. 2, 3, 5, 6, 8, 11, 7, 10

Specify the correct statement about hashing algorithm (Select the best answer).

Select one:

A. The expected complexity of hashing algorithm is O(1). However by the collision resolution, sometimes it may take O(n).

B. If the chaining method is used for collision resolution, insertion and searching (and sometimes deletion) can take constant time: O(1).

C. No matter how many data items there are, insertion and searching (and sometimes deletion) always take constant time: O(1).

D. If the coalesced method is used for collision resolution, insertion and searching (and sometimes deletion) always take constant time: O(1).

A. The expected complexity of hashing algorithm is O(1). However by the collision resolution, sometimes it may take O(n).

The following is the main part of bubble sort pseudocode:

do

swapped := false

for i := 0 ton-2

if a[i] > a[i+1] then

swap(a[i],a[i+1])

swapped := true

end if

end for

while swapped

Consider the list of ten integers below:

5, 3, 10, 11, 1, 8,0,2,6,4

What is the list after the FIRST iteration (for i = 0 to n-2) in a bubble sort? (sorting from smallest to largest).

Select one:

A. 3, 5, 10, 8, 1, 0, 2, 6, 4, 11

B. 3, 5, 10, 1, 8, 0, 2, 6, 4, 11

C. 3, 5, 10, 0, 1, 8,2,6,4,11

D. 3, 5, 10, 1, 8,0,2,4,6,11

B. 3, 5, 10, 1, 8, 0, 2, 6, 4, 11

Select the most correct definition of a tree:

(1)

A tree T is a set of one or more nodes such that

T is partitioned into disjoint subsets:

- A single node r, the root

- Sets that are trees, called subtrees of r

(2)

A tree T is a set of nodes such that either

- T is empty, or

- T is partitioned into disjoint subsets:

+)A single node r, the root, and

+)Trees, called subtrees of r

(3)

A tree T is a set of nodes such that either

- T is empty, or

- T is partitioned into disjoint subsets:

+) A single node r, the root, and

+)Non-empty trees, called subtrees of r

(2)

The efficiency of searching elements in a hash table is the same as in a linked list.

Select one:

False

True

False

Partitioning is a technique used in

Select one:

A. Insertion sort

B. It is not used in sorting algorithms.

C. Quick sort

D. Bubble sort

E. Selection sort

C. Quick sort

What is the result of the breadth first traverse of the binary search tree T, after inserting the following keys into the tree sequentially (suppose T is empty before insertion):

7,8,4, 0, 1, -1, 10, 24

Select one:

A. 7,4,8, 0, 10,-1,1,24

B. 24, 10, 8, 7, 4, 1, 0, -1

C. 7,4,8, 0, 10, 1, -1,24

D. -1, 0, 1, 4, 7, 8, 10, 24

A. 7,4,8, 0, 10,-1,1,24

The height of a complete binary tree with n nodes is

1. nlog2n

2. nlog2(n+1)

3. log2(n)

4. log2(n+1)

Select one:

A. 4.

B. 3.

C. 1.

D. 2.

A. 4.

In the worst-case mergesort is

Select one:

A. O(n)

B. O(1)

C. O(n^2)

D. O(nlogn)

D. O(nlogn)

In Huffman coding, both the sender and receiver must have a copy of the same

code in order for the decoded file to match the encoded file.

Select one:

a. True

b. false

a. True

What is the best case of bubble sort algorithm?

Select one:

A. When an array to be sorted is already sorted.

B. None of the other choices

C. There is no best case for bubble sort algorithm. All cases are equal.

D. When the array is sorted in the reversed order.

A. When an array to be sorted is already sorted.

Select the statement that is most correct.

Select one:

A. For a recursive method to terminate there must be one or more limit conditions.

B. For a recursive method to terminate there must be one or more steps.

C. There is no difference between a recursive method and a non-recursive method.

D. A recursive method is a method that invokes itself directly or indirectly. For a recursive method to terminate there must be one or more base cases.

D. A recursive method is a method that invokes itself directly or indirectly. For a recursive method to terminate there must be one or more base cases.

In the array implementation, dequeuing can be executed in constant time O(n)

Select one:

True

False

False

In the worst case, insertion sort algorithm is_____

Select one:

A. O(n)

B. O(n^2)

C. O(n^3)

D. O(nlogn)

B. O(n^2)

In all binary trees, there are 2¹ nodes at level i.

Select one:

True

False

False

State True or False: "In a binary search tree, all the nodes that are left descendants of node A have key values greater than A; all the nodes that are A's right descendants have key values less than (or equal to) A."

Select one:

True

False

False

What is the minimum number of nodes in a full binary tree with height 3?

(In a tree the height of root is 1, and in a full binary tree every node other than

the leaves has two children).

Select one:

A. 4

B. 5

C. 6

D. 7

D. 7

Specify the correct statement about coalesced chaining method for handling

collision (select the best answer).

Select one:

A. In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the last available position of the table.

B. In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the first available position of the table.

C. In coalesced hashing, the linked list is created outside the hash table and a colliding keys are put in the list connected to the colliding position of the table.

D. Because in coalesced hashing, the linked list is created inside the hash table, thus searching must be carried out sequentially.

A. In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the last available position of the table.

In the doubly linked list implementation, enqueuing can be executed in constant

time O(1).

Select one:

True

False

True

Given a description of an algorithm:

sort(data[])

{for i = 1 to data.length-1

x = data[i];

move all elements data[j] greater than x by one position from left to right;

place x in its proper position;

}

Select the most correct statement:

Select one:

A. This is bubble sort algorithm

B. It is not used in sorting algorithms.

C. This is quick sort algorithm

D. This is insertion sort algorithm

E. This is a tricky question. This method cannot be used to sort any data.

D. This is insertion sort algorithm

In a Heap tree

Select one:

A. Values in a node is greater than every value in children of it.

B. Both of other conditions applies.

C. Values in a node is greater than every value in left sub tree and smaller than right sub tree.

A. Values in a node is greater than every value in children of it.

Select the most correct statement about complexity of mergesort.

Select one:

A. Best case is O(nlogn), the worst case is O(n^2)

B. The best case is O(n), and the worst case is O(n^2)

C. Both best and worst cases are O(nlogn)

D. The best case is O(n), and the worst case is O(nlogn)

C. Both best and worst cases are O(nlogn)

What would be the time complexity to insert an element at the second position

in the linked list?

Select one:

a. None of the mentioned

b. O(1)

c. O(n²)

d. O(n)

b. O(1)

Recursive definitions on most computers are eventually implemented using a run-time stack and this implementation is done by the operating system.

Select one:

True

False

True

To implement an AVL tree, a concept balance factor is introduced (bal = height(right)-height(left). An AVL tree is created using data :(10,90,5,1,8,0,2,9}. What is the balance factor of the node 10?

Select one:

A. -1

B. 1

C. 2

D. 2

A. -1

The advantage of arrays over linked list is that they allow random accessing.

Select one:

True

False

True

Specify the correct statement about coalesced chaining method for handling collision (select the best answer).

Select one:

A. In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the first available position of the table.

B. In coalesced hashing, the linked list is created outside the hash table and a colliding keys are put in the list connected to the colliding position of the table.

C. In coalesced hashing, the linked list is created inside the hash table. Each position pos in the table contains 2 fields: info and next. The next field contains the index of the next key that is hashed to pos.

D. Because in coalesced hashing, the linked list is created inside the hash table, thus the searching must be carried out sequentially.

C. In coalesced hashing, the linked list is created inside the hash table. Each position pos in the table contains 2 fields: info and next. The next field contains the index of the next key that is hashed to pos.

Specify the correct statement about chaining method for handling collision

Select one:

A. In chaining, each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys

B. In chaining, some positions of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys

C. None of the other choices

D. In chaining, the linked-list is used instead of array for a hash table

A. In chaining, each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys

What is value of the Boundary Folding Hash Function if K = 34-56-89-3 and

TSize = 100?

Select one:

A. 91

B. 34

C. 89

D. 56

A. 91

Select the most correct statement about complexity of selection sort

Select one:

A. The best case is O(n), and the average case is O(n^2)

B. The best case is O(n), and the worst case is O(n^2)

C. Both best and worst cases are O(n^2)

D. The best case is O(n), and the average case is O(nlogn)

Both best and worst cases are O(n^2)

Select the most correct statement about complexity of bubble sort.

Select one:

A. The best case is O(n), and the worst case is O(n^2)

B. The best case is O(nlogn), and the worst case is O(n^2)

C. Both best and worst cases are O(n^2)

D. The best case is O(n), and the worst case is O(nlogn)

A. The best case is O(n), and the worst case is O(n^2)

Specify the correct statement about a binary search tree(select the most suitable

one).

Select one:

A. For better searching performance, a tree should be in back-bone shape.

B. The main purpose of balancing a tree is to keep the tree in good shape.

C. In a binary search tree, all the nodes that are left descendants of node A have key values greater than A; all the nodes that are A's right descendants have key values less than (or equal to) A.

D. It is necessary to build a tree with optimized height to stimulate searching

operation.

D. It is necessary to build a tree with optimized height to stimulate searching

operation.

Which of the following is useful in traversing a given graph by breadth first search?

Select one:

a. Queue

b. set

c. stack

d. List

a. Queue

In the average case, quicksort is

Select one:

A. O(1)

B. O(n^2)

C. O(nlogn)

D. O(n)

C. O(nlogn)

What is the correct definition of a hash function? (Select the best answer)

Select one:

A. Hash function h(x) is a function which transforms a particular key x, be it a string. number, record, or the like, into a positive integer.

B. Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into non-negative integer.

C. Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into an index i = h(x) in the table T, where T[i] is used for storing an item having key x or its address.

D. Hash function h(x) is a function which transforms a particular key x (string, or number) into an index i = h(x) in the table T, where T[i] is used for storing an item having key x or its address. X

C. Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like, into an index i = h(x) in the table T, where T[i] is used for storing an item having key x or its address.

In the best-case, mergesort is

Select one:

A. O(nlogn)

B. O(1)

C. O O(n^2)

D. O(n)

A. O(nlogn)

Suppose you are using the LZW algorithm to encode the message

AABABCADAB contents of the dictionary at the beginning of encoding are:

(1) A (2) B (3) C (4) D

What string is denoted by code word (7)?

Select one:

a. AB

b. BA

c. BC

d. AD

b. BA

State True or False: "A balanced tree is one whose root has many more left

descendents than right descendants, or vice versa."

Select one:

True

False

False

In recursion, the condition for which the function will stop calling itself is

Select one:

a. Base case

b. Worst case

c. Best case

d. There is no such condition

a. Base case

Which of the following algorithms solves the all-pair shortest path problem?

Select one:

a. Dijkstra's algorithm

b. Prim's algorithm

c. Warshall's algorithm

d. Floyd's algorithm

d. Floyd's algorithm

Select correct statement:

Select one:

A.In the stack implemented by array, popping is executed in lear time O(n).

B.In the stack implemented by array, popping is executed in constant time O(1).

C.Stack cannot be implemented using doubly linked list.

B.In the stack implemented by array, popping is executed in constant time O(1).

Select the most correct definition of a binary tree:

(1)

A binary tree T is a set of one or more nodes such that

T is partitioned into 3 disjoint subsets:

- A single node r, the root

- Two sets that are binary trees, called left subtree and right subtree of r

(2)

A binary tree T is a set of nodes such that either

- T is empty, or

- T is partitioned into 3 disjoint subsets:

+) A single node r, the root, and

+) Two non-empty binary trees, called left subtree and right subtree of r

(3)

A binary tree T is a set of nodes such that either

T is empty, or

T is partitioned into 3 disjoint subsets:

-A single node r, the root, and

-Two binary trees, called left subtree and right subtree of r

(3)

The operation for adding an entry to a queue is traditionally called:

Select one:

A. append

B. insert

C. add

D. enqueue

enqueue

The operation for adding an entry to a stack is traditionally called:

Select one:

A. add

B. insert

C. append

D. push

D. push

Specify the correct statement about bucket addressing method for handling collision

(select the best answer).

Select one:

A. Bucket is a kind of list which holds items in the hash table.

B. Colliding elements in the same position in the hash table are placed on a bucket assosiated with that position.

C. All of the statements are incorrect.

D. A bucket is a block of space which is large enough to store multiple items. All colliding items are stored on bucket instead of an array.

B. Colliding elements in the same position in the hash table are placed on a bucket assosiated with that position.

Linked lists are not suitable to for the implementation of?

Select one:

a. Insertion sort

b. selection sort

c. Polynomial manipulation

d. Binary search

d. Binary search

If locality is a concern, you can use............... to traverse the graph.

Select one:

a. Breadth First Search

b. None of others

c. Either BFS or DFS

d. Depth First Search

d. Depth First Search

Select the most correct statement about complexity of heapsort

Select one:

A. The best case is O(n), and the worst case is O(nlogn) *

B. Best case is O(nlogn), the worst case is O(n^2)

C. Both best and worst cases are O(nlogn)

D. The best case is O(n), and the worst case is O(n^2)

C. Both best and worst cases are O(nlogn)