CMSC 341 Exam 2 Study Guide: Priority Queues and Data Structures

Play an AI-generated podcast conversation about this lesson

What is the primary characteristic of a priority queue?

It only supports insertion and removal of elements at the beginning
It is a type of stack data structure
It stores a collection of prioritized elements (correct)
It follows the First-In-First-Out (FIFO) principle

What determines the priority of an element in a priority queue?

The type of the element
The key associated with the element (correct)
The order of insertion
The size of the element

Which of the following scenarios is an example of a priority queue?

A line of people waiting for a movie
A stack of books
An emergency room (correct)
A set of identical twins

What is the purpose of a key in a priority queue?

To determine the priority of an element (D) Signup and view all the answers

Which operation is supported by a priority queue?

Removal of elements in order of priority (D) Signup and view all the answers

What is the purpose of a key in a data storage system?

To provide a unique identifier for a specific object (B) Signup and view all the answers

What is the primary advantage of using Map ADTs?

It allows accessing information in O(1) time (A) Signup and view all the answers

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

To generate an index number for a bucket (A) Signup and view all the answers

What is the component of a hash table that stores the actual data?

Bucket array (D) Signup and view all the answers

What is the result of the calculation 772%13 in the hash function example?

5 (D) Signup and view all the answers

What is the input to the hash function in the example given?

The sum of the ASCII values of the word 'pumpkin' (B) Signup and view all the answers

What is the Null Path Length (NPL) of a leaf node in a leftist heap?

0 (B) Signup and view all the answers

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 (D) Signup and view all the answers

What is the Null Path Length (NPL) of a node with one child in a leftist heap?

0 (D) Signup and view all the answers

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 (D) Signup and view all the answers

What happens when the root node is removed in a leftist heap deletion operation?

The two leftover heaps are merged (C) Signup and view all the answers

What is the primary difference between a leftist heap and a skew heap?

The structure of the heap itself (C) Signup and view all the answers

What is the time complexity of searching for a specific item in a Binary Search Tree in the worst case?

O(log n) (D) Signup and view all the answers

In an array, what is the time complexity of traversing through the items sequentially?

O(n) (A) Signup and view all the answers

What is the time complexity of accessing data points using index numbers?

O(1) (B) Signup and view all the answers

What is a collision in a Hash Table?

When two different keys map onto the same hash value (C) Signup and view all the answers

What is one of the solutions to collisions in a Hash Table?

Chaining (A) Signup and view all the answers

What is the time complexity of insertion in a linked list?

O(1) (C) Signup and view all the answers

What is the purpose of probing in a hash table?

To handle collisions and find the next available index (C) Signup and view all the answers

What is the benefit of keeping a hash table less than half full?

It guarantees finding an empty cell using quadratic probing (B) Signup and view all the answers

What is the advantage of using an odd divisor in a hash table?

It ensures that the divisor is not even (D) Signup and view all the answers

What is the problem with deleting entries from a hash table using open addressing?

It affects the search pattern (C) Signup and view all the answers

When is it a good idea to use a hash table?

When fast access is required (A) Signup and view all the answers