NEW
Font size
WorksheetsHash
Total questions: 20
Worksheet time: 10mins
If a list of items is in random order use a
Binary search
Linear Seach
Hashing gives each item
A sequential address
A logarithmic address
No address
A unique address
A hash table is
an abstract data structure
an array
an integer
made of pine
Address <----- key MOD(numberOfSlots)
IF KEY = 5432 and numberOfSlots = 1000
Address = ?
5
432
543
5432
Address <----- key MOD(numberOfSlots)
IF KEY = 5432 and numberOfSlots = 100
Address = ?
5
4
32
5432
when an algorithm generates the same address for different primary keys it is known as
Knock
Bang
Collisions
DoubleHash
a synonym is
a word bank
a key
a collision
a list
What is the status after adding 10
What is the status after adding 7
Divide the item into equal-size pieces
Add the pieces together
Perform the mod step to get an address
Which hashing method does this describe
folding method
alphanumeric
mid-square
mod
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
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)
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
