Read all questions before beginning. You will have until 1pm Monday to finish this exam.
You are not allowed to use the internet in general for this exam, only what
is linked from this page and the Java API.
You may use your text and course notes.
You are bound by the Honor Code for this exam, which you need to sign.
Show your work on all problems for full credit.
Turn a sheet with Q1-Q5, your
signature and the honor code for the whole exam.
Question 1
Draw the state of the memory in Java after executing the following commands with the ListNode
class. You should do this by hand, not using the computer to find the answer. Show the state after each
command for full credit.
ListNode front = new ListNode(4, null);
ListNode temp = front;
front = new ListNode(8, front);
front = new ListNode(16, front);
front.getNext().setNext(front.getNext());
front.getNext().getNext().getNext().getNext().setNext(new ListNode(23, null));
front.setNext(front.getNext().getNext());
temp.setNext(front);
front = temp;
Question 2
Use the following preorder and inorder traversal information to construct the correct binary tree.
(note this is not a binary search tree, just a binary tree)
- Preorder: 6 1 3 2 4 5 7 8
- Inorder: 1 6 4 2 7 5 8 3
Question 3
What will be the state of the BinarySearchTree below after
Question 4
What is the best way to order the following Strings for insertion into a BinarySearchTree if you want to minimize height?
- coking
- cohortial
- couplemer
- deabilidal
- curariorateure
- repleumorigibiliariter
- matrily
- demicalness
- mobilitize
- chasetation
- synthreak
- femiautile
- moduction
- urbortness
- unreling
Question 5
What data structure (Queue, Stack, List, BinarySearchTree) we discussed in class would be the most
efficient for you use in each situation below and why?
- A simulation of people entering and exiting a bank?
- Repeatedly looking up telephone numbers in a phone book?
- Tennis balls in a tennis ball can?