The notes below are essentially a version of the actual quiz in which the critical details that will appear on the actual quiz have been omitted. This should help you prepare. Omissions are denoted by question marks, etc. Please do not write me to clarify what I've left out. I'm giving you a lot here! If you have questions, just study your textbook and make up some examples and work through them until you're comfortable that you know how the code works and how it relates to the trees and/or arrays.

• DURATION: ONE HALF HOUR (1/2 HOUR)
• This is a closed-book, no calculators exam.
• It is more important that you do some work on each problem than it is to do one very well and do nothing on the other.
• Show your work.
• In both questions below, be sure that your detailed line-by-line analysis is consistent with your intuition about what moves are made in the tree and what result you'd expect just by knowing how the algorithms behave, without referring to the code. In other words, does it agree with your common sense about these algorithms?

Question 1.This question deals with a heap (not a binary search tree!). Below, you are given code and you are to explain how it operates for a specific case.

1. Your are to begin with the heap shown below . Draw and fill in the array corresponding to the heap.
   < A PICTURE OF A HEAP WILL APPEAR HERE.>
2. Assume you are to insert a new item with key ??, or remove the maximum item using this code:
   CODE HERE
3. The critical lines in the ??() code below are numbered ??.
   CODE FOR FIXUP OR FIXDOWN HERE
4. The while loop in ??() is executed a number of times to accomplish the insert or remove.
5. For each of the times the while loop executes, show the following pieces of information:
   • The value of ?? that allows the test to succeed ....
   • The values in line ?? that are reset, etc..
   • ... and so forth.
6. What is the value of ?? that finally leads to the while condition failing and to the termination of the loop?

Question 2. This question deals with a binary search tree (BST) (not a heap!). It proceeds in much the same way that Question 1 did, in which you are given code and you are to explain how it operates for a specific case.

1. Your are to begin with the BST shown below.
   < A PICTURE OF A BST WILL APPEAR HERE.>
2. Assume you are to insert a new item with key ??, using this code:
   

   
   void insert(Item x)
     { Key v = x.key();
       if (head == 0) 
         { head = new node(x); return; }
       link p = head;
      L1: for (link q = p; q != 0; p = q ? q : p)
       L2:  q = (v < q->item.key()) ? q->l : q->r; 
       L3:if (v < p->item.key()) p->l = new node(x); 
                         else p->r = new node(x);
     }
   
   

3. The three critical pieces in the insert() code above are numbered.
4. The for loop in insert() is executed a number of times to accomplish the insert of the item ??.
5. For each of the times the for loop executes, show the following three pieces of information:
   • The value of ?? and the ?? update. You can show this by drawing a small part of the BST and showing which pointers correspond to p and q.
   • The values of ?? that lead to the conditional being true or false (say which it is) in L2.
   • What link is reached that eventually causes the for loop to terminate?
   • Once the for loop is terminated, what is the value of the boolean conditional in the if statement in L2 and which of the two new node assignment statements is done?
   • Where is the final position of the new node? Draw the finished tree with the new node in the correct place.