Assigned Mar 10th 1pm
Due Mar 15th, 8am
Read all questions before beginning. You will have 48 hours from when you begin this exam until
you must finish working. The exam must be completed by 8am March 15th, 2010.
You are not allowed to use the internet in general for this exam, only what
is linked from this page and the Java API. You may use the computer to compile and test
your Java code. You are bound by the Honor Code for this exam, which you need to sign.
Show your work on all problems for full credit.
Create a directory on the cs.centenary.edu server called exam1, and
copy your solutions there. Turn in the answers to Questions 3 and 4 under my door, with your
signature and the honor code for the whole exam.
Question 1
Implement a version of the Stack<E> interface using one ArrayQueue<E> as your only
data member. You can use the files Queue.java,
Stack.java and ArrayQueue.java
from the book code. You should turn in a file called
QStack.java, of which the basic
template is provided for you.
Question 2
Using an ArrayStack, write a static method called isMatch(String s) in the Java file called
MatchingParens.java. This method
brings in a String and will return
true if every left parenthesis has a matching right bracket, and they are properly
nested, otherwise return false. When you encounter a left parenthesis, push it on the
Stack, and when you encounter a right parenthesis, it must match the top of the Stack and pop it off or the
String is invalid. The parenthesis you must test are "<" and ">",
"(" and ")", "{" and "}", and "[" and "]". Your code should work correctly on the test cases
provided. You must add two cases of your own, one which should return true, one which
should return false.
Question 3
Draw the state of the ArrayQueue q after executing all of the following commands, using the ArrayQueue code given
above. You should do this by hand, not using the computer to find the answer. Note that this is
a slightly different implementation than what we did in class. Show the state after each
command for full credit.
ArrayQueue q = new ArrayQueue();
q.add(5);
q.add(9);
q.add(4);
q.remove();
q.add(17);
q.add(58);
q.add(47);
q.remove();
q.remove();
q.remove();
q.add(5);
Question 4
Draw the state of the memory in Java after executing the following commands with the ListNode
class. You should do this by hand, not using the computer to find the answer. Show the state after each
command for full credit.
ListNode front = new ListNode(4, null);
ListNode temp = front;
front = new ListNode(8, front);
front = new ListNode(16, front);
front.getNext().setNext(front.getNext());
front.getNext().getNext().getNext().getNext().setNext(new ListNode(23, null));
front.setNext(front.getNext().getNext());
temp.setNext(front);
front = temp;