Answers to CSE205 Exam 3 Review Questions
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());
}
}
Output:
[Blue]
[Blue, Red]
[Blue, Red, Green]
[Blue, Orange, Red, Green]
[Orange, Red, Green]
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.
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());
}
}
Output:
[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.
4) Convert the following iterative method to a recursive one:
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);
}
5) What is the output of the following recursive method?
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.
6) Write a recursive method int power(int i, int j) which determines the
result of ij where j >= 0.
public int powerR(int i, int j) {
if (j == 0)
return 1; // i0 = 1 for any i
else
return powerR(i, j-1) * i; // ij = ij-1 * i = power(i, j-1)*i
}
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 (After finishing this, try to write a method
that prints 1 + 2 + 3 + 4 at home)
public void sumReverse(int n) {
if (n == 1)
System.out.println(n);
else
{ System.out.print(n + " + ");
sumReverse(n-1); //print (n-1) + (n-2) + … + 2 + 1
}
}
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]
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
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]
10 4 3 12 7
[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]
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
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 this sub arrays which will be partitioned
into smaller sub-arrays. Then keep applying the partition method to
such sub-arrays, until every sub-array is partitioned to have only one
element.
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;
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;
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;
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);
}
Powered by TCPDF (www.tcpdf.org)
