Data Structure

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