Review Problems for Midterm I
The midterm will cover the following data structures:
- Stacks
- Queues
- Linked lists (singly/doubly linked, circular/non-circular)
- 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
Answer the following questions about the program below:
- 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!