Midterm Practice Problems

Solutions will be posted under Practice Problem Solutions 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. Inheritance and Polymorphism

public class A extends B {
    public void twist() {
        System.out.println("ho!");
    }
}
public class B {
    public void twist() {
        System.out.println("ouch!");
    }
    public void shout() {
        System.out.println("oh!");
    }
}
public class C extends A {
    public void gasp() {
        System.out.println("why?");
    }
}

You create the following objects of the above classes:
```
A a1 = new A();
B b1 = new B();
C c1 = new C();
```
(Note: The above constructor calls are fine, because Java gives us a constructor with no parameters when we don’t define our own constructor.)

Explain why each of the following method calls either would or would not compile:
```
a1.shout()
a1.gasp()
b1.twist()
c1.toString()
```
Given the objects created in the previous problem, what would the output be of the following statements?
```
c1.twist();
c1.shout();
```
Given the above class definitions, which of the following assignment statements would be allowed, and which would not be allowed?
```
A a1 = new C();
A a2 = new B();
B b1 = new C();
Object o = new A();
```
Explain your answers briefly.

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

IV. 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!)
Review problems 4 and 5 from PS5 and problem 2, 6, and 7 from PS6

V. 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?

VI. Linked Lists

A doubly linked list is constructed from nodes that are instances of the following class:
```
public class DNode {
    private char ch;
    private DNode next;
    private DNode prev;
}
```
The next field holds a reference to the next node in the linked list, and the prev field holds a reference to the previous node in the linked list.

Below is a list of three of these nodes, along with two reference variables, n and p, that refer to specific nodes in the list:

Which of the following expressions does not refer to the third node in the list?
1. p.next
2. n.next.next
3. p.prev.next
4. p.prev.next.next
5. n.next.next.prev.next
The diagram below shows a linked list of characters that is constructed from instances of the StringNode class from lecture:

In addition, we have included two variables that each store a reference to one of the nodes in the linked list, along with the memory address of each node. You should assume that the ch field has the same address as the node itself, and that the address of the next field is 2 bytes after the beginning of the node.
1. What is the memory address of the field given by the expression head.next.next?
2. What is the value of the expression head.next.next?
3. Write one or more lines of code that remove the node containing the character 's' from the list.
4. Modify the diagram to reflect the results of executing the following lines on the original version of the list (before the 's' was removed):
```
q = q.next;
q.next = head;
```

Last updated on October 28, 2026.