# Sample Final for Introduction to Computer Science II

The final exam will take place on THURS MAY 9 at 2:00 pm for all sections. Professor Berger's exam will be in room 101 WWH, Marateck's in rm 121/122 Meyer Bldg. It will be closed book closed notes. Here are some questions to prepare you for taking the exam.
1. Write a procedure that copies a linked list pointed to by List1 to another pointed to by List2 such that the nodes in the copied list are in the reverse order to those in the original list. You may assume that a class Stack exists with the following methods: push(x) , pop(), isFull() , and isEmpty() . The nodes of the list are defined by:

```class Node
{
int info;
Node next;
}
```

(b)What is the time analysis for this process?

2. (a) method Correct , shown below, is used to set the balance field for each node of a tree. This field is defined as the difference of the heights of the left and right subtrees for each node. Express the time analysis of this algorithm for a full tree of 15 nodes as a sum of the contributions of each generation. How does each generation's contribution compare approximately for large N? What is the time analysis in big Oh notation for this algorithm for a bushy tree of N nodes.

```class Treenode
{
int balance, info;
TreeNode left, right;
}

int max(int A, int B)
{
if( a > b)  return a;
else return b;
}

int height(TreeNode t )
/* pre: A tree exists and t originally points to the root.
post: the function returns the height of the tree.*/
{
if (T = null) return -1;
else return 1 + max(height(t.left), height(t.right))
}

void correct(TreeNode  t)
{
/* pre: a binary tree with a node definition that includes a balance field.
post: the balance field for each node is assigned. */
{
if( t != null)
{
correct(t.left);
t.balance = height(t.left) - height(t.right);
correct(t.right)
}
}
```
(b)What is the time analysis for this algorithm for a BST formed from a list of sorted numbers. (c) Rewrite function height as a method called setBalance so that it does not use method Correct and sets the balance field in O(n). Use the following heading: int setBalance(TreeNode t)

3. Draw a 2-3 tree for the following data: k, a, t, u, b, s, c, d, m, p, n

4. Draw a Huffman tree for the following sets of letters and frequencies: (H, 4), (G, 9), (B, 2), (A,11) Using this tree decode 100011?

5. Given an instance list of class Node, write a program segment that deletes the last node in the list. Use the following class:
```class   Node
{

char info;
Node next;
}
```
What is the the time analysis for this process in big Oh notation?

6. You are given an instance t of class Tree. Write a recursive method called delete that deletes all the nodes of a tree. Use the following class definition:
```class Tree
{
int info;
Tree   left, right;
}
```
what is the the time analysis for this process in big Oh notation?

7. Suppose that you have a complete tree described by the following class defininition, which is in heap form except for the info part of the root. Write a recursive routine that reheapifies it. You may use the heading void reheap(Heap tree, left, right)
```class Heap
{
int  info;
Heap  left, right;
}
```
What is the time analysis of this method in big Oh notation?