McqMate
Chapters
101. |
A full binary tree can be generated using |
A. | post-order and pre-order traversal |
B. | pre-order traversal |
C. | post-order traversal |
D. | in-order traversal |
Answer» A. post-order and pre-order traversal |
102. |
The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is |
A. | 3 |
B. | 1 |
C. | 2 |
D. | any number |
Answer» B. 1 |
103. |
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? |
A. | L N M O Q P T |
B. | N M O P O L T |
C. | L M N O P Q T |
D. | O P L M N Q T |
Answer» A. L N M O Q P T |
104. |
Find the postorder traversal of the binary tree shown below. |
A. | P Q R S T U V W X |
B. | W R S Q P V T U X |
C. | S W T Q X U V R P |
D. | none |
Answer» C. S W T Q X U V R P |
105. |
For the tree below, write the in-order traversal. |
A. | 6, 2, 5, 7, 11, 2, 5, 9, 4 |
B. | 6, 5, 2, 11, 7, 4, 9, 5, 2 |
C. | 2, 7, 2, 6, 5, 11, 5, 9, 4 |
D. | none |
Answer» A. 6, 2, 5, 7, 11, 2, 5, 9, 4 |
106. |
For the tree below, write the level-order traversal. |
A. | 2, 7, 2, 6, 5, 11, 5, 9, 4 |
B. | 2, 7, 5, 2, 11, 9, 6, 5, 4 |
C. | 2, 5, 11, 6, 7, 4, 9, 5, 2 |
D. | none |
Answer» B. 2, 7, 5, 2, 11, 9, 6, 5, 4 |
107. |
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) |
A. | O(1) |
B. | O(nlogd) |
C. | O(logd) |
D. | O(d) |
Answer» D. O(d) |
108. |
What is the time complexity of level order traversal? |
A. | O(1) |
B. | O(n) |
C. | O(logn) |
D. | O(nlogn) |
Answer» B. O(n) |
109. |
Which of the following graph traversals closely imitates level order traversal of a binary tree? |
A. | Depth First Search |
B. | Breadth First Search |
C. | Depth & Breadth First Search |
D. | Binary Search |
Answer» B. Breadth First Search |
110. |
In a binary search tree, which of the following traversals would print the numbers in the ascending order? |
A. | Level-order traversal |
B. | Pre-order traversal |
C. | Post-order traversal |
D. | In-order traversal |
Answer» D. In-order traversal |
111. |
The number of edges from the root to the node is called of the tree. |
A. | Height |
B. | Depth |
C. | Length |
D. | Width |
Answer» B. Depth |
112. |
The number of edges from the node to the deepest leaf is called of the tree. |
A. | Height |
B. | Depth |
C. | Length |
D. | Width |
Answer» A. Height |
113. |
What is a full binary tree? |
A. | Each node has exactly zero or two children |
B. | Each node has exactly two children |
C. | All the leaves are at the same level |
D. | Each node has exactly one or two children |
Answer» A. Each node has exactly zero or two children |
114. |
What is a complete binary tree? |
A. | Each node has exactly zero or two children |
B. | A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left |
C. | A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right |
D. | A tree In which all nodes have degree 2 |
Answer» C. A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right |
115. |
What is the average case time complexity for finding the height of the binary tree? |
A. | h = O(loglogn) |
B. | h = O(nlogn) |
C. | h = O(n) |
D. | h = O(log n) |
Answer» D. h = O(log n) |
116. |
Which of the following is not an advantage of trees? |
A. | Hierarchical structure |
B. | Faster search |
C. | Router algorithms |
D. | Undo/Redo operations in a notepad |
Answer» D. Undo/Redo operations in a notepad |
117. |
In a full binary tree if number of internal nodes is I, then number of leaves L are? |
A. | L = 2*I |
B. | L = I + 1 |
C. | L = I – 1 |
D. | L = 2*I – 1 |
Answer» B. L = I + 1 |
118. |
In a full binary tree if number of internal nodes is I, then number of nodes N are? |
A. | N = 2*I |
B. | N = I + 1 |
C. | N = I – 1 |
D. | N = 2*I + 1 |
Answer» D. N = 2*I + 1 |
119. |
In a full binary tree if there are L leaves, then total number of nodes N are? |
A. | N = 2*L |
B. | N = L + 1 |
C. | N = L – 1 |
D. | N = 2*L – 1 |
Answer» D. N = 2*L – 1 |
120. |
Which of the following is incorrect with respect to binary trees? |
A. | Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k |
B. | Let T be a binary tree with λ levels. Then T has no more than 2λ – 1 nodes |
C. | Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1)) |
D. | Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1)) |
Answer» D. Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1)) |
121. |
Which of the following is false about a binary search tree? |
A. | The left child is always lesser than its parent |
B. | The right child is always greater than its parent |
C. | The left and right sub-trees should also be binary search trees |
D. | In order sequence gives decreasing order of elements |
Answer» D. In order sequence gives decreasing order of elements |
122. |
What is the speciality about the inorder traversal of a binary search tree? |
A. | It traverses in a non increasing order |
B. | It traverses in an increasing order |
C. | It traverses in a random fashion |
D. | It traverses based on priority of the node |
Answer» B. It traverses in an increasing order |
123. |
What are the worst case and average case complexities of a binary search tree? |
A. | O(n), O(n) |
B. | O(logn), O(logn) |
C. | O(logn), O(n) |
D. | O(n), O(logn) |
Answer» D. O(n), O(logn) |
124. |
What are the conditions for an optimal binary search tree and what is its advantage? |
A. | The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost |
B. | You should know the frequency of access of the keys, improves the lookup time |
C. | The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time |
D. | The tree should be just modified and improves the lookup time |
Answer» A. The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost |
125. |
Which of the following is not the self balancing binary search tree? |
A. | AVL Tree |
B. | 2-3-4 Tree |
C. | Red – Black Tree |
D. | Splay Tree |
Answer» B. 2-3-4 Tree |
126. |
The binary tree sort implemented using a self – balancing binary search tree takes time is worst case. |
A. | O(n log n) |
B. | O(n) |
C. | O(n2) |
D. | O(log n) |
Answer» A. O(n log n) |
127. |
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 |
A. | At least one |
B. | At most one |
C. | Two |
D. | At most two |
Answer» B. At most one |
128. |
Associative arrays can be implemented using |
A. | B-tree |
B. | A doubly linked list |
C. | A single linked list |
D. | A self balancing binary search tree |
Answer» D. A self balancing binary search tree |
129. |
Which of the following is a self – balancing binary search tree? |
A. | 2-3 tree |
B. | Threaded binary tree |
C. | AA tree |
D. | Treap |
Answer» C. AA tree |
130. |
A self – balancing binary search tree can be used to implement |
A. | Priority queue |
B. | Hash table |
C. | Heap sort |
D. | Priority queue and Heap sort |
Answer» A. Priority queue |
131. |
In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly? |
A. | AVL tree |
B. | AA tree |
C. | Splay tree |
D. | Red – Black tree |
Answer» C. Splay tree |
132. |
The minimum height of self balancing binary search tree with n nodes is |
A. | log2(n) |
B. | n |
C. | 2n + 1 |
D. | 2n – 1 |
Answer» A. log2(n) |
133. |
What is an AVL tree? |
A. | a tree which is balanced and is a height balanced tree |
B. | a tree which is unbalanced and is a height balanced tree |
C. | a tree with three children |
D. | a tree with atmost 3 children |
Answer» A. a tree which is balanced and is a height balanced tree |
134. |
Why we need to a binary tree which is height balanced? |
A. | to avoid formation of skew trees |
B. | to save memory |
C. | to attain faster memory access |
D. | to simplify storing |
Answer» A. to avoid formation of skew trees |
135. |
What is the maximum height of an AVL tree with p nodes? |
A. | p |
B. | log(p) |
C. | log(p)/2 |
D. | P⁄2 |
Answer» B. log(p) |
136. |
Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations? |
A. | just build the tree with the given input |
B. | find the median of the set of elements given, make it as root and construct the tree |
C. | use trial and error |
D. | use dynamic programming to build the tree |
Answer» B. find the median of the set of elements given, make it as root and construct the tree |
137. |
What maximum difference in heights between the leafs of a AVL tree is possible? |
A. | log(n) where n is the number of nodes |
B. | n where n is the number of nodes |
C. | 0 or 1 |
D. | atmost 1 |
Answer» A. log(n) where n is the number of nodes |
138. |
What is missing? |
A. | Height(w-left), x-height |
B. | Height(w-right), x-height |
C. | Height(w-left), x |
D. | Height(w-left) |
Answer» A. Height(w-left), x-height |
139. |
Why to prefer red-black trees over AVL trees? |
A. | Because red-black is more rigidly balanced |
B. | AVL tree store balance factor in every node which costs space |
C. | AVL tree fails at scale |
D. | Red black is more efficient |
Answer» B. AVL tree store balance factor in every node which costs space |
140. |
Which of the following is the most widely used external memory data structure? |
A. | AVL tree |
B. | B-tree |
C. | Red-black tree |
D. | Both AVL tree and Red-black tree |
Answer» B. B-tree |
141. |
B-tree of order n is a order-n multiway tree in which each non-root node contains |
A. | at most (n – 1)/2 keys |
B. | exact (n – 1)/2 keys |
C. | at least 2n keys |
D. | at least (n – 1)/2 keys |
Answer» D. at least (n – 1)/2 keys |
142. |
A B-tree of order 4 and of height 3 will have a maximum of keys. |
A. | 255 |
B. | 63 |
C. | 127 |
D. | 188 |
Answer» A. 255 |
143. |
Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written? |
A. | 14 |
B. | 7 |
C. | 11 |
D. | 5 |
Answer» C. 11 |
144. |
trees are B-trees of order 4. They are an isometric of trees. |
A. | AVL |
B. | AA |
C. | 2-3 |
D. | Red-Black |
Answer» D. Red-Black |
145. |
What is the best case height of a B-tree of order n and which has k keys? |
A. | logn (k+1) – 1 |
B. | nk |
C. | logk (n+1) – 1 |
D. | klogn |
Answer» A. logn (k+1) – 1 |
146. |
Which of the following is true? |
A. | larger the order of B-tree, less frequently the split occurs |
B. | larger the order of B-tree, more frequently the split occurs |
C. | smaller the order of B-tree, more frequently the split occurs |
D. | smaller the order of B-tree, less frequently the split occurs |
Answer» A. larger the order of B-tree, less frequently the split occurs |
147. |
In a max-heap, element with the greatest key is always in the which node? |
A. | Leaf node |
B. | First node of left sub tree |
C. | root node |
D. | First node of right sub tree |
Answer» C. root node |
148. |
What is the complexity of adding an element to the heap. |
A. | O(log n) |
B. | O(h) |
C. | O(log n) & O(h) |
D. | O(n) |
Answer» C. O(log n) & O(h) |
149. |
The worst case complexity of deleting any arbitrary node value element from heap is |
A. | O(logn) |
B. | O(n) |
C. | O(nlogn) |
D. | O(n2) |
Answer» A. O(logn) |
150. |
Heap can be used as |
A. | Priority queue |
B. | Stack |
C. | A decreasing order array |
D. | Normal Array |
Answer» A. Priority queue |
151. |
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. |
A. | 2 |
B. | 100 |
C. | 17 |
D. | none |
Answer» A. 2 |
152. |
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 |
A. | O(n*n*logn) |
B. | O(n*logn) |
C. | O(n*n) |
D. | O(n *logn *logn) |
Answer» B. O(n*logn) |
153. |
Which of the following statements for a simple graph is correct? |
A. | Every path is a trail |
B. | Every trail is a path |
C. | Every trail is a path as well as every path is a trail |
D. | Path and trail have no relation |
Answer» A. Every path is a trail |
154. |
For the given graph(G), which of the following statements is true? |
A. | G is a complete graph |
B. | G is not a connected graph |
C. | The vertex connectivity of the graph is 2 |
D. | none |
Answer» C. The vertex connectivity of the graph is 2 |
155. |
What is the number of edges present in a complete graph having n vertices? |
A. | (n*(n+1))/2 |
B. | (n*(n-1))/2 |
C. | n |
D. | Information given is insufficient |
Answer» B. (n*(n-1))/2 |
156. |
The given Graph is regular. |
A. | True |
B. | False |
C. | none |
D. | none |
Answer» A. True |
157. |
A connected planar graph having 6 vertices, 7 edges contains regions. |
A. | 15 |
B. | 3 |
C. | 1 |
D. | 11 |
Answer» B. 3 |
158. |
If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is |
A. | (n*n-n-2*m)/2 |
B. | (n*n+n+2*m)/2 |
C. | (n*n-n-2*m)/2 |
D. | (n*n-n+2*m)/2 |
Answer» A. (n*n-n-2*m)/2 |
159. |
Which of the following properties does a simple graph not hold? |
A. | Must be connected |
B. | Must be unweighted |
C. | Must have no loops or multiple edges |
D. | Must have no multiple edges |
Answer» A. Must be connected |
160. |
What is the maximum number of edges in a bipartite graph having 10 vertices? |
A. | 24 |
B. | 21 |
C. | 25 |
D. | 16 |
Answer» C. 25 |
161. |
Which of the following is true? |
A. | A graph may contain no edges and many vertices |
B. | A graph may contain many edges and no vertices |
C. | A graph may contain no edges and no vertices |
D. | A graph may contain no vertices and many edges |
Answer» B. A graph may contain many edges and no vertices |
162. |
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? |
A. | v=e |
B. | v = e+1 |
C. | v + 1 = e |
D. | v = e-1 |
Answer» B. v = e+1 |
163. |
For which of the following combinations of the degrees of vertices would the connected graph be eulerian? |
A. | 1,2,3 |
B. | 2,3,4 |
C. | 2,4,5 |
D. | 1,3,5 |
Answer» A. 1,2,3 |
164. |
A graph with all vertices having equal degree is known as a |
A. | Multi Graph |
B. | Regular Graph |
C. | Simple Graph |
D. | Complete Graph |
Answer» B. Regular Graph |
165. |
Which of the following ways can be used to represent a graph? |
A. | Adjacency List and Adjacency Matrix |
B. | Incidence Matrix |
C. | Adjacency List, Adjacency Matrix as well as Incidence Matrix |
D. | No way to represent |
Answer» C. Adjacency List, Adjacency Matrix as well as Incidence Matrix |
166. |
The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is |
A. | 2((n*(n-1))/2) |
B. | 2((n*(n+1))/2) |
C. | 2((n-1)*(n-1))/2) |
D. | 2((n*n)/2) |
Answer» D. 2((n*n)/2) |
167. |
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? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 |
168. |
Number of vertices with odd degrees in a graph having a eulerian walk is |
A. | 0 |
B. | Can’t be predicted |
C. | 2 |
D. | either 0 or 2 |
Answer» D. either 0 or 2 |
169. |
How many of the following statements are correct? |
A. | All cyclic graphs are complete graphs. |
B. | All complete graphs are cyclic graphs. |
C. | All paths are bipartite. |
D. | All cyclic graphs are bipartite. |
Answer» B. All complete graphs are cyclic graphs. |
170. |
What is the number of vertices of degree 2 in a path graph having n vertices,here n>2. |
A. | n-2 |
B. | n |
C. | 2 |
D. | 0 |
Answer» A. n-2 |
171. |
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? |
A. | O(E*E) |
B. | O(V*V) |
C. | O(E) |
D. | O(V) |
Answer» B. O(V*V) |
172. |
With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess? |
A. | (V*(V-1))/2 |
B. | (V*(V+1))/2 |
C. | (V+1)C2 |
D. | (V-1)C2 |
Answer» A. (V*(V-1))/2 |
173. |
The topological sorting of any DAG can be done in time. |
A. | cubic |
B. | quadratic |
C. | linear |
D. | logarithmic |
Answer» C. linear |
174. |
If there are more than 1 topological sorting of a DAG is possible, which of the following is true. |
A. | Many Hamiltonian paths are possible |
B. | No Hamiltonian path is possible |
C. | Exactly 1 Hamiltonian path is possible |
D. | Given information is insufficient to comment anything |
Answer» B. No Hamiltonian path is possible |
175. |
Which of the given statement is true? |
A. | All the Cyclic Directed Graphs have topological sortings |
B. | All the Acyclic Directed Graphs have topological sortings |
C. | All Directed Graphs have topological sortings |
D. | All the cyclic directed graphs have non topological sortings |
Answer» D. All the cyclic directed graphs have non topological sortings |
176. |
What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph? |
A. | Depends on a Graph |
B. | Will always be zero |
C. | Will always be greater than zero |
D. | May be zero or greater than zero |
Answer» B. Will always be zero |
177. |
Where is linear searching used? |
A. | When the list has only a few elements |
B. | When performing a single search in an unordered list |
C. | Used all the time |
D. | When the list has only a few elements and When performing a single search in an unordered list |
Answer» D. When the list has only a few elements and When performing a single search in an unordered list |
178. |
What is the best case for linear search? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(1) |
Answer» D. O(1) |
179. |
What is the worst case for linear search? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(1) |
Answer» C. O(n) |
180. |
What is the best case and worst case complexity of ordered linear search? |
A. | O(nlogn), O(logn) |
B. | O(logn), O(nlogn) |
C. | O(n), O(1) |
D. | O(1), O(n) |
Answer» D. O(1), O(n) |
181. |
Which of the following is a disadvantage of linear search? |
A. | Requires more space |
B. | Greater time complexities compared to other searching algorithms |
C. | Not easy to understand |
D. | Not easy to implement |
Answer» B. Greater time complexities compared to other searching algorithms |
182. |
What is the advantage of recursive approach than an iterative approach? |
A. | Consumes less memory |
B. | Less code and easy to implement |
C. | Consumes more memory |
D. | More code has to be written |
Answer» B. Less code and easy to implement |
183. |
Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion? |
A. | 5 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» C. 3 |
184. |
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? |
A. | 90 and 99 |
B. | 90 and 94 |
C. | 89 and 99 |
D. | 89 and 94 |
Answer» A. 90 and 99 |
185. |
What is the worst case complexity of binary search using recursion? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» B. O(logn) |
186. |
What is the average case time complexity of binary search using recursion? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» B. O(logn) |
187. |
Which of the following is not an application of binary search? |
A. | To find the lower/upper bound in an ordered sequence |
B. | Union of intervals |
C. | Debugging |
D. | To search in unordered list |
Answer» D. To search in unordered list |
188. |
Binary Search can be categorized into which of the following? |
A. | Brute Force technique |
B. | Divide and conquer |
C. | Greedy algorithm |
D. | Dynamic programming |
Answer» B. Divide and conquer |
189. |
Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found? |
A. | 1 |
B. | 3 |
C. | 4 |
D. | 2 |
Answer» D. 2 |
190. |
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? |
A. | 90 and 99 |
B. | 90 and 100 |
C. | 89 and 94 |
D. | 94 and 99 |
Answer» A. 90 and 99 |
191. |
What is the time complexity of binary search with iteration? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» B. O(logn) |
192. |
What is an external sorting algorithm? |
A. | Algorithm that uses tape or disk during the sort |
B. | Algorithm that uses main memory during the sort |
C. | Algorithm that involves swapping |
D. | Algorithm that are considered ‘in place’ |
Answer» A. Algorithm that uses tape or disk during the sort |
193. |
What is an internal sorting algorithm? |
A. | Algorithm that uses tape or disk during the sort |
B. | Algorithm that uses main memory during the sort |
C. | Algorithm that involves swapping |
D. | Algorithm that are considered ‘in place’ |
Answer» B. Algorithm that uses main memory during the sort |
194. |
What is the worst case complexity of bubble sort? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» D. O(n2) |
195. |
What is the average case complexity of bubble sort? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» D. O(n2) |
196. |
Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements? |
A. | It is faster |
B. | Consumes less memory |
C. | Detects whether the input is already sorted |
D. | Consumes less time |
Answer» C. Detects whether the input is already sorted |
197. |
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? |
A. | 4 |
B. | 2 |
C. | 1 |
D. | 0 |
Answer» A. 4 |
198. |
What is the best case efficiency of bubble sort in the improvised version? |
A. | O(nlogn) |
B. | O(logn) |
C. | O(n) |
D. | O(n2) |
Answer» C. O(n) |
199. |
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? |
A. | 4 |
B. | 2 |
C. | 1 |
D. | 0 |
Answer» B. 2 |
200. |
What is an in-place sorting algorithm? |
A. | It needs O(1) or O(logn) memory to create auxiliary locations |
B. | The input is already sorted and in-place |
C. | It requires additional storage |
D. | It requires additional space |
Answer» A. It needs O(1) or O(logn) memory to create auxiliary locations |
Done Reading?