Fall 2000 PIC 10b Practice Final

The final is Sunday, Dec 10 3-6pm in Moore 100.

The real final will have seven problems of equal value and should be about
the same difficulty. One problem from the practice final is guaranteed
to be on the actual final.

1. Define the following terms:
    (a) FILO
    (b) tail recursion
    (c) memoization
    (d) external node
    (e) adaptive sorting

2. Write a function with prototype: 

       template<class Item>
       Node<Item>* reverse(Node<Item>* list);

   to reverse a linked-list where the Node's
   class is:

       template <class Item>	
       class Node
       {
	  public:
	    Node(Item i, Node* n){item=i; next=n;}

 	    void setItem(Item i){item =i;}
            void setNext(Node* n){next=n;}

	    Item getItem(){return item;}
	    Node* getNext(){return next;}
	
          private:
	    Item item;
	    Node* next;	
       };

3.  Briefly explain why the first version of insertion sort we described
    in class was non-adaptive and why it runs in time O(N2)
    if N items are to be sorted.

4. Consider the following tree:

	           a
                  / \
                 h   p1
                    / \
                   p2  y

   Write out the nodes in the order they would be visited if one did a
   (a) a preorder traversal, (b) an inorder traversal, (c) postorder traversal,
   and (d) a level order traversal.

5. Let the node's for a binary tree be given by the struct:
 
   struct node { int item; node *l, *r;};
   typedef node *link; 


   Write a recursive function  with prototype:
   
	int exNodeCount(link h);

   to compute the number of external nodes in the tree pointed to by h.

6. A palindrome is a string that is spelled the same forwards and backwards.
   For example, "bob" and "abba" are palindromes but toy in not since "toy"
   spelled backwards is "yot". Describe an algorithm in English or C++ that
   uses a stack to check if a word is a palindrome. You can assume you are
   told in advance the length of the word.

7. Write a divide and conquer program with prototype

   int min(int a[], int l, int r)

   to return the minimum value stored in a[] for indices between and
   including l and r. 

8. Explain how a Queue ADT works and give an example of where one would
   use a Queue.

9. Explain using words and diagrams the intermediate steps that a mergesort
   algorithm would go through in sorting:

       2 7 4 8 1 5 


10. Suppose the following keys 7,2,4,3,5 are inserted into a hash table
    of size 5 with hash function x%5 where collisions are resolved using
    linear probing. Write out the resulting hash table.