Virtual Labs

1. In a linear-probing hash table, which circumstance can result in linear running time for a search hit in the worst case?

a: All keys hash to the same index. Explanation

Explanation

b: All keys hash to different indices. Explanation

Explanation

c: All keys hash to even-numbered indices. Explanation

Explanation

d: All keys hash to different even-numbered indices. Explanation

Explanation

2. In a hash table, what is the definition of a collision?

a: Two entries are identical except for their keys. Explanation

Explanation

b: Two entries with different data have exactly the same key. Explanation

Explanation

c: Two different keys produce the same hash-table index. Explanation

Explanation

d: Two entries with the same key produce different hash-table indices. Explanation

Explanation

3. Which statement correctly describes the purpose of a hash function in a hash table?

a: It maps a key to a value used to determine a table index. Explanation

Explanation

b: It sorts all keys before storing them. Explanation

Explanation

c: It guarantees a unique index for every possible key. Explanation

Explanation

d: It stores all values in sequential memory locations. Explanation

Explanation

4. What is the average-case time complexity of insertion in a well-designed hash table?

O(n)

Explanation

O(\log n)

Explanation

O(n^2)

Explanation

O(1)

Explanation

5. Which factor has a direct effect on the load factor of a hash table?

a: The number of stored elements and the table size. Explanation

Explanation

b: Only the length of the keys. Explanation

Explanation

c: Only the data type of the stored values. Explanation

Explanation

d: Only the number of hash functions used. Explanation

Explanation

6. Which collision-resolution technique uses a second hash function to determine the probe step?

a: Linear probing Explanation

Explanation

b: Separate chaining Explanation

Explanation

c: Double hashing Explanation

Explanation

d: Quadratic probing Explanation

Explanation

7. If a hash table uses separate chaining and all

n

keys map to the same index, what is the worst-case search complexity?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

8. Suppose a hash table has 20 slots and contains 15 elements. What is its load factor?

0.25

Explanation

0.50

Explanation

0.75

Explanation

1.33

Explanation

9. Why is maintaining a suitable load factor important for an open-addressing hash table?

a: It guarantees that collisions never occur. Explanation

Explanation

b: It helps limit the number of probes required during operations. Explanation

Explanation

c: It guarantees sorted order of the keys. Explanation

Explanation

d: It removes the need for a hash function. Explanation

Explanation

Hash Tables