Review Problems for Midterm I

• Stacks
• Queues
• Linked lists (singly/doubly linked, circular/non-circular)
• Priority queues: behavior, linked lists implementation, heap implementation (for the heap implementation you need to know pictures and algorithms only, no Java code).

• 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.
• using objects and methods, memory pictures.
• arrays of primitive types; arrays of objects.
• writing classes and methods.
• static variables and methods.

Review 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

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

Problem 2

• 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

Problem 4

• 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

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[0].setNext(nodes[1]);
	nodes[3].setNext(nodes[0]);
	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());
	temp.setNext(nodes[1].getNext());
	nodes[1].setNext(temp);
	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

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!