Hashing Interview Question Part 3

24. Which of the following are not hash functions?
a. division
b. coupling
c. folding
d. extraction
e. mid square
Ans. c



25. The following paragraph is connected with hashing:
The process of mapping large amounts of data into a smaller table is called …… (i) ……. A good hash function should satisfy two criteria, namely quickness to compute and minimisation of the number of …… (ii) ……. Minimization of …… (iii) …… can be achieved by choosing a hash function that spreads the incoming data as evenly as possible over the hash table.

Correct terms for the blanks positions are:
(a) (i) indexing (ii) collisions (iii) couplings
(b) (i) hashing (ii) collisions (iii) couplings
(c) (i) hashing (ii) collisions (iii) collisions
(d) (i) indexing (ii) collisions (iii) collisions

Ans. c


26. What is the best definition of a collision in a hash table?
a. Two entries are identical except for their keys.
b. Two entries with different data have the exact same key.
c. Two entries with different keys have the same exact hash value.
d. Two entries with the exact same key have different hash values.
Ans. c
27. The phenomenon wherein two keys that hash into different values compete with each other in successive rehashes is called ____________ .
Ans. primary clustering
28. ________ is a collision resolution technique that puts all the elements that hash to the same slot in a linked list.
a. chaining
b. open addressing
c. closed addressing
d. hashing
Ans. a
29. Given a hash table T with m slots that stores n elements,the load factor is
a. α = m*n
b. α = n/m
c. α = m+n
d. α = m/n
Ans. b
30. If a hash table in which collision are resolved by chaining, a successful search takes ______ time on the average, under the assumption of simple uniform hashing.
a. Q(1+a)
b. θ(1+α)
c. Ω(1+α)
d. O(1+α)
Ans. a
31. Inserting an element into an open-address hash table with load factor a requires at most ______ probes on average, assuming uniform hashing.
a. 1/(1+α)
b. 1/(1-α)
c. 1+α
d. 1/α
Ans. b

32. One of the collision resolution techniques and the methods used is open addressing include __________ .
Ans. Overflow block

33. The collision resolution techniques and methods used in closed addressing include
i)linked list
ii) binary tree
iii) overflow block
The correct options are
a. i and ii only
b. i only
c. ii only
d. i,ii and iii only
Ans. a