CS 117, Spring 2003, Exam #2 (100 points)	Name:_____________________________

1. (20 points) You need to store a list of names that changes on a regular basis, such as in a telephone directory. Suppose that you decide to store the names in an array of Strings that is as big as you will ever need, i.e. the array has lots of blank space at the end. Assume that there are 100 names currently in the array.

Suppose that you decide to store the names in sorted order.
(a) Would you use sequential or binary search on this array to look up a name?

(b) In the worst case, approximately how many comparisons will it take to look up a particular name?

(c) In the worst case, approximately how many assignments will it take to insert a new name (assuming you have already figured out where it needs to go)?

(d) In the worst case, approximately how many assignments will it take to delete a name already in the array (assuming that you already know where it is)?

Now suppose that this array is not in any kind of sorted order.

(e) Would you use sequential or binary search on this array to look up a name?

(f) In the worst case, approximately how many comparisons will it take to look up a particular name?

(g) In the worst case, approximately how many assignments will it take to insert a new name (assuming you have already figured out where it needs to go)?

(h) In the worst case, approximately how many assignments will it take to delete a name already in the array (assuming that you already know where it is)?

Now suppose that you choose to store the data not in an array at all, but instead as an unsorted linked list.

(i) Would you use sequential or binary search to look up a name?

Now suppose that you choose to store the data in a sorted linked list.

(j) Would you use sequential or binary search on this array to look up a name?

2. (22 points) Write a method to sort an array of integers in descending order. Indicate in a comment which sorting algorithm you are coding.

public void sortDescending(int[] array)
{

3. (22 points) Write a method that does a binary search for a particular element in an array, assuming that the elements have been sorted in descending order. Your method should return the index of the location in the array where the item is found, or a -1 if the element is not in the array.

public int binarySearch(int[] array, int lookupValue)
{

4. (22 points) The following method takes as input a two-dimensional array that holds scores for a bowling league. Each row (first subscript) corresponds to a bowler, and each column (second subscript) corresponds to a particular game. Write a method which prints to the screen the maximum value for each column (game).

public void findMaxColumnValues(int[][] bowlingScores)
{

5. (14 points) What is output from the following program, when the method main is run? Make clear where you have written the actual output.

class TestClass
{
    public static int mystery(int w, int b, int many[])
    {
        w = -8;
        b = 10;
        int z = 3;
        int y = 42;
        many[1] = -97;
        many = new int[3];
        many[0] = 15;
        many[1] = 10;
        many[2] = 5;
        return w;
    }

    public static void main(String[] args) {
        int w = 99;
        int x = 64;
        int y = 29;
        int[] list = {-31, 9, 3};
        int z = mystery(w,x,list);
        System.out.println(w);
        System.out.println(x);
        System.out.println(y);
        System.out.println(z);
        for (int i=0; i < list.length; i++)
            System.out.println(list[i]);
    }
}