UNIVERSITY OF TORONTO
Faculty of Arts and Science
DECEMBER EXAMINATIONS 1997
CSC 108F
Duration - 3 hours
Examination aids allowed: textbook only (Lewis & Loftus, Java Software
Solutions).
Check that this examination paper has 11 pages (including this cover
page and the empty back cover page).
Answer all questions in the space provided in this paper. When the
response requires you to write a program, your marks will depend on
the style of your program as well as its correctness. (However,
comments are generally not necessary.) All programs must be written in
Java.
1. [20 marks = 12 + 8]
-- -------------------
(a) Each of these program fragments contains at least one logical
or syntax error. Describe the worst error briefly. (There is intended
to be just one error in each case, but if you think you have found
more than one, judge for yourself which is worst.)
public static int f (int x) {
if (x >= 0)
return x*12.6;
else
return x/0.126;
}
// Sum 1/i**2, for i = 1, 2, ..., N
public static double invSquares (int N) {
double sum = 0;
for (int i=1; i<=N; i++)
sum += 1/(i*i);
return sum;
}
public static void m (String s) {
return ("my input is " + s);
}
and in main():
System.out.println (m("hi"));
in main():
int count;
while (true) {
s = stdin.readLine(); // Assume stdin is defined as usual.
if (s.equals("quit"))
break;
count += 1;
System.out.println(s);
}
System.out.println("number of lines read = " + count);
(b) Consider the following Java program:
import java.io.*;
public class Wow {
public static void main (String[] args) throws IOException {
DataInputStream stdin = new DataInputStream (System.in);
final int SAVE = 10;
int temp = 999;
int num = Integer.parseInt (stdin.readLine());
while (num > 0) {
if (num < temp) { //
if (num > SAVE) { //
temp = num; //
System.out.println (temp); //
} //
else //
System.out.println ("-"); //
} //
else //
System.out.println ("-"); //
num = Integer.parseInt (stdin.readLine());
}
System.out.println("RESULT: " + temp);
}
}
i) What does this program output if given the numbers 5 10 15 20 -1,
in that order, as input?
ii) What does this program output if given the numbers 20 25 5 15 -1,
in that order, as input?
iii) What does this program output if given the numbers 1000 5 2000 -
1, in that order, as input?
iv) Rewrite the two if-statements (marked by "//") with just one if-
statement that performs the exact same function.
2. [15 marks = 1 + 2 + 12]
-- -----------------------
Assume that a Fraction class has been defined as follows:
class Fraction {
private int numerator;
private int denominator;
public Fraction (int a, int b) {
numerator = a;
denominator = b;
reduce();
}
// Returns this fraction's numerator
public int getNumerator () {
return numerator;
}
// Returns this fraction's denominator;
public int getDenominator () {
return denominator;
}
// Prints this fraction.
public void print () {
System.out.println(numerator + "/" + denominator);
}
// Reduces this Fraction to its simplest form.
// For example, 6/8 would be reduced to 3/4.
public void reduce () {
// Details omitted (but you do not have to complete this method).
}
// Returns true if this Fraction equals otherFrac, and false otherwise.
public boolean equals (Fraction otherFrac) {
// Must first reduce both myself and fraction otherFrac.
reduce();
otherFrac.reduce();
// Now see if we're equal.
if (numerator == otherFrac.getNumerator() &&
denominator == otherFrac.getDenominator())
return true;
else
return false;
}
// Divides this fraction in half.
public void halve () {
denominator = denominator * 2;
reduce();
}
}
(a) What variables does the method reduce have to examine and
possibly change?
(b) How can the equals method compare two Fractions for equality
when it only has one Fraction parameter?
(c) For each code fragment below, circle the right answer to
indicate whether it will run successfully or produce an error message.
If it runs successfully, state what the output will be. If it produces
an error message, explain the problem (but do not simply give the
contents of the error message).
Fraction f1 = new Fraction(3, 5);
Fraction f2 = new Fraction(3, 5);
Fraction f3 = f1;
if (f1 == f2)
System.out.println("alpha");
if (f1 == f3)
System.out.println("beta");
if (f1.equals(f2))
System.out.println("gamma");
if (f1.equals(f3))
System.out.println("delta");
Runs successfully
Produces an error message
Fraction[] list;
list = new Fraction[15];
System.out.print("The numerators are: ");
for (int i=0; i<15; i++)
System.out.print(list[i].getNumerator());
Runs successfully
Produces an error message
Fraction apple = new Fraction (1, 2);
Fraction peach = new Fraction (4, 5);
Fraction pear = apple;
peach.halve();
pear.halve();
apple.print();
peach.print();
pear.print();
Runs successfully
Produces an error message
3. [20 marks = 10 + 10]
-- --------------------
(a) Consider a two-dimensional array that contains integers in a
triangular pattern. The array is square, but only a triangular part is
used, as in this example:
2
1 7
3 6 8
4 2 5 3
Write a method that sums the numbers along the perimeter of the
triangle - the first column, the bottom row and the diagonal. In our
example, the sum is:
2 + 1 + 3 + 4 + 2 + 5 + 3 + 8 + 7 = 35.
The first line of the method is given below. Notice that the method
takes just one argument, the array itself. The array is square, and
its length is the number of rows and columns.
public static int perimeterSum (int[][] A) {
// You write the rest:
(b) An increasing array of integers is an array in which every
element is greater than the one before it.
i) Which of the following are increasing arrays of integers? Circle
the correct answers.
(1, 4, 5, 7) increasing not increasing
(10) increasing not increasing
(4, 3, 2, 1) increasing not increasing
(1, 4, 4, 6) increasing not increasing
(-1, 0, 3) increasing not increasing
(-10, -5, -8) increasing not increasing
ii) Write a Java method that determines if an array of integers is an
increasing array of integers. Its only parameter should be an array of
integers. It should return a boolean value of true if the array is
increasing, and false otherwise. You can assume that the array has
been initialized appropriately. (You do not have to write the entire
program - only one method.)
4. [15 marks = 1 + 2 + 3 + 6 + 3]
-- ------------------------------
Here are a Person class and the beginnings of a FamilyInfo class:
class Person {
public String name; // Assume this field is unique for every Person.
public int birthYear;
public String mother;
public String father;
}
// FamilyInfo class: keeps track of people in a family.
// The data structure used is an array of Persons.
class FamilyInfo {
private Person[] list;
private int familySize; // # of people currently in this list
// Other methods not shown here would include methods to build a
// FamilyInfo, methods for adding new Persons to it, and methods
// for searching and printing it.
// Returns the integer index in our list of the Person with the
// given 'name', or -1 if that Person isn't in our list.
private int find (String name) {
// Details omitted.
}
// Prints the given 'name' and the names of all that Person's maternal
// ancestors stored in this FamilyInfo. That is, prints the mother,
// grandmother, great grandmother, and so on, until we have no more
// information. (After all, we only have information on a finite number
// of people).
public void printMaternalAncestors (String name) {
// Details omitted.
}
}
(a) What kind of variable is "list"? Circle the correct choice.
instance variable class variable
(b) The variable list should not be (and is not) declared public. Why not?
(c) Say that we have instantiated (created) a FamilyInfo variable
"myFamily" and stored the following information into it (using methods
not shown here):
* Peter was born in 1958, and his parents were Katie and Inman.
* Inman was born in 1931 and his parents were Lois and William.
We have no further information about Katie, Lois, or William.
Draw a diagram showing the contents of the myFamily object at this
stage.
(d) Fill in the body of the printMaternalAncestors. Assume that
the method find has already been written and use it to help you. Your
method can stop printing maternal ancestors when it encounters an
ancestor not found in the list.
(e) If we had a FamilyInfo containing k people and we called
printMaternalAncestors, what is the greatest number of times that the
find method might have to be called?
Consider a single call to the find method. If the FamilyInfo has k
people in it, what is the greatest number of elements of list that
might have to be examined?
5. [10 marks]
-- ----------
Complete this main( ) method to read a list of integers, ending with -1.
Print the second-largest integer in the list.
The list cannot contain -1, but it may contain other negative
integers. If the largest value appears twice in the list, then that
value is both the largest and the second-largest. If there are fewer
than 2 items in the list, your program should print an error message.
public static void main (String[] args) throws IOException {