NEW
Font size
WorksheetsHashing
Total questions: 20
Worksheet time: 18mins
What is the load factor?
Average array size
Average key size
Average chain length
Average hash table length
In simple chaining, what data structure is appropriate?
Singly linked list
Doubly linked list
Circular linked list
Binary trees
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
Hashing is not the problem of finding an appropriate mapping of keys into addresses.
True
False
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
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
h(i) =i^2 mod 10
h(i) =i^3 mod 10
h(i) = (11 ∗ i^2) mod 10
h(i) = (12 ∗ i) mod 10
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
Separate chaining is easier to implement as compared to open addressing .
True
False
In open addressing the hash table can never become full.
True
False
Which of the following trait of a hash function is most desirable?
it should cause less collisions
it should cause more collisions
it should occupy less space
it should be easy to implement
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is
80
0.0125
8000
1.25
Which of the following statement(s) is TRUE?
1) A hash function takes a message of arbitrary length and generates a fixed length code.
2) A hash function takes a message of fixed length and generates a code of variable length.
3) A hash function may give the same hash value for distinct messages.
1 only
1 & 3 only
2 & 3 only
3 only
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
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S1 to S7 initially entered using a hashing function with linear probing.The maximum number of comparisons needed in searching an item that is not present is
3
4
5
6
The characters of the string K R P C S N Y T J M are inserted into a hash table of size 10 using hash function
h(x) = ((ord(x) - ord(A) + 1)) mod 10
(here ord(A) = 1, ord(B)=2, so on)
If linear probing is used to resolve collisions, then the following insertion causes collision
Y
C
M
P
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
