CS 2401 Final Exam

Date: Dec 9, 2011.
Name: ____________________________________________

1. Write two methods to insert an element into a given position in a list of characters, one for a list implemented as an array and one for an implementation using a linked list. For example, insert(3, 'a') would insert the charater 'a' into position 3 in the list. Throw an exception for any invalid operations.

2. Write two methods for searching an array of integers: (1) an iterative implementation of sequential search and (2) a recursive implementation of binary search. Trace each method when looking for element 6 in the sorted list 1, 4, 8, 13, 25.

3. Answer the following short answer questions about binary and sequential search in an ordered list.
  1. What is the best, worst, and average number of elements that sequential and binary search will look at? Do NOT use big-oh notation, give exact values for a list with n elements.
  2. Briefly describe the advantages and disadvantages of the two search algorithms.
  3. Suppose you have an unsorted list and you want to find a single element in the list. Would it be faster to do a sequential search, or to first sort the list and then use binary search to find the element? Justify your answer.

4. Write a method that returns a new two-dimensional array of doubles with n rows and m columns (n and m are parameters of the method). Set each element of the matrix to a random double value between 0 and 1. What is the worst-case complexity of your method, using big-oh notation?

5. Write a recursive method to compute the power ab. Trace your code on the example of a = 5 and b = 3. Describe advantages and disadvantages of recursion vs. iteration in solving a problem, from the viewpoint of easiness to write, easiness to understand, and running time.

6. Rewrite the expression 2 * 5 - (3 + 1) 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.

7. Show, step by step, the state of a queue implemented as a 4-element array as we execute the following operations: enqueue R, enqueue B, dequeue, enqueue N, enqueue V, dequeue, enqueue Y. Write a method for enqueuing when the queue is represented as an array.

8. Answer the following questions about sorting.
  1. Show, step by step, how mergesort, quicksort, and heapsort will sort the following list of elements: 6, 3, 15, 9, 12, 1. For quicksort, use the first element of the array as the pivot.
  2. Write code for either selection sort or 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.

9. 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: 4, 2, 1, 8, 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?

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

11. For extra credit: Implement one of heapsort, mergesort, or quicksort.

12. For extra credit: Write a method to remove a given element from a binary search tree (you do not need to re-balance the tree).