December 2010 - Question No 24 & 25

24. Linear probing suffers from a problem known as

(A) Secondary clustering
(B) Primary clustering
(C) Both (A) and (B)
(D) None of these

Ans:-B

Explanation:- Linear probing is a term associated with hashing. Linear probing is a collision resolving technique in hashing. It suffers from a problem known as primary clustering. Any chosen hash function should uniformly distribute the records across the given available address space but sometimes clusters appear. If linear probing is used, it might spend a lot of time probing within the cluster instead of searching in the subsequent available space. One more collision resolving technique is Quadratic probing. Again we might come across the same topic depending on the nature of question encountered in future.

---

25. Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?

(A) 90, 40, 65, 50, 88
(B) 90, 110, 80, 85, 88
(C) 190, 60, 90, 85, 88
(D) 65, 140, 80, 70, 88

Ans:-C

Explanation:- Inorder to find a solution for a question like above, given the data draw a binary search tree for each one of the options. The first item is the root. Any value less than the root will form the left side of the tree and any value greater than the root will form the right side of the tree. When you draw such a tree, if you find no node has a left and right child then such a sequence would be valid. If you find that the tree has a left and right child for any node then that sequence is invalid. If you draw the tree for all the 4 options given in the question you will find that only option C does not have left and right child for any node. So option C is correct.