Time Left - 15:00 mins

GATE 2019 - P&DS Quiz-9 (Binary Search Tree ) (App update required to attempt this test)

Attempt now to get your rank among 730 students!

Question 1

Consider the table of 15 items as given below:
AL, EX, FN, FU, IF, IW, LE, LO, NI, OP, OR, RD, RN, TE, TI
By using binary search method, after how many passes will the search for the item IF be determined?

Question 2

Every binary tree whose preorder search produces the string J B A C D I H E G F must have 10 vertices. What else do the trees have in common?
(i) The root must be labeled J
(ii) If J has a right child it must be labeled B, otherwise the left child is labeled B
(iii) If J has a left child it must be labeled B, otherwise the right child is labeled B
(iv) F will always be at the lower most level

Question 3

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.

Question 4

Suppose you want to build an address book with entries in alphabetical order by last name, which of the following abstract data type is most appropriate for the problem?

Question 5

Consider the pre-order traversal of BST
100 , 50 , 10 , 70 , 400 , 500
What would be the corresponding post-order traversal of the same BST?

Question 6

A binary search tree was constructed by inserting following elements in to an initially empty binary tree.
50, 27, 16, 88, 34, 65, 77,52, 93, 4, 12, 29, 44, 92
Preorder and postorder traversals of the resultant binary search tree were stored in arrays A and B respectively. How many elements have same index location in both the arrays? [Assume arrays A and B start from the same index]

730 attempts
3 upvotes
11 comments

Tags :

GATE & PSU CS Programming and Data Structures

Mar 28GATE & PSU CS