The exam will take place at 7:30pm on Thursday, October 12. Please arrive a bit early so that we can begin the exam right at 7:30. We have been assigned three rooms for this exam. Please go to the appropriate room based on the table below.
Upson 111 | all students in the accelerated stream |
Upson B17 | students in regular stream whose last name begins with A through K |
Philips 101 | students in regular stream whose last name begins with L through Z |
The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).
The exam includes material covered in lecture through October 5. The course web is in the process of being updated to show readings corresponding to the lecture topics.
The exam will attempt to gauge your knowledge and understanding of course concepts. You should understand the terms and concepts used in the course, but you shouldn't need to memorize the specific code given in the text or in lecture.
The review questions given here are not meant to exhaust the possible topics for exam questions. Check the online material and consider reviewing the lectures and homework assignments.
The great conductor Seiji Ojava has set up a rather tangled Java program with the classes and interfaces shown in Figure 1.
A skeleton code for interface C is shown below:
interface C extends A, B { ... }
Answer the following questions about this program.
- A r = new A();
- A r = new F();
- A r = (A)(new F());
- A r = new G();
- F r = new G();
- G r = new F();
- G r = (G)(new F());
- B r = new I();
Java Nagila is learning about complex numbers. She has written a class named Complex for representing complex numbers, shown on the next page. She forgot to include methods for updating the real and imaginary parts of complex numbers. Fortunately, she remembered that she could use inheritance to extend the behavior of classes, so she wrote a new class called BComplex, declared to be a subclass of Complex, that has methods for updating the real and imaginary parts of complex number. Finally, she wrote a client class that tests these classes out. These classes are shown on the next page. Unfortunately, when she went to compile and run this program, the Java compiler gave her many errors. Fortunately, you are her 211 consultant, so she immediately came to see you for help. Explain to Java Nagila the errors she made, specifying the line number of each line that needs to be fixed, explaining briefly what the error is, and showing her how to fix it. For example,
Line 6 Constructor must have same name as class name. Java is case-sensitive. So change complex to Complex.
Be sure to read the comments to figure out what Java Nagila had intended to write.
1. //class for Complex numbers 2. class Complex { 3. private float x; 4. private float y; 5. //constructor for class Complex 6. public Complex complex(float r, float i) { 7. //initialize instance variable x 8. float x = r; 9. //initialize instance variable y 10. float y = i; 11. } 12. //return real part of complex number 13. public int Re() { 14. return x;} 15. //return imaginary part of complex number 16. public int Im() { 17. return y;} 18. } 19. //subclass of Complex that includes methods for 20. //writing to real and imaginary parts of complex numbers 21. class BComplex implements Complex{ 22. //method for assigning to real part of complex number 23. public void setRe(float r){ 24. x = r; 25. return null; 26. } 27. //method for assigning to imaginary part of complex number 28. public void setIm(float i){ 29. y = i; 30. return; 31. } 32. } 33. //client class 34. class testComplex{ 35. public void main(String arg) { 37. Complex c = new BComplex(1.0f,2.0f); 38. c.setRe(3.0); 39. System.out.println(c.x); 40. System.out.println(c instanceof BComplex); 41. } 42. }
The AAI is initialized to the following values: 1st row: 2 2nd row: 5, 4 3rd row: 4, 5, 4A frequency table is computed for the AAI, i.e. how many times a particular value occurs in the AAI. In our case the frequency table computed would look like this:
Value: 0 1 2 3 4 5 Frequency: 0 0 1 0 3 2The histogram based on these frequencies would look like this:
* ** * ** 012345i.e. each "bar" in the histogram has number of "stars" equal to the frequency of the value indicated below the bar. The next few pages show skeleton code for a class called ArrayOfArrays. You need to complete this skeleton code, without modifying any code given to you, by answering 7 short questions numbered (a) through (g).
public class ArrayOfArrays { public static void main(String args[]) { // Creates an AAI which has 3 rows. int[][] values = new int[3][]; // (a) (4 points) // Write code which creates the following structure for the AAI: // 1st row of length 1, 2nd of length 2 and 3rd of length 3. // (b) (3 points) // Write code to initialize the rows of the AAI as follows: // 1st row: 2 // 2nd row: 5, 4 // 3rd row: 4, 2, 4 // Computes the frequencies and prints the histogram int[] frequencies = computeFrequencies(values); printHistogram(frequencies); // (c) (3 points) values[0] = values[2] = values[1]; // What will the following statement print? // The code for method printValues appears below. printValues(values); } //end of main method // Prints an AAI. public static void printValues(int[][] anAAI) { for (int i = 0; i < anAAI.length; i++) { for (int j = 0; j < anAAI[i].length; j++) System.out.print(anAAI[i][j]); System.out.println(); } } // (d) (3 points) // Write a method to compute the max value in a non-empty array of int. public static int findMax(int[] anIntArray) { } // end method // (e) (4 points) // Write a method to compute the max value in an AAI. public static int findMax(int[][] anAAI) { } // end method // (f) (8 points) // Write a method to compute the frequencies of values in an AAI. // Assume all values in the AAI are greater or equal to 0. // The method should return an array of int containing the frequencies. public static int[] computeFrequencies(int[][] anAAI) { } // end method // (g) (10 points) // Write a method to print the histogram, assuming that the values // in the AAI are between 0 and 9. For example, // given the present data, it should print the following: // * // ** // * ** // 012345 public static void printHistogram(int[] anIntArray) { } // end method }//end of class ArrayOfArrays
Write the body for the power method which calculates an:
public static long power (long a, in n) { /* code omitted */ }
You may assume that n > 0. Your method must calculate an
recursively in O(log n) time. No points will be awarded for solutions
which don't fit the time bound.
Using words and pictures (no Java code, pseudo-code is OK), carefully explain
how to insert an Object x into a doubly linked list given a reference to the
node before the insertion point.
Write a Java class called ArrayQueue that implements the following interface with a "circular array." You may assume that there is an upper bound (positive!) to the maximum number of elements in the queue at any one time. As long as the number of elements in the queue does not exceed the maximum, the queue should be able to be used indefinitely. You may also assume that the enqueue and dequeue operations won't fail because of overflow or underflow, respectively. You must use an array.
public interface Queue { boolean isEmpty (); // True iff queue has no elements boolean isFull (); // True iff queue has reached max size void makeEmpty (); // Removes all elements from queue void enqueue (Object x); // Adds the object to the rear of queue Object dequeue (); // Removes an object from front of queue }
1 2 3 * 4 - 12 6 / 7 * + +