CPSC 124, Winter 1998

Quiz Number 6


This is the sixth quiz given in CPSC 124: Introductory Programming, Winter 1998. See the information page for that course for more information.

The answers given here are sample answers that would receive full credit. However, they are not necessarily the only correct answers.


Question 1: Carefully explain all the steps that the computer takes when it executes the statement:

int[] list = new int[42];

Answer: The computer creates an array, initializes it, creates a variable, and stores a reference to the array in the variable. More precisely, the computer performs the following four steps (not necessarily in exactly this order):

  1. Space is allocated on the heap for an array of 42 integers.
  2. Each of the 42 spaces in the array is initialized to zero.
  3. Space is allocated for a variable of type int[], which is named "list."
  4. A pointer to the newly created array is stored as the initial value of the variable, list.

Question 2: How would insertion sort be used to sort the following list of five numbers? Show what the list would look like after each phase, and explain briefly:

           25  12  73  6  31

Answer:

           25  12  73   6  31
           12  25  73   6  31
           12  25  73   6  31
            6  12  25  73  31
            6  12  25  31  73

The initial array is shown on the first line above. Each line after that shows how the array looks after the next phase of insertion sort. The part of the array that is known to be sorted in each step is shown in blue. In each step, the next number in the unsorted part of the list is inserted into its correct position in the sorted part of the list. (The numbers inserted in the second, third, fourth, and fifth lines above are 12, 73, 6, and 31, respectively.)


Question 3: Complete the following subroutine so that it will search a given array, A, for a given number, item. Return true if the item is found, false otherwise.

           static boolean searchFor(int[] A, int item) {

           }  // end of subroutine searchFor()

Answer: The completed subroutine looks like this:

           static boolean searchFor(int[] A, int item) {

               for (int i = 0; i < A.length; i++) {
                   if (A[i] == item)
                      return true;    // item was found (in position i in the array)
               }

               return false;   // The entire array has been searched without finding
                               // the item.

           }  // end of subroutine searchFor()

Question 4: Suppose that the classes Employee and Date are defined as follows:

            class Employee {                      class Date {
               String name;                          int month;   // from 1 to 12
               double hourlyWage;                    int day;     // from 1 to 31
               Date dateOfBirth;                     int year;    // from 1901 to 2099
            }                                     }

Consider an array, emp:

           Employee emp = new Employee[1000];

Suppose this array has already been filled with data about 1000 employees. Write a code segment that will count the number of employees who earn more than 25.00 per hour.

Answer: Note that the data for employee number i is stored in emp[i]. In particular, the hourly wage for employee i is emp[i].hourlyWage. The number of employees with hourly wage greater than $25.00 can be determined as follows:

              int count = 0;
              for (int i = 0; i < 1000; i++) {
                  if (emp[i].hourlyWage > 25)
                      count++;
              }

Question 5: Using the same setup as in the previous problem, write a code segment that will print out the name of each employee whose birthday is today, March 4. (That is, the employee's month of birth is 3 and day of birth is 4. Note that the year of birth is not relevant.)

Answer: The date of birth for employee number i is emp[i].dateOfBirth, so the month in which that employee was born is emp[i].dateOfBirth.month, and the day of the month is emp[i].dateOfBirth.day. So the following code will find all employees whose birthday is March 4:

           for (int i = 0; i < 1000; i++) {
               if ( emp[i].dateOfBirth.month == 3
                          && emp[i].dateOfBirth.day == 4 )
                  console.putln("Happy Birthday, " + emp[i].name);
           }

David Eck, 5 March 1998