Midterm Practice Problems

Solutions will be posted under Other Content on Blackboard as we get closer to the exam.

These problems are not comprehensive, so make sure to review all of the relevant materials.

I. Java Basics

Consider the following lines of Java code:
```
int[] a = {5, 4, 3, 2, 1};
int[] b = {5, 4, 3, 2, 1};
int[] c = a;
for (int i = 0; i < b.length; i++) {
    c[i] = b[i];
}
b[3] += b.length;
a[3]--;
System.out.println(a[3] + " " + b[3] + " " + c[3]);
```
1. Draw a single memory diagram that shows the final result of these lines. Include both the stack and the heap in your diagram. You may assume that these lines are part of the main method.
2. Indicate what will be printed by the final line of code shown above.
Write a static method shiftRight that takes an array of integers and shifts all of the array elements one position to the right, with the original last element wrapping around to become the new first element. For example, consider this array:
```
int[] values = {0, 2, 4, 6, 8, 10};
```
After calling shiftRight(values), the contents of the values array should be {10, 0, 2, 4, 6, 8}.
Write a method with the header
```
public static int indexLast(int[] arr1, int[] arr2)
```
that takes two arrays of integers and that returns the index of the last occurrence of the sequence represented by the first array in the second array, or -1 if the sequence represented by the first array does not appear in the second array. For example, suppose that you have these arrays:
```
list1: {1, 3, 6}
list2: {1, 3, 5, 7, 8, 12, 1, 3, 17, 1, 3, 6, 9, 1, 3, 6}
```
then the call indexLast(list1, list2) should return 13 because the last occurrence of the sequence of values in list1 appears in list2 starting at index 13. You may assume that both arrays have at least one element.
Write a mutator for the Rectangle class from lecture that doubles the width of a Rectangle object.

II. Recursion

Write a recursive static method named sumReciprocals that takes as its only parameter an integer n that you can assume is positive, and that uses recursion (no loops!) to compute and return a floating-point value that is the sum of the reciprocals of the integers from 1 to n. For example, sumReciprocals(2) should return 1.5, which is 1/1 + 1/2, and sumReciprocals(4) should return approximately 2.0833, which is 1/1 + 1/2 + 1/3 + 1/4.
Write a recursive static method called removePadding() that takes a string s and that uses recursion to return a new string in which all leading and trailing spaces have been removed. For example, the call removePadding(" hello world ") should return "hello world".

A program for recursive backtracking includes a method similar to this one:

public boolean key_function(int i) {
    if (i > imax) {
        return true;
    }

    for (int alternative = 0; alternative < n; alternative++) {
        if (is_valid(alternative, i)) {
            apply_alt(alternative);
            if (_________________) {    // what goes here?
                return true;
            }
            remove_alt(alternative);
        }
    }

    return false;
}

The blank should be replaced by:

is_safe(i)
apply_alt(alternative + 1)
key_function(alternative + 1)
key_function(i)
key_function(i + 1)

III. Algorithm Analysis Questions 1-3 involve the following method:

public static int mystery(int a[]) {
    int n = a.length;
    int result = 0;

    for (int i = 1; i < n; i++) {
        int x = a[i];        // Question 4

        int sum = 0;
        for (int j = 0; j < 3; j++) {
            sum *= a[i];     // Question 5
        }
        result += sum;

        int j = i;
        while (j > 0) {
            result += a[j];  // Question 6
            j--;
        }
    }

    return result;            
}

What is the big-O expression for the number of times that the line
```
int x = a[i];
```
is executed?
1. O(n)
2. O(n²)
3. O(n log(n))
4. O(log(n))
5. O(n!)
What is the big-O expression for the number of times that the line
```
sum *= a[i];
```
is executed?
1. O(n)
2. O(n²)
3. O(n log(n))
4. O(log(n))
5. O(n!)
What is the big-O expression for the number of times that the line
```
result += a[j];
```
is executed?
1. O(n)
2. O(n²)
3. O(n log(n))
4. O(log(n))
5. O(n!)

IV. Sorting

The following array is to be sorted using insertion sort:
```
{18, 10,  8, 35,  9, 29,  5}
```
Which of the following shows the contents of the array at the end of one of the iterations of the algorithm?
1. { 5, 10, 8, 35, 9, 29, 18}
2. { 5, 8, 9, 35, 10, 29, 18}
3. { 8, 9, 10, 35, 18, 29, 5}
4. { 8, 10, 18, 35, 9, 29, 5}
5. {10, 8, 18, 9, 29, 5, 35}
Here is an array that has just been partitioned by the first step of quicksort:
```
{3, 0, 2, 4, 5, 8, 7, 6, 9}
```
Which of the following statements is correct?
1. 5 could be the pivot, but 7 could not be.
2. 7 could be the pivot, but 5 could not be.
3. Neither 5 nor 7 could be the pivot.
4. Either 5 or 7 could be the pivot.
The following array is to be sorted:
```
{19, 22, 11, 13, 53, 34, 25}
```
Which of the algorithms that we discussed in lecture will cause the array to be ordered as follows
```
{19, 11, 13, 22, 34, 25, 53}
```
at an intermediate stage in the sorting process?
1. insertion sort
2. bubble sort
3. quicksort (with an initial pivot of 13)
4. selection sort
5. merge sort
Through experiment, you determine that selection sort performs 5000 comparisons when sorting a array of some size k. If you doubled the size of the array to 2k, approximately how many comparisons would you expect it to perform?
1. 5000
2. 10000
3. 20000
4. 40000
5. it would depend on the contents of the array
Through experiment, you determine that selection sort performs 5000 moves when sorting a array of some size k. If you doubled the size of the array to 2k, approximately how many moves would you expect it to perform?
1. 5000
2. 10000
3. 20000
4. 40000
5. it would depend on the contents of the array
The following array is to be sorted:
```
{17, 53, 71, 36, 46, 41, 23, 12}
```
1. During the execution of quicksort, what would the array look like after the first call to the partition() method?
2. During the execution of quicksort, what would the array look like after the second call to the partition() method?
3. After the initial pass of bubble sort, how would the array be ordered?
4. After three passes of selection sort, how would the array be ordered?
5. After four passes of insertion sort, how would the array be ordered?
6. During the execution of mergesort, what would the array look like after the third call to the merge() method?

Last updated on March 18, 2026.