15 Questions

Questions and Answers

- 1.Which of the following trees have height as O(lgn) where number of nodes is n.
- A.
R-B Tree

- B.
Binary Search Tree

- C.
Binary Tree

- D.
2-3 Tree

- 2.For a 2 -3 Tree which of the following is true
- A.
A 2-3 Tree may have root node with only one child

- B.
Maximum number of children of any node is 3

- C.
A leave can hight either 2 or 3 in a 2-3 tree

- D.
Minimum number of children of any node is 2.

- 3.If we first delete a key from an R-B tree and add it back then, how does the structure of resulting R-B tree compare with original R-B tree?
- A.
Both trees will be same in all cases

- B.
Both will be different in all the cases

- C.
Both trees may be same or different depending on the case.

- 4.If we first delete a key from 2-3 tree and then add it back then, how does the structure of resulting 2-3 tree compare with original 2-3 tree?
- A.
Both trees will be same in all cases

- B.
Both will be different in all the cases

- C.
Both trees may be same or different depending on the case.

- 5.
**The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?**- A.
2exp(h-1)-1

- B.
2exp(h+1)-1

- C.
2exp(h)-1

- D.
2exp(h+1)-1

- 6.The tree is an example of
- A.
2-3 tree

- B.
Binary search Tree

- C.
Binomial Heap

- D.
Fibonacci Heap

- 7.The following are the case of ...................in red black Tree
- A.
Insert

- B.
Find

- C.
Delete

- D.
None of these

- 8.
**Suppose a binary tree is constructed with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be?**- A.
(n+1)/2

- B.
(n-1)/2

- C.
(n/2)-1

- D.
(n+1)/2

- 9.
**The run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is**- A.
O(nlg(n))

- B.
O(√n)

- C.
O(n)

- D.
O(lg(n))

- 10.
**If n numbers are to be sorted in ascending order in O(nlogn) time, which of the following tree can be used**- A.
Binary Tree

- B.
Binary Search Tree

- C.
Max- heap

- D.
Min-Heap

- 11.The rotation need to be done is
- A.
LL

- B.
LR

- C.
RL

- D.
None of these

- 12.
**A 2-3 is a tree such that**a) All internal nodes have either 2 or 3 children b) All path from root to leaves have the same length The number of internal nodes of a 2-3 tree having 9 leaves could be- A.
4

- B.
5

- C.
6

- D.
7

- 13.
**Which type of traversal of binary search tree outputs the value in sorted order?**- A.
Pre-order

- B.
Post-order

- C.
In-order

- D.
None of these

- 14.
**Suppose we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequence could not be the sequence of the node examined?**- A.
925, 202, 911, 240, 912, 245, 258, 363

- B.
924, 220, 911, 244, 898, 258, 362, 363

- C.
925, 202, 911, 240, 912, 245, 258, 363

- D.
2, 399, 387, 219, 266, 382, 381, 278, 363

- 15.
**A binary search tree is generated by inserting in order the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24**The number of the node in the left sub-tree and right sub-tree of the root, respectively, is- A.
(4,7)

- B.
(7,4)

- C.
(8,3)

- D.
(3,8)