CSC 122: Computer Science II, Fall 2005

Exam 1 Sample Questions and Solutions

1. Consider the following array:
   

   16

   8

   11

   4

   5

   2

   9

   13

   
   Show the results of running selection sort on this array. Show the first two passes through selection sort.
   

   2	8	11	4	5	16	9	13
   2	4	11	8	5	16	9	13

2. Show the results of running bubble sort on the original array from question #1. Show the results of the first two passes.
   

   8	11	4	5	2	9	13	16
   8	4	5	2	9	11	13	16

3. Answer the following questions about sorting. For all parts, assume that running time includes comparisons between items in the array and swaps or assignments for values in the array.
   1. Show an array that would result in the best running time for bubble sort.
      

      2

      4

      6

      8

      10

      12

   2. Show an array that would result in the worst running time for insertion sort.
      

      9

      8

      7

      6

      5

      4

4. Consider the following code fragment:

   for ( int i = 0; i < n - 1; i++ ) {
       for ( int j = 0; j < n - 1; j++ ) {
           System.out.println( "Hello!" );
       }
   }
   

   How many "Hello!"s are printed? Give an exact answer (in terms of n) as well as an answer in O( ) notation.

   Exact: (n-1)*(n-1)
   O(n²)
5. What is the O( ) of the following expressions? Explain your answers.
   1. n³ + 10n² + 100n + 1000
      
      O(n³)
   2. n lg n + n² + 10
      
      O(n²)

6. Consider the following function.

   public void mystery( int n, int m ) {
     if ( m > n ) {
       System.out.print( m + " " );
       mystery( m – 1, n );
     }
     else if ( m < n ) {
       System.out.print( n + " " );
       mystery( m + 1, n );
     }
     else
       System.out.println( "Done" );
   }
   

   What is the output for each of the following method calls:

   1. mystery( 1, 3 )?
      3 2 Done
   2. mystery( 3, 3 )?
      Done
   3. mystery( 5, 3 )?
      5 5 Done
   4. mystery( 1, 5 )?
      5 4 4 3 Done

7. Write a Java method called printStars that takes one integer parameter called n. The method should display a single line of n stars ('*') on the screen. To receive full credit, the function must be written recursively. Little to no credit will be given for a non-recursive solution. For example, printStars( 5 ) would print ***** to the screen.

   public void printStars(int n)
   {
       if (n>0) {
           System.out.print("*");
           printStars(n-1);
       }
       System.out.println();
   }
   	

8. Write a Java method called calcProduct that takes two integer parameters, m and n. The method should return the product of all the integers from m to n inclusive. To receive full credit, the method must be written recursively. Little to no credit will be given for a non-recursive solution. For example, calcproduct( 5, 3 ) should return 60 (5 x 4 x 3). You cannot assume that the parameters are in any particular order.

   public int calcProduct(int m, int n)
   {
       int prod;
       if (m == n) {
           prod = m;
       }
       else if(m < n) {
           prod = m * calcProduct(m+1, n);
       }
       else {
           prod = n * calcProduct(m, n+1);
       }
       return prod;
   }
   	

Questions, short answer and otherwise, could also be asked about the following topics:

• Greedy algorithms
• Divide-and-Conquer algorithms
• The advantages of Unit Testing
• Searching
• O(n log n) sorting algorithms
• Recurrence equations
• Loop invariant (informal)

The exam will be closed-book, closed-notes. It will be designed to be completed in 1 hour, It will be held Wednesday, September 28 from 7:00-9:00 pm in Julian 111.

DePauw University, Computer Science Department, Fall 2005
Maintained by Brian Howard (bhoward@depauw.edu). Last updated