CSC 122: Computer Science II, Fall 2005
Exam 1 Sample Questions
-
Consider the following array:
Show the results of running selection sort on this array. Show the first two passes
through selection sort.
- Show the results of running bubble sort on the original array from question #1.
Show the results of the first two passes.
- 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.
- Show an array that would result in the best running time for bubble sort.
- Show an array that would result in the worst running time for insertion sort.
-
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.
- What is the O( ) of the following expressions? Explain your answers.
-
n3 + 10n2 + 100n + 1000
-
n lg n + n2 + 10
-
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:
- mystery( 1, 3 )?
- mystery( 3, 3 )?
- mystery( 5, 3 )?
- mystery( 1, 5 )?
- 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.
- 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.
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