Review Problems for Midterm I

The midterm will cover the following data structures: The midterm will cover the following Java topics:

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:

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:

Problem 4

Answer the questions below without running the program. Then run the program to check your answers.

public class Review1 {
    public static void main(String [] args) {
	Node [] nodes = new Node[5];
	nodes[0] = new Node(1);
	nodes[1] = new Node(2);
	nodes[2] = new Node(3);
	// Draw memory picture 1

	nodes[3] = nodes[2];
	nodes[4] = nodes[2].getNext(); 
	// Draw memory picture 2
	// what will be printed by each of the following statements?

	System.out.println("print1 = " + nodes[0].getNext().getData());
	System.out.println("print2 = " + nodes[2].getNext().getData());
	System.out.println("print3 = " + (nodes[3].getNext() == nodes[4]));

	// adding a new node
	Node temp = new Node(nodes[3].getNext().getData());
	nodes[2] = temp;
	// Draw memory picture 3

	// what will be printed by each of the following statements?
	// the print statements are commented out so that you can work
	// on the first group of prints first
	System.out.println("print4 = " + nodes[0].getNext().getNext().getData());
	System.out.println("print5 = " + (nodes[0].getData() == nodes[2].getData()));
	System.out.println("print6 = " + (nodes[0] == nodes[2]));

	// write a loop to print the data fields of all array elements
	// what will be printed by the loop?


Problem 5

Write a class FlipFlop which has an integer data field and a constructor that takes one integer. The class has a static boolean variable flip. If flip is true, the constructor sets the data field to the value opposite to the value passed to it. I.e. if flip is true, FlipFlop(7) creates an object with the data value -7, and FlipFlop(-5) creates an object with data field 5. If flip is false, the sign is not changed.

Every time a new object is created, the value of flip is changed: true to false, and false to true.

Test the class by creating an array of FlipFlops and then printing them out (write the getData() method for FlipFlop so that you can print it out). Try different loops: passing only positive numbers to constructor, only negative numbers, use a random number generator to change the signs of inputs to the constructor randomly.

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.