CSC 16 : Final Exam Study Guide.


The final exam will be comprehensive, but with emphasis on the material 
covered after the first exam.

Topics to study:

  Old topics:

     Usage of pointers, stack and heap allocation.

     Basic operations on linked lists: length, sum, insert, delete, etc ...
       (only one question of this form).

     Recursion with lists.

     oop versus static style.

     **Binary search and quicksort algorithms and their advantages.
          (not the implementation, just algorithm)

  New Topics:

     The use of stacks.  push/pop/peek.

     Binary trees and search trees:

       Basic class definition.

       Basic operations such as "size", "depth", "sum", 
       pre/in/post-order traversal, etc ...
   
       For binary search trees, study how to lookup and insert (one
       of these will be on the test).
       
       ** Checking if a structure is indeed a binary search tree **

       Understand when recursion is really needed and when it's not.

       You don't have to write the code for deleting a node from a 
       tree, but you need to UNDERSTAND THE ALGORITHM.  I may ask you
       for example, to draw a tree before and after a node has been deleted.


    Hash Tables: understand the difference between open and closed hashing
         algorithms.

         Understand what makes a good hash function.

    Polymorphic classes such as cell<T>

         Understand when a method can be considered "naturally polymorphic".
         Study the sample programs on open hash tables, stacks, and lab12.

	 What is an abstract class?




-------------------
Practice Problems, sample solutions to be posted.
-------------------


Given :

class node
{ int head;
  node left, right;
  public node(int h, node l, node r) {head=h; left=l; right=r;}
...

1. Write a function that returns the smallest integer in a tree
   (not binary search tree).


2. Write a function that returns the smallest integer in a binary
   SEARCH tree.  Do NOT use recursion.


3. Explain the effect on tree A of the following code (draw a diagram)

   node A = new node(3, new node(2,null,null), null);
   node i = A.right;
   i = new node(4,null,null);

   (be careful - i is a pointer, and where is it pointing to?)

4. Implement the insert function for binary search trees:

   public void insert(int x)
   { ...


5. Given the following tree:

      9
    /   \
   5     10
  / \     \ 
 3   7     11
    / \
   6   8

Determine the order in which the nodes will be printed using a 

preorder:

inorder:

postorder traversal (post order is right-left-head).


6. The tree in problem 5 is a binary search tree.  Draw the tree after the
   root (9) is deleted.


7. Explain the purpose of the "Deleted" array in a closed hash table.  That
   is, why is it necessary to distinguish between a slot that was never
   occupied and a slot that's empty but was previously occupied.  


8. Consider the following functions on binary trees (not nessarily search trees).  
   Which of the following functions are "naturally polymorphic", and which
   will require abstraction (in the form of abstract classes and dynamic
   dispatch).  That is, assume that the node class has been parameterized.

   class node<T>
   { T head;
     node<T> left, right;
     ...
   }

   size:  find the number of nodes in a tree.

   depth: find the length of the longest branch.

   max  : find the largest element in a general binary tree.

   smax : find the largest element in binary SEARCH tree (think!).

   
9. A tree is called "normal" if every node is either null or has both
   non-null left and right branches.  In other words, either both left and
   right are null or neither are null.  Write a procedure that checks for
   this property.

   Is this function naturally polymorphic?


10. The binary search algorithm works well with a sorted array, and with
    binary search trees.  Explain why it doesn't work with sorted linked 
    lists.



(more may be added later ...)

11.  Consider the polymorphic cell class

class cell<A>
{
  A head;
  cell<A> tail;
  cell(A h, cell<A> t) {head=h;  tail=t; } 
  ...
}


11a.  Write code to use this class to construct a list of 2 Integers.

11b.  Write a procedure within the class to find and return the middle
      cell of the list (this is naturally polymorphic because you
      never have to consider the head).  That is, if there are 5 elements,
      return the 3rd element.  If there are 8 elements, return the 5th
      element (the one slightly to the right of center). 
      Naturally you'll need to find the length first.