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?
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 (n^{2}).
IV. Binary search implemented using a linked list is efficient.
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 m^{th} record is the first record to result in collision is
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 (m^{th}) 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