Assigned April 14th 7pm
Due April 16th, 2pm
Read all questions before beginning. You will have 43 hours from when you begin this exam until
you must finish working.
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 the computer to compile and test
your Java code. You are bound by the Honor Code for this exam, which you need to sign.
Show your work on all problems for full credit.
Create a directory on the cs.centenary.edu server called exam2, and
copy your code there. Turn a sheet with Q1-Q5, your
signature and the honor code for the whole exam.
Question 1
Show the result of the partition method of quicksort on the following array, given bottom = 0 and top = 7:
[9, 3, 4, 6, 8, 1, 2, 5]
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 3 4 6 8 1 2 5
- Inorder: 3 9 8 6 2 1 5 4
Question 3
What will be the state of the BinarySearchTree below after
- Adding 5
- Removing 3
- Removing 7
Question 4
What is the best way to order the following Strings for insertion into a BinarySearchTree if you want to minimize height?
- keypads
- melon
- ergotic
- pilings
- purloined
- unclasping
- enricher
- apotheosized
- codeless
- cheesecake
- grayly
- parasang
- bright
- summerizes
- unscathed
- arbor
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?
Question 6
Dick Grune describes what he believes is the simplest sorting algorithm: Gnome Sort.
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.
Implement this algorithm as an inplace algorithm to sort an array of int in a method public static void gnomeSort(int[] data).
- What is the worst case time performance?
- What is the best case?
- What is the average case?
- Find one array where Gnome Sort performs better than Bubble Sort.