CSC234 - Exam 2

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-Q7, your signature and the honor code for the whole exam. You have until April 9 at 8:30am to complete 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<Integer> p = new ListNode<Integer>(4);
ListNode<Integer> q = new ListNode<Integer>(7, p);
p.setNext(q.getNext());
q.setNext(new ListNode<Integer>(2, new ListNode<Integer>(5)));
p.getNext().getNext().setNext(q.getNext());
q.getNext().setItem(9);

Question 2

Use the following preorder and inorder traversal information to construct the correct binary tree that holds Strings. (note this is not a binary search tree, just a binary tree)

Preorder: t, f, c, r, m, g, a, p
Inorder: f, t, m, r, g, c, a, p

Question 3

Draw the BinarySearchTree<Integer> below after removing the 5, following the remove operation as discussed in the text and in class for binary search trees. Describe this process in English in your own words.

Now, remove the root, and again, draw the resulting Binary Search tree.

Question 4

The following numbers are added to a Heap in the order given. Which number is the parent of 9?

[5, 7, 2, 4, 9, 13, 4, 5, 20, 8]

Question 5

What data structure (Queue, Stack, List, BinarySearchTree, Heap) we discussed in class would be the most efficient and closest match for you use in each situation below and why? What would you need to change to make it work?

Simulating people entering and exiting a grocery store?
Searching for dietary habits of lemurs on the internet?
Placing and firing bullets in a firearm magazine?
Triage management at a Emergency Room?

Question 6

Show the steps involved in the first pass of the QuickSort and BubbleSort algorithms on the following list of numbers. Describe this process in English in your own words.

[5, 7, 2, 4, 9, 13, 4, 5, 20, 8]

Question 7

Dick Grune claims that Gnome Sort is the simplest sorting algorithm. Analyze this algorithm for time efficiency using the tools we learned in class.