Q2. Suppose that the following keys are inserted in some order into an initially
ID: 3915374 • Letter: Q
Question
Q2. Suppose that the following keys are inserted in some order into an initially empty linear-probing hash table of size 7 (assuming no resizing), using the following table of hash values: 4 marks] Key Hash Give the contents of the linear-probing array if the keys are inserted in alphabetical order: A, B, C, D, E, F, G inserted in alphabetical order A a) Which of the following could be the contents of the linear-probing array if the keys are inserted in some other order? b) 01 23 4 5|6 0 1 2 3 4 5 6Explanation / Answer
a)
Insert A
0 1 2 3 4 5 6
--------------------------------------------------------
A
Insert B
0 1 2 3 4 5 6
-------------------------------------------------------
B A
Insert C (collision)
0 1 2 3 4 5 6
-------------------------------------------------------
B A C
Insert D
0 1 2 3 4 5 6
-------------------------------------------------------
D B A C
Insert E
0 1 2 3 4 5 6
-------------------------------------------------------
D B E A C
Insert F(collision)
0 1 2 3 4 5 6
-------------------------------------------------------
D B F E A C
Insert G
0 1 2 3 4 5 6
-------------------------------------------------------
G D B F E A C
b) III Beacause collision will occur only with A&C and D&F, so either one of A or C will be at index 5 or D or F will be at index 1. In I and II, neither of this condition is trie and in III F is at index 1. So III could be possible state of the table.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.