Virtual Labs

1. Which of the following is the standard linear probing function?

F(i)=1

Explanation

F(i)=i

Explanation

F(i)=i^2

Explanation

F(i)=i+1

Explanation

2. In linear probing, which expression represents the probe position after a collision?

H(x)=key\bmod table\ size

Explanation

H(x)=(key+F(i^2))\bmod table\ size

Explanation

H(x)=(key+F(i))\bmod table\ size

Explanation

H(x)=(key+F(i^3))\bmod table\ size

Explanation

3. What does linear probing do when the initially computed slot is occupied?

a: Checks the next table slot sequentially. Explanation

Explanation

b: Creates a new hash table. Explanation

Explanation

c: Deletes the existing element. Explanation

Explanation

d: Stops the insertion permanently. Explanation

Explanation

4. Which type of clustering is particularly associated with linear probing?

a: Secondary clustering only Explanation

Explanation

b: Primary clustering Explanation

Explanation

c: Tree clustering Explanation

Explanation

d: No clustering Explanation

Explanation

5. If

h(k)=k\bmod10

and linear probing is used, what is the initial index for key

37

3

Explanation

7

Explanation

10

Explanation

37

Explanation

6. What is the average-case search complexity of linear probing when the load factor is kept suitably low and the hash function distributes keys well?

O(n^2)

Explanation

O(n)

Explanation

O(\log n)

Explanation

O(1)

Explanation

7. Suppose a table has size

10

and

h(k)=k\bmod10

. If index 4 is occupied, which index is checked next by linear probing?

3

Explanation

4

Explanation

5

Explanation

8

Explanation

8. Why can linear probing become inefficient when the load factor becomes high?

a: It causes all keys to be deleted. Explanation

Explanation

b: Longer clusters and probe sequences become more likely. Explanation

Explanation

c: The hash function stops accepting integer keys. Explanation

Explanation

d: The table automatically becomes sorted. Explanation

Explanation

9. Which statement correctly describes the worst-case behavior of linear probing?

a: Search always takes

O(1)

time. Explanation

Explanation

b: Search always takes

O(\log n)

time. Explanation

Explanation

c: Search can take

O(n)

time when many positions must be examined. Explanation

Explanation

d: Search always takes

O(n^2)

time. Explanation

Explanation

Hash Tables