Suppose the that the keys A through G with the hash values given below, are inse

Question

Suppose the that the keys A through G with the hash values given below, are inserted in some order
into an initially empty table of size 7 using a linear-probing table (with no resizing).
key
hash(M = 7)
A
2
B
0
C
0
D
4
E
4
F
4
G
2
Which of the following could not possibly result from inserting these keys?
(a) E F G A C B D
(b) C E B G F D A
(c) C B G A F E D
(d) B D F A C E G
(e) B C A E D F G
(f) C B A G D F E
(g) C G B A D E F
(h) F G B D A C E
(i) G E C A D B F
Give the minimum and maximum number of probes that could be required to build a table of size 7
with the keys in Question 1, and an insertion order that justifies your answer.

Explanation / Answer

(a) E F G A C B D --- not possible

(b) C E B G F D A   --- not possible

(d) B D F A C E G   --- not possible

(e) B C A E D F G --- not possible

(g) C G B A D E F --- not possible

(h) F G B D A C E --- not possible

(i) G E C A D B F --- not possible

The minimum and maximum number of probes is same and equal to 5 with insertion order, C B G A D E F.

Since the number of letters hash to same location are no more than the subsequent locations before another letter mapping, the order in which the letters appear doesn't matter, so minimum probes equals maximum probes.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.