Final Exam Spring 2004. Key

1A		60
		  \
		  170
		 /   \
	   146   217
	   /
	 104
	 
B	GHAVANNLEIS

C	AVHNGELNSI

D	VANHELSING

E	0 0 2 2 4 4

F	5 4 3 2 1 0

G	0 2 1 2

H	O(log N)

I	O(log N)

J	O(1)

K	O(N), N = number of nodes in the tree

L	O(N^2)

M	O(N)

N	appropriate drawing

O	Answers varies but Big O had to match chosen data structure

P	63

Q	O(N^2)

R	1. all ops are O(1) for hashtable O(logN) for BST in ave case
	2. can use anything as keys for hashtable, but BST can only
	   use Comparables for keys

S.	5

T.	So that tha ArrayList can hold any type of Objects (all objects in Java are descendants of the Object class) and thus only have to create the ArrayList 1 time.

2.	
{	helper("", root);	}

private void helper(String code, HuffNode n)
{	//base case?
	if( n.getLeft() == null && n.getRight() == null )
		System.out.println( n.getChar() + " " + code);
	else
	{	helper(code + "0", n.getLeft() );
		helper(code + "1", n.getRight() );
	}
}

3A
private int iMySize;
private ArrayList myKeys;
private ArrayList myValues;

have two ArrayLists, 1 to hold keys, and the other to hold the values for those keys. The ArrayList that holds values will be an ArrayList of ArrayList with the element mapping to the ArrayList of keys. (Note, there are many other viable ways of implementing the Map with ArrayLists.)

3B	
int pos = myKeys.indexOf(key);
if( pos == -1)
{	myKeys.add(key);
	ArrayList temp = new ArrayList();
	temp.add(value);
	myValues.add(temp);
	iMySize++;
}
else
{	ArrayList temp = (ArrayList)(myValues.get(pos));
	int valPos = temp.indexOf(value);
	if(valPos == -1)
	{	temp.add(value);
		iMySize++;
	}
}
O(N + M/N)

3C
ArrayList result = new ArrayList();
int pos = myKeys.indexOf(key);
if(pos != -1)
{	ArrayList temp = (ArrayList)(myValues.get(pos));
	for(int i = 0; i < temp.size(); i++)
		result.add(temp.get(i));
}
return result;
O(N + M/N)

4A
int resuls = -1;
if( nodeNum >= 0 && nodeNum < g.numNodes() )
{	for(int i = 0; i < g.numNodes(); i++)
	{	if( g.linkeExists(nodeNum, i)
		{	result++;
		}
	}
}
return result;

4B
ArrayList result = new ArrayList;
int max = 0;
int numLinks;
for(int i = 0; i < g.numNodes(); i++)
{	numLinks = numDirectLinks(g, i);
	if(numLinks == max)
		result.add(new Integer(i));
	else if( numLinks > max )
	{	max = numLinks;
		result.clear();
		result.add(new Integer(i));
	}
}
return result;