2. The maximum number of nodes in a tree for which post-order and pre-order traversals may be
equal is
Correct : B. 1
3. The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q.
Which of following is post-order traversal of the tree?
Correct : A. L N M O Q P T
4. Find the postorder traversal of the binary tree shown below.
Correct : C. S W T Q X U V R P
5. For the tree below, write the in-order traversal.
Correct : A. 6, 2, 5, 7, 11, 2, 5, 9, 4
6. For the tree below, write the level-order traversal.
Correct : B. 2, 7, 5, 2, 11, 9, 6, 5, 4
7. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth
and n is the number of nodes)
Correct : D. O(d)
8. What is the time complexity of level order traversal?
Correct : B. O(n)
9. Which of the following graph traversals closely imitates level order traversal of a binary tree?
Correct : B. Breadth First Search
10. In a binary search tree, which of the following traversals would print the numbers in the ascending
order?
Correct : D. In-order traversal
11. The number of edges from the root to the node is called of the tree.
Correct : B. Depth
12. The number of edges from the node to the deepest leaf is called of the tree.
Correct : A. Height
13. What is a full binary tree?
Correct : A. Each node has exactly zero or two children
14. What is a complete binary tree?
Correct : C. A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
15. What is the average case time complexity for finding the height of the binary tree?
Correct : D. h = O(log n)
16. Which of the following is not an advantage of trees?
Correct : D. Undo/Redo operations in a notepad
17. In a full binary tree if number of internal nodes is I, then number of leaves L are?
Correct : B. L = I + 1
18. In a full binary tree if number of internal nodes is I, then number of nodes N are?
Correct : D. N = 2*I + 1
19. In a full binary tree if there are L leaves, then total number of nodes N are?
Correct : D. N = 2*L – 1
20. Which of the following is incorrect with respect to binary trees?
Correct : D. Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
21. Which of the following is false about a binary search tree?
Correct : D. In order sequence gives decreasing order of elements
22. What is the speciality about the inorder traversal of a binary search tree?
Correct : B. It traverses in an increasing order
23. What are the worst case and average case complexities of a binary search tree?
Correct : D. O(n), O(logn)
24. What are the conditions for an optimal binary search tree and what is its advantage?
Correct : A. The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
25. Which of the following is not the self balancing binary search tree?
Correct : B. 2-3-4 Tree
26. The binary tree sort implemented using a self – balancing binary search tree takes time is
worst case.
Correct : A. O(n log n)
27. An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees
of any node differ by
Correct : B. At most one
28. Associative arrays can be implemented using
Correct : D. A self balancing binary search tree
29. Which of the following is a self – balancing binary search tree?
Correct : C. AA tree
30. A self – balancing binary search tree can be used to implement
Correct : A. Priority queue
31. In which of the following self – balancing binary search tree the recently accessed element can be
accessed quickly?
Correct : C. Splay tree
32. The minimum height of self balancing binary search tree with n nodes is
Correct : A. log2(n)
33. What is an AVL tree?
Correct : A. a tree which is balanced and is a height balanced tree
34. Why we need to a binary tree which is height balanced?
Correct : A. to avoid formation of skew trees
35. What is the maximum height of an AVL tree with p nodes?
Correct : B. log(p)
36. Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given
without performing any rotations?
Correct : B. find the median of the set of elements given, make it as root and construct the tree
37. What maximum difference in heights between the leafs of a AVL tree is possible?
Correct : A. log(n) where n is the number of nodes
38. What is missing?
Correct : A. Height(w-left), x-height
39. Why to prefer red-black trees over AVL trees?
Correct : B. AVL tree store balance factor in every node which costs space
40. Which of the following is the most widely used external memory data structure?
Correct : B. B-tree
41. B-tree of order n is a order-n multiway tree in which each non-root node contains
Correct : D. at least (n – 1)/2 keys
42. A B-tree of order 4 and of height 3 will have a maximum of keys.
Correct : A. 255
43. Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many
nodes are written?
Correct : C. 11
44. trees are B-trees of order 4. They are an isometric of trees.
Correct : D. Red-Black
45. What is the best case height of a B-tree of order n and which has k keys?
Correct : A. logn (k+1) – 1
46. Which of the following is true?
Correct : A. larger the order of B-tree, less frequently the split occurs
47. In a max-heap, element with the greatest key is always in the which node?
Correct : C. root node
48. What is the complexity of adding an element to the heap.
Correct : C. O(log n) & O(h)
49. The worst case complexity of deleting any arbitrary node value element from heap is
Correct : A. O(logn)
50. Heap can be used as
Correct : A. Priority queue
51. If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of
root node after second iteration if leaf node (value 100) is chosen to replace the root at start.
Correct : A. 2
52. An array consists of n elements. We want to create a heap using the elements. The time complexity
of building a heap will be in order of
Correct : B. O(n*logn)
53. Which of the following statements for a simple graph is correct?
Correct : A. Every path is a trail
54. For the given graph(G), which of the following statements is true?
Correct : C. The vertex connectivity of the graph is 2
55. What is the number of edges present in a complete graph having n vertices?
Correct : B. (n*(n-1))/2
56. The given Graph is regular.
Correct : A. True
57. A connected planar graph having 6 vertices, 7 edges contains regions.
Correct : B. 3
58. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph
G'(Complement of G) is
Correct : A. (n*n-n-2*m)/2
59. Which of the following properties does a simple graph not hold?
Correct : A. Must be connected
60. What is the maximum number of edges in a bipartite graph having 10 vertices?
Correct : C. 25
61. Which of the following is true?
Correct : B. A graph may contain many edges and no vertices
62. For a given graph G having v vertices and e edges which is connected and has no cycles, which of
the following statements is true?
Correct : B. v = e+1
63. For which of the following combinations of the degrees of vertices would the connected graph be
eulerian?
Correct : A. 1,2,3
64. A graph with all vertices having equal degree is known as a
Correct : B. Regular Graph
65. Which of the following ways can be used to represent a graph?
Correct : C. Adjacency List, Adjacency Matrix as well as Incidence Matrix
66. The number of possible undirected graphs which may have self loops but no multiple edges and
have n vertices is
Correct : D. 2((n*n)/2)
67. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions.
What will be the number of connected components?
Correct : B. 2
68. Number of vertices with odd degrees in a graph having a eulerian walk is
Correct : D. either 0 or 2
69. How many of the following statements are correct?
Correct : B. All complete graphs are cyclic graphs.
70. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
Correct : A. n-2
71. What would the time complexity to check if an undirected graph with V vertices and E edges is
Bipartite or not given its adjacency matrix?
Correct : B. O(V*V)
72. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
Correct : A. (V*(V-1))/2
73. The topological sorting of any DAG can be done in time.
Correct : C. linear
74. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
Correct : B. No Hamiltonian path is possible
75. Which of the given statement is true?
Correct : D. All the cyclic directed graphs have non topological sortings
76. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed
Acyclic Graph?
Correct : B. Will always be zero
77. Where is linear searching used?
Correct : D. When the list has only a few elements and When performing a single search in an unordered list
78. What is the best case for linear search?
Correct : D. O(1)
79. What is the worst case for linear search?
Correct : C. O(n)
80. What is the best case and worst case complexity of ordered linear search?
Correct : D. O(1), O(n)
81. Which of the following is a disadvantage of linear search?
Correct : B. Greater time complexities compared to other searching algorithms
82. What is the advantage of recursive approach than an iterative approach?
Correct : B. Less code and easy to implement
83. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
Correct : C. 3
84. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding
array elements) in the first and second levels of recursion?
Correct : A. 90 and 99
85. What is the worst case complexity of binary search using recursion?
Correct : B. O(logn)
86. What is the average case time complexity of binary search using recursion?
Correct : B. O(logn)
87. Which of the following is not an application of binary search?
Correct : D. To search in unordered list
88. Binary Search can be categorized into which of the following?
Correct : B. Divide and conquer
89. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element
is found?
Correct : D. 2
90. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid
values(corresponding array elements) generated in the first and second iterations?
Correct : A. 90 and 99
91. What is the time complexity of binary search with iteration?
Correct : B. O(logn)
92. What is an external sorting algorithm?
Correct : A. Algorithm that uses tape or disk during the sort
93. What is an internal sorting algorithm?
Correct : B. Algorithm that uses main memory during the sort
94. What is the worst case complexity of bubble sort?
Correct : D. O(n2)
95. What is the average case complexity of bubble sort?
Correct : D. O(n2)
96. Which of the following is not an advantage of optimised bubble sort over other sorting techniques
in case of sorted elements?
Correct : C. Detects whether the input is already sorted
97. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many
iterations will be done to sort the array?
Correct : A. 4
98. What is the best case efficiency of bubble sort in the improvised version?
Correct : C. O(n)
99. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many
iterations will be done to sort the array with improvised version?
Correct : B. 2
100. What is an in-place sorting algorithm?
Correct : A. It needs O(1) or O(logn) memory to create auxiliary locations