Binary Search Tree (BST) || Mock Test on UGC NET Computer Science Mock Test with Video Solution || PART IV || Data Structure

This mock test best on GATE Computer Science Questions , Previous Year Question Paper UGC NET Computer Science and ISRO Computer Science Question Papers.

Series : Data Structure and Algorithm

Topic : Binary Search Tree (BST) in Data Structure

1) The following numbers are inserted into an empty binary search tree in the given order:

10, 1, 3, 5, 15, 12, 16

What is the height of the binary search tree ?
(A)3
(B)4
(C) 5
(D) 6                                                                        Previous Year Question Paper UGC NET Computer Science

2) Suppose that we have numbers between 1 and 1,000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined ?
(A) 925, 221, 912, 245, 899, 259, 363, 364
(B) 3, 400, 388, 220, 267, 383, 382, 279, 364
(C) 926, 203, 912, 241, 913, 246, 364
(D) 3, 253, 402, 399, 331, 345, 398, 364  Previous Year Question Paper UGC NET Computer Science

3) 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    Previous Year Question Paper UGC NET Computer Science

4) You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, …, n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
(A)O(Logn)
(B)O(n)
(C) O(nLogn)
(D) none of the above, as the tree cannot be uniquely determined.  GATE Computer Science Questions

5) What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
(A) Θ(logn) for both insertion and deletion
(B) Θ(n) for both insertion and deletion
(C) Θ(n) for insertion and Θ(logn) for deletion
(D) Θ(logn) for insertion and Θ(n) for deletion                              GATE Computer Science Questions

6) While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

(A) 65
(B) 67
(C) 69
(D) 83                                                                                                      GATE Computer Science Questions

7) Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?
(A){10, 75, 64, 43, 60, 57, 55}
(B){90, 12, 68, 34, 62, 45, 55}
(C) {9, 85, 47, 68, 43, 57, 55}
(D) {79, 14, 72, 56, 16, 53, 55}                                                                GATE Computer Science Questions

8) When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 2