The final will be on Thursday, December 16. It will last 2 hours, from 9 until 11.
You should know the material presented in lecture and in the assigned readings. You are responsible for everything up to and including the material covered on Tuesday, Dec. 7. The main topics we covered were: arrays, stack, queues, linked lists, searching, sorting, recursion, tress, graphs and hashing.
I will not try to pick some small detail out of the reading and test you on it.
1. Consider the following binary tree.
a
/ \
b c
/ \ \
d e f
/ \
g h
Which of the following might be the output of a postorder traversal
of this tree ?
a. dghebafc
b. dgehbfca
c. dghebfca
d. dbgehafc
e. dbgehfca
2. Here is the adjacency matrix A of a weighted undirected graph. Assume
the vertices are $v sub 1, v sub 2, v sub 3, v sub 4, and v sub 5$ and that
position (i,j) in the matrix corresponds to edge ($v sub i, v sub j$).
0 3 6 2 4
3 0 2 0 4
A = 6 2 0 0 1
2 0 0 0 7
4 4 1 7 0
a. Draw a picture of this graph.
b. Give a breadth first search of the graph starting at vertex $V sub 2$.
c. Find the length of the shortest path from vertex 2 to vertex 5
in this graph.
3. What is output ?
#define SIZE 4
int WhatIsThis (int [], int);
void main( void )
{
int a[SIZE]={1,2, 3, 4};
cout << "\nThe result is: " << WhatIsThis(a, SIZE)) < endl;
}
int WhatIsThis (int b[], int num)
{
if (num == 1)
return b[0];
else
return b[num -1] + WhatIsThis(b, num - 1);
}
4. Draw a binary tree corresponding to the arithmetic expression
(2+3)/2*(4/12)-6.
Write is the prefix expression gotten from preorder traversal of this tree ?
5. a. Construct a heap with the following keys.
2,6,4,12,57,1,5
b. Now carry out the first step of heapsort.
What element of the tree is outputted ?
What heap results after this first element is output and the
heap is rebuilt ?
6. Assume we have a hash table of size 7 and you use the following hash
function. h(k) = (2k+1) % 7
For collision resolution you use the standard open addressing collision resolution
method where the increment is given by P(k) = max (1, k/7 mod 7).
a. Draw a picture of the hash table and show how it gets filled as you
add the keys 12, 7, 18, 2, 11 .
b. Assume some time later the hash table looks like :
16 7 18 11 12 2 e
(e = empty)
Now you search for the keys 16, 17 and 18. How many probes are needed for these
three key searches.
-----------------------
Some answers:
1. c
2b. 2,1,4,5,3 (among others)
2c. Shortest ath has length 3
3. Output is ,
The result is: 10
5. Prefix expression is - * / + 2 3 2 / 4 12 - 6
6. a Table looks like: e 7 18 11 12 2 e
(Here e = empty)
b. 18 takes 1 probe
17 takes 4 probes
16 takes 2 probes