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):
- (12 points) Give the worst case big-O cost for the following algorithms or code fragments:
- (3 points) Pre-order traversal of a binary tree of N items.
- (3 points) Insert operation on a binary search tree.
- (3 points) Binary search on an array of length N.
- (3 points) N get operations on a java.util.LinkedList of length N.
- (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.