CS 2401 Final Exam

Date: August 6, 2012
Name: ____________________________________________

1. Rewrite the expression 8 * 6 - (20 + 12) using postfix notation. Show, step by step, how a stack can be used to compute the value of the resulting expression. Briefly describe why a stack is different from a list.

2. Suppose you start with an empty AVL-balanced binary search tree.

  1. Show, step by step, what will happen if we add the following elements to an AVL-balanced binary search tree: 8, 20, 12, 6. Don't forget to balance at each step when necessary.
  2. Show how the resulting tree will look in both a reference-based and an array-based implementation of trees.
  3. Why is balancing necessary in a binary search tree?

3. Answer the following questions about sorting.

  1. Show, step by step, how mergesort, quicksort, and heapsort will sort the following list of elements: 8, 6, 20, 12.
  2. Write code for bubble sort.
  3. Draw a table showing the worst and average-case complexity for bubble, insertion, selection, merge, quick, and heap sort using big-oh notation.

4. Suppose you have implemented a hash table as an array of linked lists, with an array of size 4. As the hash function, use modulo 4, so h(n) = n % 4. Show how this hash table will look after inserting the following elements: 8, 6, 20, and 12. What are the main advantages and disadvantages of hash tables?

5. Write two methods for searching an array of integers: (1) sequential search and (2) binary search. Trace each method when looking for element 6 in the list obtained by sorting the values 8, 20, 12, and 6. What are advantages and disadvantages of sequential search and binary search? Why do we need to sort lists in the first place?

6. The Olympic results are given in a table, where each row represents a country, and columns represent gold, silver, and bronze medals. For example, the element r[0][0] is the number of gold medals earned by the 0-th country. Write a method that takes the table as an input, and returns a new array which lists the total number of medals for each country. For example, if we start with the table

     2   0   1
     3   2   0
     0   0   2
in which the 0-th country earned 2 + 0 + 1 = 3 medals, the 1-st country earned 3 + 2 + 0 = 5 medals, and the 2nd country earned 0 + 0 + 2 = 2 medals, your method should return an array with values
   3
   5
   2

7. Write a recursive method for computing the sum of all the elements of an array. Start with an algorithm in English, then translate this algorithm into code. Trace your method on the example of the following array with 3 elements: 2, 0, and 1.

8. Let us assume that a queue is implemented as an array of size 5. Show, step-by-step, what will happen if first tourists A, B, C, and D join the queue, then A gets a ticket, then B gets a ticket, and then E and F join the queue. Write Java methods for enqueue and dequeue when a queue is implemented as an array.