1. Assuming that Thing is some user-defined type, which of the following functions uses the least useful parameter list? 

 (a) bool f( const Thing x ); f() gets its own copy of x, but is unable to mutate it.

 (b) bool f( const Thing& x ); save space and protect the integrity of the object

 (c) bool f( Thing& x ); save space and permit f() to easily mutate the object

 (d) bool f( Thing x ); give f() its own copy of x to work with.         Correct answer is         (a)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

2. Each of the following is a basic C++ type EXCEPT 

 (a) char

 (b) bool

 (c) unsigned int

 (d) byte         Correct answer is         (d)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

3. All of the following characters are allowed to be part of a valid C++ identifier EXCEPT 

 (a) X

 (b) 3

 (c) - (hyphen)

 (d) _ (underscore)         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

4. The value of the C++ expression 10/3 is     

 (a) 3

 (b) 3.33333

 (c) 4

 (d) 1         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (a) No Feedback       

 

5. Assume that Thing is a user-defined type. Which of the following print functions for Thing is the safest and most efficient?  

 (a) void print( Thing* x );

 (b) void print( Thing x );

 (c) void print( const Thing& x );

 (d) void print( Thing& x ); Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

6. The "maximal munch rule" for compilers is to read as many characters as can possibly be assembled into a meaningful syntactic construct. Consider the following code fragment.

      int a = 5; int b = 10;

        cout << (a+++b) << " ";

      cout << a << " " << b << endl;

If the C++ compiler follows the maximal munch rule, what is printed as a result of the code fragment?

 (a) 15 5 11

 (b) 15 6 10

 (c) 16 6 10

 (d) 16 5 11         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

7. Which of the following statements uses the C++ pre-increment operator?

 (a) x = y+y;

 (b) x += y;

 (c) x = ++y;

 (d) x = y++;         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

8. The signature of a function is 

 (a) the name of the function

 (b) the name of the function and its parameter list

 (c) the number of parameters

 (d) the body of the function         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

9. Which of the following expressions evaluates to true in C++ if and only if the index variable i is in bounds for an array of size 10? 

 (a) 0 < 10

 (b) 0 <= i && i < 10

 (c) 0 <= i && i <= 10

 (d) 0 <= i < 10   Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

10. Which of the following descriptions of C++ are true?

I.      It is a small, tidy language like C.

II.     It is a teaching language like Pascal.

III.  It is a safe, garbage collected language like Java.      

         (a) I only

 (b) None

 (c) I and II

 (d) III only         Correct answer is         (b)

        Your score on this question is:        10.00

 

 

 

1. What is the type name used to represent extra precision real numbers in C++?      

 (a) long float

 (b) real

 (c) double

 (d) float         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

2. Assuming that Thing is some user-defined type, which of the following functions uses the least useful parameter list? 

 (a) bool f( const Thing x ); f() gets its own copy of x, but is unable to mutate it.

 (b) bool f( Thing& x ); save space and permit f() to easily mutate the object

 (c) bool f( Thing x ); give f() its own copy of x to work with.

 (d) bool f( const Thing& x ); save space and protect the integrity of the object         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (a) No Feedback       

 

3. All of the following characters are allowed to be part of a valid C++ identifier EXCEPT 

 (a) X

 (b) - (hyphen)

 (c) _ (underscore)

 (d) 3         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

4. Which of the following derived types is significantly different with respect to the other three?     

 (a) union

 (b) function

 (c) structure

 (d) array         Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

5. The value of the C++ expression 10/3 is     

 (a) 1

 (b) 3

 (c) 3.33333

 (d) 4         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

6. In C++, evaluation of the expression left && right is accurately described by which of the following? (Assume that left && right is a syntactically correct expression.)     

 (a) The expression right will be evaluated before the expression left is evaluated.

 (b) The expression right will be evaluated if and only if the expression left evaluates to false.

 (c) The expression right will always be evaluated.

 (d) The expression right will be evaluated if and only if the expression left evaluates to true.

        Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

7. Under the declaration,

      int  n = 10;

which of the following loop constructs executes statement n times?      

 (a) do statement while( n-- );

 (b) while( n-- ) statement;

 (c) while( --n ) statement;

 (d) for( int i = 1; i < n; i++ ) statement;         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

8. Which of the following control structures can lead to non-terminating behavior?

         (a) A switch statement

 (b) A while loop

 (c) An if-else statement

 (d) A return statement         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

9. Compilers follow the "maximal munch rule" (read as many characters as can possibly be assembled into a meaningful syntactic construct). Therefore, what happens with the following?

      int a = 5; int b = 10;

     cout << (a+++++b) << " ";

     cout << a << " " << b << endl;  

 (a) Prints 15 6 11

 (b) Does not compile.

 (c) Prints 15 7 10

 (d) Prints 16 6 11   Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

10. Which company was responsible for the development of C++?      

 (a) IBM

 (b) SUN

 (c) Microsoft

 (d) AT&T         Correct answer is         (d)

        Your score on this question is:        10.00

 

 

 

1. What is the type name used to represent extra precision real numbers in C++?      

 (a) float

 (b) long float

 (c) double

 (d) real         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

2. All of the following characters are allowed to be part of a valid C++ identifier EXCEPT 

 (a) X

 (b) _ (underscore)

 (c) - (hyphen)

 (d) 3         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

3. Under the declaration,

      int  n = 10;

which of the following loop constructs executes statement n times?      

 (a) for( int i = 1; i < n; i++ ) statement;

 (b) do statement while( n-- );

 (c) while( --n ) statement;

 (d) while( n-- ) statement;         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

4. Consider the following code fragment.

      bool  b = false;

      int   f( int x ) { ... }

      cout << f(b) << endl;

Which of the following is true?       

 (a) This will compile and execute properly in part because in the function call both bool and int are built-in types.

 (b) This will compile and execute properly in part because in the function call the types match exactly.

 (c) This will compile and execute properly in part because in the function call the bool will be converted to an int.

 (d) This will not compile.         Correct answer is         (c)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

5. How does C++ handle memory allocation?       

 (a) Allocation and deallocation is completely shielded from the programmer.

 (b) Allocation and deallocation is the responsibility of the programmer.

 (c) C++ always uses a garbage collector.

 (d) C++ has a garbage collector that can be used or turned off.         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

6. The "maximal munch rule" for compilers is to read as many characters as can possibly be assembled into a meaningful syntactic construct. Consider the following code fragment.

      int a = 5; int b = 10;

        cout << (a+++b) << " ";

      cout << a << " " << b << endl;

If the C++ compiler follows the maximal munch rule, what is printed as a result of the code fragment?

 (a) 15 6 10

 (b) 16 6 10

 (c) 15 5 11

 (d) 16 5 11         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (a) No Feedback       

 

7. Compilers follow the "maximal munch rule" (read as many characters as can possibly be assembled into a meaningful syntactic construct). Therefore, what happens with the following?

      int a = 5; int b = 10;

     cout << (a+++++b) << " ";

     cout << a << " " << b << endl;  

 (a) Prints 15 7 10

 (b) Does not compile.

 (c) Prints 16 6 11

 (d) Prints 15 6 11   Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

8. The signature of a function is 

 (a) the body of the function

 (b) the number of parameters

 (c) the name of the function and its parameter list

 (d) the name of the function         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

9. Execution of the conditional statement

      if( x = expr ) ;

has what effect?       

 (a) A compile-time error is produced.

 (b) The value of expr is assigned to x and then x is evaluated.

 (c) The value of expr is assigned to x if and only if that value is true.

 (d) The values of x and expr are evaluated and compared.         Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

10. Which of the following expressions evaluates to true in C++ if and only if the index variable i is in bounds for an array of size 10? 

 (a) 0 <= i < 10

 (b) 0 <= i && i < 10

 (c) 0 < 10

 (d) 0 <= i && i <= 10         Correct answer is         (b)

        Your score on this question is:        10.00

 

 

 

1. Assuming that Thing is some user-defined type, which of the following functions uses the least useful parameter list? 

 (a) bool f( const Thing& x ); save space and protect the integrity of the object

 (b) bool f( Thing x ); give f() its own copy of x to work with.

 (c) bool f( Thing& x ); save space and permit f() to easily mutate the object

 (d) bool f( const Thing x ); f() gets its own copy of x, but is unable to mutate it.         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

2. Each of the following is a basic C++ type EXCEPT 

 (a) char

 (b) bool

 (c) unsigned int

 (d) byte         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

3. Which of the following derived types is significantly different with respect to the other three?     

 (a) function

 (b) union

 (c) structure

 (d) array         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (a) No Feedback       

 

4. The value of the C++ expression 10/3 is     

 (a) 3.33333

 (b) 3

 (c) 1

 (d) 4         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

5. Suppose inf is an available ifstream and c is an available character. Consider the following code fragment.

do

    c = inf.get();

while (!inf.eof() && isspace(c));

Which of the following accurately describes the effect of executing this fragment?

 (a) Characters are read until a white space is read.

 (b) The number of non-white-space characters is counted.

 (c) Characters are read until the end of the file is reached.

 (d) Characters are read until a non-white-space character is read or until the end of the file is reached.

        Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

6. Which of the following is true about the default parameter passing mechanism in C++ ?     

 (a) It depends on where the function is defined.

 (b) It is chosen automatically by the compiler.

 (c) It is call-by-value.

 (d) It is call-by-reference.    Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

7. The "maximal munch rule" for compilers is to read as many characters as can possibly be assembled into a meaningful syntactic construct. Consider the following code fragment.

      int a = 5; int b = 10;

        cout << (a+++b) << " ";

      cout << a << " " << b << endl;

If the C++ compiler follows the maximal munch rule, what is printed as a result of the code fragment?

 (a) 16 5 11

 (b) 15 6 10

 (c) 16 6 10

 (d) 15 5 11         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

8. Execution of the conditional statement

      if( x = expr ) ;

has what effect?       

 (a) The values of x and expr are evaluated and compared.

 (b) The value of expr is assigned to x if and only if that value is true.

 (c) The value of expr is assigned to x and then x is evaluated.

 (d) A compile-time error is produced.         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

9. Which of the following descriptions of C++ are true?

I.      It is a small, tidy language like C.

II.     It is a teaching language like Pascal.

III.  It is a safe, garbage collected language like Java.      

 (a) I and II

 (b) III only

 (c) None

 (d) I only         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

10. Which company was responsible for the development of C++?      

 (a) IBM

 (b) AT&T

 (c) SUN

 (d) Microsoft         Correct answer is         (b)

        Your score on this question is:        10.00

 

 

 

1. What is the type name used to represent single characters in C++?      

 (a) character

 (b) char

 (c) Char

 (d) Character         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

        2.             What is the type name used to represent extra precision real numbers in C++?      

         (a) float

 (b) long float

 (c) real

 (d) double         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

3. Assuming that Thing is some user-defined type, which of the following functions uses the least useful parameter list? 

 (a) bool f( Thing x ); give f() its own copy of x to work with.

 (b) bool f( Thing& x ); save space and permit f() to easily mutate the object

 (c) bool f( const Thing& x ); save space and protect the integrity of the object

 (d) bool f( const Thing x ); f() gets its own copy of x, but is unable to mutate it.         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

4. Each of the following is a basic C++ type EXCEPT 

 (a) bool

 (b) byte

 (c) char

 (d) unsigned int    Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

5. The use of argv in the code

      int main( int argc, char *argv[] )

has what purpose? 

 (a) To control where in memory the program is executed

 (b) To hand over a number of strings to the program

 (c) To hand over a number of file names to the program

 (d) The purpose is system-dependent and is not uniform across systems.         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.4 of the course notes.

   (b) No Feedback       

 

6. Under the declaration,

      int  n = 10;

which of the following loop constructs executes statement n times?      

 (a) while( --n ) statement;

 (b) do statement while( n-- );

 (c) while( n-- ) statement;

 (d) for( int i = 1; i < n; i++ ) statement;         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (c) No Feedback       

 

7. How does C++ handle memory allocation?       

 (a) C++ has a garbage collector that can be used or turned off.

 (b) Allocation and deallocation is the responsibility of the programmer.

 (c) Allocation and deallocation is completely shielded from the programmer.

 (d) C++ always uses a garbage collector.         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

8. Assume that Thing is a user-defined type. Which of the following print functions for Thing is the safest and most efficient?  

 (a) void print( Thing* x );

 (b) void print( Thing& x );

 (c) void print( Thing x );

 (d) void print( const Thing& x );         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (d) No Feedback       

 

9. Which of the following lists of C++ types are ordered increasingly by size, as computed by sizeof() ? 

 (a) long, int, char, short

 (b) char, short, int, long

 (c) long, int, short, char

 (d) short, char, int, long         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.1.1 of the course notes.

   (b) No Feedback       

 

10. Which of the following expressions evaluates to true in C++ if and only if the index variable i is in bounds for an array of size 10? 

 (a) 0 <= i && i <= 10

 (b) 0 < 10

 (c) 0 <= i < 10

 (d) 0 <= i && i < 10         Correct answer is         (d)

        Your score on this question is:        10.00

 

 

Chapter 2:

1. Which of the following define an array A of 10 pointers to integers?

I.      int *A[10];

II.     int (*A)[10];

III.   int &A[10];

 (a) None

 (b) I

 (c) III

 (d) II         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

2. What, if anything, is wrong with the following code fragment?

      bool  *bp;  int  x;

      bp = &x; 

 (a) The & should be a *.

 (b) A pointer to an int cannot be assigned to a variable that is a pointer to a bool.

 (c) Nothing

 (d) The assignment should be *bp = &x;.         Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

3. Which of the following types of memory is most likely to cause the production of errors in a program? 

 (a) The free store.

 (b) Static memory.

 (c) They are all equally dangerous in C++.

 (d) Automatic memory.         Correct answer is         (a)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

4. If A is an array of 100 integers, which of the following properly deallocates A? 

 (a) delete A[100];

 (b) delete A;

 (c) delete [] A;

 (d) delete [100] A;         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

5. Which of the following is true about variables with dynamic extent?    

 (a) They are created and destroyed by the programmer.

 (b) They are created by the programmer, but destroyed by the compiler.

 (c) They are created and destroyed by the compiler.

 (d) They are destroyed only at the end of execution.         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (a) No Feedback       

 

6. Each of the following fragments produces a memory leak EXCEPT:

 (a) int *A = new int[5]; A = 0; delete [] A;

 (b) int *A = new int[10]; delete A;

 (c) int *A = new int[5]; A = new int[5]; delete [] A;

 (d) int *A = new int[10]; delete [] A;         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

7. C++ currently supports two types of strings: null-terminated C-style strings, and the string class in the Standard Library. Which of the following claims is false? 

 (a) The string class provides more operations than the C string library.

 (b) Null-terminated strings can be processed efficiently with pointers.

 (c) A C++ program may use either null-terminated strings or the string class, but not both.

 (d) For simple tasks dealing with many short strings, null-terminated strings are the implementation of choice.

        Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

8. Consider the following code fragment.

      int  A[100], *p, *q;

      for( p = A, q = p + 99; p < A+100; p++, q-- )

            swap( p, q );

Execution of this code fragment has what effect on the array A?     

 (a) It rotates the array 1 place to the left.

 (b) It has no effect.

 (c) It zeroes out the whole array.

 (d) It reverses the array.         Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

9. The scope of a variable concerns  

 (a) the amount of memory it occupies

 (b) the time of its existence

 (c) its visibility within a program

 (d) its type         Correct answer is         (c)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

10. Which of the following libraries supports null-terminated strings?    

 (a) string

 (b) cwchar

 (c) cstdlib

 (d) string.h         Correct answer is         (d)

        Your score on this question is:        10.00

 

 

1. Consider the following code fragment. Thing *tp = new Thing; tp = new Thing; Which of the following is true concerning this code fragment?

 (a) When executed, it creates a new instance of Thing and then overwrites it by yet another instance.

 (b) When executed, it creates a new instance of Thing and then loses all access to it as it creates yet another instance.

 (c) It will not compile.

 (d) When executed, it creates two instances of Thing and makes the first point to the second.

        Correct answer is         (b)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

2. Which of the following statements properly allocates an array of 100 integers?  

 (a) int A = new int[100];

 (b) int *A = new int[100];

 (c) int &A = new int[100];

 (d) int *A = new (int) 100;         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

3. What, if anything, is wrong with the following code fragment?

      bool  *bp;  int  x;

      bp = &x; 

 (a) A pointer to an int cannot be assigned to a variable that is a pointer to a bool.

 (b) The & should be a *.

 (c) The assignment should be *bp = &x;.

 (d) Nothing         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (a) No Feedback       

 

4. Which of the following types of memory is most likely to cause the production of errors in a program? 

 (a) Static memory.

 (b) The free store.

 (c) They are all equally dangerous in C++.

 (d) Automatic memory.         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

5. If A is an array of 100 integers, which of the following properly deallocates A? 

 (a) delete A[100];

 (b) delete [100] A;

 (c) delete [] A;

 (d) delete A;         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

6. Consider the following declarations.

      int  (*f)(int);

      int   *g(int);

Which of the following correctly characterizes f and g?

I.      f is a pointer to a function from integers to integers, and g is a function from integers to pointers to integers.

II.     both f and g are functions from integers to pointers to integers

III.   f is a function from integers to pointers to integers, and g is a pointer to a function from integers to integers   

 (a) II only

 (b) I only

 (c) III only

 (d) none         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

7. Which of the following declares p to be a pointer to an integer?       

 (a) int **p;

 (b) int &p;

 (c) int p[]

 (d) int *p;         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

8. Consider the following code fragment.

      int  A[100], *p, *q;

      for( p = A, q = p + 99; p < A+100; p++, q-- )

            swap( p, q );

Execution of this code fragment has what effect on the array A?     

 (a) It zeroes out the whole array.

 (b) It has no effect.

 (c) It reverses the array.

 (d) It rotates the array 1 place to the left.         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

9. Which of the following makes p point to the third element of an array A (i.e., point to A[2]) ?

 (a) p = A[2];

 (b) p = *A + 2;

 (c) p = ++(++A);

 (d) p = A + 2;         Correct answer is         (d)

        Your score on this question is:        0.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

10. Which of the following libraries supports null-terminated strings?    

 (a) string

 (b) string.h

 (c) cwchar

 (d) cstdlib         Correct answer is         (b)

        Your score on this question is:        0.00

 

 

 

1. Consider the following code fragment. Thing *tp = new Thing; tp = new Thing; Which of the following is true concerning this code fragment?

 (a) When executed, it creates a new instance of Thing and then overwrites it by yet another instance.

 (b) When executed, it creates two instances of Thing and makes the first point to the second.

 (c) It will not compile.

 (d) When executed, it creates a new instance of Thing and then loses all access to it as it creates yet another instance.

        Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

2. Which of the following statements properly allocates an array of 100 integers?  

 (a) int *A = new (int) 100;

 (b) int &A = new int[100];

 (c) int A = new int[100];

 (d) int *A = new int[100];         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

3. If A is an array of 100 integers, which of the following properly deallocates A? 

 (a) delete A;

 (b) delete [] A;

 (c) delete [100] A;

 (d) delete A[100];         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

4. The parameters in the main part of a program often take one of the two following forms.

    Version 1:  int  main( int argc, char **argv )

    Version 2:  int  main( int argc, char *argv[] )

What is the difference between the two?

 (a) Version 1 uses a variable-size array, but Version 2 uses a fixed-size array.

 (b) None

 (c) Version 1 uses a linked list of strings, but version 2 uses an array.

 (d) Version 1 uses one long array of chars, but version 2 uses several small arrays         Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

5. Which of the following is true about variables with dynamic extent?    

 (a) They are created and destroyed by the programmer.

 (b) They are created and destroyed by the compiler.

 (c) They are destroyed only at the end of execution.

 (d) They are created by the programmer, but destroyed by the compiler.         Correct answer is         (a)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (a) No Feedback       

 

6. Consider the following code fragment.

      int  A[100], *p, *q;

      for( p = A, q = p + 99; p < A+100; p++, q-- )

            swap( p, q );

Execution of this code fragment has what effect on the array A?     

 (a) It zeroes out the whole array.

 (b) It rotates the array 1 place to the left.

 (c) It reverses the array.

 (d) It has no effect.         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

7. What is the effect of the following code fragment?

      int   A[100];

     for( int *p = A; p < A + 100; ++p )

          *p = 0; 

 (a) It sets 100 pointers in A to 0.

 (b) It produces an out-of-bounds error.

 (c) It zeroes out the 100 elements of array A.

 (d) It zeroes out A[0]-many elements of array A.         Correct answer is         (c)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (c) No Feedback       

 

8. Which of the following makes p point to the third element of an array A (i.e., point to A[2]) ?

 (a) p = A[2];

 (b) p = A + 2;

 (c) p = ++(++A);

 (d) p = *A + 2;    Correct answer is         (b)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (b) No Feedback       

 

9. Which of the following libraries supports null-terminated strings?    

 (a) cwchar

 (b) string

 (c) cstdlib

 (d) string.h         Correct answer is         (d)

        Your score on this question is:        10.00

        Feedback:       

   See section 1.2.1 of the course notes.

   (d) No Feedback       

 

10. What, if anything, is wrong with the following code fragment?

      Thing  *ptr = new Thing;

      ptr = NULL;    

 (a) When executed, it will create an instance of Thing and then remove the only reference to this instance without destroying it first.

 (b) When executed, it will assign a NULL pointer to a variable that is a pointer to a Thing.

 (c) When executed, it will create an instance of Thing and then overwrite it with NULL.

 (d) Nothing         Correct answer is         (a)

        Your score on this question is:        10.00

 

7. Consider the following code fragment.

 

      char  *str1 = "word";

      char  *str2;

      str2 = str1;

 

Which of the following correctly characterizes the effect of executing this fragment?

 

 

 

 (a) The null-terminated string "word" is copied to str2.

 (b) The pointer str2 is set so as to point at the first character in the null-terminated string "word".

 (c) The non-null characters of "word" are copied to str2.

 (d) Nothing is changed. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 

 

Chapter 3:

 

 1.

 To which of the following is object-based programming ideally suited?

 

 

  (a) Attaining the highest possible efficiency

 (b) Implementing simple monolithic programs

 (c) Providing elegant mechanisms for code reuse

 (d) Encapsulation 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 If a user-defined class Complex has overloaded operator+=, then one would expect this operator to have which of the following declarations?

 

 

  (a) Complex& operator+=( const Complex& rhs );

 (b) void operator+=( const Complex& rhs );

 (c) void operator+=( float real, float imag );

 (d) Complex& operator+=( const Complex rhs ); 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 If a user-defined class overloads both operator== and operator<, which other operator, if any, is implicitly overloaded as a consequence?

 

 

  (a) operator<=

 (b) operator<<

 (c) operator!=

 (d) No other operator 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 4.

 A user-defined class Thing that has value semantics behaves very much like

 

 

  (a) any class that has a default constructor

 (b) a pointer to a built-in type such as int* or float*

 (c) an expression of arithmetic

 (d) a built-in type such as int or float 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 What is the difference between a C++ class and a C++ struct ?

 

 

  (a) The default access in a class is private and in a struct is public.

 (b) There is no difference.

 (c) The default access in a class is public and in a struct is private.

 (d) Structs cannot contain function members. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 6.

 Assume that Thing is a user-defined class, and consider the following code fragment, where B is an instance of Thing.

 

      Thing  A = B

 

Which of the following is a class member that is used in this code fragment?

 

 

 

  (a) The assignment operator

 (b) The default constructor

 (c) The copy constructor

 (d) The destructor 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 Consider the following class outline for a user-defined implementation of real numbers.

 

      class  RealNumber {

            ...

            private:

                    RealNumber(void) {}

      };

 

Which of the following is true about such an implementation?

 

 

 

  (a) It exhibits good general defensive programming by using private constructors.

 (b) All RealNumber objects will be read-only.

 (c) Since the class defines a private constructor, it cannot define any public constructors.

 (d) It will be impossible to place RealNumber objects into a container. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 Consider the following class outline for a user-defined implementation of real numbers.

 

      class  RealNumber {

      ...

             RealNumber( float x );

             RealNumber( float x, float y=0 );

      };

 

What, if anything, is wrong with the outline?

 

 

 

  (a) Default values are not allowed in constructors.

 (b) There is no reasonable way to construct a real from two real parameters.

 (c) The second constructor conflicts with the first.

 (d) Nothing 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 9.

 Which of the following statements properly describes the restriction in C++ regarding what a function can return?

 

 

  (a) Neither functions nor function objects can be returned.

 (b) Neither function pointers nor function objects can be returned.

 (c) Functions cannot be returned, but function objects can be returned.

 (d) Function pointers cannot be returned, but function objects can be returned. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Which of the following correctly describes the difference between an ordinary function and a function object?

 

 

 (a) Function objects execute faster on some machines.

 (b) Functions are allowed to be recursive.

 (c) A function object may contain data that persist between calls.

 (d) The compiler can perform type checking with function objects. 

 

 Correct answer is  (c)

 

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

 

1.

 Suppose a user-defined class Thing has a simple constructor that does not require any calls to new. Which of the following is true about the destructor?

 

 

  (a) It will not contain calls to delete.

 (b) It might contain calls to delete, but might not.

 (c) The appropriate destructor will be provided automatically by the compiler.

 (d) In this case, no destructor is required for class Thing. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 Of the following methods, which is least important in a user-defined class with value semantics?

 

 

  (a) The output operator

 (b) A destructor

 (c) The assignment operator

 (d) A copy constructor 

 

 Correct answer is  (a) 

 

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

 

7.

 The purpose of a constructor is to

 

 

  (a) handle assignments between instances of the class

 (b) initialize data members of a class properly after space has been allocated

 (c) clean up memory when an instance goes out of scope

 (d) prevent memory leaks 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 8.

 The purpose of the assignment operator is to

 

 

  (a) initialize data members when an instance is first created

 (b) provide for proper assignment between objects

 (c) prevent memory leaks

 (d) be used internally in an object's copy constructor 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 Consider the following class outline for a user-defined implementation of real numbers.

 

      class  RealNumber {

      ...

             RealNumber( float x );

             RealNumber( float x, float y=0 );

      };

 

What, if anything, is wrong with the outline?

 

 

 

  (a) There is no reasonable way to construct a real from two real parameters.

 (b) Nothing

 (c) The second constructor conflicts with the first.

 (d) Default values are not allowed in constructors. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Consider the class outline below.

 

      class  Stack {

      ...

             explicit Stack( int n );

      };

 

What is the purpose of the explicit in this outline?

 

 

 

  (a) To make sure that the constructor does not apply to short, only to int

 (b) To draw attention to the fact that there is a constructor

 (c) To prevent the Stack destructor from damaging the data stored in the stack

 (d) To inhibit automatic conversions from an integer to a Stack 

 

 Correct answer is  (d)

 

 

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

 

 

 

 4.

 The purpose of a constructor is to

 

 

  (a) prevent memory leaks

 (b) handle assignments between instances of the class

 (c) initialize data members of a class properly after space has been allocated

 (d) clean up memory when an instance goes out of scope 

 

 Correct answer is  (c) 

 

 

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

 

 

2.

 Assume that Thing is a user-defined class, and consider the following function.

 

Thing  f(Thing& A)  {

  Thing B;

  B.x  =  A.x;

  return B;

}

 

Where in this code will a copy constructor be used?

 

 

 

  (a) In the return operation

 (b) In the creation of the local variable B

 (c) In copying the data from A to B

 (d) In passing the parameter 

 

 Correct answer is  (a) 

 

 

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

 

1.

 What is the most compelling reason for a random number generator to be implemented as a function object?

 

 

  (a) So that the generator can be seeded

 (b) Efficiency

 (c) A random number generator needs to maintain state between uses

 (d) The use of a function object can increase the "randomness" of the generator 

 

 Correct answer is  (c) 

 

 

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

 

 

 

 1.

 What is the purpose of class templates?

 

 

  (a) To avoid the use of dangerous pointers

 (b) To easily specify a group of related classes

 (c) To increase the efficiency of the class methods

 (d) To improve the portability of code 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 Consider the following templated array copy function and arrays.

 

      template<class S, class T>  void  copy( S a[], T b[], int n ) {

          for(int i = 0; i < n; i++ ) a[i] = b[i];

      }

      char   C[10];

      int    I[10];

      float  F[10];

 

Which of the following calls to copy would produce a compile time error?

 

copy( F, C, 10 );

copy( I, C, 10 );

copy( C, F, 10 );

 

 

 

  (a) None

 (b) I

 (c) III

 (d) II 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 Consider the following templated swap function.

 

      template<class T>  void  swap( T& a, T& b ){

          T tmp = a; a = b; b = tmp;

      }

 

Determining the right choice of type parameter T occurs at which of the following times?

 

 

 

  (a) In part at compile time, and in part at run time

 (b) Compile time only

 (c) Run time only

 (d) Link time 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 Which of the following is true about the run-time efficiency of using templated functions versus using nontemplated functions?

 

 

  (a) The run-time efficiency is the same for both.

 (b) The run-time efficiency is better for templated functions.

 (c) The run-time efficiency is slightly worse for templated functions.

 (d) The run-time efficiency is much worse than for templated functions. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 Which of the following is true about compilation of a templated function or class?

 

 

  (a) Templates are not handled during compilation.

 (b) Compilation takes much, much longer.

 (c) Compilation takes slightly longer.

 (d) Compilation takes less time. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 What, if anything, is wrong with the following function declaration?

 

      template<class A, class B>  A  f( B x );

 

 

 

 

  (a) Nothing

 (b) The compiler cannot determine B when f is called.

 (c) The compiler cannot determine A when f is called.

 (d) The parameter should be passed by reference. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 Consider the following outline of a templated array class.

 

      template<class T> class Array { ... }

 

Which of the following is true about using this outline to implement a general container class?

 

 

 

  (a) It is a poor choice since templates slow down compilation.

 (b) It is a poor choice since the type matching will slow down access at runtime.

 (c) It is a reasonable way to implement such a class.

 (d) It is impossible since the algorithm cannot know how to copy an instance of type T. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 Consider the following outline of a templated array class.

 

      template<class T>  class Array { ... }

 

Which of the following declarations are in error with respect to using such a class?

 

Array<Array<int> > A;

Array<Array<int>*> A;

Array<int**> A;

 

 

 

  (a) None

 (b) II only

 (c) I only

 (d) III only 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 Consider the following templated function.

 

   template<class T> T Apply( T x, T (*ff)(T) ){ return ff(x); }

 

Which of the following is true concerning its use?

 

 

 

  (a) The input function must return the same type as its argument, and the templated function returns the result of calling the second input on the first input.

 (b) The input function must return the same type as its argument, and the templated function returns a pointer to the result of calling the second input on the first input.

 (c) The input function can be arbitrary, and the templated function returns the result of calling the second input on the first input.

 (d) The input function can be arbitrary, and the templated function returns a pointer to the result of calling the second input on the first input. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Consider the following templated function.

 

  template<class Func>

  void mystery( Func f, int n, typename Func::result_type& x ) {

          for( int i = 0; i < n; i++ )

              x += f(i);

  }

 

If the first actual parameter of a call to mystery is a function object f that properly defines result_type and if n0 and x0 are the values of the second and third actual parameters, which of the following accurately describes the result of executing that call?

 

 

 

  (a) x0+f(0)+f(1)+...+f(n0-1)is stored in x.

 (b) x0+f(0)+f(1)+...+f(n0)is stored in x.

 (c) f(0), f(1), ..., and f(n0-1) are stored in x in succession.

 (d) f(0), f(1), ..., and f(n0) are stored in x in succession. 

 

 Correct answer is  (a) 

 

 

 

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

 

8.

 Consider the following outline of a templated array class.

 

      template<class T>  class Array { ... }

 

Which of the declarations below is in obvious error with respect to using such a class?

 

 

 

  (a) Array<int> A(10,0);

 (b) Array<int> A<int>;

 (c) Array<int> A;

 (d) Array<int> A(10); 

 

 Correct answer is  (b) 

 

 

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

 

 

 6.

 If templates were removed from C++, which of the following would be true?

 

Some algorithms could no longer be implemented.

Any particular algorithm could still be implemented, but often less elegantly.

Any particular algorithm could still be implemented, but the efficiency would often be catastrophically worse.

 

 

 

  (a) II only

 (b) I only

 (c) II and III

 (d) None 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 7.

 Consider the following outline of a templated sorting function.

 

      template<class T>  void  sort( T a[], int n ) { ... }

 

For a given sorting algorithm S, which of the following is true about using this outline to implement S?

 

 

 

  (a) It is a poor choice since it does not work with linked lists.

 (b) It is a reasonable way to implement S.

 (c) It is a poor choice since templates slow down sorting.

 (d) It is impossible since the algorithm cannot know how to compare two instances of type T. 

 

 Correct answer is  (b) 

 

 

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

 

3.

 Consider the following templated array copy function and arrays.

 

      template<class T>  void  copy( T a[], T b[], int n ) {

          for(int i = 0; i < n; i++ ) a[i] = b[i];

      }

      char   C[10], CC[10];

      int    I[10];

      float  F[10];

 

Which of the following calls to copy would produce a compile time error?

 

 

 

  (a) copy( C, CC, 10 );

 (b) copy( I, F, 10 );

 (c) copy( I, (int*)F, 10 );

 (d) copy( I, I, 10 ); 

 

 Correct answer is  (b) 

 

 

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

 

 

 1.

 In a template definition

 

      template<class T>  ...

 

the template parameter T ranges over

 

 

 

  (a) all types

 (b) classes as well as structs

 (c) only built-in types

 (d) only user-defined classes 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 2.

 Consider the following template specification.

 

      template<int n>  ...

 

In use, the template parameter n can be replaced by

 

 

 

  (a) any type of value

 (b) arithmetic type values only

 (c) int values and int containers only

 (d) int values only 

 

 Correct answer is  (d) 

 

 

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

 

 

4.

 Consider the following templated swap function and data types.

 

      template<class T>  void  swap( T& a, T& b ){

          T tmp = a; a = b; b = tmp;

      }

      char   c1, c2;

      int    i1, i2;

      float  A[10];

 

Which of the following calls to swap produces a compile time error?

 

swap( i1, c2 )

swap( c1, i2 );

swap( A[5], A[2] );

 

 

 

  (a) I and II

 (b) II and III

 (c) I, II, and III

 (d) I only 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 

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

 

 

1.

 The purpose of function templates is to

 

 

  (a) help the type-checker search for errors

 (b) easily specify a family of operationally equivalent functions

 (c) replace generic void* pointers in C

 (d) increase the efficiency of various algorithms 

 

 Correct answer is  (b) 

 

 

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

 

 

1.

 Which of the following is true of multiple inheritance?

 

 

  (a) It provides for the elegant construction of a new class from existing classes.

 (b) It is an important idea in Object-Oriented Programming, but currently it is not implemented in C++.

 (c) It allows the application of inheritance over and over, producing deep hierarchies.

 (d) It causes one type to behave like several types. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 2.

 Polymorphism is a mechanism that is used in order to

 

 

  (a) determine the type of an object dynamically at run time

 (b) build new classes on top of existing ones

 (c) protect data members from illegal access

 (d) determine methods of a class based on its data members 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 What is composition?

 

 

  (a) It is an important idea in Object Oriented Programming, but currently it is not implemented in C++.

 (b) It is the inclusion of one class in another as a data member.

 (c) It is the same as polymorphism.

 (d) It is a method to build new classes on top of existing ones. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 Inheritance is an important feature of C++ because

 

 

  (a) it is a powerful code reuse mechanism

 (b) it can often replace templates

 (c) it greatly increases efficiency

 (d) it makes type-checking much easier 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 In which of the following situations would private inheritance be a sound choice?

 

 

  (a) Whenever multiple inheritance is used

 (b) To derive a numerical array class from a general one

 (c) To derive a stack from a general linked list class

 (d) When the base class is templated 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 6.

 Under what circumstances will a member function in C++ display polymorphic behavior?

 

 

  (a) If and only if the class has multiple inheritance

 (b) If and only if the class is not templated

 (c) Always

 (d) If and only if the function is explicitly declared to be virtual 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 7.

 Consider the following inheritance declarations.

 

      class Base    { public: int x; private int y; };

      class Derived: public Base  { public: int z; };

      Derived  D;

 

Under these declarations, which of the following statements, if any, will fail to compile?

 

 

 

  (a) None

 (b) D.x = 555;

 (c) D.y = 555;

 (d) D.z = 555; 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 Which of the following is true about a class without a (user-defined) constructor?

 

 

  (a) It must have a destructor.

 (b) It may have a destructor, but might not.

 (c) It cannot have an assignment operator.

 (d) It cannot have a destructor. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 The purpose of initializers in a constructor is to

 

 

  (a) make it easier to implement value semantics

 (b) avoid assignments and use copy constructors directly

 (c) avoid the copy constructor

 (d) make sure all data members are initialized 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 10.

 Every class that is supposed to behave like a built-in type must overload which operator?

 

 

  (a) The output operator

 (b) The assignment operator

 (c) The call operator

 (d) The comma operator 

 

 Correct answer is  (a) 

 

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

 

 

 

 9.

 The proper tool for writing an array class whose instances can have some elements with ints and other elements with floats is the use of

 

 

  (a) inheritance

 (b) unions

 (c) templates

 (d) casting 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.5.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 How should a copy constructor function in a linked list class?

 

 

  (a) It should copy the list header, but should copy the nodes only if there are less than four nodes.

 (b) It should copy only the list header, and not the nodes.

 (c) A linked list class should not have a copy constructor.

 (d) It should copy all the nodes and the list header. 

 

 Correct answer is  (d) 

 

 

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

 

3.

 All of the following are features of object-oriented programming EXCEPT

 

 

  (a) inheritance

 (b) encapsulation

 (c) polymorphism

 (d) garbage collection 

 

 Correct answer is  (d)

 

 

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

 

4.

 Which of the following is necessary in order to obtain polymorphic behavior in C++?

 

 

  (a) Multiple inheritance is avoided.

 (b) Templates are avoided.

 (c) Only instances of the base class are used.

 (d) Pointers or references are used with virtual functions. 

 

 Correct answer is  (d) 

 

 

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

 

6.

 What is the role of the destructor for the base class when an instance of a derived class goes out of scope?

 

 

  (a) It will not be called and it cannot be called at such a time.

 (b) It is available to be called by the user to prevent the destructor for the derived class from being called..

 (c) It must be called by the user, unless the derived class uses dynamic memory (the heap).

 (d) It is called automatically. 

 

 Correct answer is  (d) 

 

 

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

 

 

 8.

 The proper tool for writing a linked list that can have some elements with ints and other elements with floats is the use of

 

 

  (a) templates

 (b) casting of ints to floats and the use of a simple list

 (c) inheritance

 (d) unions 

 

 Correct answer is  (c) 

 

 

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

 

6.

 Consider the following inheritance declarations.

 

    class Base { virtual  void f(int); virtual void f(float); };

    class Derived: public Base  { void f(int); };

    Derived  D;

    Base     B, *p = &D;

 

In the context of these declarations, the two functions that are used in the two calls D.f(3.1415); and p-f(3.1415); are, respectively,

 

 

 

  (a) Derived::f(int) and Derived::f(int)

 (b) Base::f(double) and Derived::f(int)

 (c) Base::f(double) and Base::f(double)

 (d) Derived::f(int) and Base::f(double) 

 

 Correct answer is  (a) 

 

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

 

 

 1.

 Which of the following is true of inheritance?

 

 

  (a) It causes one type to behave like several types.

 (b) It protects data members from illegal access.

 (c) It provides for the elegant construction of a new class from an existing class.

 (d) It is an important idea in Object Oriented Programming, but currently it is not implemented in C++. 

 

 Correct answer is  (c)

 

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

 

Chapter 6:

 

 

 1.

 How should a copy constructor function in a linked list class?

 

 

  (a) A linked list class should not have a copy constructor.

 (b) It should copy all the nodes and the list header.

 (c) It should copy the list header, but should copy the nodes only if there are less than four nodes.

 (d) It should copy only the list header, and not the nodes. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 2.

 Which of the following is the main reason for using recursion?

 

 

  (a) To avoid templates and inheritance

 (b) To improve efficiency

 (c) To obtain short, elegant solutions

 (d) To use less memory 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 3.

 Consider the function defined as follows.

 

      int  f( int n )

      {

          if( n == 0 ) return 0;

          if( (n & 1) == 0 ) return f(n/2);

          return f(n/2) + 1;

      }

 

The value returned by the call f( 10 ); is

 

 

 

  (a) 5

 (b) 3

 (c) 1

 (d) 2 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 4.

 Consider the following definition of a recursive function f.

 

      int  f( int n )

      {

          if( n == 0 ) return 0;

          if( (n & 1) == 0 ) return f(n/2);

          return f(n/2) + 1;

      }

 

What does f compute?

 

 

 

  (a) The number of digits in the binary expansion of the input

 (b) The number of 1's in the binary expansion of the input

 (c) The logarithm of the input

 (d) A pseudo-random number between 1 and n 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 Assuming non-negative arguments, what is the purpose of the following recursive function?

 

      int  ff( int n, int m )

      {

          if( n == 0 ) return m;

          return  ff( n-1, m*n );

      }

 

 

 

 

  (a) It computes the least common multiple of n and m.

 (b) It computes m * (n!)

 (c) It computes (m + n)!

 (d) It computes the greatest common divisor of n and m. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 6.

 Consider the following definition of a recursive function ff.

 

      int  ff( int n, int m )

      {

          if( n == 0 ) return m;

          return  ff( n - 1, m + 1 );

      }

 

If the values of n and m are nonnegative, what is returned by ff( n , m )?

 

 

 

  (a) The product of n and m

 (b) The sum of n and m

 (c) The greatest common divisor of n and m

 (d) The least common multiple of n and m 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 7.

 Consider the following definition of a recursive function ff.

 

      int  ff( int n, int m )

      {

          if( n == 0 ) return 0;

          return  ff( n - 1, m ) + m;

      }

 

If the values of n and m are nonnegative, what is returned by ff( n , m )?

 

 

 

  (a) The product of n and m

 (b) The least common multiple of n and m

 (c) The greatest common divisor of n and m

 (d) The sum of n and m 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 Consider the following definition of a recursive function f.

 

      bool  f( int x )

      {

            if( (x & 1) == 1 )  return (x == 1);

            return  f( x >> 1 );               // right shift

      }

 

The value returned by the call f(x)will determine whether the input x is

 

 

 

  (a) a prime

 (b) a power of 2

 (c) odd

 (d) even 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 9.

 Consider the following recursive definition of a function to compute Fibonacci numbers.

 

      int  Fibonacci( int n )

      {

      if( n == 0 ) return 0;

      if( n == 1 ) return 1;

      return  F(n-1) + F(n-2);

      }

 

Why is the function Fibonacci problematic to use?

 

 

 

  (a) The depth of the recursion is prohibitively large for large n.

 (b) The total number of recursive calls is prohibitively large for large n.

 (c) The double recursion is difficult to implement.

 (d) The memory requirement is prohibitively large for large n. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 10.

 Given an array of length n, the extra space requirement in merge sort due the call stack is about

 

 

  (a) n

 (b) log n

 (c) n2

 (d) some small constant 

 

 Correct answer is  (a) 

 

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

 

1.

 What would be the consequences for algorithms if recursion were removed from C++?

 

 

  (a) None

 (b) Some algorithms could no longer be implemented.

 (c) All algorithms could still be implemented, but often less elegantly.

 (d) All algorithms could still be implemented, but the efficiency would often be catastrophically worse. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 2.

 Which of the following is the main reason for using recursion?

 

 

  (a) To avoid templates and inheritance

 (b) To improve efficiency

 (c) To use less memory

 (d) To obtain short, elegant solutions 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 3.

 A recursive function is one that

 

 

  (a) calls other functions

 (b) is called from main()

 (c) uses no loops of any kind

 (d) calls itself 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 4.

 The specification for an algorithm must include all of the following EXCEPT:

 

 

  (a) A precise description of all the data structures used

 (b) A precise description of the output

 (c) A precise description of how the output is computed from the input

 (d) A precise description of the input 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 Consider the following definition of a recursive function ff.

 

      int  ff( int n, int m )

      {

          if( n == 0 ) return m;

          return  ff( n - 1, m + 1 );

      }

 

If the values of n and m are nonnegative, what is returned by ff( n , m )?

 

 

 

  (a) The least common multiple of n and m

 (b) The greatest common divisor of n and m

 (c) The sum of n and m

 (d) The product of n and m 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Consider the following definition of a recursive function f.

 

      int  f( int x )

      {

            if( x == 0 )  return 1;

            return  x * f( x - 1 );

      }

 

The inputs for which f will terminate are all x such that x is

 

 

 

  (a) odd

 (b) unrestricted

 (c) non-negative

 (d) even 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 7.

 Consider the following definition of a recursive function f.

 

      int  f( int x )

      {

            if( x == 0 )  return 1;

            return  x * f( x );

      }

 

For which inputs x will the call f(x)terminate?

 

 

 

  (a) For all inputs x

 (b) For all even inputs x only

 (c) For all odd inputs x only

 (d) For x = 0 only 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 8.

 Consider the following definition of a recursive function f.

 

      bool  f( int x )

      {

            if( (x & 1) == 1 )  return (x == 1);

            return  f( x >> 1 );               // right shift

      }

 

The value returned by the call f(x)will determine whether the input x is

 

 

 

  (a) a power of 2

 (b) even

 (c) odd

 (d) a prime 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 Consider the following definition of a recursive function what?

 

      int  what( int (*f)(int), int x, int n )

      {

            if( n == 0 )  return x;

            return  f( what( f, x, n - 1 ) );

      }

 

If n is a non-negative integer, then the call what( f, x, n )returns

 

 

 

  (a) fn(x)

 (b) f(x)regardless of the value of n

 (c) f(x) unless f is recursive, in which case it returns fn-1(x)

 (d) f(x + n) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.6.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 Assume List is a linked list of integers.

 

List  mystery( int a, int b, List L )

{

  if( L is empty ) return L;

  if(a == first(L)) return prepend( b, mystery(a, b, tail(L)) );

  return prepend( first(L), mystery( a, b, tail(L) ) );

}

 

The call mystery(a, b, L)returns a linked list just like L except that

 

 

 

  (a) every occurrence of b has been replaced by an occurrence of a

 (b) every occurrence of a has been replaced by an occurrence of b

 (c) the list is rotated

 (d) the list is reversed 

 

 Correct answer is  (b) 

 

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

 

 

 2.

 How many calls to itself is a recursive function allowed to make?

 

 

  (a) At most one

 (b) At most two

 (c) Any number

 (d) None 

 

 Correct answer is  (c)

 

 

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

 

Chapter 7:

 

1.

 What is the asymptotic running time of bubble sort on an input array with length n?

 

 

  (a) O(n log n)

 (b) O(2n)

 (c) O(n)

 (d) O(n2) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 What is the asymptotic running time of insertion sort on an input array with length n?

 

 

  (a) n

 (b) n log n

 (c) 2n

 (d) n2 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 3.

 Which of the following statements about insertion sort is true asymptotically?

 

 

  (a) Insertion sort is faster than merge sort, but consumes less memory.

 (b) Insertion sort is slower than merge sort, and consumes more memory.

 (c) Insertion sort is slower than merge sort, but consumes less memory.

 (d) Insertion sort is slower than merge sort, and consumes about the same memory. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 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 of the code fragment above is

 

 

 

  (a) O(n)

 (b) O(log n)

 (c) O(n2)

 (d) O(n log n) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 Consider the following recursive definition of a function f.

 

int  f(int  n)

{

  if( n == 0 ) return 1;

  else return  f(n / 2);

}

 

The asymptotic running time of the call f(n) is

 

 

 

  (a) O(log n)

 (b) O(n2)

 (c) O(n)

 (d) O(n log n) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 6.

 Using the standard gradeschool method, what is the asymptotic running time of adding two numbers that are both n digits long?

 

 

  (a) n

 (b) 2n

 (c) n3

 (d) n2 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 What is the asymptotic running time of merge sort with an input array of length n?

 

 

  (a) O(n log n)

 (b) O(n2)

 (c) O(n)

 (d) O(2n) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 Consider the following code fragment.

 

      for( int i = 0; i < n; i++ )

            for( int j = 0; j < n; j++ )

                  for( int k = 0; k < n; k++ ) body;

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n3)

 (b) O(n)

 (c) O(2n)

 (d) O(n2) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 Consider the following code fragment.

 

    for( int i = 0; i < n; i += 2 )

            for( int j = 0; j < n; j += 3 )

                  for( int k = 0; k < n; k += 4 ) body;

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n2)

 (b) O(n)

 (c) O(n log n)

 (d) O(n3) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 10.

 Consider the following code fragment.

 

    for( int i = 0; i < n; i++ )

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

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n)

 (b) O(n2)

 (c) O(n log n)

 (d) O(n3) 

 

 Correct answer is  (b) 

 

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

 

 

1.

 What is the asymptotic running time of bubble sort on an input array with length n?

 

 

  (a) O(2n)

 (b) O(n)

 (c) O(n2)

 (d) O(n log n) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

 

 

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

 

 2.

 What is the asymptotic running time of insertion sort on an input array with length n?

 

 

  (a) n2

 (b) n log n

 (c) 2n

 (d) n 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 Which of the following statements about insertion sort is true asymptotically?

 

 

  (a) Insertion sort is slower than merge sort, and consumes about the same memory.

 (b) Insertion sort is slower than merge sort, but consumes less memory.

 (c) Insertion sort is slower than merge sort, and consumes more memory.

 (d) Insertion sort is faster than merge sort, but consumes less memory. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 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 of the code fragment above is

 

 

 

  (a) O(n)

 (b) O(n log n)

 (c) O(log n)

 (d) O(n2) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 5.

 Consider the following code fragment.

 

      for( int i = 1; i < n; i *= 2 ) body;

 

If body executes in O(1) time, then the asymptotic running time of the code fragment above is

 

 

 

  (a) O(n log n)

 (b) O(n2)

 (c) O(log n)

 (d) O(n) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Consider the following recursive definition of a function f.

 

int  f(int  n)

{

  if (n == 0) return 1;

  else return  f(n >> 1);

}

 

The asymptotic running time of the call f(n) is

 

 

 

  (a) O(log n)

 (b) O(n log n)

 (c) O(n2)

 (d) O(n) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 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) linear

 (d) logarithmic 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 8.

 Using the standard gradeschool method, what is the asymptotic running time of multiplying two numbers that are both n digits long?

 

 

  (a) 2n

 (b) n2

 (c) n3

 (d) n 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 Using the standard gradeschool method, what is the asymptotic running time of adding two numbers that are both n digits long?

 

 

  (a) n2

 (b) n

 (c) 2n

 (d) n3 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 10.

 Consider the following code fragment.

 

    for( int i = 0; i < n; i += 2 )

            for( int j = 0; j < n; j += 3 )

                  for( int k = 0; k < n; k += 4 ) body;

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n2)

 (b) O(n)

 (c) O(n3)

 (d) O(n log n) 

 

 Correct answer is  (c) 

 

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

 

1.

 What is the asymptotic running time of insertion sort on an input array with length n?

 

 

  (a) 2n

 (b) n log n

 (c) n2

 (d) n 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 2.

 Which of the following statements about insertion sort is true asymptotically?

 

 

  (a) Insertion sort is slower than merge sort, and consumes more memory.

 (b) Insertion sort is faster than merge sort, but consumes less memory.

 (c) Insertion sort is slower than merge sort, and consumes about the same memory.

 (d) Insertion sort is slower than merge sort, but consumes less memory. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 3.

 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 of the code fragment above is

 

 

 

  (a) O(n2)

 (b) O(n)

 (c) O(log n)

 (d) O(n log n) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 Consider the following code fragment.

 

      for( int i = 1; i < n; i *= 2 ) body;

 

If body executes in O(1) time, then the asymptotic running time of the code fragment above is

 

 

 

  (a) O(n)

 (b) O(n log n)

 (c) O(n2)

 (d) O(log n) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 Consider the following recursive definition of a function f.

 

int  f(int  n)

{

  if( n == 0 ) return 1;

  else return  f(n / 2);

}

 

The asymptotic running time of the call f(n) is

 

 

 

  (a) O(n log n)

 (b) O(n2)

 (c) O(log n)

 (d) O(n) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Consider the following recursive definition of a function f.

 

int  f(int  n)

{

  if (n == 0) return 1;

  else return  f(n >> 1);

}

 

The asymptotic running time of the call f(n) is

 

 

 

  (a) O(n2)

 (b) O(n log n)

 (c) O(log n)

 (d) O(n) 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 7.

 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) logarithmic

 (b) quadratic

 (c) exponential

 (d) linear 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 Consider the following code fragment.

 

      for( int i = 0; i < n; i++ )

            for( int j = 0; j < n; j++ )

                  for( int k = 0; k < n; k++ ) body;

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(2n)

 (b) O(n3)

 (c) O(n2)

 (d) O(n) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 1.7.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 Consider the following code fragment.

 

    for( int i = 0; i < n; i++ )

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

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n3)

 (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.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 10.

 Consider the following code fragment.

 

for( int i = 0; i < n; i += 2 )

  for(int  j = i; j > 0; j -= 3 ) body

 

If body executes in O(1) time, then the asymptotic running time of this code fragment is

 

 

 

  (a) O(n2)

 (b) O(n log n)

 (c) O(n)

 (d) O(n3) 

 

 Correct answer is  (a) 

 

 

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

Chapter 8:

 

 1.

 Access to ranges of elements in an STL container is typically handled by

 

 

  (a) pointers

 (b) suitable access member functions

 (c) iterators

 (d) references 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 2.

 Consider the following statement using the STL remove routine.

 

      remove( a, b, x );

 

What of the following accurately describes what the variables a and b represent?

 

 

 

  (a) pointers

 (b) references

 (c) containers

 (d) iterators 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 3.

 Consider the following declaration which makes use of a user-defined class Thing.

 

      vector<Thing>  A(10);

 

In order that it compile, the class Thing must have which of the following?

 

 

 

  (a) an assignment operator

 (b) a destructor

 (c) a default constructor

 (d) a copy constructor 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 Execution of the code fragment

 

    list<int>  A(10);

 

does which of the following?

 

 

 

  (a) Creates an empty linked list of ints, but reserves memory for 10 entries

 (b) Creates a linked list of 10 ints, with each element initially 0.

 (c) Creates a linked list of 10 ints, with each element initially containing random values.

 (d) Creates 10 linked list of ints, all initially empty. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 Consider the execution of the following.

 

    list<int>  A(10,20);

 

Which of the following accurately describes what is created?

 

 

 

  (a) A linked list of size 10, each containing 10 arrays of ints of size 20

 (b) An array of size 20 of linked list, each containing 20 ints

 (c) A linked list of 10 ints, with each element initially 20

 (d) a linked list of 10 linked lists, each containing 20 ints 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Execution of the code fragment

 

    stack<int,vector<int> >  S;

 

does which of the following?

 

 

 

  (a) Creates a stack of ints, based on an integer vector

 (b) Creates a vector of integer stacks

 (c) Creates a stack of integer vectors

 (d) Produces an execution error 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 Execution of the code fragment

 

    stack<int,list<int> >  S;

 

does which of the following?

 

 

 

  (a) Creates a list of integer stacks

 (b) Produces an execution error

 (c) Creates a stack of ints, based on an integer list

 (d) Creates a stack of integer lists 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 When using two iterators first and last to define a range of items in some container, which of the following is true concerning what they point to?

 

 

  (a) first points at the first item, and last at a position one past the last element.

 (b) first points at the first item, and last at the last element.

 (c) It depends on the type of container.

 (d) first points at a position one before the first item, and last at a position one past the last element. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 The STL contains a general purpose search function:

 

      find( first, last, x );

 

What does find return if it finds item x?

 

 

 

  (a) The Boolean value true

 (b) A reference to x

 (c) An iterator pointing to x

 (d) A pointer pointing to x 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Consider the following code fragment using the STL iota() routine.

 

      vector<int>  A(10);

      iota( A.begin(), A.end(), 0 );

 

Which of the following most accurately describes the result of executing this fragment?

 

 

 

  (a) Vector A is filled with the values 0, 1, 2, ..., 9.

 (b) The size of vector A is reset to 0.

 (c) A search for 0 is conducted in vector A.

 (d) Vector A is filled with 0s. 

 

 Correct answer is  (a) 

 

 

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

 

1.

 Consider the following code fragment.

 

      stack<int>  S;

      S.push(123);

      S.push(456);

 

Now consider the following statement.

 

   cout << S.pop() << endl;

 

Which of the following most accurately describes what goes wrong when that statement is executed?

 

 

 

  (a) An execution error occurs because pop() is a private member function.

 (b) pop() requires an argument.

 (c) An execution error occurs because an STL stack has no member function pop().

 (d) pop() does not return a value. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (d) No Feedback 

 

 

 

 

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

 

 2.

 Execution of the code fragment

 

    stack<int,vector<int> >  S;

 

does which of the following?

 

 

 

  (a) Produces an execution error

 (b) Creates a stack of ints, based on an integer vector

 (c) Creates a vector of integer stacks

 (d) Creates a stack of integer vectors 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 3.

 Execution of the code fragment

 

    stack<int,list<int> >  S;

 

does which of the following?

 

 

 

  (a) Creates a list of integer stacks

 (b) Creates a stack of ints, based on an integer list

 (c) Produces an execution error

 (d) Creates a stack of integer lists 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 For an STL iterator it, execution of the statement

 

    it--;

 

does which of the following?

 

 

 

  (a) Pre-decrements the item to which the iterator points.

 (b) Steps the iterator backwards to the previous item.

 (c) Decreases by 1 the size of the container pointed to by it.

 (d) Post-decrements the item to which the iterator points. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 What is the difference between a bidirectional iterator (BDI) and a random access iterator (RAI)?

 

 

  (a) A BDI cannot be moved backwards, but a RAI can.

 (b) A RAI supports post-increment, but a BDI does not.

 (c) The RAI can jump in arbitrary increments and decrements; a BDI can only move in increments/decrements of one.

 (d) They only differ with respect to efficiency, but they support the same operations. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Consider the following code fragment.

 

      list<int>::iterator  it;

      for(  it = L.end(); it != L.begin(); --it )

      cout << *it << endl;

 

Which of the following most accurately describes what is wrong with it?

 

 

 

  (a) The operator* cannot be used on an STL iterator.

 (b) There is no decrement operation for list iterators.

 (c) Linked lists in the STL are circular, so the loop will never terminate.

 (d) It will cause an attempt to access a non-existing list element. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 7.

 When using two iterators first and last to define a range of items in some container, which of the following is true concerning what they point to?

 

 

  (a) first points at a position one before the first item, and last at a position one past the last element.

 (b) It depends on the type of container.

 (c) first points at the first item, and last at a position one past the last element.

 (d) first points at the first item, and last at the last element. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 The STL contains a general purpose search function:

 

      find( first, last, x );

 

What does find return if it finds item x?

 

 

 

  (a) An iterator pointing to x

 (b) The Boolean value true

 (c) A reference to x

 (d) A pointer pointing to x 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 The STL contains a general purpose search function:

 

      find( first, last, x );

 

What does find return if it fails to find item x?

 

 

 

  (a) An iterator equal to begin

 (b) A NULL pointer

 (c) The Boolean value false

 (d) An iterator equal to last 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 10.

 The STL contains a general purpose search function:

 

      find( first, last, x );

 

What search method does find use?

 

 

 

  (a) It depends on the type of container.

 (b) Binary search

 (c) Linear search

 (d) It depends on whether the data are sorted. 

 

 Correct answer is  (c)

 

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

 

 

1.

 Access to ranges of elements in an STL container is typically handled by

 

 

  (a) iterators

 (b) suitable access member functions

 (c) pointers

 (d) references 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 2.

 Consider the following statement using the STL remove routine.

 

      remove( a, b, x );

 

What of the following accurately describes what the variables a and b represent?

 

 

 

  (a) iterators

 (b) references

 (c) pointers

 (d) containers 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 Consider the execution of the following.

 

   list<int>  A(10);

 

Which of the following accurately describes what is created?

 

 

 

  (a) A linked list of 10 ints, with each element initially 0.

 (b) An empty linked list of ints, but reserves memory for 10 entries.

 (c) A linked list of 10 ints, with each element initially containing random values.

 (d) 10 linked list of ints, all initially empty. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 4.

 Consider the execution of the following.

 

    list<int>  A(10,20);

 

Which of the following accurately describes what is created?

 

 

 

  (a) A linked list of 10 ints, with each element initially 20

 (b) A linked list of size 10, each containing 10 arrays of ints of size 20

 (c) An array of size 20 of linked list, each containing 20 ints

 (d) a linked list of 10 linked lists, each containing 20 ints 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 Execution of the code fragment

 

    stack<int,list<int> >  S;

 

does which of the following?

 

 

 

  (a) Creates a stack of ints, based on an integer list

 (b) Creates a stack of integer lists

 (c) Produces an execution error

 (d) Creates a list of integer stacks 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 6.

 For an STL iterator it, execution of the statement

 

    ++it;

 

does which of the following?

 

 

 

  (a) Pre-increments the item to which the iterator points.

 (b) Advances the iterator to the next item.

 (c) Post-increments the item to which the iterator points.

 (d)

Increase by 1 the size of the container pointed to by it.

 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 7.

 Execution of which of the following statements sets an STL iterator it so that it points to the first element of a container A?

 

 

  (a) A.reset( it );

 (b) it = A.begin();

 (c) begin( A, it );

 (d) A.begin( it ); 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 8.

 Consider the following code fragment.

 

      li    st<int>::const_iterator  it;

      for(  it = L.begin(); it != L.end(); ++it )

      *it = 0;

 

What is syntactically wrong with this fragment?

 

 

 

  (a) Nothing

 (b) The use of the prefix increment operator on a const iterator.

 (c) The assignment using a const iterator

 (d) The traversal using a const iterator 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 9.

 Consider the following code fragment.

 

      list<int>::iterator  it;

      for(  it = L.end(); it != L.begin(); --it )

      cout << *it << endl;

 

Which of the following most accurately describes what is wrong with it?

 

 

 

  (a) The operator* cannot be used on an STL iterator.

 (b) There is no decrement operation for list iterators.

 (c) It will cause an attempt to access a non-existing list element.

 (d) Linked lists in the STL are circular, so the loop will never terminate. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Consider the following code fragment using the STL iota() routine.

 

      vector<int>  A(10);

      iota( A.begin(), A.end(), 0 );

 

Which of the following most accurately describes the result of executing this fragment?

 

 

 

  (a) The size of vector A is reset to 0.

 (b) A search for 0 is conducted in vector A.

 (c) Vector A is filled with the values 0, 1, 2, ..., 9.

 (d) Vector A is filled with 0s. 

 

 Correct answer is  (c) 

 

 

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

 

 9.

 Consider the following statement using the STL sort() routine.

 

      sort( A.begin(), A.end(), f );

 

Which of the following most accurately describes the result of executing this statement?

 

 

 

  (a) Container A is sorted using the Boolean valued function f for comparisons.

 (b) Container A is sorted using the function f for assignments.

 (c) Container A is sorted using sorting algorithm f.

 (d) Container A is sorted by applying function f to its elements. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 

 

 10.

 Consider execution of the following statement.

 

      accumulate( A.begin(), A.end(), 0 );

 

Which of the following most accurately describes the effects?

 

 

 

  (a) The sum of the elements in vector A is computed.

 (b) All the elements in vector A are set to 0.

 (c) All of the elements of vector A are copied to A[0].

 (d) The number of 0's in vector A is counted. 

 

 Correct answer is  (a) 

 

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

 

 2.

 Execution of the code fragment

 

    list<int>  A(10);

 

does which of the following?

 

 

 

  (a) Creates a linked list of 10 ints, with each element initially 0.

 (b) Creates a linked list of 10 ints, with each element initially containing random values.

 (c) Creates 10 linked list of ints, all initially empty.

 (d) Creates an empty linked list of ints, but reserves memory for 10 entries 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 Consider the execution of the following.

 

   list<int>  A(10);

 

Which of the following accurately describes what is created?

 

 

 

  (a) An empty linked list of ints, but reserves memory for 10 entries.

 (b) A linked list of 10 ints, with each element initially 0.

 (c) 10 linked list of ints, all initially empty.

 (d) A linked list of 10 ints, with each element initially containing random values. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.1.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 

Chapter 9:

 

1.

 The size of an STL vector is defined to be the

 

 

  (a) maximum number of elements that can be stored in the vector without resizing

 (b) number of elements currently stored in the vector

 (c) number of bytes the vector occupies in memory

 (d) total of the sizes of the data members in the vector class 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 2.

 The capacity of an STL vector is defined to be the

 

 

  (a) number of elements currently stored in the vector

 (b) maximum number of elements the vector could possibly have on the given machine

 (c) maximum number of elements that can be stored in the vector without resizing

 (d) difference between the current number of elements and the maximum number of elements 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 3.

 Assume that L is an STL list object. Consider the following statement.

 

      while( L.size() > 0 ) { ... }

 

Which of the following most accurately describes what is wrong with that statement?

 

 

 

  (a) size() requires an argument.

 (b) The loop never terminates since size() always returns a positive value.

 (c) Does not compile, since size() is not a member function of class list.

 (d) The size() function takes time linear in the length of the list, so this is potentially very inefficient. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 4.

 Of the following code outlines, which provides the best way to obtain a stack class from an already existing linked list class?

 

 

  (a) template<class T> class Stack: public list<T> { ... };

 (b) template<class T> class Stack: private list<T> { ... };

 (c) template<class T> class Stack: { list<T> &L; ... };

 (d) template<class T> class Stack: { list<T> L; ... }; 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 For an adjacency list implementation of a graph with n vertices and e edges, what is the order of the time required to calculate all the outdegrees?

 

 

  (a) O(n * e)

 (b) O(n + e)

 (c) O(n^2)

 (d) O(n^3) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 6.

 For an adjacency list implementation of a graph with n vertices and e edges, what is the order of the time required to calculate all the indegrees?

 

 

  (a) O(n * e)

 (b) O(n + e)

 (c) O(n^3)

 (d) O(n^2) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 7.

 The time to convert an adjacency list implementation of a graph with n vertices and e edges to an adjacency matrix implementation has what order?

 

 

  (a) O(n + e)

 (b) O(n^2)

 (c) O(n * e)

 (d) O(n log n) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 8.

 The definition of the product of two Boolean matrices is the same as the usual product of matrices except that

 

 

  (a) false is interpreted as 0, true is interpreted as 1, and then ordinary matrix multiplication is used

 (b) addition is interpreted as logical-and, and multiplication is interpreted as logical-or

 (c) addition is interpreted as logical-or, and multiplication is interpreted as logical-and

 (d) addition is interpreted as logical-and, and multiplication is interpreted as logical-xor 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 If A is an adjacency matrix for a graph G, then the matrix product A * A represents all pairs of vertices (u,v) such that

 

 

  (a) there is a vertex x such that (u,x) and (x,v) are edges of G

 (b) u and v are connected by two edges

 (c) there is a vertex x such that (u,x) and (v,x) are edges of G

 (d) u and v are not connected by an edge 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 The time to compute the reverse graph for an adjacency matrix implementation of a graph with n vertices and e edges has what order? (The reverse graph has the same vertices but all the edges are reversed.)

 

 

  (a) O(n^2)

 (b) O(n)

 (c) O(n + e)

 (d) O(n * e) 

 

 Correct answer is  (a) 

 

 

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

 

2.

 If A is an STL vector, then the effect of executing the statement

 

      A[i] = x;

 

is to

 

 

 

  (a) create an iterator x pointing to position i in the array

 (b) check array bounds, enlarge the vector if necessary, and then write x to position i

 (c) write x to position i of the vector, without bounds checking

 (d) check array bounds, and write x to position i if and only if i is in the proper range 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 3.

 Consider the following program segment.

 

vector<int>  A(10);

A.resize(0);

A.push_back(5000);

 

At the end of an execution of this fragment, the size of vector A is

 

 

 

  (a) 5000

 (b) 0

 (c) 1

 (d) 10 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 Consider the following two ways of creating a vector filled with 1,2,...,1000.

 

   // method I

       vector<int>   A(1000);             

       iota( A.begin(), A.end(), 1 );

      // method II

    vector<int>   A;

    for( int i = 1; i <= 1000; i++ )

          A.push_back( i );

 

Which of the following is true about these two methods?

 

 

 

  (a) Method I is slightly faster than II.

 (b) Which method is faster depends on machine and compiler.

 (c) Method II is slightly faster than I.

 (d) Method I is very much faster than II. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 Consider the following code fragment concerning the STL list class.

 

      list<int>   L(10);

      L[3] = 555;

 

The fragment will produce a compile time error because

 

 

 

  (a) the class list does not support a constructor with given length

 (b) the class list does not support the bracket operator

 (c) L is an array of 10 list objects, and we cannot assign 555 to a list object

 (d) the class list only supports the const version of the bracket operator 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 6.

 For an adjacency list implementation of a graph with n vertices and e edges, what is the order of the time required to calculate all the outdegrees?

 

 

  (a) O(n^2)

 (b) O(n^3)

 (c) O(n * e)

 (d) O(n + e) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 7.

 The time to convert an edge list implementation of a graph with n vertices and e edges to an adjacency list implementation has what order?

 

 

  (a) O(n^2)

 (b) O(n + e)

 (c) O(n * e)

 (d) O(n log n) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 The time to compute the reverse graph for an adjacency matrix implementation of a graph with n vertices and e edges has what order? (The reverse graph has the same vertices but all the edges are reversed.)

 

 

  (a) O(n^2)

 (b) O(n + e)

 (c) O(n * e)

 (d) O(n) 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 The time to compute the reverse graph for an adjacency list implementation of a graph with n vertices and e edges has what order? (The reverse graph has the same vertices but all the edges are reversed.)

 

 

  (a) O(n * e)

 (b) O(n + e)

 (c) O(n^2)

 (d) O(n) 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.2.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 10.

 The time to perform depth first search, starting at the first vertex of a graph with n vertices and e edges implemented as an adjacency list has what order?

 

 

  (a) O(n^2)

 (b) O(n * e)

 (c) O(n + e)

 (d) O(n) 

 

 Correct answer is  (c) 

 

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

 

 4.

 Which of the following describes a property that const iterators for lists have that ordinary iterators for lists do not?

 

 

  (a) In the const version, the iterators can only be incremented, but never decremented

 (b) In the const version, there is no operator*()

 (c) In the const version, operator*() returns a const reference

 (d) In the const version, operator*() copies the value 

 

 Correct answer is  (c) 

 

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

 

 

 1.

 If A is an STL vector, then the effect of executing the statement

 

    A.push_back( x );

 

is to

 

 

 

  (a) check whether the capacity of A is larger than the size of A, enlarges A if necessary, and append x to A

 (b) append x to A, without checking the size and capacity of A

 (c) append x to A if and only if the size of A is less than capacity of A

 (d) append x to A if there is room, and otherwise overwrites the currently last element of A 

 

 Correct answer is  (a) 

 

 

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

 

Chapter 10:

 

1.

 Consider the following recursive definition of a function search that performs search in a binary tree.

 

bool search(Type  a, Tree  T)  {

  if (empty(T))  {

    return false;

  }

  else

  if(a == data(T))  {

    return true;

  }

  else  {

    bool  bl = search(a, left(L));

    bool  br = search(a, right(L));

    return  bl || br;

  }

}

 

Which of the following describes a problem with the function when executed?

 

 

 

  (a) It might fail to terminate.

 (b) It might take linear time unnecessarily.

 (c) It might terminate prematurely.

 (d) It might take quadratic time unnecessarily. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 2.

 A node in a tree that does not have a predecessor is called

 

 

  (a) a parent node

 (b) an internal node

 (c) a leaf

 (d) a root 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 3.

 Which of the following is true about the total number of nodes in a tree with depth 2?

 

 

  (a) It is at most 1.

 (b) It is at most 3.

 (c) It is at most 2.

 (d) There is no bound on the number of nodes. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 Which of the following is true about the total number of nodes in a binary tree with depth 2?

 

 

  (a) It is at least 7.

 (b) It is at least 2.

 (c) It is at least 3.

 (d) It is at least 4. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 5.

 A full node in a binary tree has how many children?

 

 

  (a) 1 or 2

 (b) 2

 (c) 1

 (d) 0 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 6.

 In the standard array implementation of a binary tree the nodes are stored in an array. What is the convention for the array position of the parent of the node in position p of the array?

 

 

  (a) p/2

 (b) 2 * p + 1

 (c) 2 * p

 (d) p - 1 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 Consider the following pseudo-code, which indicates part of a standard binary tree algorithm.

 

      print( node )

      {

      if( there is a left child )  print( left child );

      print  data;

      if( there is a right child )  print( right child );

      }

 

Which of the following is the standard name for this algorithm?

 

 

 

  (a) Inorder traversal

 (b) Postorder traversal

 (c) Preorder traversal

 (d) Binary search 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 8.

 A tree can be implemented as a graph whose vertices are the nodes of the tree and where an edge (u,v) indicates that u is the parent of v. Which of the following indicates all the nodes of such an implementation that are reachable by a depth first search starting at the root?

 

 

  (a) Only the interior nodes of the tree

 (b) Only the nodes in the left subtree of the root

 (c) All nodes in the tree

 (d) Only the leaves of the tree 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 9.

 During a failed search for an element in a completely balanced binary search tree of size 1,000,000, approximately how many nodes of the tree is visited?

 

 

  (a) 200

 (b) 20

 (c) 10,000

 (d) 1000 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 10.

 If numbers 1,2,...,n are inserted into a binary search tree, in order, then the result for large n is a

 

 

  (a) tree where all nodes are full

 (b) totally unbalanced tree

 (c) completely balanced tree

 (d) mildly unbalanced tree 

 

 Correct answer is  (b) 

 

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

 

 

3.

 Which of the following is true about the depth of a tree with exactly 3 nodes?

 

 

  (a) There is no bound on the depth.

 (b) It is at most 1.

 (c) It is at most 2.

 (d) It is at most 3. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 4.

 Which of the following is true about the total number of nodes in a binary tree with depth 2?

 

 

  (a) It is at most 4.

 (b) It is at most 2.

 (c) It is at most 7.

 (d) There is no bound on the number of nodes. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 A full node in a binary tree has how many children?

 

 

  (a) 1

 (b) 0

 (c) 2

 (d) 1 or 2 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 In the standard array implementation of a binary tree the nodes are stored in an array. What is the convention for the array position of the parent of the node in position p of the array?

 

 

  (a) 2 * p + 1

 (b) p/2

 (c) 2 * p

 (d) p - 1 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 7.

 Consider the following pseudo-code, which indicates part of a standard binary tree algorithm.

 

      print( node )

      {

      print  data;

      if( there is a left child )  print( left child );

      if( there is a right child )  print( right child );

      }

 

Which of the following is the standard name for this algorithm?

 

 

 

  (a) Binary search

 (b) Postorder traversal

 (c) Preorder traversal

 (d) Inorder traversal 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 Searching for an element in a binary search tree takes O(s) steps where s is

 

 

  (a) the depth of the tree

 (b) 1 (the search takes constant time)

 (c) the size of the tree

 (d) the number of leaves of the tree 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 If numbers 1,2,...,n are inserted into a binary search tree, in order, then the result for large n is a

 

 

  (a) totally unbalanced tree

 (b) tree where all nodes are full

 (c) mildly unbalanced tree

 (d) completely balanced tree 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 Which of the following sequences cannot represent values visited during a binary search?

 

 

  (a) 10, 20, 30, 40, 50

 (b) 30, 50, 40, 45, 42

 (c) 50, 40, 30, 20, 10

 (d) 10, 20, 30, 15, 18 

 

 Correct answer is  (d) 

 

 

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

 

3.

 A node in a tree that does not have any children is called

 

 

  (a) an internal node

 (b) an empty node

 (c) a leaf

 (d) a root 

 

 Correct answer is  (c) 

 

 

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

 

4.

 Which of the following is true about the depth of a tree with exactly 3 nodes?

 

 

  (a) There is no bound on the depth.

 (b) It is at most 2.

 (c) It is at most 3.

 (d) It is at most 1. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 Which of the following is true about the total number of nodes in a tree with depth 2?

 

 

  (a) It is at most 2.

 (b) It is at most 3.

 (c) There is no bound on the number of nodes.

 (d) It is at most 1. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

In the standard array implementation of a binary tree, the nodes are stored in an array. What is the convention for the array position of the left child of the node in position p of the array?

 

 

  (a) 2 * p + 1

 (b) 2 * p

 (c) p + 1

 (d) p/2 

 

 Correct answer is  (b) 

 

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

 

6.

 Which of the following is true about the total number of nodes in a binary tree with depth 2?

 

 

  (a) It is at least 2.

 (b) It is at least 3.

 (c) It is at least 4.

 (d) It is at least 7. 

 

 Correct answer is  (b) 

 

 

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

 

9.

 Suppose S is a binary search tree and x is not an element of S. Consider the following code fragment.

 

      S.insert( x );

      S.remove( x );

 

If T is the tree that results from executing the fragment, what is the relationship between S and T?

 

 

 

  (a) S and T differ in exactly one leaf.

 (b) S is a proper subtree of T.

 (c) S and T are the same.

 (d) S and T differ in exactly the root. 

 

 Correct answer is  (c) 

 

 

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

 

 

3.

 Which of the following is true about the depth of a tree with exactly 3 nodes?

 

 

  (a) It is at most 1.

 (b) There is no bound on the depth.

 (c) It is at most 3.

 (d) It is at most 2. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 Which of the following is true about the total number of nodes in a tree with depth 2?

 

 

  (a) It is at most 2.

 (b) There is no bound on the number of nodes.

 (c) It is at most 1.

 (d) It is at most 3. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 Which of the following is true about the total number of nodes in a binary tree with depth 2?

 

 

  (a) It is at most 7.

 (b) There is no bound on the number of nodes.

 (c) It is at most 4.

 (d) It is at most 2. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 6.

 Which of the following is true about the total number of nodes in a binary tree with depth 2?

 

 

  (a) It is at least 4.

 (b) It is at least 7.

 (c) It is at least 2.

 (d) It is at least 3. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 7.

 In the standard array implementation of a binary tree the nodes are stored in an array. What is the convention for the array position of the parent of the node in position p of the array?

 

 

  (a) p - 1

 (b) 2 * p

 (c) p/2

 (d) 2 * p + 1 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 Consider the following pseudo-code, which indicates part of a standard binary tree algorithm.

 

      print( node )

      {

      if( there is a left child )  print( left child );

      print  data;

      if( there is a right child )  print( right child );

      }

 

Which of the following is the standard name for this algorithm?

 

 

 

  (a) Preorder traversal

 (b) Postorder traversal

 (c) Inorder traversal

 (d) Binary search 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.3.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 9.

 Which of the following traversals of a binary search tree will produce a sorted list if a visit to a node prints what is stored there?

 

 

  (a) Postorder

 (b) Inorder

 (c) Preorder

 (d) Level-by-level 

 

 Correct answer is  (b) 

 

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

 

 

Chapter 11:

 

1.

 In the context of hashing, what is meant by a collision?

 

 

  (a) Two key/value pairs have the same value.

 (b) The insertion algorithm cannot find an empty slot in the table.

 (c) Two different keys hash to the same slot.

 (d) The hash function returns a value larger than the table size. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 2.

 Which of the following is true about a good hash function?

 

 

  (a) It should produce apparently random values for given items.

 (b) It should never output a prime number.

 (c) It should produce small outputs for small inputs.

 (d) It should only output prime numbers. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

 Suppose a user-defined hash function has the following prototype.

 

      size_t  hash( const Thing& x );

 

Suppose further that it produces values of size up to 32 bits. To use this function with a hash table of size m, the user should

 

 

 

  (a) call the function repeatedly until a value less than m appears

 (b) compute hash( x ) % m

 (c) compute hash( x ) / m

 (d) modify x until a value less than m appears 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 Which of the following indicates the reaction time, in general, for searching in an open addressing hash table of size 1,000,000 with a load factor of 0.9?

 

 

  (a) It may fail to find an element that is present.

 (b) It will be almost instantaneous.

 (c) It may "find" an element that is no longer there.

 (d) It will be noticeably slow. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 In searching for an entry with key k in a chaining hash table, the slot p = hash(k) is computed, after which it is necessary to

 

 

  (a) compute p + k to find the right position for the entry

 (b) traverse a linked list to check if any entry there has key k

 (c) check if the entry in slot p has key k

 (d) check if the entry in slot p, or p+1, p+2, and so forth, has key k 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 6.

 In searching for an entry with key k in an open addressing hash table, the slot p = hash(k) is computed, after which it is necessary to

 

 

  (a) check if the entry in slot p has key k, then p+1 if necessary, then p+2, and so forth.

 (b) traverse a linked list to check if any entry there has key k

 (c) compute p + k to find the right position for the entry

 (d) check only if the entry in slot p has key k 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 7.

 What is the purpose of using memoizing?

 

 

  (a) To eliminate recursion in computing function values

 (b) To speed up access in a hash table

 (c) To store return values of functions, in order to avoid recomputation

 (d) To improve the memory requirements of hash tables 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 Consider the following outline of a memoized function.

 

      int  f( int x ) { ... }

 

How many steps does it take to make 10000 calls to f on input x = 1000?

 

 

 

  (a) About 10000 times the number of steps used in computing f(1000)

 (b) About 10000 steps

 (c) A small, constant number of steps

 (d) About 10000 steps, plus computing f(1000) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 9.

 The appropriate return type for a search function on a chaining hash table is

 

 

  (a) a Boolean

 (b) a pair consisting of a Boolean and an iterator

 (c) a list node

 (d) an iterator 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 10.

 Consider the following definition of a function hash.

 

   size_t  hash( const char *str )

      {

          size_t  h = 0;

          for( ; *str != '0'; str++ )

               h = h*256 + *str;

      }

 

What, if anything, is wrong with hash as a hash function for null-terminated strings?

 

 

 

  (a) Nothing

 (b) It is very slow to compute.

 (c) If the string is very long, there will be overflow.

 (d) It only takes into account the last few characters long strings. 

 

 Correct answer is  (d) 

 

 

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

 

 

1.

 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,v)

 (b) hash() (a random position computed by the hash function using k)

 (c) hash(v)

 (d) hash(k) 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 In the context of hashing, what is meant by a collision?

 

 

  (a) Two key/value pairs have the same value.

 (b) Two different keys hash to the same slot.

 (c) The insertion algorithm cannot find an empty slot in the table.

 (d) The hash function returns a value larger than the table size. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 3.

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

 

 

  (a) Hash tables take up a lot of memory.

 (b) Collisions will occur.

 (c) Hash functions are hard to compute.

 (d) Access in hash tables is slow. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 4.

 Suppose a user-defined hash function has the following prototype.

 

      size_t  hash( const Thing& x );

 

Suppose further that it produces values of size up to 32 bits. To use this function with a hash table of size m, the user should

 

 

 

  (a) modify x until a value less than m appears

 (b) compute hash( x ) / m

 (c) call the function repeatedly until a value less than m appears

 (d) compute hash( x ) % m 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 5.

 Which of the following indicates the reaction time, in general, for searching in an open addressing hash table of size 1,000,000 with a load factor of 0.9?

 

 

  (a) It will be almost instantaneous.

 (b) It may fail to find an element that is present.

 (c) It may "find" an element that is no longer there.

 (d) It will be noticeably slow. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 6.

 In searching for an entry with key k in an open addressing hash table, the slot p = hash(k) is computed, after which it is necessary to

 

 

  (a) traverse a linked list to check if any entry there has key k

 (b) check only if the entry in slot p has key k

 (c) compute p + k to find the right position for the entry

 (d) check if the entry in slot p has key k, then p+1 if necessary, then p+2, and so forth. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 7.

 Consider the following outline of a memoized function.

 

      int  f( int x ) { ... }

 

How many steps does it take to make 10000 calls to f on input x = 1000?

 

 

 

  (a) About 10000 times the number of steps used in computing f(1000)

 (b) About 10000 steps, plus computing f(1000)

 (c) A small, constant number of steps

 (d) About 10000 steps 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 8.

 Which of the following correctly indicates where keys and associated values are stored in hash tables when chaining is used?

 

 

  (a) Each key/value pair is stored in a node of a linked list.

 (b) The keys are stored in the list header, and the associated values are stored in the linked lists.

 (c) Each key is stored in the table, and the associated value is stored in a linked list.

 (d) The keys are stored in the table, and the associated values are stored in the list header. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00  

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 9.

 Which of the following correctly indicates where keys and associated values are stored in hash tables when open addressing is used?

 

 

  (a) Each key/value pair is stored in the table.

 (b) The values are stored in a slot in the table, and keys are stored in the slots that follow.

 (c) Each key is stored in a slot in the table, and the associated value is stored in one of the slots that follow.

 (d) The keys are stored in the list header, and the associated values are stored in linked lists. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 Consider the following definition of a function hash.

 

      size_t  hash( const char *str )

      {

          size_t  h = 0;

          for( ; *str != '0'; str++ )

               h += *str;

      }

 

What, if anything, is wrong with hash as a hash function for null-terminated strings?

 

 

 

  (a) It makes no sense to add characters.

 (b) All permutations of a word hash to the same slot.

 (c) Nothing

 (d) If the string is very long, there will be overflow. 

 

 Correct answer is  (b) 

 

 

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

 

1.

 In the context of hashing, what is meant by a collision?

 

 

  (a) The insertion algorithm cannot find an empty slot in the table.

 (b) Two key/value pairs have the same value.

 (c) The hash function returns a value larger than the table size.

 (d) Two different keys hash to the same slot. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 2.

 If a hash table of size m contains n items, what is the load factor of the table?

 

 

  (a) n/m

 (b) n + m

 (c) m - n

 (d) m/n 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 3.

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

 

 

  (a) Collisions will occur.

 (b) Hash tables take up a lot of memory.

 (c) Access in hash tables is slow.

 (d) Hash functions are hard to compute. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 4.

 Which of the following is true about a good hash function?

 

 

  (a) It should never output a prime number.

 (b) It should only output prime numbers.

 (c) It should produce apparently random values for given items.

 (d) It should produce small outputs for small inputs. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 5.

 In searching for an entry with key k in an open addressing hash table, the slot p = hash(k) is computed, after which it is necessary to

 

 

  (a) check only if the entry in slot p has key k

 (b) traverse a linked list to check if any entry there has key k

 (c) compute p + k to find the right position for the entry

 (d) check if the entry in slot p has key k, then p+1 if necessary, then p+2, and so forth. 

 

 Correct answer is  (d) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (d) No Feedback 

 

 

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

 

 6.

 When the load factor in a hash table becomes too high, the table must be resized. What should happen with the old entries?

 

 

  (a) All the old entries should go into the same positions they occupied in the old table.

 (b) The old entries should be spread out in the new table (e.g., if the new table is twice as large, an old entry at slot p should be moved to slot 2*p).

 (c) They go into the slots that result from recomputing all the hash values.

 (d) The resize command for the underlying array will take care of everything. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 7.

 Which of the following correctly indicates where keys and associated values are stored in hash tables when open addressing is used?

 

 

  (a) Each key is stored in a slot in the table, and the associated value is stored in one of the slots that follow.

 (b) The keys are stored in the list header, and the associated values are stored in linked lists.

 (c) Each key/value pair is stored in the table.

 (d) The values are stored in a slot in the table, and keys are stored in the slots that follow. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 8.

 The appropriate return type for a search function on a chaining hash table is

 

 

  (a) a Boolean

 (b) a pair consisting of a Boolean and an iterator

 (c) an iterator

 (d) a list node 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 For a templated hash table to cope with some user-defined key type Thing, the user has to specify

 

 

  (a) the type Thing and a hash function for Thing.

 (b) just the size of the table, templates take care of the rest.

 (c) the type Thing, a hash function for Thing, and equality testing for Thing.

 (d) just the type Thing. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 10.

 Consider the following definition of a function hash.

 

      size_t  hash( const char *str )

      {

          size_t  h = 0;

          for( ; *str != '0'; str++ )

               h += *str;

      }

 

What, if anything, is wrong with hash as a hash function for null-terminated strings?

 

 

 

  (a) It makes no sense to add characters.

 (b) Nothing

 (c) If the string is very long, there will be overflow.

 (d) All permutations of a word hash to the same slot. 

 

 Correct answer is  (d) 

 

 

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

 

 

1.

 If a hash table of size m contains n items, what is the load factor of the table?

 

 

  (a) n/m

 (b) m - n

 (c) m/n

 (d) n + m 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 2.

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

 

 

  (a) Access in hash tables is slow.

 (b) Hash tables take up a lot of memory.

 (c) Collisions will occur.

 (d) Hash functions are hard to compute. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 3.

 Suppose a user-defined hash function has the following prototype.

 

      size_t  hash( const Thing& x );

 

Suppose further that it produces values of size up to 32 bits. To use this function with a hash table of size m, the user should

 

 

 

  (a) compute hash( x ) % m

 (b) modify x until a value less than m appears

 (c) compute hash( x ) / m

 (d) call the function repeatedly until a value less than m appears 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 4.

 Which of the following indicates the reaction time, in general, for searching in a chaining hash table of size 1,000,000 with a load factor of 0.9?

 

 

  (a) It will be almost instantaneous.

 (b) It will be noticeably slow.

 (c) It may "find" an element that is no longer there.

 (d) It may fail to find an element that is present. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 0.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 5.

 In order for the division method to work in the context of hashing, the table size should be

 

 

  (a) a power of two

 (b) a perfect square

 (c) a prime

 (d) anything but a prime 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 6.

 Which of the following correctly indicates where keys and associated values are stored in hash tables when chaining is used?

 

 

  (a) The keys are stored in the list header, and the associated values are stored in the linked lists.

 (b) Each key is stored in the table, and the associated value is stored in a linked list.

 (c) Each key/value pair is stored in a node of a linked list.

 (d) The keys are stored in the table, and the associated values are stored in the list header. 

 

 Correct answer is  (c) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (c) No Feedback 

 

 

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

 

 7.

 Which of the following correctly indicates where keys and associated values are stored in hash tables when open addressing is used?

 

 

  (a) The keys are stored in the list header, and the associated values are stored in linked lists.

 (b) Each key/value pair is stored in the table.

 (c) Each key is stored in a slot in the table, and the associated value is stored in one of the slots that follow.

 (d) The values are stored in a slot in the table, and keys are stored in the slots that follow. 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 8.

 The appropriate return type for a search function on a chaining hash table is

 

 

  (a) a list node

 (b) a pair consisting of a Boolean and an iterator

 (c) a Boolean

 (d) an iterator 

 

 Correct answer is  (b) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (b) No Feedback 

 

 

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

 

 9.

 Consider the following definition of a function hash.

 

      size_t  hash( const char *str )

      {

          size_t  h = 0;

          for( ; *str != '0'; str++ )

               h += *str;

      }

 

What, if anything, is wrong with hash as a hash function for null-terminated strings?

 

 

 

  (a) All permutations of a word hash to the same slot.

 (b) It makes no sense to add characters.

 (c) Nothing

 (d) If the string is very long, there will be overflow. 

 

 Correct answer is  (a) 

 

 Your score on this question is: 10.00 

 

 Feedback:

   See section 2.4.1 of the course notes.

   (a) No Feedback 

 

 

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

 

 10.

 Consider the following definition of a function hash.

 

   size_t  hash( const char *str )

      {

          size_t  h = 0;

          for( ; *str != '0'; str++ )

               h = h*256 + *str;

      }

 

What, if anything, is wrong with hash as a hash function for null-terminated strings?

 

 

 

  (a) Nothing

 (b) If the string is very long, there will be overflow.

 (c) It is very slow to compute.

 (d) It only takes into account the last few characters long strings. 

 

 Correct answer is  (d)