28 Questions
What is the primary characteristic of a priority queue?
It stores a collection of prioritized elements
What determines the priority of an element in a priority queue?
The key associated with the element
Which of the following scenarios is an example of a priority queue?
An emergency room
What is the purpose of a key in a priority queue?
To determine the priority of an element
Which operation is supported by a priority queue?
Removal of elements in order of priority
What is the purpose of a key in a data storage system?
To provide a unique identifier for a specific object
What is the primary advantage of using Map ADTs?
It allows accessing information in O(1) time
What is the purpose of a hash function in a hash table?
To generate an index number for a bucket
What is the component of a hash table that stores the actual data?
Bucket array
What is the result of the calculation 772%13 in the hash function example?
5
What is the input to the hash function in the example given?
The sum of the ASCII values of the word 'pumpkin'
What is the Null Path Length (NPL) of a leaf node in a leftist heap?
0
What happens when the left child of the new root is 'hanged up' in the merge operation of two leftist heaps?
It is merged with the leftover heap
What is the Null Path Length (NPL) of a node with one child in a leftist heap?
0
What is the main purpose of the Null Path Length (NPL) in a leftist heap?
To determine the shortest path to a null or leaf node
What happens when the root node is removed in a leftist heap deletion operation?
The two leftover heaps are merged
What is the primary difference between a leftist heap and a skew heap?
The structure of the heap itself
What is the time complexity of searching for a specific item in a Binary Search Tree in the worst case?
O(log n)
In an array, what is the time complexity of traversing through the items sequentially?
O(n)
What is the time complexity of accessing data points using index numbers?
O(1)
What is a collision in a Hash Table?
When two different keys map onto the same hash value
What is one of the solutions to collisions in a Hash Table?
Chaining
What is the time complexity of insertion in a linked list?
O(1)
What is the purpose of probing in a hash table?
To handle collisions and find the next available index
What is the benefit of keeping a hash table less than half full?
It guarantees finding an empty cell using quadratic probing
What is the advantage of using an odd divisor in a hash table?
It ensures that the divisor is not even
What is the problem with deleting entries from a hash table using open addressing?
It affects the search pattern
When is it a good idea to use a hash table?
When fast access is required
Review priority queues, heaps, maps, and hash tables, including chaining and collisions, as well as AVL trees. This study guide covers key concepts for the CMSC 341 Exam 2. Test your understanding of these data structures and their applications.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free