# Second Midterm Exam Review Problems

1. The following two lines both generate compiler warnings. What is wrong with them?

Stack<String stack1 = new Stack();

Stack stack2 = new Stack<String();

2. While String is a sub-type of Object (that is, every String object “is a” Object object),

it is not true that Bag<String is a sub-type of Bag<Object. Explain why. (Hint: If

A “is a” B, then everything you can do with B you can also do with A. What can you do

with a Bag<Object that you cannot do with a Bag<String?)

3. What is wrong with the following code fragment? How do you fix it?

List<String listOfStrings = new ArrayList<String();

String s;

for (s : listOfStrings)

System.out.println(s);

4. (a) Suppose that it is an Iterator object. Write a small piece of Java code that prints

all the objects of it to System.out.

(b) Suppose that it is an Iterator object that returns Rectangle objects. Write a

small piece of Java code that inserts all the objects of it into a newly created Stack

object.

5. The following code is supposed to fill list3 with every possible sum of elements from

list1 and list2. So list3 should end up holding

{11, 12, 13, 21, 22, 23, 31, 32, 33, 41, 42, 43, 51, 52, 53}

But the code is incorrect. What is wrong? How could you fix it?

List<Integer list1 = Arrays.asList(10, 20, 30, 40, 50);

List<Integer list2 = Arrays.asList( 1, 2, 3);

List<Integer list3 = new ArrayList<Integer();

for (Iterator<Integer it1 = list1.iterator(); it1.hasNext(); )

for (Iterator<Integer it2 = list2.iterator(); it2.hasNext(); )

{

int n = it1.next();

int m = it2.next();

list3.add( n + m );

}

for (int i : list3)

System.out.print(i + " ");

System.out.println();

6. Here are three ways we might declare a generic class that holds a pair of references to

two objects of the same type. Suppose that p1, p2, and p3 are references to objects of

type Pair1<T, Pair2<T, and Pair3<T respectively. In what way can p1, p2 and p3

be used to make comparisons?

class Pair1<T extends Comparable<T

class Pair2<T extends Comparable<T implements Comparable<T

class Pair3<T extends Comparable<T implements Comparable<Pair3<T

7. Suppose we perform the following series of stack operations on a single, initially empty

stack:

push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7),

push(6), pop(), pop(), push(4), pop(), pop().

Draw a picture of the stack at the point where it contains the maximum number of

elements (be sure to indicate the top and bottom of the stack). How many of the above

operations had been performed at that point?

8. Suppose you have a stack s that contains (1 2 3), with 1 being the top-of-stack, and a

queue q that is empty. Using no other variables and only the push() and pop() stack

operations and the add() and remove() queue operations, show a sequence of operations

that leave the queue q empty and the stack s with each of the following contents.

(a) Leave the stack s with the contents (1 3 2) with 1 as top-of-stack.

(b) Leave the stack s with the contents (3 1 2) with 3 as top-of-stack.

9. Suppose we implement a stack using a partially-filled array. What is wrong with storing

the top-of-stack at location [0] and the bottom of the stack at the last used position of

the array?

10. If we use a partially-filled array to implement a queue, which is better and why? Having

the front of the queue at location [0] (and the rear at the last used position of the

array), or having the rear of the queue at location [0] (and the front at the last used

position of the array).

11. If we use a linked list with a head and a tail reference to implement a stack, which is

better and why? Having the top-of-stack at the head of the linked list, or having the

top-of-stack at the tail of the linked list?

12. If we use a linked list with a head and a tail reference to implement a queue, which is

better and why? Having the front of the queue at the head of the linked list, or having

the front of the queue at the tail of the linked list?

13. Here is an incorrect pseudo code for an algorithm which is supposed to determine whether

a String of parentheses is balanced:

boolean isBlanced( String input )

{

declare a character stack

while ( input has more characters )

{

read a character from input

if ( the character is a ’(’ )

push it on the stack

else if ( the stack is not empty )

pop a character off the stack

else

return false

}

return true

}

Give an example of an input string that is made up of only the characters ’(’ and ’)’,

is unbalanced, but for which this algorithm will return true. Explain what is wrong with

the algorithm. Can this algorithm ever incorrectly return false when its input string is

a balanced string?

14. Convert the following expression from postfix to infix notation. Use the minimum num-

ber of parentheses needed.

6 3 2 4 + - *

15. Convert the following expressions from infix to postfix notation.

1 + 2 + 3 + 4

1 + (2 + (3 + 4))

1 + (2 + 3) + 4

2 * 3 * (9 + (3 - 1) + 4) * (5 - 1)

16. Using the two stack algorithm for evaluating fully parenthesized infix expressions, draw

the contents of the two stacks just after the ’4’ token has been read from the following

input string and processed by the algorithm.

"( ( ( 2 * 3 ) * ( 9 + ( ( 3 - 1 ) + 4 ) ) ) * ( 5 - 1 ) )"

17. A Queue object can be implemented using two Stack objects. Below is an outline of

how to do this. Complete the implementations of the add() and remove() methods.

The key idea is that if you push all the elements from one stack onto an empty stack,

then the items get reversed and what was the top-of-stack on the original stack becomes

the bottom of the new stack.

In the implementation below, one of the stacks is used to implement the add() method

and the other stack is for the remove() method. It should always be the case that one

of the two stacks is empty and the contents of the queue are in the other stack. By

shifting the elements from one stack to the other, you can move the front of the queue

to the top of a stack, or you can move the rear of the queue to the top of a stack.

import java.util.Stack;

public class Queue<T

{

private Stack<T forAdding = new Stack<T();

private Stack<T forRemoving = new Stack<T();

public void add(T item)

{

}

public T remove( )

{

T result = null;

return result;

}

}

18. A Stack object can be implemented using one Queue object. Below is an outline of how

to do this. Complete the implementations of the push() and pop() methods.

Hint: To pop an item from the stack, get all of the items from the queue one at a time

and put them at the rear, except for the last one which you should remove and return.

import java.util.Queue;

public class Stack<T

{

private Queue<T queue = new Queue<T();

public void push(T item)

{

}

public T pop( )

{

T result = null;

return result;

}

}

12-08-2015 at 01:11 h

Stack<String stack1 = new Stack();

Stack stack2 = new Stack<String();

2. While String is a sub-type of Object (that is, every String object “is a” Object object),

it is not true that Bag<String is a sub-type of Bag<Object. Explain why. (Hint: If

A “is a” B, then everything you can do with B you can also do with A. What can you do

with a Bag<Object that you cannot do with a Bag<String?)

3. What is wrong with the following code fragment? How do you fix it?

List<String listOfStrings = new ArrayList<String();

String s;

for (s : listOfStrings)

System.out.println(s);

4. (a) Suppose that it is an Iterator object. Write a small piece of Java code that prints

all the objects of it to System.out.

(b) Suppose that it is an Iterator object that returns Rectangle objects. Write a

small piece of Java code that inserts all the objects of it into a newly created Stack

object.

5. The following code is supposed to fill list3 with every possible sum of elements from

list1 and list2. So list3 should end up holding

{11, 12, 13, 21, 22, 23, 31, 32, 33, 41, 42, 43, 51, 52, 53}

But the code is incorrect. What is wrong? How could you fix it?

List<Integer list1 = Arrays.asList(10, 20, 30, 40, 50);

List<Integer list2 = Arrays.asList( 1, 2, 3);

List<Integer list3 = new ArrayList<Integer();

for (Iterator<Integer it1 = list1.iterator(); it1.hasNext(); )

for (Iterator<Integer it2 = list2.iterator(); it2.hasNext(); )

{

int n = it1.next();

int m = it2.next();

list3.add( n + m );

}

for (int i : list3)

System.out.print(i + " ");

System.out.println();

6. Here are three ways we might declare a generic class that holds a pair of references to

two objects of the same type. Suppose that p1, p2, and p3 are references to objects of

type Pair1<T, Pair2<T, and Pair3<T respectively. In what way can p1, p2 and p3

be used to make comparisons?

class Pair1<T extends Comparable<T

class Pair2<T extends Comparable<T implements Comparable<T

class Pair3<T extends Comparable<T implements Comparable<Pair3<T

7. Suppose we perform the following series of stack operations on a single, initially empty

stack:

push(5), push(3), pop(), push(2), push(8), pop(), pop(), push(9), push(1), pop(), push(7),

push(6), pop(), pop(), push(4), pop(), pop().

Draw a picture of the stack at the point where it contains the maximum number of

elements (be sure to indicate the top and bottom of the stack). How many of the above

operations had been performed at that point?

8. Suppose you have a stack s that contains (1 2 3), with 1 being the top-of-stack, and a

queue q that is empty. Using no other variables and only the push() and pop() stack

operations and the add() and remove() queue operations, show a sequence of operations

that leave the queue q empty and the stack s with each of the following contents.

(a) Leave the stack s with the contents (1 3 2) with 1 as top-of-stack.

(b) Leave the stack s with the contents (3 1 2) with 3 as top-of-stack.

9. Suppose we implement a stack using a partially-filled array. What is wrong with storing

the top-of-stack at location [0] and the bottom of the stack at the last used position of

the array?

10. If we use a partially-filled array to implement a queue, which is better and why? Having

the front of the queue at location [0] (and the rear at the last used position of the

array), or having the rear of the queue at location [0] (and the front at the last used

position of the array).

11. If we use a linked list with a head and a tail reference to implement a stack, which is

better and why? Having the top-of-stack at the head of the linked list, or having the

top-of-stack at the tail of the linked list?

12. If we use a linked list with a head and a tail reference to implement a queue, which is

better and why? Having the front of the queue at the head of the linked list, or having

the front of the queue at the tail of the linked list?

13. Here is an incorrect pseudo code for an algorithm which is supposed to determine whether

a String of parentheses is balanced:

boolean isBlanced( String input )

{

declare a character stack

while ( input has more characters )

{

read a character from input

if ( the character is a ’(’ )

push it on the stack

else if ( the stack is not empty )

pop a character off the stack

else

return false

}

return true

}

Give an example of an input string that is made up of only the characters ’(’ and ’)’,

is unbalanced, but for which this algorithm will return true. Explain what is wrong with

the algorithm. Can this algorithm ever incorrectly return false when its input string is

a balanced string?

14. Convert the following expression from postfix to infix notation. Use the minimum num-

ber of parentheses needed.

6 3 2 4 + - *

15. Convert the following expressions from infix to postfix notation.

1 + 2 + 3 + 4

1 + (2 + (3 + 4))

1 + (2 + 3) + 4

2 * 3 * (9 + (3 - 1) + 4) * (5 - 1)

16. Using the two stack algorithm for evaluating fully parenthesized infix expressions, draw

the contents of the two stacks just after the ’4’ token has been read from the following

input string and processed by the algorithm.

"( ( ( 2 * 3 ) * ( 9 + ( ( 3 - 1 ) + 4 ) ) ) * ( 5 - 1 ) )"

17. A Queue object can be implemented using two Stack objects. Below is an outline of

how to do this. Complete the implementations of the add() and remove() methods.

The key idea is that if you push all the elements from one stack onto an empty stack,

then the items get reversed and what was the top-of-stack on the original stack becomes

the bottom of the new stack.

In the implementation below, one of the stacks is used to implement the add() method

and the other stack is for the remove() method. It should always be the case that one

of the two stacks is empty and the contents of the queue are in the other stack. By

shifting the elements from one stack to the other, you can move the front of the queue

to the top of a stack, or you can move the rear of the queue to the top of a stack.

import java.util.Stack;

public class Queue<T

{

private Stack<T forAdding = new Stack<T();

private Stack<T forRemoving = new Stack<T();

public void add(T item)

{

}

public T remove( )

{

T result = null;

return result;

}

}

18. A Stack object can be implemented using one Queue object. Below is an outline of how

to do this. Complete the implementations of the push() and pop() methods.

Hint: To pop an item from the stack, get all of the items from the queue one at a time

and put them at the rear, except for the last one which you should remove and return.

import java.util.Queue;

public class Stack<T

{

private Queue<T queue = new Queue<T();

public void push(T item)

{

}

public T pop( )

{

T result = null;

return result;

}

}

12-08-2015 at 01:11 h

You'll get 1 file (45.3KB)