SAMPLE PRELIM 1 – CS100J – FALL 2002

 

Question 1  Trace the sequence of assignments to variables made by the program segment given below when it is run with input data 5.  Repeated assignments of the same value to a variable should be repeated in the table.  You may not need all of the table columns that have been provided.

Assume that variable in has been declared such that expression in.readInt() inputs one integer value.   

int p = in.readInt();

int d = 0;

int n = 0;

while ( p  > 1 ){

d = 2;

while ( (p % d) != 0 ) d = d + 1;

if ( d == p ) n = n + 1;

p = p - 1;

      }

System.out.println(n);

 

time ΰ  

p

?

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

d

?

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n

?

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

––––––––––––––––––––-Solution To Question 1:––––––––-––––––––––––––

 

 

time ΰ  

p

?

5

 

 

 

 

 

 

 

4

 

3

 

 

 

2

 

 

1

 

 

 

 

d

?

 

0

 

2

3

4

5

 

 

2

 

2

3

 

 

2

 

 

 

 

 

 

n

?

 

 

0

 

 

 

 

1

 

 

 

 

 

2

 

 

3

 

 

 

 

 

 

 

 

–––––––––––––––––––––––––––––––––––––––––––-––––––––-––––––––––––––

 

 

–––––––––––––––––––––––––––––––––––––––––––-––––––––-––––––––––––––

Question 2  Complete the program segment according to the following input/output specification.

Input. The input of your program consists of two or more positive integers terminated by a -1.  The positive integers specify one or more runs, where a run is an sequence that begins and ends with the same value.  In particular, the first integer of the first run (if there is at least one run) is given by the first integer in the input; the remaining values of the first run are given by subsequent integers up until the first integer of the run is repeated. The first integer of the second run (if there is a second run) is given by the next integer, and so on.

Here is some sample input consisting of three runs of length 5, 4, and 2, respectively.

10 50 50 20 10

50 60 75 50

50 50

-1 -1

Notice that runs are as short as possible, e.g., we do NOT say that the above input consists of two runs of lengths 5 and 6, respectively.  Assume that the input is well formed, i.e., no run is left open (e.g., 10 -1).

Output.  Output the number of runs and the average length run (rounded to the nearest whole number). For the sample input given above, the output would be:

Number of runs: 3

Average run length: 4

-------------------------------------------------------------------------------------------------------------------------------------------

TokenReader in = new TokenReader(System.in);

int first = in.readInt();     // first integer of the current run.

int next = in.readInt();      // next integer of the current run.

int length = 2;               // length of the current run so far.

int sum = 0;                  // total length of completed runs so far.

int nRuns = 0;                // number of completed runs so far.

 

while ( ________________________________________ ) {

 

if (_______________________________________________) {

 

 

 

 

 

 

 

 

 

  

      }

      else {

 

 

 

 

 

 

 

 

 

 

      }

      next = in.readInt();

}

 

System.out.println( _______________________________________________________ );

 

System.out.println( _______________________________________________________ );

 

 

––––––––––––––––––––-Solution To Question 2:––––––––-––––––––––––––

 

 

while ( first != -1 && next != -1 ){

 

if ( next != first ) {

 

 

length++;

 

 

 

 

 

 

  

      }

      else {

 

 

nRuns++;

sum += length;

first = in.readInt();

length = 2;

 

 

 

 

      }

      next = in.readInt();

}

 

System.out.println( "Number of runs: " + nRuns );

 

System.out.println( "Av. run length: " ++ Math.round( (double)sum/nRuns) );

 

 

–––––––––––––––––––––––––––––––––––––––––––-––––––––-––––––––––––––

 

Question 3  Complete the program segment according to the following input/output specification.

 

Input.  The input consists of a non-negative integer n followed by n additional non-negative integers.  For example,

4 5 3 0 2

Output. Output n lines of stars (*'s), where the number of *'s in a line is given by the corresponding integer in the input.  For example, for the input given, the output would be:

*****

***

<a blank line>

**

-----------------------------------------------------------------------------------------------------------------------------------------------

TokenReader in = new TokenReader(System.in);

 

int n = in.readInt();   // number of lines of output requested.

 

// other declarations

 

 

 

 

 

 

 

// statements

 

 

 

 

 

 

 

 

 

 

 

 

 

 

––––––––––––––––––––-Solution To Question 3:––––––––-––––––––––––––

 

 

TokenReader in = new TokenReader(System.in);

 

int n = in.readInt();   // number of lines of output requested.

 

// other declarations

 

int stars;

 

 

// statements

 

while ( n > 0 ){

     stars = in.readInt();

     while ( stars > 0 ) {

           System.out.print("*");

           stars–-;

     }

     System.out.println();

     n–-;

}

 

 

 

 

 

––––––––––––-–––––-Another Solution To Question 3:–––––––-–––-–––––

 

 

TokenReader in = new TokenReader(System.in);

 

int n = in.readInt();   // number of lines of output requested.

 

// other declarations

 

int line = 1;

int j, stars;

 

 

// statements

 

while ( line <=n ){

     stars = in.readInt();

     j = 1;

while ( j <= stars ) {

           System.out.print("*");

           j++;

     }

     System.out.println();

     line++;

}

 

 

 

–––––––––––––––––––––––––––––––––––––––––––-––––––––-––––––––––––––

 

 

Question 4 

a) Draw a picture of the "world,” i.e., all objects, variables and methods at the moment the following program reaches the line indicated. Use the diagramming technique illustrated in lecture:

·                                 ·         Draw objects as rectangles with dashed borders containing the object's instance variables.

·                                 ·         Each object should contain two compartments separated by a dashed line.

·                                 ·         The upper compartment should contain the object's instance variables; the lower compartment should show the object's instance methods.

·                                 ·         Each variable should be drawn as a solid rectangle.  The name of the variable should appear to the left of the rectangle, and the contents of the variable should be written in the rectangle.

·                                 ·         Draw object references as arrows pointing to the objects to which they refer.


b) What is the output of method "main" below?

public class Q1 {
    private static int a = 1;
    private int b;
    private Q1 c = null;

    public Q1() {
        b = a;
        a = 2*a;
    }

    public String toString() {
        String s = "null";
        if (c != null) s = "" + c.b;
        return a + " " + b + " " + s;
    }

    public void magic(int a) {
        Q1 now = this;
        while (now != null) {
            System.out.println(a + " " + now);
            now = now.c;
        }
    }

    public static void main (String[] args) {
        Q1 a = new Q1();
        Q1 b = new Q1();
        Q1 c = new Q1();
        c = a;
        a.c = b;
        c.c.b++;
    // draw a picture of "the world" as it exists at THIS LINE
        c.magic(7);
    }
}

––––––––––––––––––––-Solution To Question 4:––––––––-––––––––––––––

 

 

8
 

int a
 
4a)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q1 c

 

 

 

4b)

 

7 8 1 3

7 8 3 null

Question 5 

a) In the code for Q4 above, label each variable declaration with a unique integer.  Then label each variable use throughout the code with the integer of the corresponding declaration.  This will illustrate your understanding of the scope of names in Java.

b) Does method "toString()" above return a value or print a value?  How --Java willing-- would you change the code for method "toString()" to make it do the other (print instead of return or vice versa)?

c) Define the term "class".

d) Define the term "method".

e) Explain the difference between public and private.

f) Explain the differences between static and non-static.

––––––––––––––––––––-Solution To Question 5:––––––––-––––––––––––––

 

5 a)

There is a * beside the number if it is a declaration.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 



5b) Returns a value.

To print then put System.out.println(“asdf”) and remove return type.

 

 

 

5c) Class is a named group of declarations and methods

 

 

 

5d) Method is a parameterized group of declarations and statements

 

 



5e) Private and public are visibility modifiers for fields. Private fields are not visible outside of the class definition and public fields are visible outside of the class definition.

 

 

 

 

 

5f) Static fields - there is only one instance of this field no matter how many class instances are created. Non static – there is an instance of this field for each class instance.

 Question 6 

a) What is the pattern for repeatedly doing something N times?  The pattern for processing an input sequence of pairs of values terminated by a pair of stopping values?

b) Androids Trurl and Klapaucius perform a random walk on a grid.  Both begin at square (0,0).  At each step, they independently move one square to the right and one square up or down, e.g., from (0,0), each android will move independently to either (1,1) or (1,-1).  Trurl's probability of moving up is 60%; Klapaucius' probability of moving is 45%.

Write a code segment to simulate 200 steps of their random walk and count how many times they meet during their walk (how often they are standing on the same square).  Output this number to the screen.  Do not include their starting position in your count.

HINT: The expression Math.random() <= 0.4 will be true with probability 40%.  Function Math.random() returns a random number strictly between 0.0 and 1.0.

 

6a)

set a counter to 0

while(the counter is less than N)

{

          increment counter by one

}
 

read in to value1

read in to value2

 

while(value1 != stopping value and value2 != stopping value)

{

          do some stuff;

          read in to value1

          read in to value2

}
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 



6b)

int N = 200; // Max number of iterations for the loop

int counter =  0; // This keeps track of the number of iterations through the loop

 

// This keeps track of the number of times the droids have met

int met = 0;

 

// These keep track of the y position of the droid

int droid1y = 0;

int droid2y = 0;

 

// Loop N times and get the number of times the droids meet

while(counter < N)

{

                // Check to see if Trurl moves up or down

                if(Math.random() <= 0.60)

                                droid1y += 1;

                else

                                droid1y -= 1;

 

                // Check to see if Klapaucius moves up or down

                if(Math.random() <= 0.45)

                                droid2y += 1;

                else

                                droid2y -= 1;

 

                // Check to see if they are now in the same position

                // Don’t check x because it is always the same (same right speed)

                if(droid1y == droid2y)

                                met++;

 

counter = counter + 1;

}

System.out.println(“They met “ + met + “times”);