Exam 3 Review Questions
Question 1: Trace the output of the following Linked List code,
which uses an Iterator.
import java.util.*;
public class LinkedListTester {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
ListIterator<String> iterator = list.listIterator();
iterator.add("Blue");
System.out.println(list.toString());
iterator.add("Red");
System.out.println(list.toString());
iterator.add("Green");
System.out.println(list.toString());
iterator = list.listIterator();
iterator.next();
iterator.add("Orange");
System.out.println(list.toString());
iterator = list.listIterator();
iterator.next();
iterator.remove();
System.out.println(list.toString());
Answer:
[Blue]
[Blue, Red]
[Blue, Red, Green]
[Blue, Orange, Red, Green]
[Orange, Red, Green]
Question 2: What is an ADT (an Abstract Data Type) and why are
they considered to be “abstract?”
Answer: An ADT is a collection of data and the particular
operations that are allowed on that data. An ADT has a name, a
domain of values, and a set of operations that can be performed.
An ADT is considered to be “abstract” because the operations you
can perform are separated from the underlying implementation.
That is, the details on how an ADT stores its data and
accomplishes its methods are separate from the concept that it
embodies.
Question 3: Trace the output of the following Stack code.
import java.util.*;
public class StackTester {
public static void main(String[] args) {
Stack<String> mystack = new Stack<String>();
mystack.push("Blue"); System.out.println(mystack.toString());
mystack.push("Red"); System.out.println(mystack.toString());
mystack.push("Green"); System.out.println(mystack.toString());
} } System.out.println(mystack.pop());
System.out.println(mystack.toString());
mystack.push("Orange"); mystack.push("Yellow");
System.out.println(mystack.toString());
System.out.println(mystack.peek());
System.out.println(mystack.toString());
mystack.pop();
mystack.pop();
mystack.pop();
System.out.println(mystack.toString()); }
}
Answer:
[Blue]
[Blue, Red]
[Blue, Red, Green]
Green
[Blue, Red]
[Blue, Red, Orange, Yellow]
Yellow
[Blue, Red, Orange, Yellow]
[Blue]
A Stack is LIFO (Last In First Out), like a stack of tiles, the last
tile you added to the top of the pile, is the first tile you can
remove.
Question 4: Convert the following iterative method to a recursive
one:
Answer:
public int IterativeFactorial(int n) {
int i = 0;
int result = 1;
while (i <= n - 1) {
result = result * (n - i);
i++;
}return result;
}
Recursive form that follows the syntax of the code above:
//initial call from main with i = 0
public int RecursiveFactorial(int n, int i) { if (i == n - 1) return 1;
else return RecursiveFactorial(n, i + 1) * (n - i);
}
A more basic Factorial method (iterative):
public int FactorialI(int n) {
int result = 1;
int i = 1;
while (i <= n) {
result = result * i;
i++;
}return result;
}
Basic Factorial method in recursive form:
public int FactorialR(int n) {
if (n == 1) return 1;
else return n * FactorialR(n – 1);
}
Question 5: What is the output of the following recursive method?
Answer:
public String RecursiveMethod(String input) {
int n = input.length();
if (n == 1) return input.substring(0, 1);
else return input.charAt(n - 1) +
RecursiveMethod(input.substring(0, n - 2)); If called from main
with: RecursiveMethod(".?oplllZe*H");
Output: Hello.
Question 6: Write a recursive method int power(int i, int j) which
determines the result of ij where j >= 0.
Answer:
public int powerR(int i, int j) {
if (j == 0)
return1; //i0 =1for any i else
return powerR(i, j-1) * i; // ij = ij-1 * i = power(i, j-1)*i
}
Question 7: Write a recursive method void sumReverse(int n) that
when given an integer n > 0, prints the integer expression (with
addition operator). For example, if n is 4, your
}method would print: 4 + 3 + 2 + 1 that prints 1 + 2 + 3 + 4 at
home)
Answer:
public void sumReverse(int n) {
if (n == 1)
System.out.println(n);
else
(After finishing this, try to write a method
{ System.out.print(n + " + ");
sumReverse(n-1); //print (n-1) + (n-2) + ... + 2 + 1
} }
Question 8: Demonstrate how the following array is sorted using
Selection Sort. Show the array after each pass of the outer loop.
[10, 4, 3, 12, 7]
Answer:
Pass 1: 3 4 10 12 7
Pass 2: 3 4 10 12 7
Pass 3: 3 4 7 12 10
Pass 4: 3 4 7 10 12
Question 9: Demonstrate how the following array is sorted using
Merge Sort. Show the array after each recursive call (after
merging). [10, 4, 3, 12, 7]
Answer:
1043127
[10 4] [3 12 7]
[10] [4] [3] [12 7]
[10] [4] [3] [12] [7]
[4 10] [3 7 12]
[3 4 7 10 12]
Question 10: Perform the partition method of quick sort once on
the array [11, 7, 15, 3, 12, 9, 2, 10]. Show the array after each
iteration of the while loop in the partition method. Use the first
element (here it is 11) as the pivot.
Answer:
11,7,15,3,12,9,2,10
-> i j <-
(i will look for an element >= pivot from left and j will look for an
element <= pivot from right)
SWAP
10,7,15,3,12,9,2,11,
i j
ij SWAP
10,7,2,3,12,9,15,11,
i j
SWAP
10,7,2,3,9,12,15,11,
J i
STOP
Thus, this is partitioned into [10, 7, 2, 3, 9] and [12, 15, 11]
Note that in order to sort this array completely, you need to apply
the partition method to each of these sub arrays which will be
partitioned into smaller sub-arrays. Then keep applying the
partition method to such sub-arrays, until every subarray is
partitioned to have only one element.
Question 11: Show the instructions required to create a linked list
that is referenced by head and stores in order, the int values 3, 6
and 2. Assume that Node’s constructor receives no parameters.
Answer:
Node head = new Node( );
head.info = 3;
head.next = new Node( );
head.next.info = 6;
head.next.next = new Node( );
head.next.next.info = 2;
head.next.next.next = null;
Question 12: Assume that head references a linked list that stores
the values 3, 6 and 2 in that order. Show the instructions needed to
move the value 2 in front of the value 6 (so that the list is now 3,
2, 6).
Answer:
Node temp = head.next;
head.next = head.next.next;
head.next.next = temp;
temp.next = null;
Question 13: Assume that head references a linked list that stores
the values 3, 6 and 2. Show the instructions needed to delete the
Node with 3 from the list so that head would reference the list of 6
and 2.
Answer:
head = head.next;
Question 14: Assume that head references a linked list although
we don’t know what is currently stored in that list. Write a block
of code using a try-catch block that will work through the entire
linked list printing each element out, stopping only when we have
reached the end of the list because a NullPointerException is
thrown. Once the Exception is thrown, output the number of
elements found in the list.
Answer:
int count = 0;
try
{Node temp = head;
while (true)
{
System.out.println(temp.info);
temp = temp.next;
count++;
catch (NullPointerException npe)
{
System.out.println(“Number of elements in the list is ” + count);
}
Handout: Searching and Sorting
Question 1: Classes in a software system can have various types
of relationships to each other List the three of the most common
relationships:
Answer: Dependency A uses B 2.Aggregation: A has-a B
3.Inheritance A is-a B
Question 2: For the following Array show how the array would be
sorted using Selection sort after each pass of the outer
loop.[9,6,14,11,3,12,7,5]
Answer: Selection sort:
[3,6,14,11,9,12,7,5]
[3,5,14,11,9,12,7,6]
[3,5,6,11,9,12,7,14]
[3,5,6,7,9,12,11,14]
[3,5,6,7,9,12,11,14]
[3,5,6,7,9,11,12,14]
[3,5,6,7,9,11,12,14]
Question 3: For the following Array show how the array would be
sorted using Insertion sort after each pass of the outer loop.
[9,6,14,11,3,12,7,5]
Answer: Insertion sort:
[6,9,14,11,3,12,7,5]
[6,9,14,11,3,12,7,5]
[6,9,11,14,3,12,7,5]
[3,6,9,11,14,12,7,5]
[3,6,9,11,12,14,7,5]
[3,6,9,11,12,14,7,5]
[3,6,7,9,11,12,14,5]
Question 4: Assume a sorted array number has the following
values in position 0 through 12.
5 8 13 23 24 25 43 51 67 69 70 71 72
a.Using a binary search, what values are examined (list in order) to
determine if 51 is in the array?
Answer: 43, 69, 51
b. Using binary search, what values are examined (list in order) to
determine if 6 is in the array?
Answer: 43, 13, 5, 8
Handout: Big-O notation & analyzing different sorting
algorithms
Question 1: What would be the output of the following program
(line for line)?
public class MyClass
{
public int myInt = 42;
public int[] myIntArray = {1, 2, 3, 4};
public MyClass myNext = null;
public String toString()
{ String result = new String("");
}
result += myInt;
for (int i = 0; i<4; i++)
result +=(" " + myIntArray[i]);
return result;
public static void main(String[] argv) { MyClass inst1 = new
MyClass(); MyClass inst2 = new MyClass();
MyClass inst3 = inst1;
inst3.myNext = inst1;
inst2.myNext = inst3;
inst1.myIntArray[0] = 9;
inst2.myIntArray[1] = 11;
inst3.myIntArray[2] = 13;
inst1 = inst2;
inst2.myNext = inst1;
inst3.myNext = inst1.myNext;
inst1.myNext.myIntArray[3] = 15;
inst2.myNext.myInt =21;
inst3.myNext.myInt= 23;
System.out.println(inst1);
System.out.println(inst2);
System.out.println(inst3);
}// end main
}// end class
Answer:
23 1 11 3 15
23 1 11 3 15
4292134
Question 2: What is the complexity of the following code (in
terms of the length of the array), assuming someMethod has a
complexity of O(1)?
for(int i = 0; i < array.length; i++)
for(int j = 0; j < array.length; j++)
someMethod(array[j]) __________
Answer:
The complexity of this code is O(n2).
Question 3: What is the complexity of the following code (in
terms of the length of the array)?
for(int i = 0; i < 5; i++)
System.out.println(array[i]);
Answer: The complexity of this code is O(1), since the length of
the array does not matter.
Question 4: Which of the following algorithms has a time
complexity of O(log2 n)?
a) insertion sort b) selection sort c) bubble sort d) linear search e)
binary search
Answer: e
Question 5: Which of the following algorithms has a worst-case
complexity of O(n2)?
a) insertion sort
b) selection sort
c) bubble sort
d) all of the above e) neither a, b, nor c
Answer: d
Handout: Recursion
Question 1: Write the output generated by the following program
public class TestWierdPowerMethod
{
public static int pow( int base, int power ) { // pre: both arguments
are >= 1
if( power == 1 ) return base;
else
return base * pow( base, power-1 );
}
public static void main(String[] args)
{
System.out.println( pow(4, 1) ); System.out.println( pow(4, 2) );
System.out.println( pow(4, 3) );
} }
Answer:
4
16
64
Question 2: Write the output generated by the following program
public class Mystery
{
public static void writeStuff( int n )
{
if( n == 0 )
System.out.print( n ); else
{
System.out.print( "[" ); writeStuff( n - 1 ); System.out.print( "]" );
} }
public static void moreStuff( int n, String s )
{
if( n == 1 )
System.out.println( s + n ); else
{
s = s + "+=";
moreStuff( n - 1, s ); }
}
public static void main(String[] args)
{
writeStuff( 1 ); System.out.println( ); writeStuff( 2 );
System.out.println( ); writeStuff( 3 ); System.out.println( );
moreStuff( 1, "One: " ); moreStuff( 2, "" ); moreStuff( 3, "Three: "
);
} }
Answer:
[0]
[[0]]
[[[0]]]
One: 1
+=1
Three: +=+=1
Question 3: Using recursion, complete method goingUp so it
displays all the numbers from the first argument to the last in
ascending order (separate with a space). You can NOT use a loop.
What is the base case? When should the method call itself
(recursive case)?
public class TestGoingUp
{
public static void goingUp( int start, int stop ) {
}
public static void main(String[] args)
{
goingUp( 1, 5 ); System.out.println( ); goingUp( 2, 7 );
System.out.println( ); goingUp( 3, 3 ); System.out.println( );
} }
Answer:
public static void goingUp( int
{
if( start <= stop )
{
System.out.print( start + " " );
goingUp( start + 1, stop ); }}
Question 4: Write a recursive method reverseArray that reverses
the elements in an array of ints. The program below must generate
the output shown in the box. reverseArray can not use a loop.
public class TestReverse {
public static void show( int[] x, int n ) { System.out.print( "[ " );
for(int j = 0; j < n; j++ ) System.out.print( x[j] + " " );
System.out.println( "]" ); }
public static void main(String[] args) { int[] x = { 1, 2, 3, 4, 5, 6,
7, 8 };
show( x, x.length ); reverseArray( x, 0, x.length-1 ); show( x,
x.length );
} }
Answer:
public static void reverseArray( int[] x, int first, int last )
{
if( first < last )
{ // Do nothing if last >= first empty array or one with one element
swap( x, first, last );
reverseArray( x, first + 1, last - 1 ); }
}
public static void swap( int[] x, int first, int last )
{
int temp = x[first]; x[first] = x[last]; x[last] = temp;
}
Handout: Linked List
Question 1: Trace the output of the following code using the
LinkedList and ListIterator class we discussed in class.
public class LinkedListTester
{
public static void main(String[] args)
{
LinkedList list1 = new LinkedList(); ListIterator iterator =
list1.listIterator();
iterator.add("Apple"); printList(list1);
iterator.add("Orange"); printList(list1); iterator.add("Tomato");
printList(list1);
iterator = list1.listIterator(); iterator.next(); iterator.next();
iterator.add("Banana"); printList(list1); iterator.next();
iterator.add("Lemon"); printList(list1);
iterator = list1.listIterator(); iterator.next(); iterator.remove();
while (iterator.hasNext()) System.out.println(iterator.next());
}
//This method prints out the content of LinkedList public static
void printList(LinkedList list1)
{
ListIterator iterator = list1.listIterator(); String result = "{ ";
while (iterator.hasNext())
result += iterator.next() + " "; result += "}";
System.out.println(result); }
}
For following questions, assume that a linked list is implemented
using the Node class where a Node contains instance data of int
info; and Node next; where next references the next Node in the
linked list. Also assume that head references the first Node in the
list.
Answer:
{ Apple }
{ Apple Orange }
{ Apple Orange Tomato }
{ Apple Orange Banana Tomato }
{ Apple Orange Banana Tomato Lemon }
Orange
Banana
Tomato
Lemon
Question 2: Which of the following instructions would create an
initially empty linked list?
a) Node head = new Node( ); b) Node head = Node;
c) Node head = null;
d) Node head = new Node(0); e) Node head = list;
Answer: c. Explanation: The initial linked list will be empty, and
so head should be null to indicate that there are no Nodes in the
list yet. The answer in b is syntactically invalid, and the answers in
a and d may be invalid depending on what parameter(s) the Node
constructor expects, but in any event, the answers in a and d will
create a Node, and therefore the initial list will not be empty.
Question 3: Assume Node temp references the last element of the
linked list. Which of the following conditions is true about temp?
a) (temp.info = = 0)
b) (temp.next = = null)
c) (temp = = head)
d) (temp = = null)
e) (temp.next = = null && temp.info = = null)
Answer: b. Explanation: Since temp is the last Node in the list,
there is no next node, so temp.next is null. The answer in e is
incorrect because temp references the last Node and this Node
does have a value, so temp.info will equal some int value
Question 4: Assume Node temp is currently set equal to head.
Which of the following while loops could be used to iterate
through each element of a linked list?
a) while (head != null)
head = temp.next;
b) while (temp != null)
temp = temp.next;
c) while (head != null)
temp = temp.next;
d) while (head != null)
head = head.next;
e) while (temp != null)
head = head.next;
Assume that the countIt and sumIt methods in next two questions
receive a parameter Node temp, which references the first Node in
a linked list where Node is a class that consists of data instances
int info and Node next and further assume that the int variables
count and sum are initialized to 0.
Answer: b
Question 5: Write a method to count the number of items in the
linked list?
Answer:
public int countIt(Node temp) {
while (temp != null)
{
count++;
temp = temp.next;
}
return count; }
Question 6: Write a method to sum all of the items in the linked
list?
For following questions, assume you have a linked list of integer
values and access to the beginning of the list. Each node has value
and next instance variables. You may use any of the LinkedList
methods from LinkedList.java, posted under “Code Examples” on
the course web site.
Answer:
public int sumIt(Node temp) { while (temp != null)
{sum += temp.info;
temp = temp.next;
}
return sum; }
Question 7: Write a method sumAlternate that computes and
returns the sum of every other value in the list starting with the
first one. For example, if the original list is: 1 2 3 4 5 this method
would return 9.
Answer:
/* This solution uses a boolean variable that alternates on every
pass through the while loop in order to add up every other value.
public int sumAlternate()
{
Node current = head;
int sum = 0;
boolean everyOther = true;
while(current != null
}
}
return sum;
{
if(everyOther)
{
} else
everyOther = true; current = current.next;
Question 8: Write a method sumEvens that computes and returns
the sum of all even numbers in the list. .For example, if the
original list is: 1 2 3 4 5 this method would return 6
Answer:
This solution solves it simply by setting current to
current.next.next, so long as current.next is not null.This solution
does not go through the while loop as long as the previous one,
since it skips over every other one.
*/
public int sumAlternate()
{
Node current = head; int sum = 0;
while(current != null)
{
else
}
return sum;
}
2.
public int sumEvens()
{
Node current = head; int sum = 0;
while(current != null)
} }
{
if(current.value % 2 == 0) sum += current.value;
sum += current.value; if(current.next != null)
current.next = current.next.next; current = null;
current = current.next; return sum;
Handout: Stack and Queue
Question 1: Use the linked structure above to answer the
following questions?
What is the value of first.data?
What is the value of first.next.data?
What is the value of first.next.next.data?
What is the value of first.next.next.next?
Answer:
First
Second
Third
null
Question 2: Write out the order of elements that are contained in a
stack after the following operations are performed.
myStack.push(new Integer(8)); myStack.push(new Integer(6));
Integer num1 = myStack.pop(); myStack.push(new Integer(3));
myStack.push(new Integer(4)); myStack.push(new Integer(15));
myStack.push(new Integer(12)); myStack.push(new Integer(9));
myStack.pop();
myStack.pop();
myStack.pop(); myStack.push(new Integer(19));
Answer: 8 3 4 1 9 (from bottom to top stack)
Question 3: One use of a Stack is to reverse the order of input.
Write a method that reads a series of Strings from the keyboard
(assume the Scanner class has been imported) and outputs the
Strings in reverse order of how they were entered. The input will
end with the String “end” but do not output the String “end”.
Assume that SStack is a Stack that can store Strings. Remember to
declare and instantiate your SStack in your method.
Answer:
public void reverseOrder( )
{
SStack s = new SStack( );
Scanner scanner = new Scanner(System.in); String in =
scanner.next( );
while (!in.equals(“end”))
{s.push(in);
in = scanner.next( );
}
while (!s.empty( ))
{
} }
Question 4: Write the output generated by the following code
using the LinkedStack class:
Stack opStack = new LinkedStack( ); System.out.println(
opStack.isEmpty( ) ); opStack.push( ">" );
opStack.push( "+" );
opStack.push( "<" );
System.out.print( opStack.peek( ) ); System.out.print(
opStack.peek( ) ); // careful System.out.print( opStack.peek( ) );
Answer:
<
<
<
Question 5: Write the output generated by the following code
using the LinkedStack class.
Stack aStack = new LinkedStack( ); aStack.push( "3" );
aStack.push( "2" );
aStack.push( "1" ); System.out.println( System.out.println(
aStack.pop(); System.out.println( aStack.pop();
System.out.println( aStack.pop(); System.out.println(
aStack.isEmpty( ) ); aStack.peek( ) );
aStack.peek( ) ); aStack.peek( ) ); aStack.isEmpty( ) );
Answer:
False
1
2
3
True
Powered by TCPDF (www.tcpdf.org)
