## 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.

```

```
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.

```

```
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.

```

```
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).