Data Structure Test Set 4
| Q16➡ | Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ? (i) preorder and postorder (ii) inorder and postorder (iii) preorder and inorder (iv) level order and postorder |
| i ➥ (i) only |
| ii ➥ (ii), (iii) |
| iii ➥ (iii) only |
| iv ➥ (iv) only |
| Q17➡ | The numbers 1, 2, …. n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be |
| i ➥ p |
| ii ➥ p + 1 |
| iii ➥ n – p |
| iv ➥ n – p + 1 |
| Q18➡ | In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is: |
| i ➥ 2h – 1 |
| ii ➥ 2h – 1 + 1 |
| iii ➥ 2h – 1 |
| iv ➥ 2h |
| Q19➡ | A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be |
| i ➥ 8, 7, 6, 5, 4, 3, 2, 1 |
| ii ➥ 1, 2, 3, 4, 8, 7, 6, 5 |
| iii ➥ 2, 1, 4, 3, 6, 7, 8, 5 |
| iv ➥ 2, 1, 4, 3, 7, 8, 6, 5 |
| Q20➡ | Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? |
| i ➥ 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95 |
| ii ➥ 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29 |
| iii ➥ 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95 |
| iv ➥ 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29 |
Weekly Test GATE/NTA NET CSA
17-ii.
18-iv
19-iv
20-i
16 , iii
17, ii
18, ii
19, ii
20, i
17:n-p-1
19: ii
20: i