1. Multiple choice question (Total of 10 marks, 2 marks each)
i. Which of the following stack operations could throw an EmptyStackException?
a) isEmpty()
b) push( Object o )
c) pop()
d) two or more of the above answers.
ii. A parentheses balancing program would be best implemented using a:
a) A queue
b) A stack
c) A list
d) Any of the above
iii. If the characters 'Z', 'Y', 'X', and 'W' are placed in a queue (in that order, Z first, Y second etc), and then removed one at a time, in what order will they be removed?
a) W X Z Y
b) Z Y W X
c) Z Y X W
d) W X Y Z
iv. What is the time complexity of the following program fragment:
for (int i=0; i<n; i++)
for (int j=0; j<i; j++)
magic = magic + j;
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)
v. Suppose you were implementing a singly-linked list with element tail which refers to the last node in the list. Each node object includes a
private Node next;
reference which refers to the next node in the list. Below is some (correct) code that inserts a node at the end of the list.
x = new Node( 'A', null);
tail.setNext( x );
tail = x;
Under which of the following conditions would it fail?
a) The list is empty
b) The list has exactly one node
c) The list has exactly two nodes
d) More than one of the above
e) None of the above (the code does not fail in any of these cases)
2. (a) What is the main advantage of using a Vector instead of an Array? (6 marks)
You don’t have to specify the size of the Vector when you create it; space is dynamically allocated.
(b) Give one important advantage from being able to define your own exception classes in Java? (6 marks)
You can write your own handler for dealing with situations that shouldn’t occur but it is better to gracefully handle it then let the program crash.
(c) Describe one important advantage of using design patterns in your programs. (6 marks)
It will be easier for other programmers to understand your program as you can document your code using the pattern. Furthermore, you will have a solution that you know others have used before and that it works.
3. Give one real world example problem of where a LIFO data structure could be used and one example problem of where a FIFO data structure could be used (8 marks)
LIFO: Last In First Out e.g. stack, the parenthesis problem or postfix calculations
FIFO: First In First Out e.g. queue, passengers checking in for a flight, events to be processed by a user interface.
4. Analyze the running time of the following piece of code (show your work): (10 marks)
int BinarySearch (int[] a, int x) {
int left = 0;
int right = a.length -1;
while (left<=right) {
int mid = (left+right)/2;
if (a[mid] == x) return mid;
else if (x < a[mid]) right = mid-1;
else left = mid+1;
}
return –1;
}
This is a binary search algorithm. Each time through the while loop, the number of elements to be searched is half of what it was in the previous iteration. Therefore the running time is O(log n).
5. Describe in words what the following algorithm does: (8 marks)
int sum(int k) {
if (k==1) return 1;
else return sum(k-1) + k;
}
Pseudocode/code and program understanding style questions:
7. For a doubly linked-list data structure, write a pseudocode method add(Object o, int index) which takes the object to insert into the data field and an index which is the number of the element after insertion (indexed from zero, like an array). If there are fewer elements in the linked list than index, then your routine should add the new node to the end of the list. Clearly state any assumptions that you make. (20 marks)
2 marks: Create new node with Object o as node data
6 marks: move through doubly linked-list correctly to find correct position for node insertion
6 marks: insert node correctly at that position, managing next and previous pointers correctly
6 marks: correctly handling the case where index for insertion is greater than the number of nodes in the list
// should be pseudocode….
public void add(Object o, int index) {
// for a doubly linked data structure we can assume we have at least
// the following reference in our class:
// Dnode first , Dnode last (we don’t really need last …)
//CREATE NEW NODE
Dnode temp = new Dnode(o);
Dnode curr = first;
//CHECK IF LIST IS EMPTY
if (curr == null) {
first = temp;
last = temp;
return;
}
//MOVE TO CORRECT POSITION
for (int i = 0; i++; i<index) {
if ( curr == null ) {
//moved off the end of the list
last.next = temp;
temp.prev = last;
last = temp;
return;
} else {
curr= curr.getNext();
}
}
//INSERT ELEMENT
temp.prev = curr.prev;
curr.prev.next = temp;
temp.next = curr;
curr.prev = temp;
}
8. The following piece of code iteratively calculates n! (i.e. n factorial, 1*2*3….*n): (8 marks)
public int factorial(int n){
int result = 1;
for (int i = 1; i<=n; i++){
result = result*i;
}
return result;
}
The following is an attempt at a recursive implementation for n! but it is not correct! Explain what is wrong and show how to fix it:
public int factorial(int n) {
if (n == 1) {
return 1
}
return n*factorial(n-1);
}
Needed to add a base case for the recursion to work – otherwise it will run forever.
9. See the following segment of the TreeMap.java code we covered in class. Show how you rewrite the preorder iterator as a postorder iterator: (12 marks)
private class PreOrderIterator implements Enumeration {
private int curNode;
private Vector pre;
private Vector post;
private int curSize;
public PreOrderIterator() {
pre = new Vector();
post = new Vector();
curNode = 0;
curSize = 0;
preorder(root);
curNode = 0;
}
private void preorder(TreeNode t) {
if (t != null) {
pre.add(t);
curNode++; curSize++;
Vector children = t.getChildren();
for (int i=0; i<children.size(); i++) {
TreeNode child = (TreeNode)children.elementAt(i);
preorder(child);
}
}
}
public boolean hasMoreElements() {
return curNode < curSize;
}
public Object nextElement() {
return pre.elementAt(curNode++);
}
} // end private class
private void postorder(TreeNode t) {
if (t != null) {
Vector children = t.getChildren();
for (int i=0; i<children.size(); i++) {
TreeNode child = (TreeNode)children.elementAt(i);
postorder(child);
}
post.add(t);
curSize++;
}
}
Bonus Question (max. 5 marks): What is the time complexity of bubble sort using an array based implementation? Justify your answer.
a) O(n log n)
b) O(n2)
c) O(n3)
d)
O(n)
O(n2) – include justification for full marks