Collision Resolution Techniques: Open Addressing, Chaining - Interactive Learning Quizzes

Question 1

In linear probing, if the initial probe encounters a collision, where does the search for an empty slot proceed?

Accepted Answer

To the next available slot in the hash table

Answer

To a random position in the hash table

Answer

To the position determined by the hash function

Answer

To the position with the highest load factor

Question 2

Under which condition is open addressing more memory-efficient than chaining in a hash table?

Accepted Answer

Low load factor

Answer

High load factor

Answer

Poorly implemented hash function

Answer

Array-based hash table implementation

Question 3

In open addressing, which probing technique employs a constant step size to locate an empty slot?

Accepted Answer

Linear probing

Answer

Quadratic probing

Answer

Double hashing

Answer

Robin Hood hashing

Question 4

Which of the following is NOT a disadvantage of open addressing?

Accepted Answer

Enhanced performance for sparsely populated tables

Answer

Increased search time for unsuccessful lookups

Answer

Space waste due to clustering

Answer

Potential for secondary clustering

Question 5

What is the fundamental distinction between linear probing and quadratic probing?

Accepted Answer

Linear probing uses a constant step size while quadratic probing uses a variable step size

Answer

Linear probing is generally faster than quadratic probing

Answer

Quadratic probing is more effective in handling collisions

Answer

Linear probing utilizes a hash function while quadratic probing does not

Question 6

In chaining, what data structure is used to store elements that collide at a particular slot in the hash table?

Accepted Answer

A linked list

Answer

An array

Answer

A binary search tree

Answer

A hash function

Question 7

In quadratic probing, what formula is used to determine the step size for the next probe?

Accepted Answer

h(key) + i^2

Answer

h(key) + i

Answer

h(key) * i

Answer

h(key) / i

Question 8

In chaining, how are collisions handled?

Accepted Answer

Storing colliding elements in a linked list or other data structure

Answer

Creating a new slot in the hash table

Answer

Replacing the existing element in the slot

Answer

Ignoring the collision

Question 9

Explain how the load factor of a hash table influences the efficiency of collision resolution techniques, considering the trade-offs involved in selecting an appropriate load factor.

Accepted Answer

Lower load factor increases collisions, diminishing performance.

Answer

Increased load factor reduces collisions, enhancing performance.

Answer

Load factor has no significant effect on collision resolution performance.

Question 10

Which of the following is NOT a potential limitation of linear probing as a collision resolution technique in hashing?

Accepted Answer

Guaranteed successful insertion even in a full table

Answer

Increased search time in the presence of clustering

Answer

Potential for primary clustering

Answer

Increased memory consumption

Question 11

When using quadratic probing, the increment added to the probe sequence follows which pattern?

Accepted Answer

Quadratically increasing

Answer

Constant

Answer

Linearly increasing

Answer

Randomly generated

Question 12

Which data structure is typically utilized in chaining as a collision resolution technique?

Accepted Answer

Linked list

Answer

Array

Answer

Stack

Answer

Queue

Question 13

In open addressing, the probe sequence is typically generated using:

Accepted Answer

A hash function

Answer

A random number generator

Answer

A linear search algorithm

Answer

A binary search algorithm

Question 14

Which search strategy is typically employed in conjunction with chaining?

Accepted Answer

Linear search

Answer

Binary search

Answer

Depth-first search

Answer

Breadth-first search

Question 15

As the load factor of a hash table using open addressing approaches 1, the average search time:

Accepted Answer

Increases quadratically

Answer

Remains constant

Answer

Increases linearly

Answer

Decreases exponentially

Question 16

In a hash table using quadratic probing, the probe sequence for a key with hash value 'h' is given by:

Accepted Answer

h, h + 2, h + 4, ...

Answer

h, h + 1, h + 2, ...

Answer

h + 1, h + 4, h + 9, ...

Answer

h + 1, h + 2, h + 4, ...

Question 17

Which of the following is a primary disadvantage of linear probing?

Accepted Answer

It suffers from primary clustering, leading to increased search and insertion times.

Answer

It requires additional memory for storing overflow records.

Answer

It is generally less efficient than chaining for resolving collisions.

Answer

It is only applicable to small hash tables.

Question 18

What is the key distinction between linear probing and quadratic probing in collision resolution?

Accepted Answer

Linear probing increments the probe sequence linearly, while quadratic probing increments it with a quadratic function.

Answer

Linear probing is always more efficient than quadratic probing.

Answer

Quadratic probing is always more efficient than linear probing.

Answer

Both linear and quadratic probing use the same probing sequence.

Question 19

Which of the following is a primary advantage of chaining in collision resolution?

Accepted Answer

It effectively eliminates primary clustering, resulting in more efficient search and insertion operations.

Answer

It is inherently more memory-efficient compared to open addressing techniques.

Answer

It consistently outperforms open addressing techniques in terms of efficiency.

Answer

It is significantly easier to implement than open addressing techniques.

Question 20

What is the load factor of a hash table defined as?

Accepted Answer

The ratio of the number of elements stored in the table to the total number of slots available.

Answer

The number of slots or buckets in the hash table.

Answer

The number of elements currently stored in the hash table.

Answer

The maximum number of elements that can be stored in the hash table without exceeding a certain threshold.

Question 21

Which of the following is not considered a collision resolution technique in hashing?

Accepted Answer

Binary search

Answer

Open addressing (linear probing, quadratic probing)

Answer

Chaining (linked lists)

Answer

Dynamic hashing (resizing the hash table)

Question 22

What is the worst-case time complexity of searching for an element in a hash table using linear probing?

Accepted Answer

O(n) - Linear time, proportional to the number of elements

Answer

O(1) - Constant time

Answer

O(n^2) - Quadratic time, proportional to the square of the number of elements

Answer

O(log n) - Logarithmic time, proportional to the logarithm of the number of elements

Question 23

Which of the following is a potential disadvantage of chaining in collision resolution?

Accepted Answer

It can lead to secondary clustering within individual chains, potentially impacting performance.

Answer

It requires additional memory for storing overflow records, similar to open addressing techniques.

Answer

It is inherently less efficient than open addressing techniques, regardless of the load factor.

Answer

It is only applicable to small hash tables and becomes impractical for larger datasets.

Question 24

What is the primary purpose of a hash function in the context of hashing?

Accepted Answer

To map input keys to unique slots or buckets within a hash table.

Answer

To generate random numbers for use in collision resolution.

Answer

To sort data elements based on their key values.

Answer

To compress data by reducing its size.

Question 25

What is an important consideration regarding the ideal load factor for a hash table?

Accepted Answer

It depends on the specific hash function and the desired performance characteristics.

Answer

A load factor of 0.5 is generally considered optimal for most applications.

Answer

A higher load factor (e.g., 0.75 or greater) always leads to better performance.

Answer

A lower load factor (e.g., 0.25 or less) is always preferable to avoid collisions.

Question 26

How does the load factor influence the selection of an appropriate collision resolution technique for a given data distribution?

Accepted Answer

The load factor affects the number of collisions, impacting the technique's effectiveness.

Answer

The load factor is only relevant for open addressing techniques.

Answer

The load factor is irrelevant in selecting a collision resolution technique.

Answer

The load factor is unrelated to data distribution and can be ignored.

Question 27

Which collision resolution technique uses open addressing, where items are stored directly in the hash table?

Accepted Answer

Linear probing

Answer

Double hashing

Answer

Chaining

Answer

Closed addressing

Question 28

In linear probing, if a collision occurs at the desired hash table location, what is the next action taken?

Accepted Answer

The probe moves linearly to the next available location in the hash table.

Answer

The probe moves randomly through the hash table.

Answer

The probe moves quadratically through the hash table.

Question 29

Which of the following is an advantage of quadratic probing over linear probing in collision resolution?

Accepted Answer

Reduced clustering of items, leading to improved performance.

Answer

Guaranteed resolution of all collisions.

Answer

Faster probe sequence, resulting in quicker search operations.

Answer

Improved cache locality, enhancing memory access efficiency.

Question 30

In chaining, collisions are resolved by creating what data structure at the point of collision?

Accepted Answer

A linked list

Answer

A binary search tree

Answer

A balanced tree

Answer

A separate hash table

Question 31

In chaining, which search strategy is typically employed to locate an item within a linked list created at the point of collision?

Accepted Answer

Linear search

Answer

Binary search

Answer

Interpolation search

Answer

Jump search

Question 32

Identify the simplest collision resolution technique in open addressing

Accepted Answer

Linear probing

Answer

Double hashing

Answer

Quadratic probing

Answer

Chaining

Question 33

In linear probing, when the desired location is occupied, how do you search for the next free location?

Accepted Answer

Using linear increments

Answer

Using quadratic increments

Answer

Using chaining

Answer

Using hashing

Question 34

In quadratic probing, which increments are used to search for the next free location?

Accepted Answer

Quadratic increments

Answer

Modulo-based increments

Answer

Hashing-based increments

Answer

Linear increments

Question 35

Compared to linear probing, quadratic probing offers the advantage of:

Accepted Answer

Reduced primary clustering

Answer

Improved insertion rate

Answer

Lower memory usage

Answer

Faster search time

Question 36

In chaining, what type of data structure do hash table entries point to?

Accepted Answer

Linked lists

Answer

Arrays

Answer

Hash tables

Answer

B-trees

Question 37

Identify a potential drawback of using chaining

Accepted Answer

Increased memory overhead

Answer

Primary clustering

Answer

Slower search time

Answer

Complex implementation

Question 38

In linear probing, the next available position for an element is determined by:

Accepted Answer

Incrementing the current index by a value of 1

Answer

Multiplying the current index by a constant value

Answer

Decrementing the current index by a value of 1

Answer

Adding a quadratic function to the current index

Question 39

In quadratic probing, the next available position for an element is determined by:

Accepted Answer

Applying a quadratic function to the current index

Answer

Applying a linear function to the current index

Answer

Subtracting a constant value from the current index

Answer

Multiplying the current index by a constant value

Question 40

When chaining is utilized in collision resolution, the elements that are inserted are commonly stored within:

Accepted Answer

Linked lists or binary search trees

Answer

Arrays or stacks

Answer

Queues or heaps

Question 41

Which statement regarding open addressing is incorrect?

Accepted Answer

Open addressing always exhibits better performance compared to chaining.

Answer

Open addressing is generally easier to implement than chaining.

Answer

Open addressing can lead to the formation of clusters of elements with adjacent keys (primary clustering).

Answer

Open addressing requires less space than chaining.

Question 42

In the context of collision resolution, which of the following is a real-world application of chaining?

Accepted Answer

Storing synonyms within a dictionary

Answer

Finding the shortest path in a graph

Answer

Maintaining a list of elements in sorted order.

Answer

Implementing a set of integers

Question 43

Which open addressing technique uses a probe distance that increases quadratically with each collision?

Accepted Answer

Quadratic probing

Answer

Chaining

Answer

Linear probing

Answer

Double hashing

Question 44

How does chaining resolve collisions in a hash table?

Accepted Answer

By storing colliding elements in a linked list associated with the corresponding hash table slot.

Answer

By using multiple hash functions.

Answer

By increasing the size of the hash table.

Answer

By probing to the next available slot in the hash table.

Question 45

When is linear probing typically less efficient than quadratic probing?

Accepted Answer

When the hash table has a high load factor.

Answer

When the load factor is less than 50%.

Answer

When the load factor is equal to 1.

Answer

When the load factor is low.

Question 46

Which of the following is NOT a benefit of open addressing?

Accepted Answer

It requires additional memory for collision resolution.

Answer

It can reduce memory overhead compared to chaining.

Answer

It can offer faster insertion and deletion operations.

Answer

It can improve locality of reference.

Question 47

What is a potential disadvantage of using chaining for collision resolution?

Accepted Answer

The possibility of long linked lists, which can increase search time.

Answer

Reduced search time compared to open addressing.

Answer

Improved memory utilization compared to open addressing.

Question 48

In open addressing, the sequence of probes for an empty slot is determined by:

Accepted Answer

The hash function used and the chosen collision resolution technique.

Answer

The size of the hash table.

Answer

The load factor of the hash table.

Question 49

What is a benefit of using chaining in collision resolution?

Accepted Answer

It can improve search performance for keys that hash to the same location.

Answer

It guarantees constant-time lookups for all keys.

Answer

It reduces memory overhead compared to open addressing.

Question 50

In quadratic probing, what is the formula for calculating the probe distance for the i-th collision?

Accepted Answer

i^2

Answer

i

Answer

i/2

Answer

2i