CSCD 226 Exam 1 Name_________________________

100 points Section_____

 

1.      (a - 2 points) What is a reference? (b - 2 points) Declare one AND make it refer to something. (c - 2 points) If we pass a reference to an object to a method, and make the reference IN THE METHOD refer to a brand new object of that type, will the reference to the object that was specified in the method call also refer to this new object?.

 

 

 

 

 

 

 

 

2.      (a - 3 points) What is the this reference? (b - 2 points) When is it implicitly used. (c - 3 points) Why dont static methods have access to the this reference?

 

 

 

 

 

 

 

 

 

3.      (4 points) What is garbage collection and when is it necessary?

 

 

 

 

 

 

4.      (a 2 points) What is the difference between a static variable and an instance variable? (describe each for full credit) (b 2 points) What is the difference between a static method and an instance method? (describe each for full credit)

 

 

 

 

 

 

 

 

5.      (5 points) What is the Comparable interface used for and why is it so important to the Java programming language as a whole? (HINT: think about the Insertion Sort method that takes an array of Comparable objects as a parameter)


 

6.      (24 pts) Given the following array of numbers, show what the array will look like after three passes through the array for (a) (Smart) Bubble Sort, (b) Selection Sort, and (c) Insertion Sort. Show all work possible for partial credit.

 

 

ORIGINAL ARRAY

90

80

70

20

10

30

40

0

 

(Smart) Bubble Sort

after 1st pass

 

 

 

 

 

 

 

 

after 2nd pass

 

 

 

 

 

 

 

 

after 3rd pass

 

 

 

 

 

 

 

 

 

ORIGINAL ARRAY

90

80

70

20

10

30

40

0

 

Selection Sort

after 1st pass

 

 

 

 

 

 

 

 

after 2nd pass

 

 

 

 

 

 

 

 

after 3rd pass

 

 

 

 

 

 

 

 

 

ORIGINAL ARRAY

90

80

70

20

10

30

40

0

 

Insertion Sort

after 1st pass

 

 

 

 

 

 

 

 

after 2nd pass

 

 

 

 

 

 

 

 

after 3rd pass

 

 

 

 

 

 

 

 

 

7.      (6 points) Why must Selection Sort and Insertion Sorts outer loop execute n-1 times to guarantee the array is sorted when the same is not necessary for Bubble Sort? NOTE: the reason for Selection Sort is different than for Insertion Sort. Describe each for full credit.

 

 


 

8.      (9 points) Based on the following code for Binary Search, perform a hand trace to show values assigned to all variables in the routine. Assume a target value of 80 and that the array contains the following data:

5

19

34

47

61

75

86

98

 

public static int binarySearch(int[] array, int target)

{

int low = 0, high = array.length - 1, mid;

 

while (low <= high)

{

mid = (low + high) / 2;

 

if (target > array[mid])

low = mid + 1;

else if (target < array[mid])

high = mid - 1;

else

return mid;

}//end while

 

return -1;

}//end binarySearch method

 

low

high

mid

target

 

 

 

80

 

 

 

9.      (16 points) Given the following regular Bubble Sort code, add the necessary code to smarten it up based on class discussion. You may remove code if you feel its necessary. The bottom line is to make it clear what changes need to be made.

 

public static void bubbleSort(int[] numbers)

{

int i, j, temp;

 

 

for(i = 0 ; i < numbers.length - 1 ; i++)

{

 

for (j = 1 ; j < numbers.length ; j++)

{

 

if (numbers[j-1] > numbers[j])

{

 

temp = numbers[i-1];

numbers[i-1] = numbers[i];

numbers[i] = temp;

 

}//end then clause

 

}//end inner for

 

}//end outer for

 

}//end bubbleSort method


 

10.  (18 points) Write a method that will convert all lower case characters to uppercase in an array of characters. The method has one parameter, an array of characters. Do not worry about placing the method inside a class. Do not worry about invoking the method. NOTE: A has an ASCII/Unicode value of 65, B is 66, Z is 90. a is 97, b is 98, and z is 122.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

EXTRA CREDIT

(1 point) What is the formula for computing the number of checks Binary Search will take to determine beyond a doubt if the target is in the array?

 

 

(2 points) Show how to arrive at this formula (NOTE: we did this on the board in class J)

 

 

 

 

 

 

 

(2 points) How many checks are necessary for an array of size 17,000? NO CALCULATORS ARE ALLOWED!