CSE326 Midterm Exam #1
July 9, 2004
Each part of each problem is worth 4 points except where noted
1. In a binary tree, "full nodes" are those with two children.
A. What is the relationship between the number of
full nodes and the number of leaves in a binary tree? Iluustrate
with a couple of examples.
B. Now prove your answer with a careful proof.by induction.
2. Let f and g be functions, and suppose that for every n>1, it
is true that f(n) < g(n). Clearly f(n) = O(g(n)).
Is it also possible that g(n) = O(f(n))? Explain.
3. Suppose the time complexity function of an algorithm is approximated at 5*2N.
The algorithm is programmed and timed to run for about 5 seconds when N
= 10. Given just this information, estimate how long it would
take to run when N = 20.
4. Each of the following functions is defined at least for values of n
>= 2. Give a big-Theta bound for each of these
functions. You do not need to explain your answer. (2 pts. each)
f(n) = n * (n % 7)
f(n) = n % (n - 1)
f(n) = (n * n) % (n + 1)
5. Outline the steps to solve
this problem using the classes,
interfaces, and methods of the Java Collections framework. Give
code that is pretty close to real, compilable Java if possible (without
taking too much of your valuable time!).
John and Brenda each have a list of all the books they own.
A. Print out all the books owned by either of them (listing each book only once), and then
B. print out only the books they both own.
6. Given an initially empty stack S of characters, what is on the stack
after these operations have completed? (For possible partial
credit, show your work).
S.push('s');
S.push('t');
S.push('u');
char ch = S.pop();
ch = S.pop();
S.push('v');
S.push(ch);
S.push('w');
ch = S.pop();
7. Given an initially empty queue Q of characters, what is in the queue
after these operations have completed? (For possible partial
credit, show your work).
Q.enqueue('s');
Q.enqueue('t');
Q.enqueue('u');
char ch = Q.dequeue();
ch = Q.dequeue();
Q.enqueue('v');
Q.enqueue(ch);
Q.enqueue('w');
ch = Q.dequeue();
8. Think about the stack-based algorithm for evaluating post-fix
expressions. (You can assume, if it helps, that all the
operations are binary, left-associative).
A. In terms of that algorithm, how do you determine whether a given
expression is a valid postfix expression? (For example, A B + is
valid but Z + Y is not).
B. Give an algorithm for determining if a given expression is valid
postfix or not. Do not use a stack (do something simpler if possible).
9. There is a stack-based algorithm for converting in-fix expressions into
postfix. Show how this works, by showing the state of the stack
and the output at each
step during the conversion of this expression. You can do this by
crossing out old values if you are neat and clear about it; otherwise,
redraw the stack at each stage.
A * (B + C / D) + E
10. Suppose you are told that A B C D is the pre-order traversal of a
binary tree, and that A B C D is also the in-order traversal of
the same tree! Either give a tree which satisfies this, or
explain why it is not possible.
11. Draw the tree resulting from inserting the following values into an initially empty binary search tree:
5 10 20 3 7 4 1 6 11 19
12. Give worst-case and
average-case bounds (big-Theta if possible, otherwise just big-O) for
the time of each of the following, assuming a reasonable implementation
(2 pts. each):
A. Insertion into a queue (array-based implementation)
B. Deletion from a binary search tree
C. Finding the max value in a binary search tree
D. Deletion from a list (linked-list implementation)
E. Insertion in a list at given position (array-based implementation)
13. In this problem, we deal exclusively with binary trees of
integers. It might help you to think of these integers as
weights, and to think of the tree like an Alexander Calder mobile with
objects of different weights dangling from it.
Define a node
to be "weight-balanced" if the sum of all the weights (i.e., the integer values)
in the left
subtree is equal to the sum of all the weights in the right
subtree. Note that with this definition, every leaf node is
weight-balanced.
A (2 pts.) Give an exmple of a tree (with 4 or more nodes) whose
root is weight-balanced but where no other non-leaf nodes are
weight-balanced.
B. (2 pts.) Give an example of a tree (with 4 or more nodes) in which every node is weight-balanced.
C. (2 pts.) Give an example of a binary search tree (with 4 or more nodes) in which the root is weight-balanced.
D. (8 pts.) Implement the following method in Java:
/** Return true iff the node is weight-balanced or is null.*.
boolean checkBalance(BinTreeNode node);
Use this class definition:
public class BinTreeNode {
Object element;
BinTreeNode left;
BinTreeNode right;
}
Your are free to write helper methods if you wish.
E. Give a bound for the running time of your algorithm (2 pts.)