# Data Structure and Algorithm Analysis Set 10

## Data Structure and Algorithm Analysis

### Questions 91 to 100

91.
For the bubble sort algorithm, what is the time complexity of the best/worst case? (assume that the computation stops as soon as no more swaps in one pass)
 (a) best case: O(n)      worst case: O(n*n) (b) best case: O(n)      worst case: O(n*log(n)) (c) best case: O(n*log(n)) worst case: O(n*log(n)) (d) best case: O(n*log(n)) worst case: O(n*n) (e) best case: O( 1)     worst case: O( n ).
92.
For the quick sort algorithm, what is the time complexity of the best/worst case?
 (a) best case: O(n)      worst case: O(n*n) (b) best case: O(n)      worst case: O(n*log(n)) (c) best case: O(n*log(n)) worst case: O(n*log(n)) (d) best case: O(n*log(n)) worst case: O(n*n) (e) best case: O(n*log(n)) worst case: O(n*n*n).
93.
In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K. The computation time needed to find a data item on T is
 (a) O(K*K) (b) O(M*M) (c) O(N) (d) O(K) (e) O( 1 ).
94.
When we organize our data as an ordered list, what is the time complexity of inserting/deleting a data item to/from the list?
 (a) O(length_of_list*length_of_list) (b) O(length_of_list) (c) O(log(length_of_list * length_of_list)) (d) O(1) (e) O( log(length_of_list)*length_of_list ).
95.
Five statements about B-trees are below. Four of them are correct. Which one is INCORRECT?
 (a) All B-trees are also search trees (b) The word B-tree stands for balanced tree (c) The word B-tree also stands for binary tree (d) All leaves of a B-tree must be on the same level (e) B-tree is not same as B+-tree.
96.
For any B-tree of height H (H>1), after inserting a new key, is it possible for a key, K, which was located in a leaf-node to move up to the root in this regard which of the following is correct?
 (a) Can’t be defined without data (b) Never (c) Yes, only if H=2 (d) Yes, only when the half of the keys in the root are less than K and the other half of the keys in the root are greater than K (e) Yes.
97.
When we say the order of a tree is M, we mean
 (a) Every non-leaf node must have M subtrees (b) Every non-leaf node must have M keys (c) Every non-leaf node can have at most M subtrees (d) Every non-leaf node can have at most M keys (e) The Height of the tree is M.
98.
T is a search tree of order M, its size is N, and its height is K. The computation time needed to INSERT/DELETE a data item on T is
 (a) O( 1 ) (b) O( M ) (c) O( Log K ) (d) O( N ) (e) O( K ).
99.
Suppose that we have a data file containing records of famous people, and we need to build a hash table to find a record from the person's birthday. The size of the hash table is 4096. The following are hash functions which convert a birthday to an integer. Which of the following function is the best?
 (a) h1( day/month/year ) = day + month + year (b) h2( day/month/year ) = day + month*31 + year (c) h3( day/month/year ) = (day + month*31 + year*365) mod 4096 (d) h4( day/month/year ) = (day + month*31 + year*365) mod 4093 (e) h5(day/month/year ) = (day + month*31 + year*365).
100.
What is collision resolution with open addressing?
 (a) When collision happens, we create a new memory location outside of the existing table, and use a chain to link to the new memory location (b) When collision happens, we enlarge the hash table (c) When collision happens, we look for an unoccupied memory location in the existing table (d) We use an extra table to collect all collided data (e) We use indexed hash table to resolve collision.