CS100, Spring 2000, Review Questions for Prelim 1

Notes:
+ Conciseness, clarity, and style all count.
+ Arrays are NOT allowed.
+ You must use the $while$ loop: $do$-$while$ and $for$ loops are NOT allowed.
+ These are review questions.  
  + Taken as a whole, this set of questions is too long for a prelim.
  + Some questions may be too hard or too long for a prelim question.
+ As always, actually *do* the questions yourself for the most benefit:
  Only watching someone else solve them or reading the solutions is unlikely
  to be very helpful.
+ On Prelim 1, we will provide "blanks" and "boxes" for you to fill in, e.g.

    public class Q1 {
        public static void main(String[] args) {
            TokenReader in = new TokenReader(System.in);

            int next = _______________________ ; // next value to process

            // read a sequence of grades (terminated by -1); print the average
            +---------------------------------------------------------------+
            |                                                               |
            |                                                               |
            +---------------------------------------------------------------+
        }
    }

  (On Prelim 1, we will always provide the first three lines and the
  corresponding two closing braces.)

  You may NOT alter the surrounding "structure" when we do so.


1. Trace the code segment below using our tabular format with one assignment
   statement per column and heavy lines drawn for each test of the loop test.
   Also, clearly indicate any output.

    int a, c;
    double bb;
    a = 1;
    c = 4;
    while (c<10)
        if (a<8) {
            bb = (9.0*a*c) / (10*a-c);
            if (bb == (int) bb && bb<10)
                System.out.println
                    ((10*a+bb) + "/" + (10*bb+c) + " = " + a + "/" + c);
            a = a+a;
        } else {
            a = 1;
            c = 3*c - 7;
        }

2. Write a code segment to "rotate" the contents of variables a, b, c 
   using auxiliary variable tmp.

     a --> b --> c   e.g.  a=2, b=3, c=7  becomes  a=7, b=2, c=3
     ^\_________/
    
   Use only assignment statements.

3. Use (something equivalent) to the rules below to write a program to:
   (1) Read in the year.  
   (2) Print whether it is a leap year.

   Rule 1. A non-multiple of 4 is not a leap year.
   Rule 2. A multiple of 4 is a leap year.
   Rule 3. Rule 2 does not apply to multiples of 100.
   Rule 4. Rule 3 does not apply to multiples of 400.

4. What is the template for processing an input sequence with a stopping value?

5. Write a program to print the effective resistance of a number of resistors
   arranged in parallel:
   (1) Read in a non-negative integer $n$.  This is the number of resistors.
   (2) Read in $n$ resistances (in ohms) R1, R2, ..., Rn.
   (3) Print the effective resistance R.  Use the formula

        1/R = 1/R1 + 1/R2 + ... + 1/Rn.

6. Write a program to:
   (1) Read a *non-decreasing* sequence of grades; 
       the sequence is terminated by -1.
   (2) Print the number of unique values.

7. Write two programs, (a) and (b), to:
   (1) Read a sequence of non-zero integers; the sequence is terminated by 0.
   (2) Print the "second largest value" --

   (a) Print the second largest distinct value.
       ("Throw out duplicates.  Sort.  Choose the number in 2nd place.")

   (b) Print the second largest list element.
       ("Do NOT throw out duplicates.  Sort.  Choose the number in 2nd place.")

   HINT: Keep track of the largest and 2nd largest so far.

8. [This question is a little hard, but shouldn't be bad if you use the hint.]

   Write a program to:
   (1) Read a sequence of non-zero integers; the sequence is terminated by 0.
   (2) Print out the maximum sum of a subsequence.

       Consider both allowing an empty subsequence containing 0 numbers
       and disallowing an empty subsequence.

   Example: 3 18 -100 20 -10 37 0 has a max subsequence sum of 20-10+37 = 47.

   HINT: Keep track of both 
   (a) The maximum subsequence sum seen so far, and
   (b) The maximum subsequence sum seen so far of a subsequence 
       containing/ending-on the previous value.