Explore topic-wise InterviewSolutions in .

Correct option is (a) Any prime number

Easy explanation - A prime number not too CLOSE to an exact power of 2 is OFTEN a good choice for m since it REDUCES the number of collisions which are likely to OCCUR.

Correct choice is (b) H(k) = k MOD m

For explanation: In division method for creating hash functions,k keys are mapped into ONE of m SLOTS by TAKING the reminder of k divided by m.

Correct answer is (B) False

The BEST I can EXPLAIN: A hash value is expected to be UNRELATED or independent of any patterns in the distribution of keys.

correct OPTION is: (a) h(K) = lowerbound(km)

If the keys are KNOWN to be random real numbers k independently and UNIFORMLY distributed in the range 0<=k<=1, the HASH function which satisfies the condition of simple uniform hashing is

h(k)= lowerbound(km).

Right ANSWER is (c) Hash key=(hash(X)+F(i^2)) mod table size

Explanation: Hash key=(hash(x)+F(i^2)) mod table size is the formula for QUADRATIC probing. Hash key = (hash(x)+F(i)) mod table size is the formula for LINEAR probing.

Correct choice is (B) LINEAR probing

For explanation: Linear probing OFFERS BETTER cache PERFORMANCE than quadratic probing and also it preserves locality of reference.

The CORRECT answer is (a) Quadratic PROBING

Easy explanation - Quadratic probing HANDLES primary COLLISION occurring in the linear probing METHOD. Although secondary collision occurs in quadratic probing, it can be removed by extra multiplications and divisions.

Correct OPTION is (b) 2

For explanation: 2 requirements are to be MET with respect to table size. The table size should be a PRIME NUMBER and the table size should not be more than half FULL.

The CORRECT option is (a) F(i)=i^2

Best EXPLANATION: The FUNCTION of QUADRATIC probing is defined as F(i)=i^2. The function of linear probing is defined as F(i)=i.

The correct ANSWER is (b) False

The BEST EXPLANATION: In quadratic probing, if the table SIZE is prime, we can insert a new ELEMENT even though table is exactly half filled. We can’t insert element if table size is more than half filled.

Correct option is (C) lazy deletion

Explanation: STANDARD deletion cannot be performed in an open addressing hash table, because the cells might have caused collision. HENCE, the hash tables IMPLEMENT lazy deletion.

Correct option is (a) True

The best EXPLANATION: QUADRATIC PROBING can overcome primary collision that OCCURS in linear probing but a secondary collision occurs in quadratic probing.

Correct option is (d) open addressing

To explain: Quadratic PROBING comes under open addressing SCHEME to RESOLVE collisions in hash tables.

The CORRECT option is (b) \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\)

The BEST I can explain: The mathematical FORMULA for calculating the number of probes for an UNSUCCESSFUL search is \(\frac{1}{2}\frac{1+1}{(1-⅄)^2}\). For INSERTION, it is \(\frac{1}{2} \frac{1+1}{(1-⅄)}\).

Correct CHOICE is (c) H(x)= (key+ F(i)) mod table size

To explain: The hash FUNCTION used in linear probing is defined to be H(x)= (key+ F(i)) mod table size where i=0,1,2,3,…,N.

Right ANSWER is (B) F(i)=i

Easiest explanation - The function USED in linear probing is defined as, F(i)=I where i=0,1,2,3….,n.

Right choice is (a) True

Best EXPLANATION: Using random COLLISION RESOLUTION ALGORITHM, the cost of an unsuccessful search can be used to compute the average cost of a successful search.

The correct option is (d) Rehashing

Best explanation: LINEAR probing, quadratic probing and DOUBLE hashing are all collision resolution STRATEGIES for open addressing whereas rehashing is a different TECHNIQUE.

The correct option is (C) 2.5 and 1.5

For explanation: Using FORMULA, the average number of probes required for INSERTION is 2.5 and for a SUCCESSFUL search, it is 1.5.

The CORRECT ANSWER is (a) Primary collision

Explanation: Primary collision occurs due to linear probing TECHNIQUE. It is overcome using a quadratic probing technique.