See section 4.1.3 of the course notes.  
 

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

 7. 
 The asymptotic running time that most closely bounds the performance of a selection sort on an input array with length n is  
 

  (a) O(2n)
 (b) O(n2)
 (c) O(n log n)
 (d) O(n)  

 Correct answer is  (b)  

 Your score on this question is: 0.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 8. 
 Consider the following C++ code fragment.

for( int i = 0; i < n; i++ ) {
    for( int j = 0; j < n/5; j++ ) {
        body;
    }
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
 
 

  (a) O(n)
 (b) O(n log n)
 (c) O(n3)
 (d) O(n2)  

 Correct answer is  (d)  

 Your score on this question is: 0.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 9. 
 The asymptotic running time that most closely bounds the performance of insertion sort on an input array with length n is  
 

  (a) O(2n)
 (b) O(n2)
 (c) O(n log n)
 (d) O(n)  

 Correct answer is  (b)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 1.7.2 of the course notes.  
 

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

 10. 
 Consider the following definition of a recursive function, power, that will perform exponentiation.

      int  power( int b, int e )
      {
        if( e == 0 ) return 1;
        if( e % 2 = 0 ) return  power( b * b, e/2 ); 
        return  b * power( b * b, e/2 );
      }

Asymptotically in terms of the exponent e, the number of calls to power that occur as a result of the call power(b,e) is
 
 

  (a) exponential
 (b) quadratic
 (c) logarithmic
 (d) linear  

 Correct answer is  (c)  

 Your score on this question is: 0.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 Go to top of assessment.  

 Total score: 40.00 

 ? Copyright 2004 iCarnegie, Inc. All rights reserved.  
View Assessment Result: Multiple-Choice Quiz 7


 

 Your performance was as follows:  

 1. 
 Which of the following statements is true of the selection-sort algorithm? 

It is a divide-and-conquer algorithm typically implemented using recursion. 
An implementation of the algorithm typically requires the use of a hash table.
 
 

  (a) I only
 (b) I and II
 (c) None
 (d) II only  

 Correct answer is  (c)  

 Your score on this question is: 0.00  

 Feedback: 
   
See section 4.1.2, subsection "Selection Sort," in the course notes. 
 
 

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

 2. 
 Consider the following C++ template function. 

template <class T>
void mystery_sort(vector<T>& v) {

    for (int i = 0; i < v.size() - 1; i++) {
        int best = i;
        for (int j = i + 1; j < v.size(); j++) {
            if (v[j] < v[best]) {
                best = j;
            }
        }

        if (best != i) {
            T temp = v[i];
            v[i] = v[best];
            v[best] = temp;
        }
    }
}
The above function implements which of the following sort algorithms? 
 
 

  (a) Merge sort
 (b) Selection sort
 (c) Bubble sort
 (d) Quicksort  

 Correct answer is  (b)  

 Your score on this question is: 10.00  

 Feedback: 
   
See section 4.1.2, subsection "Selection Sort," in the course notes. 
 
 

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

 3. 
 In a search over a data set with 1000 items, the maximum number of items examined by a linear search is _____, and the maximum number of items examined by a binary search is _____. 
 
 

  (a) 3, 100
 (b) 100, 3
 (c) 10, 1000
 (d) 1000, 10  

 Correct answer is  (d)  

 Your score on this question is: 0.00  

 Feedback: 
   
See section 4.1.1 in the course notes. 
 
 

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

 4. 
 Which of the following search algorithms can be applied to unsorted data? 

Linear search 
Binary search
 
 

  (a) None
 (b) II only
 (c) I and II
 (d) I only  

 Correct answer is  (d)  

 Your score on this question is: 10.00  

 Feedback: 
   
See section 4.1.1 in the course notes. 
 
 

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

 5. 
 Which of the following indicates the primary difficulty with hashing in general?  
 

  (a) Access in hash tables is slow.
 (b) Collisions will occur.
 (c) Hash functions are hard to compute.
 (d) Hash tables take up a lot of memory.  

 Correct answer is  (b)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 4.1.3 of the course notes.  
 

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

 6. 
 Suppose hash() is a hash function. The main idea behind hashing is to use a key k to store a value v in which position of a table?  
 

  (a) hash(k)
 (b) hash(v)
 (c) hash(k,v)
 (d) hash() (a random position computed by the hash function using k)  

 Correct answer is  (a)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 4.1.3 of the course notes.  
 

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

 7. 
 Consider the following C++ code fragment.

for( int i = 0; i < n; i += 2 ) {
    for(int  j = i; j > 0; j -= 3 ) {
        body
    }
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
 
 

  (a) O(n2)
 (b) O(n log n)
 (c) O(n3)
 (d) O(n)  

 Correct answer is  (a)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 8. 
 Consider the following definition of a recursive function, power, that will perform exponentiation.

      int  power( int b, int e )
      {
        if( e == 0 ) return 1;
        if( e % 2 = 0 ) return  power( b * b, e/2 ); 
        return  b * power( b * b, e/2 );
      }

Asymptotically in terms of the exponent e, the number of calls to power that occur as a result of the call power(b,e) is
 
 

  (a) quadratic
 (b) exponential
 (c) logarithmic
 (d) linear  

 Correct answer is  (c)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 9. 
 Consider the following C++ code fragment.

for( int i = 0; i < n; i++ ) {
    for( int j = 0; j < n/5; j++ ) {
        body;
    }
}

If body executes in constant time, then the asymptotic running time that most closely bounds from above the performance of this code fragment is
 
 

  (a) O(n)
 (b) O(n log n)
 (c) O(n2)
 (d) O(n3)  

 Correct answer is  (c)  

 Your score on this question is: 10.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 10. 
 Consider the following code fragment.

      for( int i = n; i > 0; i /= 2 ) body;

If body executes in O(1) time, then the asymptotic running time that most closely bounds the fragment is
 
 

  (a) O(n log n)
 (b) O(log n)
 (c) O(n)
 (d) O(n2)  

 Correct answer is  (b)  

 Your score on this question is: 0.00  

 Feedback: 
   See section 4.2.1 of the course notes.  
 

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

 Go to top of assessment.  

 Total score: 70.00 

 ? Copyright 2004 iCarnegie, Inc. All rights reserved.