## Review Problems for Midterm I

The midterm will cover the following data structures:
• Stacks
• Queues
• Priority queues: behavior, array implementation, linked lists implementation
The midterm will cover the following Java topics:
• Java variables, variable declarations and scope (for instance, if a variable is declared within a loop where can you access it?)
• Java expressions, rounding.
• if/else statements, while loops, for loops, for-each loops.
• using objects and methods, object diagrams.
• arrays
• writing classes and methods.

## Review problems

Note: review problems will help you refresh the material. They are not sample problems.

Clarification: "write an algorithm" means that you can write in pseudocode or in English (but make sure that all details are spelled out). "write a program" means that you have to write and test a Java program.

### Problem 1

You are given a stack and a queue. Write an algorithm determine which of the two has more elements. At the end the stack and the queue have to be put back into the original state. Convert your algorithm into a Java program.

Now answer the same question for a stack and a linked list, a queue and an array, two stacks, etc.

### Problem 2

Write a program to create an array of 10 integer elements and initialize it to random numbers, each number between 0 and 10. Then:
• find the sum of all elements of the array.
• Create an array of 10 booleans. Go through the array of integer and set the boolean at index i to `true` if the integer at index i is less than 5, and to `false` otherwise.

### Problem 3

Write a program that has two linked lists: `odds` and `evens`. The program generates 20 random numbers between 0 and 20. If the number is even, it is added to the list `evens`. Otherwise it is added to the list `odds` (the order of elements doesn't matter). Print out both lists at the end of the program to check.

### Problem 4

You are given a priority queue. Write a program to reverse the priority queue using an array. More specifically, do the following:
• Find out the number of elements in the queue, store it in the variable n.
• Create an array of nodes of size n.
• In a loop, move the elements of the linked list to the array one by one, removing them from the queue.
• When the queue becomes empty, insert all the elements back into the queue starting from the end of the array and going backwards.
• Print the queue at the end to make sure that it is reversed.
• What is the running time of this algorithm?

### Problem 4

Draw the object diagram for this program. What will be printed in the while loop?
``````
public class Review {
public static void main(String [] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = n1;
Node n4 = n2;

n1.setNext(n4);
n2.setNext(n3);

Node n = n1;

while (n != null) {
System.out.println(n.getData());
n = n.getNext();
}
}
}
``````

### Problem 5

• Will this program work correctly?
• If yes, what will be printed by the program?
• What happens if the condition for the first for loop is changed to `i < arr.length`?
• Is it possible to change the first loop into a for-each loop? If yes, please write the loop. If not, please explain why.
• Is it possible to write the last loop (the for-each loop) as a while loop? If yes, please write the loop. If not, please explain why.
``````
public class ReviewLoop {
public static void main(String [] args) {
int [] arr = {1, 4, 5, 7, 3, 2, 1, 8, 6};

for (int i = 0; i < arr.length - 1; i = i + 2) {
arr[i] = arr[i] + arr[i + 1] / 2;
}

for (int a: arr) {
System.out.println(a);
}
}
}
``````

These are just some of the ideas for practice problems. You may create your own along the same lines. The more you practice, the better!

### That's all!

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.