07-12-2012, 05:54 PM
PRACTICAL EXAMINATION QUIZ (2011-12, V SEM)
1PRACTICAL EXAMINATION.doc (Size: 45.5 KB / Downloads: 37)
Q1. The time required to search an element in a binary search tree having n elements is
1. O(1)
2. O(log2n)
3. O(n2)
4. O(nlogn
Q2. In randomized quick sort, the expected running time of any input is
1. O(n)
2. O(n2)
3. O(nlogn)
4. None of the above
Q3. In randomized quick sort, the expected running time of any input is
5. O(n)
6. O(n2)
7. O(nlogn)
8. None of the above
Q4. The worst case running time of GRAHAM-SCAN algorithm
1. O(n)
2. O(nlogn)
3. O(n2)
4. O(1)
Q5. The running time of Dijkshtra’s algorithm is
1. O(V2)
2. O(V+E)
3. O(nlogn)
4. None of these
Q6. The running time of Kruskal’s algorithm for MST is
1. O(E)
2. O(V)
3. O(ElogV)
4. None of these
Q7. The running time of BFS is
1. O(1)
2. O(nlogn)
3. O(V+E)
4. O(n2)
Q8. In B-tree every node other than the root must have at least
1. t keys
2. one keys
3. t-1 keys
4. none of these
Q9. A full binary tree with n leaves contains
1. n nodes
2. log2n nodes
3. 2n-1 node
4. 2n nodes
Q10. The concatenation of two lists is to be performed in O(1) time. Which of the following implementation of a list should be used?
(A) All pair shortest paths (1) Greedy
(B) Quick sort (2) DFS
© Minimum weight spanning tree (3) Dynamic programming
(D) Connected components (4) Divide and conquer