ITI 1121 Study Guide - Final Guide: Exception Handling, Abstract Data Type, Stack Trace
24 Oct 2018
School
Department
Course
Professor
Université d’Ottawa
Faculté de génie
École d’ingénierie et de
technologie de l’information
University of Ottawa
Faculty of Engineering
School of Information
Technology and Engineering
Introduction to Computer Science II (ITI 1121)
Final Examination: Solutions
Instructor: Marcel Turcotte
April 2008, duration: 3 hours
Identification
Student name:
Student number: Signature:
Instructions
1. This is a closed book examination;
2. No calculators or other aids are permitted;
3. Write comments and assumptions to get partial points;
4. Beware, poor hand writing can affect grades;
5. Do not remove the staple holding the examination pages together;
6. Write your answers in the space provided. Use the backs of pages if necessary.
There are two blank pages at the end. You may not hand in additional pages.
Marking scheme
Question Points Score
1 10
2 15
3 15
4 10
5 5
6 10
7 15
8 10
Total 90
April 2008 ITI 1121 Page 2 of 25
Question 1 (10 points)
For this question, the classes Queue and Stack both implement the interface LinearCollection.
+add(E item):void
+remove():E
+isEmpty():boolean
«interface»
LinearCollection<E>
Queue<E> Stack<E>
Queue, as all the other implementations of a queue, is such that the method add enqueues the
item at the rear of the queue, the method remove dequeues the front element, and the method
isEmpty returns true if this queue contains no elements.
Stack, as all the other implementations of a stack, is such that the method add pushes the
item onto the top of the stack, the method remove pops (removes and returns) the top element,
and the method isEmpty returns true if this stack contains no elements.
ABinarySearchTree was created by adding ele-
ments in the order that follows; the resulting tree
is shown to the right.
BinarySearchTree<Integer> t;
t = new BinarySearchTree<Integer>();
t.add( 3 );
t.add( 1 );
t.add( 7 );
t.add( 9 );
t.add( 5 );
t.add( 4 );
t.add( 6 );
t.add( 2 );
t.add( 8 );
3
7
4 6
5
8
9
2
1
A. Circle the answer that corresponds
to the following method call:
t.traverse( new Queue< Node<Integer> >() );
A. 123456789
B. 214658973
C. 234558973
D. 3 1 7 2 5 9 4 6 8
E. 312754698
F. 371952864
G. 379856412
H. 864952713
I. 987654321
B. Circle the answer that corresponds
to the following method call:
t.traverse( new Stack< Node<Integer> >() );
A. 123456789
B. 214658973
C. 234558973
D. 317259468
E. 312754698
F. 371952864
G. 3 7 9 8 5 6 4 1 2
H. 864952713
I. 987654321
The source code for the method traverse can be found on the next page.
April 2008 ITI 1121 Page 3 of 25
public class BinarySearchTree< E extends Comparable<E> > {
private static class Node<T> {
private T value;
private Node<T> left = null;
private Node<T> right = null;
private Node( T value ) {
this.value = value;
}
}
private Node<E> root = null;
public void traverse( LinearCollection< Node<E> > store ) {
if ( root != null ) {
store.add( root );
while ( ! store.isEmpty() ) {
Node<E> current = store.remove();
System.out.print( " " + current.value );
if ( current.left != null ) {
store.add( current.left );
}
if ( current.right != null ) {
store.add( current.right );
}
}
System.out.println();
}
}
public boolean add( E obj ) { ... }
}
Document Summary
There are two blank pages at the end. Universit d"ottawafacult de g nie cole d"ing nierie et detechnologie de l"informationuniversity of ottawafaculty of engineeringschool of informationtechnology and engineeringapril 2008. For this question, the classes queue and stack both implement the interface linearcollection. A binarysearchtree was created by adding ele- ments in the order that follows; the resulting tree is shown to the right. The source code for the method traverse can be found on the next page. System. out. print( " " + current. value ); if ( current. left != null ) { store. add( current. left ); if ( current. right != null ) { store. add( current. right ); System. out. println(); public boolean add( e obj ) { } The abstract data type deque pronounced deck combines features of both a queue and a stack. In particular, a deque ( double-ended queue ) allows for: e cient insertions at the front or rear, e cient deletions at the front or the rear.
