Hash Table

The case in which a key other than the desired one is kept at the identified location is called?

• Hashing

• Collision

• Chaining

• Open addressing

Which of the following is not a collision resolution technique?

• Separate chaining

• Linear probing

• Quadratic probing

• Hashing

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown above.

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

• 46, 42, 34, 52, 23, 33

• 34, 42, 23, 52, 33, 46

• 46, 34, 42, 23, 52, 33

• 42, 46, 33, 23, 34, 52

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i. 9679, 1989, 4199 hash to the same value

ii. 1471, 6171 has to the same value

iii. All elements hash to the same value

iv. Each element hashes to a different value

• i only

• ii only

• i and ii only

• iii or iv

What is the worst case search time of a hashing using separate chaining algorithm?

• O(N log N)

• O(N)

• O(N^2)

• O(N^3)

What is the advantage of using a doubly linked list for chaining over singly linked list?

• it takes less memory

• it is easy to implement

• it makes the process of insertion and deletion faster

• it causes less collisions

A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

• 3

• 4

• 5

• 6

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

• A

• B

• C

• D