Read all questions before beginning.
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. You have 1 hour for this 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(7, null);
ListNode temp = front;
front = new ListNode(8, temp);
ListNode wahoo = new ListNode(5, temp);
wahoo.getNext().setNext(wahoo);
front.getNext().getNext().getNext().getNext().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: 9, 2, 5, 17, 1, 3, 12, 4
- Inorder: 2, 9, 1, 17, 3, 5, 12, 4
Question 3
Assuming alphabetical ordering, what is the best way to add the following Strings into a BinarySearchTree if you want to minimize height?
- spirity
- congs
- rawmiluthol
- decrose
- anago
- leaserted
- overnism
- olistiform
- farcham
- typefuelliber
- plexualism
- locyclear
- navictrockagery
- mifindelucket
- debirtify
Question 4
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?
- Simulating people entering and exiting a grocery store?
- Searching for lemurs in Google?
- Storing plates in the Caf?
Question 5
Gnome Sort is based on the technique used by Dutch Garden Gnomes (Du.: tuinkabouter). Here is how a
garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the
previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and
steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if
there is no pot next to him, he is done. —Dick Grune
Write a method in Java to implement Gnome Sort.
What is the algorithmic complexity of Gnome sort in the best case and worst case scenarios?