CMSC 341 Exam 2 Study Guide: Priority Queues and Data Structures
28 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

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?

    <p>To determine the priority of an element</p> Signup and view all the answers

    Which operation is supported by a priority queue?

    <p>Removal of elements in order of priority</p> Signup and view all the answers

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

    <p>To provide a unique identifier for a specific object</p> Signup and view all the answers

    What is the primary advantage of using Map ADTs?

    <p>It allows accessing information in O(1) time</p> Signup and view all the answers

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

    <p>To generate an index number for a bucket</p> Signup and view all the answers

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

    <p>Bucket array</p> Signup and view all the answers

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

    <p>5</p> Signup and view all the answers

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

    <p>The sum of the ASCII values of the word 'pumpkin'</p> Signup and view all the answers

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

    <p>0</p> 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?

    <p>It is merged with the leftover heap</p> Signup and view all the answers

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

    <p>0</p> Signup and view all the answers

    What is the main purpose of the Null Path Length (NPL) in a leftist heap?

    <p>To determine the shortest path to a null or leaf node</p> Signup and view all the answers

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

    <p>The two leftover heaps are merged</p> Signup and view all the answers

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

    <p>The structure of the heap itself</p> 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?

    <p>O(log n)</p> Signup and view all the answers

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

    <p>O(n)</p> Signup and view all the answers

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

    <p>O(1)</p> Signup and view all the answers

    What is a collision in a Hash Table?

    <p>When two different keys map onto the same hash value</p> Signup and view all the answers

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

    <p>Chaining</p> Signup and view all the answers

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

    <p>O(1)</p> Signup and view all the answers

    What is the purpose of probing in a hash table?

    <p>To handle collisions and find the next available index</p> Signup and view all the answers

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

    <p>It guarantees finding an empty cell using quadratic probing</p> Signup and view all the answers

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

    <p>It ensures that the divisor is not even</p> Signup and view all the answers

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

    <p>It affects the search pattern</p> Signup and view all the answers

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

    <p>When fast access is required</p> Signup and view all the answers

    More Like This

    Use Quizgecko on...
    Browser
    Browser