In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4.

You should be able to define or explain the following terms:

• Priority queue
• Binary heap and the heap operations
• Complete binary trees and their array-based representation
• The heap-order property
• Sorting with a heap
• The Dictionary abstract data type
• Hash tables, hash functions, hash code, a hash table's load factor
• Linear chaining and linear probing

You should be familiar with the following C++-related concepts:

• getline
• tolower
• copy constructors
• references (at least how to recognize them...)
• operator[]

Practice problems

1. For each of the code fragments below, draw the BinaryHeap that results from the code fragment, and draw its final array-based representation:

   1.   BinaryHeap<int,int> heap;
        for (int i = 1; i <= 10; ++i) {
          heap.insert(i,i);
        }
        for (int i = 1; i <= 5; ++i) {
          heap.removeMin();
        }
      

   2.   BinaryHeap<int,int> heap;
        for (int i = 10; i > 0; --i) {
          heap.insert(i,i);
        }
      

   3.   BinaryHeap<int,int> heap;
        for (int i = 1; i <= 5; ++i) {
          heap.insert(i,i);
          heap.insert(-1*i,-1*i);
        }
      

2. What is the worst-case running time of the following function? Use Big-O notation.

     void f(int n) {
       if (n < 0) {
         return;
       }
       BinaryHeap<int,int> heap;
       for (int i = 0; i < n; ++i) {
         heap.insert(i,i);
       }
       for (int i = 0; i < n; ++i) {
         cout << heap.removeMin() << endl;
       }
     }
   

3. Using linear chaining to resolve hash collisions, insert the following five items into a hash table of capacity 5, in the order given (from top to bottom):

   Key	Hash code
   A	1
   B	1
   C	1
   D	0
   E	2

4. Repeat #3 using linear probing to resolve hash collisions, instead of chaining.
5. Consider the following hash function, like the function in hashtable.inl:

     int hash(int key, int capacity) {
       return key % capacity;
     }
   

   Assuming that the hash table does not resize, complete the following code so that the total running time is asymptotically proportional to n^2:

     void f(int n) {
       HashTable<int,string> ht(n);  // Creates hash table with capacity n.
       for (int i = 0; i < n; ++i) {
   
         ht.insert(________________, "skittles");
       }
     }
   

Home Page