Microsoft Word – 3134midterm-spring2018-section2.docx
Room 417 IAB SEAT:____________
COMS W3134 Data Structures in Java – Section 2
Midterm Exam, Spring 2018
NAME:____________________
UNI:______________________
SECTION (1 or 2):__________
YOU MUST SIT IN THE SEAT DESIGNATED AT THE TOP OF THE EXAM. Failure to
do so may result in a failing grade.
There are 7 questions on this exam totaling 100 points. The exam is closed book and closed
notes. No calculators or computers are allowed. You will have 75 minutes to complete this
exam. Do not open this exam packet until instructed.
Print your name and UNI on the exam. Read and sign the academic honesty statement below.
Place all answers in this booklet. You may use the blank back of pages if you need additional
space.
Academic Honesty Statement:
I certify that I have neither given nor received unauthorized help on this exam and that I did not
use any notes, electronic devices, or other aids not specifically permitted. I will not discuss the
content of this exam with anyone who is not taking the midterm at this time. I understand that
any violation of this policy can result in an exam grade of zero and will be reported.
Signature:___________________________
DO NOT WRITE ON THIS PAGE!
Failure to comply will result in… well you know.
1 2 3 4 5 6 7 Total
1. (12 points total) Using induction, prove that the number of nodes, N, in a perfect binary
tree is odd.
2. (16 points total) Run times (for big-O costs, provide as tight a bound as you can get):
a. (12 points) Give the worst case big-O cost for the following algorithms or code
fragments:
i. (3 points) Pre-order traversal of a binary tree of N items.
ii. (3 points) Insert operation on a binary search tree.
iii. (3 points) Binary search on an array of length N.
iv. (3 points) N get operations on a java.util.LinkedList of length N.
b. (4 points) List the answers in part a from slowest growth rate to fastest growth
rate. If any have the same growth rate put them next to each other in the list and
circle them.
3. (17 points total) Expression Trees
a. (13 points) Given a mathematical expression in postfix notation (RPN) apply the
expression tree generation algorithm. Show the state of the stack at each step as
you process each token of the expression. Draw the final expression tree that is
popped off at the end.
8 2 / 5 4 * * 7 –
b. (4 points) Give an invalid postfix expression to be evaluated by the algorithm in
part a. Your example must result in tokens remaining on the stack at its
completion. (Note: You are only giving us the expression, you don’t have to run
through the algorithm.)
4. (10 points total) You are given both the post-order traversal and the in-order traversal for
a unique binary tree. Draw the corresponding tree and write down its pre-order traversal.
Post-order traversal: E D A C B F
In-order traversal: E A D F C B
5. (17 points total) Write a standalone recursive Java method, int countNodes(TreeNode
root) that, given a reference to the root node of a binary tree, returns the total number of
nodes in that tree. Assume a standard Binary TreeNode implementation with left child
and right child references.
int countNodes(TreeNode root) {
}
6. (17 points total) Imagine using a doubly linked list to implement the stack ADT for
values of type int. Skeleton code is provided below. Implement the push and pop
methods. Instead of using the methods of the List ADT, manipulate the nodes directly.
You have access to the head and tails nodes directly. This doubly linked list uses sentinel
nodes and you can assume that head and tail have already been initialized properly.
class LinkedListStack {
private static class Node {
public Node(int d, Node p, Node n) {
data = d; prev = p; next = n;
}
Node prev;
Node next;
int data;
}
Node head;
Node tail;
public push(int x) { // write this};
public int pop() { // write this};
}
7. (11 points total) Binary Search Trees:
a. (7 points) Starting with an empty Binary Search Tree, show the tree after
inserting each of the following values sequentially: 2, 4, 3, 7, 5, 8, 6.
b. (4 points) Take the tree resulting from part a and perform a full remove
operation on the value 4. When removing, you must pick your replacement from
the right subtree if there are two children. Draw the resulting tree.