NEW
Font size
WorksheetsData Structure
Total questions: 13
Worksheet time: 5mins
1. What is a hash table?
a) A structure that maps values to keys
b) A structure that maps keys to values
c) A structure used for storage
d) A structure used to implement stack and queue
If several elements are competing for the same bucket in the hash table, what is it called?
a) Diffusion
b) Replication
c) Collision
d) Duplication
What is direct addressing?
a) Distinct array position for every possible key
b) Fewer array positions than keys
c) Fewer keys than array positions
d) Same array position for all keys
What is the search complexity in direct addressing?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(1)
What is a hash function?
a) A function has allocated memory to keys
b) A function that computes the location of the key in the array
c) A function that creates an array
d) A function that computes the location of the values in the array
Which of the following is not a technique to avoid a collision?
a) Make the hash function appear random
b) Use the chaining method
c) Use uniform hashing
d) Increasing hash table size
7. What is the load factor?
a) Average array size
b) Average key size
c) Average chain length
d) Average hash table length
If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
a) Less than 1
b) Less than n
c) Less than m
d) Less than n/2
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
a) 8, _, _, _, _, _, 10
b) 1, 8, 10, _, _, _, 3
c) 1, _, _, _, _, _,3
d) 1, 10, 8, _, _, _, 3
A hash table can store a maximum of 10 records, currently there are records in location 1, 3,4,7,8,9,10. The probability of a new record going into location 2, with hash functions resolving collisions by linear probing is
a) 0.1
b) 0.6
c) 0.2
d) 0.5
Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?
a) All keys hash to same index
b) All keys hash to different indices
c) All keys hash to an even-numbered index
d) All keys hash to different even-numbered indices
The hash function is
H1(k) = k % 50.
In the case of collision, the hash function used is
H(k) = (H1(k) + M x H2(k)) % 50
where H1(k) = k % 50 and H2(k) = k % 20.
M is initialized to 0 and is incremented by 1 each time a collision occurs.
This could be categorized under which of the following collision detection technique
a)Linear Probing
b)quadratic Probing
c)Re-Hashing
d)Double Hashing
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is __________
a)80
b)0.0125
c)8000
d)1.25
