NEW
Font size
WorksheetspythonDS
Total questions: 15
Worksheet time: 7mins
Which the following simple searching
Stack
Queue
Sequence searching
Binary searching
Based on binary searching, how to get middle key
last index/2
(last index + initial index)/2
(last index - initial index)/2
(last index + initial index) % 2
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
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
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
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
