Exploring Hash Tables and Linked Lists

Which of the following is a common operation performed on a hash table?

• Sorting

• Insertion

• Merging

• Concatenation

Answer explanation

Insertion is a fundamental operation in hash tables, allowing new key-value pairs to be added. Unlike sorting, merging, or concatenation, which are not typical for hash tables, insertion is essential for their functionality.

What is the primary purpose of a hash function in a hash table?

• To encrypt data

• To sort data

• To map keys to indices

• To compress data

Answer explanation

The primary purpose of a hash function in a hash table is to map keys to indices. This allows for efficient data retrieval by converting keys into a format that can be used to quickly locate the corresponding values.

Which collision resolution technique involves placing all elements that hash to the same index into a linked list?

• Linear probing

• Quadratic probing

• Double hashing

• Chaining

Answer explanation

Chaining is a collision resolution technique where all elements that hash to the same index are stored in a linked list. This allows multiple entries to coexist at the same index without overwriting each other.

What is a key advantage of using a linked list over an array?

• Faster access time

• Dynamic size

• Easier sorting

• Less memory usage

Answer explanation

A key advantage of using a linked list over an array is its dynamic size. Linked lists can grow and shrink as needed, while arrays have a fixed size, making linked lists more flexible for varying data requirements.

Which type of linked list allows traversal in both directions?

• Singly linked list

• Circular linked list

• Doubly linked list

• Skip list

Answer explanation

A doubly linked list allows traversal in both directions because each node contains pointers to both the next and the previous nodes. In contrast, singly linked lists only allow traversal in one direction.

What is the main disadvantage of using open addressing for collision resolution in hash tables?

• Increased memory usage

• Slower search time

• Complexity in implementation

• Clustering

Answer explanation

The main disadvantage of open addressing is clustering, where groups of consecutive occupied slots form, leading to longer search times and increased collision chances. This can degrade performance significantly.

Which of the following is an application of hash tables?

• Implementing stacks

• Memory management

• Caching

• Sorting algorithms

Answer explanation

Caching is an application of hash tables as they allow for fast data retrieval by using keys to access values, making it efficient for storing frequently accessed data.

What is the time complexity of searching for an element in a hash table on average?

Answer explanation

The average time complexity for searching in a hash table is O(1) due to direct indexing using the hash function, allowing for constant time retrieval. This makes it efficient compared to O(n) or O(log n) in other data structures.

Which of the following is NOT a type of linked list?

• Singly linked list

• Doubly linked list

• Circular linked list

• Binary linked list

Answer explanation

A binary linked list is not a standard type of linked list. The common types are singly linked lists, doubly linked lists, and circular linked lists, which all have specific structures and functionalities.

What is a common use of a linked list in computer science?

• Implementing a queue

• Performing binary search

• Sorting data

• Compressing files

Answer explanation

A linked list is commonly used to implement a queue because it allows efficient insertion and deletion of elements at both ends, making it ideal for FIFO (First In, First Out) operations.