MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 35 Mcqs, each offering curated multiple-choice questions to sharpen your Data Structures and Algorithms knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Consider below sequences. How to achieve the above operation efficiently? |
| A. | use linked lists |
| B. | use avl trees |
| C. | use red-black trees |
| D. | use treaps (cartesian trees)View Answer |
| Answer» E. | |
| 2. |
Cartesian trees solve range minimum query problem in constant time. |
| A. | true |
| B. | false |
| Answer» B. false | |
| 3. |
A treap is a cartesian tree with ___________ |
| A. | additional value, which is a priority value to the key generated randomly |
| B. | additional value, which is a priority value to the key generated sequentially |
| C. | additional heap rule |
| D. | additional operations like remove a range of elements |
| Answer» B. additional value, which is a priority value to the key generated sequentially | |
| 4. |
What happens if we apply the below operations on an input sequence?i. construct a cartesian tree for input sequenceii. put the root element of above tree in a priority queueiii. if( priority queue is not empty) theniv. search and delete minimum value in priority queuev. add that to outputvi. add cartesian tree children of above node to priority queue |
| A. | constructs a cartesian tree |
| B. | sorts the input sequence |
| C. | does nothing |
| D. | produces some random output |
| Answer» C. does nothing | |
| 5. |
Which of the below statements are true?i. Cartesian tree is not a height balanced treeii. Cartesian tree of a sequence of unique numbers can be unique generated |
| A. | both statements are true |
| B. | only i. is true |
| C. | only ii. is true |
| D. | both are false |
| Answer» B. only i. is true | |
| 6. |
Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree? |
| A. | true |
| B. | false |
| Answer» B. false | |
| 7. |
In a binary tree, the number of internal nodes of degree 1 is 3, and the number of internal nodes of degree 2 is 6. The number of leaf nodes in the binary tree is |
| A. | 7 |
| B. | 8 |
| C. | 9 |
| D. | 10 |
| Answer» B. 8 | |
| 8. |
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:Note: The height of a tree with a single node is 0. |
| A. | 4 and 15 respectively |
| B. | 3 and 14 respectively |
| C. | 4 and 14 respectively |
| D. | 3 and 15 respectively |
| Answer» C. 4 and 14 respectively | |
| 9. |
If BDAECF and ABDCEF are inorder and preorder traversals of a binary tree (T) respectively, then post-order traversal of T is: |
| A. | DBFECA |
| B. | BDEFCA |
| C. | DBEFCA |
| D. | BDFEAC |
| Answer» D. BDFEAC | |
| 10. |
A complete binary tree with n non-leaf nodes contains: |
| A. | log2 n nodes |
| B. | n + 1 nodes |
| C. | 2n nodes |
| D. | 2n + 1 nodes |
| Answer» E. | |
| 11. |
Consider the following statements.S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.S2 : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.Which one of the following options is correct? |
| A. | S1 is true and S2 is true |
| B. | S1 is false and S2 is true |
| C. | S1 is false and S2 is false |
| D. | S1 is true and S2 is false |
| Answer» B. S1 is false and S2 is true | |
| 12. |
How many different trees are there with four nodes A, B, C and D ? |
| A. | 30 |
| B. | 60 |
| C. | 90 |
| D. | 120 |
| Answer» E. | |
| 13. |
Consider the following Inorder and Preorder traversal of a treeInorder – D B E F A G H CPreorder - A B D E F C G HWhat is the Postorder Traversal of the same tree |
| A. | D F E B H C G A |
| B. | D F E B G H C A |
| C. | D F E B H G C A |
| D. | D F E H B G C A |
| Answer» D. D F E H B G C A | |
| 14. |
Postorder traversal of a given binary search tree T produces following sequence of keys: 3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? |
| A. | 3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15 |
| B. | 20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9 |
| C. | 20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3 |
| D. | 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20 |
| Answer» E. | |
| 15. |
A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, What is the value of n ? |
| A. | 3 |
| B. | 4 |
| C. | 5 |
| D. | 6 |
| Answer» D. 6 | |
| 16. |
Given the following expression tree, identify the correct arithmetic expression: |
| A. | (A + B)*/A-C |
| B. | A + (B*C)/(A-C) |
| C. | A + B*C/A-C |
| D. | (A + B*C)/(A-C) |
| Answer» E. | |
| 17. |
If tree-1 and Tree-2 are the trees indicated below:Which traversals of Tree-1 and Tree-2, respectively, will produce the same sequence? |
| A. | Preorder, postorder |
| B. | Postorder, inorder |
| C. | Postorder, preorder |
| D. | None of these |
| Answer» E. | |
| 18. |
Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complex K-ary tree of depth N? |
| A. | 1/N |
| B. | N-1/N |
| C. | 1/K |
| D. | K-1/K |
| Answer» D. K-1/K | |
| 19. |
For the following binary tree, inorder traversal yields the expression: |
| A. | a + bd* - ef / |
| B. | a + b*d - e/f |
| C. | abdef* / + - |
| D. | - + * / abdef |
| Answer» C. abdef* / + - | |
| 20. |
Consider the following New-order strategy for traversing a binary tree: Visit the root;Visit the right subtree using New-order;Visit the left subtree using New-order;The New-order traversal of the expression tree corresponding to the reverse polish expression3 4 * 5 – 2 ^ 6 7 * 1 + - is given by: |
| A. | + – 1 6 7 * 2 ^ 5 – 3 4 * |
| B. | – + 1 * 6 7 ^ 2 – 5 * 3 4 |
| C. | – + 1 * 7 6 ^ 2 – 5 * 4 3 |
| D. | 1 7 6 * + 2 5 4 3 * – ^ – |
| Answer» D. 1 7 6 * + 2 5 4 3 * – ^ – | |
| 21. |
A binary tree T has n leaf nodes, the number of nodes of degree 2 in T is: |
| A. | log2n |
| B. | n - 1 |
| C. | n |
| D. | 2n |
| Answer» C. n | |
| 22. |
Consider the following three binary trees, each with 7 nodesThen A is ____binary tree, B is ___binary tree and C is_______ binary tree. |
| A. | Strictly, Strictly complete |
| B. | Complete, not strictly, strictly |
| C. | Strictly, not strictly, strictly |
| D. | Strictly, not strictly, complete |
| Answer» E. | |
| 23. |
Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf.Which of the following is correct for the full binary tree? |
| A. | e = i + n |
| B. | e = i + 2n |
| C. | e = 2i + n |
| D. | e = 2n + i |
| Answer» C. e = 2i + n | |
| 24. |
For a tree with just one node, the root node, the height of a binary tree is defined to be zero; if there are 2 levels of nodes, the height is 1 and so on. Binary search tree is built according to the usual rules with the following six keys, inserted one at a time given:B, I, N, A, R, Y. what is the height of the tree? |
| A. | 2 |
| B. | 4 |
| C. | 3 |
| D. | 5 |
| Answer» C. 3 | |
| 25. |
Consider the following treeIf the post order traversal gives ab-cd*+ then the label of the nodes 1,2,3,… will be |
| A. | +,-,*,a,b,c,d |
| B. | a,-,b,+,c,*,d |
| C. | a,b,c,d,-,*,+ |
| D. | -,a,b,+,*,c,d |
| Answer» B. a,-,b,+,c,*,d | |
| 26. |
Let post order traversal of a binary search tree (BST) is given by VSQTURP. If S < V < Q < P < T < R < U, then the pre-order traversal of the BST is: |
| A. | SVQPTRU |
| B. | PQSVRTU |
| C. | SVRUTQP |
| D. | PRQSUTV |
| Answer» C. SVRUTQP | |
| 27. |
A strictly binary tree with 10 leaves |
| A. | cannot have more than 19 nodes |
| B. | has exactly 19 nodes |
| C. | has exactly 17 nodes |
| D. | has exactly 20 nodes |
| Answer» C. has exactly 17 nodes | |
| 28. |
Consider the following rooted tree with the vertex labelled P as the root.The order in which the nodes are visited during an in-order traversal of the tree is |
| A. | SQPTRWUV |
| B. | SQPTUWRV |
| C. | SQPTWUVR |
| D. | SQPTRUWV |
| Answer» B. SQPTUWRV | |
| 29. |
CARTESIAN_TREES_SOLVE_RANGE_MINIMUM_QUERY_PROBLEM_IN_CONSTANT_TIME?$ |
| A. | true |
| B. | false |
| Answer» B. false | |
| 30. |
A treap is a cartesian tree wit? |
| A. | additional value, which is a priority value to the key generated randomly |
| B. | additional value, which is a priority value to the key generated sequentially |
| C. | additional heap rule |
| D. | additional operations like remove a range of elements |
| Answer» B. additional value, which is a priority value to the key generated sequentially | |
| 31. |
Cartesian trees are most suitable for? |
| A. | searching |
| B. | finding nth element |
| C. | minimum range query and lowest common ancestors |
| D. | self balancing a tree |
| Answer» D. self balancing a tree | |
| 32. |
Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules? |
| A. | use any tie-breaking rule between repeated elements |
| B. | cartesian tree is impossible when repetitions are present |
| C. | construct a max heap in such cases |
| D. | construct a min heap in such cases |
| Answer» B. cartesian tree is impossible when repetitions are present | |
| 33. |
What is the speciality of cartesian sorting? |
| A. | it sorts partially sorted set of data quickly |
| B. | it considers cartesian product of elements |
| C. | it sorts elements in less than O(logn) |
| D. | it is a self balancing tree |
| Answer» B. it considers cartesian product of elements | |
| 34. |
Which of the below statements are true |
| A. | |
| B. | |
| Answer» B. | |
| 35. |
What is a Cartesian tree? |
| A. | a skip list in the form of tree |
| B. | a tree which obeys cartesian product |
| C. | a tree which obeys heap property and whose inorder traversal yields the given sequence |
| D. | a tree which obeys heap property only |
| Answer» D. a tree which obeys heap property only | |