Hashing

1:	When key values are reals a similar data representation might be produced by using a hashing function with
	A. Mod B. Div C. Trunc D. Log N
	Answer: Option C Explanation :
2:	A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing.Maximum number of comparisons needed in searching an item that is not present is
	A. 6 B. 5 C. 4 D. 3
	Answer: Option B Explanation : It will be one more than the size of the biggest cluster(which is 4)because,assume a search key hashing onto in 8.By linear probing the nest location for searching is bin 9.Then 0,then 1.If all these resulted in a miss, we try at bin 2 ans stop as it is vacant.This logic may not work if deletion operation is done before the search.

3:	A hash function f defined as f(key)=key mod 7,with linear probling,insert the keys 37,38,72,48,98,11,56, into a table indexed from 11 will be stored in the location
	A. 3 B. 4 C. 5 D. 6
	Answer: Option C Explanation : f(37)=37 mod7 = 2  So,37 will be put in location 2. f(38)= 3.  So,38 will be in third location f(72)= 2  (Collision)    With linear probing as the collision resolving strategy,the alternate location for 72 should be the 4 but there is element  11 so 72 will be stored at location 5

4:	An advantage of chained hash table over the open addressing scheme is
	A. Worst case complexityof serach operation os less B. Space used is less C. Deletion is easier D. None of these
	Answer: Option C Explanation :

5:	The average search time of hashing with linear probing will be less if the load factor
	A. Is far less than one B. Equals one C. Is far greater than one D. None of these
	Answer: Option A Explanation :

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/16/1.html#ixzz2fUO344rq

6:	A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is
	A. (x-1) (x-2)...(x-(m-2))(m-1)/xm-1 B. (x-1) (x-2)...(x-(m-1))(m-1)/xm-1 C. (x-1) (x-2)...(x-(m-2))(m-1)/xm D. (x-1) (x-2)...(x-(m-1))(m-1)/xm
	Answer: Option A Explanation : Probability for the first record not colliding is x/x. Probability for the second record not colliding is x-1/x. (This is because one place is already occupied, So, favorable number of cases is x-1). Probability for the third record not colliding is x-2/x. Probability for the (m-1)th record not colliding is x-(m-2)/x. Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So probability is (m-1)/x. The required probability is (x/x) (x-1/x) (x-2/x) ... (x-(m-2)/x) (m-1/x)

7:	A hash table with 100 buckes with one slot per bucket is depicted in Fig. 6.3. The symbols, Sl to S7 are initially entered using a hashing fucntion with linear probing. The maxmmum number of comparisons needed in searching an intem that is not present is
	A. 4 B. 5 C. 6 D. 3
	Answer: Option B Explanation : It will be one more than the size of the biggest cluster (which is 4) in this case. This is because, assume a search key hashing onto bin 8. By liner probing the next location for searching is bin 9. Then 0, then 1. if all these resulted in a miss, we try at bin 2 and stop as it is vacant. This logic may not work if deletion operation is done before the search.

8:	A hasn funciton f defined as f (key) = key mod 7, with linear probibng, us used to insert the keys 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6. What will be the location of key 11?
	A. 3 B. 4 C. 5 D. 6
	Answer: Option C Explanation : f(37) = 37 mod 7 =2. So, 37 will be put in location 2. f(38) = (3. So, 38 will be in third location. f(72) =2. This results in a collision. With linear probing as the collison resolving strategy, the alternate location for 72 will be the location 4 (i.e. next vacant slot in the current configuration). Continuing this way, the final configuration will be 98, 56, 37, 38, 72, 11, 48.

9:	The average search time of hashing, with linear probing will be less if the load factor
	A. is far less than one B. equals one C. is far greater than one D. none of the above
	Answer: Option A Explanation : Load factor is the ration of number of records that are currently present and the total number of records that can be present. If the load factor is less, free space will be more. This means proability of collision is less. So, the search time will be less.

10:	A hash table can store a maximumof 10 rdcords. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going ono location 2, with a hash function resolving collisions by linear probing is
	A. 0.6 B. 0.1 C. 0.2 D. 0.5
	Answer: Option A Explanation : If the new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive the new record. THe probability is 6/10 (as 10 is the total possible number of locations).

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/16/2.html#ixzz2fUOG32UH

11:	Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8. Which of the following locations will never be probed if a collision occurs at position 4?
	A. 4 B. 5 C. 8 D. 2
	Answer: Option D Explanation : You can varify that the 1st, 3rd, 5th, 7th, ... probes check at location 5. The 2nd, 6th, 10th... probes check at location 4. The rest of the address space will never be probed.

12:	A hash table has space for 100 records. What is the probability of collision before the table is 10% full?
	A. 0.45 B. 0.5 C. 0.3 D. 0.34 (approximately)
	Answer: Option A Explanation : If there is only one record, then the probability of a collision will be 1/100. If 2, then 2/100 etc., If 9 then 9/100. So, the required probability is, (1+2+3...9)/100 = 0.45.

13:	Which of the following statements is true? I. As the number of entries inthe hash table incrases, the number of collisions increases. II. Recursive programs are efficient. III. The worst time complexity of quick sort is O (n2). IV. Binary search implemented using a linked list is efficient.
	A. I and II B. II and III C. I and IV D. I and III
	Answer: Option D Explanation : Recursive programs take more time than the equivalent non-recursive version and so not efficient. This is because of the function call overhead. In binary search, since every time the current list is probed at the middle, random access is preferred. Since linked list does not support random access, binary search implemented this way in inefficient.

14:	A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is
	A. (x-1) (x-2) ... (x-(m-2)) (m-1)/xm-4 B. (x-1) (x-2(... (x-(m-1()(m-1)/xm-1 C. (x-1) (x-2) ... (x-(m-2))(m-1)/xm D. (x-1)(x-2)...(x-(m-1))(m-1)/xm
	Answer: Option A Explanation : Probability for the first record not colliding is x/x. Probability for the second record not colliding is x-1/x. (This is because one place is already occupied. So, favourbale number of cases is x-1). Probability for the third record not colliding is x-2/x. Probability for the (m-1)th record not colliding is x-(m-2)/x. Now the next (mth) record is resulting in a collision. Out of the x places, it should hast to one of the (m-1) places already, filled. So probability is (m-1)/x. The required probability is (x/x) (x-1/x) (x-2/x) ... (x-(m-2)/x) (m-1/x)

15:	If the hashing function is the remainder on division, then clustering is more likely to occur if the storage space is divided into 40 sectors rather than 41. this conclusion is
	A. more likely to be false B. more likely to be true C. is always false D. none of the above
	Answer: Option B

Read more: http://www.avatto.com/computer/exam/mcqs/data-structure/questions/16/3.html#ixzz2fUOR517T