McqMate
167
87.4k
70+ Non Linear Data Structures - Trees Solved MCQs
in Data Structures (DS)These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) , Information Technology Engineering (IT) , Bachelor of Science in Computer Science FY (BSc CS) , Bachelor of Science in Information Technology FY (BSc IT) , Bachelor of Computer Applications (BCA) .
Chapters
Chapter: Non Linear Data Structures - Trees
| 1. |
What is the maximum number of children that a binary tree node can have? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| 2. |
The following given tree is an example for?
|
| A. | Binary tree |
| B. | Binary search tree |
| C. | Fibonacci tree |
| D. | none |
| Answer» A. Binary tree | |
| 3. |
How many common operations are performed in a binary tree? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» C. 3 | |
| 4. |
What is the traversal strategy used in the binary tree? |
| A. | depth-first traversal |
| B. | breadth-first traversal |
| C. | random traversal |
| D. | Priority traversal |
| Answer» B. breadth-first traversal | |
| 5. |
How many types of insertion are performed in a binary tree? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 6. |
What operation does the following diagram depict?
|
| A. | inserting a leaf node |
| B. | inserting an internal node |
| C. | deleting a node with 0 or 1 child |
| D. | none |
| Answer» C. deleting a node with 0 or 1 child | |
| 7. |
How many bits would a succinct binary tree occupy? |
| A. | n+O(n) |
| B. | 2n+O(n) |
| C. | n/2 |
| D. | n |
| Answer» B. 2n+O(n) | |
| 8. |
The average depth of a binary tree is given as? |
| A. | O(N) |
| B. | O(√N) |
| C. | O(N2) |
| D. | O(log N) |
| Answer» D. O(log N) | |
| 9. |
How many orders of traversal are applicable to a binary tree (In General)? 3 |
| A. | 1 |
| B. | 4 |
| C. | 2 |
| D. | 3 |
| Answer» D. 3 | |
| 10. |
If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i? |
| A. | 2i+1 |
| B. | 2i+2 |
| C. | 2i |
| D. | 4i |
| Answer» A. 2i+1 | |
| 11. |
Using what formula can a parent node be located in an array? |
| A. | (i+1)/2 |
| B. | (i-1)/2 |
| C. | i/2 |
| D. | 2i/2 |
| Answer» B. (i-1)/2 | |
| 12. |
Which of the following properties are obeyed by all three tree – traversals? |
| A. | Left subtrees are visited before right subtrees |
| B. | Right subtrees are visited before left subtrees |
| C. | Root node is visited before left subtree |
| D. | Root node is visited before right subtree |
| Answer» A. Left subtrees are visited before right subtrees | |
| 13. |
For the tree below, write the pre-order traversal. |
| A. | 2, 7, 2, 6, 5, 11, 5, 9, 4 |
| B. | 2, 7, 5, 2, 6, 9, 5, 11, 4 |
| C. | 2, 5, 11, 6, 7, 4, 9, 5, 2 |
| D. | none |
| Answer» A. 2, 7, 2, 6, 5, 11, 5, 9, 4 | |
| 14. |
For the tree below, write the post-order traversal. |
| A. | 2, 7, 2, 6, 5, 11, 5, 9, 4 |
| B. | 2, 7, 5, 2, 6, 9, 5, 11, 4 |
| C. | 2, 5, 11, 6, 7, 4, 9, 5, 2 |
| D. | none |
| Answer» C. 2, 5, 11, 6, 7, 4, 9, 5, 2 | |
| 15. |
What is the time complexity of pre-order traversal in the iterative fashion? |
| A. | O(1) |
| B. | O(n) |
| C. | O(logn) |
| D. | O(nlogn) |
| Answer» B. O(n) | |
| 16. |
What is the space complexity of the post-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) | |
| 17. |
To obtain a prefix expression, which of the tree traversals is used? |
| A. | Level-order traversal |
| B. | Pre-order traversal |
| C. | Post-order traversal |
| D. | In-order traversal |
| Answer» B. Pre-order traversal | |
| 18. |
Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is |
| A. | A, C, D, B, E |
| B. | A, B, C, D, E |
| C. | A, B, C, E, D |
| D. | D, B, E, A, C |
| Answer» B. A, B, C, D, E | |
| 19. |
What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order. |
| A. | 15 |
| B. | 3 |
| C. | 5 |
| D. | 8 |
| Answer» C. 5 | |
| 20. |
The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be |
| A. | T Q R S O P |
| B. | T O Q R P S |
| C. | T Q O P S R |
| D. | T Q O S P R |
| Answer» C. T Q O P S R | |
| 21. |
A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75? |
| A. | 7, 8, 26, 13, 75, 40, 70, 35 |
| B. | 26, 13, 7, 8, 70, 75, 40, 35 |
| C. | 7, 8, 13, 26, 35, 40, 70, 75 |
| D. | 8, 7, 26, 13, 40, 75, 70, 35 |
| Answer» D. 8, 7, 26, 13, 40, 75, 70, 35 | |
| 22. |
Which of the following pair’s traversals on a binary tree can build the tree uniquely? |
| A. | post-order and pre-order |
| B. | post-order and in-order |
| C. | post-order and level order |
| D. | level order and preorder |
| Answer» B. post-order and in-order | |
| 23. |
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 | |
| 24. |
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 | |
| 25. |
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 | |
| 26. |
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 | |
| 27. |
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 | |
| 28. |
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 | |
| 29. |
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) | |
| 30. |
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) | |
| 31. |
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 | |
| 32. |
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 | |
| 33. |
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 | |
| 34. |
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 | |
| 35. |
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 | |
| 36. |
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 | |
| 37. |
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) | |
| 38. |
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 | |
| 39. |
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 | |
| 40. |
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 | |
| 41. |
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 | |
| 42. |
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)) | |
| 43. |
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 | |
| 44. |
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 | |
| 45. |
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) | |
| 46. |
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 | |
| 47. |
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 | |
| 48. |
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) | |
| 49. |
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 | |
| 50. |
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 | |
Done Studing? Take A Test.
Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.