Database Multiple Choice Questions on “Hashing techniques”.
1. 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
Answer: a
Clarification: Hashing is also a method of sorting key values in a database table in an efficient manner.
2. A technique for direct search is
a) Binary Search
b) Linear Search
c) Tree Search
d) Hashing
Answer: d
Clarification: Hashing is one way to enable security during the process of message transmission when the message is intended for a particular recipient only.
3. The searching technique that takes O (1) time to find a data is
a) Linear Search
b) Binary Search
c) Hashing
d) Tree Search
Answer: c
Clarification: A formula generates the hash, which helps to protect the security of the transmission from unauthorized users.
4. The goal of hashing is to produce a search that takes
a) O(1) time
b) O(n2 )time
c) O(log n ) time
d) O(n log n ) time
Answer: a
Clarification: Time complexity is given by the big oh notation.
5. 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
Answer: b
Clarification: A formula generates the hash, which helps to protect the security of the transmission from unauthorized users.
6. 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
Answer: b
Clarification: Hashing is used to index and retrieve items in a database because it is easier to find the item using the shortened hashed key than using the original value.
7. Key value pairs is usually seen in
a) Hash tables
b) Heaps
c) Both Hash tables and Heaps
d) Skip list
Answer: a
Clarification: Hashing is used to index and retrieve items in a database because it is easier to find the item using the shortened hashed key than using the original value.
8. What is the best definition of a collision in a hash table?
a) Two entries are identical except for their keys
b) Two entries with different data have the exact same key
c) Two entries with different keys have the same exact hash value
d) Two entries with the exact same key have different hash values
Answer: a
Clarification: This level is the root of the tree.
9. 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
Answer: a
Clarification: If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.
10. Breadth First Search is used in
a) Binary trees
b) Stacks
c) Graphs
d) All of the mentioned
Answer: c
Clarification: Hashing is used to index and retrieve items in a database because it is easier to find the item using the shortened hashed key than using the original value.