Suppose 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 for this problem).
key: A B C D E F G
hash:2 0 0 4 4 4 2
Which of the following could not possibly result from inserting these keys?
a. EFGACBD
b. CEBGFDA
c. BDFACEG
d. CGBADEF
e. FGBDACE
f. GECADBF
Give the minimum and the maximum number of probes that could be required to build a table of size 7 with these keys, and an insertion order that justifies your answer.
non of the choices are possible.
a) E F G A C B D (4 4 2 2 0 0 4) .
possible insertion order : G,A
other elements are unable to insert
b) C E B G F D A (0 4 0 2 4 4
2) .
possible insertion order : C, F, D
other elements are unable to insert
c) B D F A C E G (0 4 4 2 0 4 2) .
possible insertion order : B
other elements are unable to insert
d) C G B A D E F (0 2 0 2 4 4
4) .
possible insertion order : C, D, E, F
other elements are unable to insert
e) F G B D A C E (4 2 0 4 2 0 4) .
possible insertion order : null
no possible insertion
f) G E C A D B F (2 4 0 2 4 0 4) .
possible insertion order : D
other elements are unable to insert
Get Answers For Free
Most questions answered within 1 hours.