CIS2168
Fall 2010

			SECOND MIDTERM
			
The total number of points is 140.


1. (5)  Specify the data fields you would define in an implementation of 
	queues using arrays. Give the reasons and uses of each field.













2. (5)  Specify the data fields you would define in an implementation of 
	queues using single linked nodes. Give the reasons and uses of 
	each field.













3. (10) Here is an expression in infix notation.
		7 + 12 / 4 * 2 - 5
	Show the content of the operator stack as this expression
	is converted to a postfix expression














4. (10) Write the method findMin that, given a BinaryTree<E extends 
	Comparable<E>> instance, returns the smallest value in that binary tree.
	
















5. (15) In the discrete event simulation homework you had to implement a 
	priority queue to order events.
	(a) define the data members of an event (5 points)
	(b) implement the put method that inserts a new event in a priority 
	queue (10 points).
	



















6. (5)  In the discrete event simulation homework you were to determine
	the average size of queues. How did you do it (in English, not 
	code).













7. (10) We are given classes "Parent" and "Child". Child is a subclass of 
	Parent. Parent has method toString that prints out "Parent". 
	Child overrides that method to print "Child".
	We then see the code
		Parent[] a = new Parent[4];
		a[0] = new Parent(); a[1] = new Child(); 
		a[2] = a[1]; a[3] = a[2];
		for (int k = 0; k < 4; k++)
		    System.out.println(a[k]);
	What will be printed out? Explain.












8. (10) Here is some code that uses java.swing classes:
		JPanel p = new JPanel();
		JButton b = new JButton();
		b.addActionListener(this);
		p.add(b);
	(a) The last two statements both do "add". What is the difference 
	(5 points)
	(b) For b.addActionListener(this) to be valid this must .. 
	(5 points)















9. (5)  Complete as you think best the following statements: 
        (a) a referenced  element of  a  __________________, is removable 
	in O(1)
	(b) An internal  _____________ is heavily used by the JVM (Java 
	Virtual Machine) when processing recursive functions
	(c) You have random access in O(1) to every element of a   
	___________
	(d) In Java, the ________________ can be used to traverse any kind 
	of Collection, e.g. lists



10.(10) Show the binary search tree that would be built assuming the data 
	is added in the sequence:  30, 15, 25, 42, 40, 19, 17, 37, 20, 46 
	



















11.(10) Show the binary search tree that would result from the tree seen 
	in question 9 if we remove 30 and 37
	





















12.(10)	We are given an object e of class T which we know to be 
	serializable. Write code to save this object to the file "moo.dat" 
	and then to read it back as the object f [ObjectOutputStream, FileOutputStream,
	ObjectInputStream, FileInputStream,readObject, writeObject]
	



















12.(15)	Implement an iterator, without remove, for binary trees.























13.(20) A class EntryStuff that has two data fields: a String (theData) and 
	an ArrayList of integers (nums). This class implements Comparable. 
	(a) Write the class and declare its data members (5 points)
	(b) Write method equals(Object o)   (10 points)
	(c) Write method compareTo(Object o) assuming the ordering of 
	EntryStuff objects is based solely on field theData.  (5 points)