1. What is the maximum number of children of a node in a binary search tree?
A. 0
B. 1
C. 2
D. 3
2. What is the minimum number of leaves in a binary search tree with N (N > 1) keys?
E. (N + 1)/2
F. N - 1
G. 0
H. 1
3. Consider a Huffman tree to encode M distinct symbols with non-zero frequencies. How many leaves are present in the Huffman tree?
A. 2
B. log2(M)
C. M
D. 2M
4. What is the worst case height of a multiway trie storing N elements, each comprised of at most Ddigits?
A. O(log(N))
B. O(log(D))
C. O(D)
D. O(N)
5. One of the goal of AVL trees is to maintain the difference between height of left and right children to within +/-1. Which of the following helps maintain the data structure?
A. Left rotation
B. Right rotation
C. Both left and right rotation
D. None of the above
6. What is the minimum number of edges in an undirected connected graph with N nodes?
A. 2
B. N
C. N – 1
D. N/2
7. Which of the following algorithms finds the shortest path from a source vertex to a destination vertex in an un-weighted undirected connected graph? Choose the best answer.
A. Depth First Search (DFS)
B. Breadth First Search (BFS)
C. Dijkstra’s algorithm
D. Both BFS and Dijkstra’s algorithm
8. Which of the following algorithms is best suited for finding a minimum spanning tree? Choose the best answer.
A. Depth First Search (DFS)
B. Breadth First Search (BFS)
C. Dijkstra’s algorithm
D. Prim’s algorithm
9. What is the difference in the number of edges between the minimum spanning tree returned by Prim’s algorithm and Kruskal’s algorithm when run on the same graph? Assume all the edge weights of the graph are distinct.
A. -1
B. 0
C. 1
D. 2
10. What is the minimum number of black nodes in a red black tree with exactly three nodes?
A. 0
B. 1
C. 2
D. 3
11. Which of the following is TRUE about a skip list with N elements?
A. The elements in the skip lists are in a sorted order.
B. Worst case run time of find operation is O(log(N)).
C. Every node has equal number of forward pointers.
D. Worst case run time of inserting an element is O(1).
12. Which of the following is FALSE about a red-black tree?
A. Root is black
B. Every subtree of a red-black tree is a valid red-black tree
C. Every node is either red or black
D. A red node can’t have a red child
13. What is the worst-case run time of deleting the minimum element in a min-heap with N elements?
A. O(1)
B. O(log N)
C. O(N)
D. O(N logN)
14. Which of the following operations uses path compression in a union-find data structure?
A. Union
B. Find
C. Create
D. Both Union and Find
15. Which is the following data structure have the best worst-case run time of inserting an element?
A. Sorted array
B. Skip list
C. Simple binary search tree
D. Red black tree
16. Which of the following is FALSE about a B-Tree?
A. A leaf in a B-tree can have twice as many elements as another leaf in the same B-tree.
B. B-trees are balanced search trees.
C. B-Tree is a binary tree
D. A node in a B-tree is designed to fit in one disk block.
17. If we have no rule in place for performing the union of two up trees, what is the worst case run
time of find and union operations in terms of the number of elements N?
A. find: O(N), union: O(1)
B. find: O(1), union: O(N)
C. find: O(log2N), union: O(1)
D. find: O(1), union: O(log2N)
18. Which of the following strategy will reduce the runtime complexity of union operation compared
to simple union and find operation?
A. Union by height and simple find
B. Union by size and simple find
C. Both A and B
D. None of the above
19. Suppose you have B+ tree data structure with M=4, L = 3. Starting with an empty tree you inserted following sequence of numbers: 12, 13, 4, 8, 1, 15, 18, and 19. How many leaves will be present in the final B+ tree?
A. 1
B. 2
C. 3
D. 4
20. Which of the following is FALSE about a 2-3 tree?
A. All the leaves are at the same level.
B. The root node must be a 2-node.
C. Every node has either one or two data elements.
D. If an internal node have one data element, then it must have two children.
Post A Comment:
0 comments: