Virtual Labs

1. Which of the following is an advantage of using a hash table for storing key-value pairs?

a: It always keeps the keys sorted. Explanation

Explanation

b: It can provide average-case constant-time lookup. Explanation

Explanation

c: It requires every key to have the same value. Explanation

Explanation

d: It eliminates the possibility of collisions. Explanation

Explanation

2. What happens when two different keys are mapped to the same index by a hash function?

a: The hash table is automatically sorted. Explanation

Explanation

b: The second key is always discarded. Explanation

Explanation

c: A collision occurs and a collision-resolution method is required. Explanation

Explanation

d: The hash function becomes invalid. Explanation

Explanation

3. What is the expected average-case time complexity of searching for a key in a well-designed hash table?

O(1)

Explanation

O(\log n)

Explanation

O(n)

Explanation

O(n^2)

Explanation

4. In which of the following applications can hash tables be used?

a: Implementing associative arrays. Explanation

Explanation

b: Implementing symbol tables. Explanation

Explanation

c: Implementing dictionaries or key-value mappings. Explanation

Explanation

d: All of the mentioned. Explanation

Explanation

5. Consider a hash table containing

n

elements. If all keys happen to be mapped to the same index and collisions are handled using separate chaining, what can be the worst-case time complexity of searching for a key?

O(\log n)

Explanation

O(1)

Explanation

O(n)

Explanation

O(n^2)

Explanation

6. What is the load factor of a hash table with

n

stored elements and table size

m

\alpha = m/n

Explanation

\alpha = n/m

Explanation

\alpha = n+m

Explanation

\alpha = n-m

Explanation

7. Which property is most desirable for a hash function used in a hash table?

a: It should map every key to index 0. Explanation

Explanation

b: It should preserve the alphabetical order of keys. Explanation

Explanation

c: It should distribute keys uniformly across the table. Explanation

Explanation

d: It should always produce a unique index for every possible key. Explanation

Explanation

8. Suppose the hash function is

h(k) = k \bmod 10

. What index is produced for the key

37

3

Explanation

7

Explanation

10

Explanation

37

Explanation

9. Why can a hash table have

O(n)

worst-case search time even though its expected search time is often

O(1)

a: Because a poor distribution of keys can cause many collisions. Explanation

Explanation

b: Because hash-table indices are always searched in sorted order. Explanation

Explanation

c: Because every hash-table operation must inspect all table positions. Explanation

Explanation

d: Because the table size is always equal to one. Explanation

Explanation

Hash Tables