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.


Answers


91.
Answer : (a)
Reason:  Best Case is the one in which it is already sorted, and hence it takes O(n) time, otherwise it takes O(n2) time.
92.
Answer : (d)
Reason:  The worst case here is, if the list is already sorted in descending order and we want to sort it in ascending order. In this case it takes O(n2) time. Otherwise it takes O( n * log(n) ) time.
93.
Answer : (c)
Reason:  As the size is N, we have to traverse almost entire tree to look for a node ( because it is not a binary search tree). And hence it takes O(N) time.
94.
Answer : (b)
Reason:  Because we have to search for deletion/insertion both in the ordered list. And the algorithm takes O(n) in this case[ best option in the given options].
95.
Answer : (c)
Reason:  As B-tree is not a binary tree, but a balanced m-way tree
96.
Answer : (e)
Reason:  Yes, this is the best option given because, if the insertion in a node causes the node to contain the keys equal to order of the tree, then the middle key of the node will be passed to one level up (it can be a root also ). A common mistake is to tick D. But, the condition stated in D is too strong. We were only asking whether a key can move up to the root, and we were not asking whether a key can become a new root!
97.
Answer : (c)
Reason:  Here in the answer ‘can’ is most important. That is “every non-leaf node ‘can’ have at most M subtrees”
98.
Answer : (e)
Reason:  In this case it is a search tree ( BST ). And hence the search time is proportional to the height of the tree. This answer assumes that M < K If M >> K, you could answer B However, M is a fixed number, but K grows when the size of data grows. Therefore, e is a better answer.
99.
Answer : (d)
Reason:  With the answer ‘a’ some of the entries in the hash table, say 3000-4000, are never used. A similar problem also applies to ‘b’, ‘e’. In the answer ‘c’, 4096 is a bad choice. It should a prime number.
100.
Answer : (c)
Reason:  The meaning of the open addressing it self is to look and probe for unoccupied and open location to place the incoming key.



Writed by
Labels: , , , , , , , , , ,

No comments :

What you think about these Questions and Answers ? Let me know in comments.

Post a Comment

Subscribe to: Post Comments ( Atom )