Computer Science 153 - Introduction to Data Structures

Exam 1 Question Pool - Fall Semester 2001


The exam questions will be taken directly from those questions listed below.



Chapter 1 Program Specification, Design, and Analysis


What is a precondition?

What is a postcondition?

Is it always possible for a function to check that its precondition is true?

Suppose that you accidently call a correctly implemented function, but the precondition is false. Is the function guaranteed to halt with a nice message?

Write the first few lines of this function so that it uses the assert facility to check its precondition:

         void exam(int i)
         // Precondition: i is not equal to 42.
         ...

Why is the order of an algorithm generally more important than the speed of the processor?

Convert each time formula to the best possible big-O notation. Do not include any spurious constants in your big-O answer.

                        Time Formula           Big O
                              10n                                                 .
                              2n²                                                 .
                              3*log2 (n)                                         .
                              2n² + 10n

Why is writing easily modifiable code important?
          A. Easily modifiable code generally has a quicker run time.
          B. Most real world programs require change at some time.
          C. Most text editors make it easy to modify code.
          D. Several people may be writing the same function at the same time.

Which phase of the software life-cycle is usually the most expensive?
          A. Analysis and specification of the task
          B. Design
          C. Implementation
          D. Maintenance and evolution

What will happen if a function is executed and the precondition for the function is not met?
          A. An error message will be printed.
          B. The program will loop indefinitely.
          C. The system will crash.
          D. Any of the above results could happen.

If the precondition fails, it is a good idea to write a useful error message and then halt the program. Why is the program halted?
          A. Most operating systems forbid continuation.
          B. The function is no longer guaranteed to make the postcondition true.
          C. The function's memory requires have become exponential (or worse).
          D. The function's running time has become exponential (or worse).

What ANSI C function is used to stop the program execution when a precondition is not met.
          A. assert();
          B. exit();
          C. return();
          D. void();

Which of these function calls will always cause a program to halt? (x is an int variable).
          A. assert(10 > 0);
          B. assert(10 < 0);
          C. assert(x < 0);
          D. None of the above will always cause a program to halt.

What does a run-time analysis usually count?
          A. The number of arithmetic and other operations required for the
               program to run
          B. The number of megabytes required for the program to run
          C. The number of seconds required for the program to run
          D. The number of seconds plus the number of megabytes
          E. The number of seconds times the number of megabytes

If run-time analysis has shown the number of operations to be 1+2+3+...+n, which of these is the correct big-O expression for describing the algorithm?
          A. O(log n)
          B. O(n)
          C. O(n log n)
          D. O(n²)

If run-time analysis has shown the number of operations to be n²+35n+6, which of these is the correct big-O expression for describing the algorithm?
          A. O(n³)
          B. O(n²)
          C. O(n)
          D. O(42)

True  False  For all possible inputs, a linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.

True  False   An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.

What term is used to describe an O(n) algorithm.
          A. Constant
          B. Linear
          C. Logarithmic
          D. Quadratic

What term is used to describe an O(1) algorithm.
          A. Constant
          B. Linear
          C. Logarithmic
          D. Quadratic

What term is used to describe an O(n²) algorithm.
          A. Constant
          B. Linear
          C. Logarithmic
          D. Quadratic

Here is some code for an integer variable n:

         while (n > 0)
         {
             n = n/10; // Use integer division
         }
What is the worst-case time analysis for the above loop?
          A. O(1)
          B. O(log n)
          C. O(n)
          D. O(n²)

Express the run-time formula (n - 2)*(n - 4) using big-O notation:
          A. O(1)
          B. O(8)
          C. O(log n)
          D. O(n)
          E. None of the above

Why is it important to test boundary values when testing programs?
          A. Calculating by hand, it's easy to find the right answers for
               boundary values.
          B. Debuggers are easier to use when testing boundary values.
          C. In practice, a large proportion of errors arise from boundary values.
          D. The correct execution of a function on all boundary values proves a function is correct.

How may boundary values for a function be found?
          A. Pick values that are one step away from different behavior.
          B. Pick values that make the precondition equal to the postcondition.
          C. Pick values where the precondition is false.
          D. Pick values where the postcondition is false.



Chapter 2 Abstract Data Types and C++ Classes


For public part of the Throttle declaration below, mark each function member header as follows: Mark C for any constructor; mark X for any function that is forbidden from changing the throttle’s data fields.

         class Throttle
         {
         public:
             Throttle( );
             Throttle(int size);
             void shut_off( );
             void shift(int amount);
             double flow( ) const;
             bool is_on( ) const;
             ...

What is an inline member function?

Here is the start of a class declaration: 
         class Foo 
         { 
         public: 
           void x(Foo f); 
           void y(const Foo f); 
           void z(Foo f) const; 
           ... 
Which of the three member functions can alter the PRIVATE member variables of the Foo object that activates the function? 
          A. Only x can alter the private member variables of the object that activates the function. 
          B. Only y can alter the private member variables of the object that activates the function. 
          C. Only z can alter the private member variables of the object that activates the function. 
          D. Two of the functions can alter the private member variables of the object that activates the 
             function. 
          E. All of the functions can alter the private member variables of the object that activates the 
              function. 

Is it possible for a member function of a class to activate another member function of the same class?
          A. No.
          B. Yes, but only public member functions.
          C. Yes, but only private member functions.
          D. Yes, both public and private member functions can be activated within another member
               function.

Can two classes contain member functions with the same name?
          A. No.
          B. Yes, but only if the two classes have the same name.
          C. Yes, but only if the main program does not declare both kinds
          D. Yes, this is always allowed.

What is the common pattern of writing class definitions?
          A. Member functions and member variables are both private.
          B. Member functions are private, and member variables are public.
          C. Member functions are public, and member variables are private.
          D. Member functions and member variables are both public.

Consider this class definition:
         class Quiz
         {
         public:
             Quiz( );
             int f( );
             int g( ) const;
         private:
             double score;
         };
Which functions may carry out an assignment score=1.0; to the private member variable score?
          A. Both f and g can carry out the assignment.
          B. f can carry out the assignment, but not g.
          C. g can carry out the assignment, but not f.
          D. Neither f nor g can carry out the assignment.

Suppose that the Foo class does not have an overloaded assignment operator. What happens when an assignment a=b; is given for two Foo objects?
          A. The automatic assignment operator is used
          B. The copy constructor is used
          C. Compiler error
          D. Run-time error

When should you use a const reference parameter?
          A. Whenever the data type might be many bytes.
          B. Whenever the data type might be many bytes, the function
               changes the parameter within its body, and you do NOT want
               these changes to alter the actual argument.
          C. Whenever the data type might be many bytes, the function changes the parameter within
               its body, and you DO want these changes to alter the actual argument.
          D. Whenever the data type might be many bytes, and the function does not change the
               parameter within its body.

Here is a small function definition:
         void f(int i, int &k)
         {
             i = 1;
             k = 2;
         }
Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?
          A. Both x and y are still 0.
          B. x is now 1, but y is still 0.
          C. x is still 0, but y is now 2.
          D. x is now 1, and y is now 2.

Here is a function prototype and some possible function calls:
         int day_of_week(int year, int month = 1, int day = 1);
         // Possible function calls:
            cout << day_of_week( );
            cout << day_of_week(1995);
            cout << day_of_week(1995, 10);
            cout << day_of_week(1995, 10, 4);
How many of the function calls are legal?
          A. None of them are legal
          B. 1 of them is legal
          C. 2 of them are legal
          D. 3 of them are legal
          E. All of them are legal

Which kind of functions can access private member variables of a class?
          A. Friend functions of the class
          B. Private member functions of the class
          C. Public member functions of the class
          D. All of the above can access private member variables
          E. None of the above



Chapter 3 Container Classes

Suppose that I have the following declarations:
         int data[100];
         size_t i;
Write a small segment of C++ code that will
     shift data[50]...data[98] up one spot to the locations data[51]...data[99].
     then insert the number 42 at location data[50].

Suppose that I have the following declarations:
         int data[100];
         size_t i;
Write a small segment of C++ code that will
     shift data[51]...data[99] down one spot to the locations data[50]...data[98].
     the value of data[99] remains at its original value.

Suppose that the Bag is implemented with a fixed-size array. Which of these operations are likely to have a constant O(1) worst-case time?
          A. insert
          B. occurrences
          C. remove
          D. None of (A), (B), and (C) have a constant worst-case time
          E. TWO of (A), (B), and (C) have a constant worst-case time
          F. ALL of (A), (B), and (C) have a constant worst-case time

Suppose that the Bag class is efficiently implemented with a fixed array with a capacity of 4000, as in Chapter 3. Choose the best description of b's member variables after we execute these statements:
         Bag b;
         b.insert(5);
         b.insert(4);
         b.insert(6);

What will be the values of b.used and b.data after the statements?
          A. b.used is 3, b.data[0] is 4, b.data[1] is 5, and b.data[2] is 6
          B. b.used is 3, b.data[0] is 5, b.data[1] is 4, and b.data[2] is 6
          C. b.used is 3, b.data[0] is 6, b.data[1] is 4, and b.data[2] is 5
          D. b.used is 3, b.data[0] is 6, b.data[1] is 5, and b.data[2] is 4

Suppose that the Bag class is efficiently implemented with a fixed array with a capacity of 4000. We execute these statements:
         Bag b;
         b.insert(5);
         b.insert(4);
         b.insert(6);
         b.remove(5);

          A. b.used is 2, b.data[0] is 4, b.data[1] is 6
          B. b.used is 2, b.data[0] is 6, b.data[1] is 4
          C. b.used is 3, b.data[0] is 4, b.data[1] is 6
          D. b.used is 3, b.data[0] is 6, b.data[1] is 4

I have an array named data, which contains n integers. I want to print all of the numbers, starting at data[0]. BUT if the number 42 occurs, then I want to stop my printing just before the 42 (without printing the 42!) Here is most of the for-loop to accomplish that:

         for (i = 0;  ___________________________________________; i++)
             cout << data[i] << endl;

What is the correct way to fill in the blank? (Be careful, the order of checking can make a difference)
          A. (data[i] != 42) && (i < n)
          B. (data[i] != 42) || (i < n)
          C. (i < n) && (data[i] != 42)
          D. (i < n) || (data[i] != 42)
          E. More than one of the above answers is correct.

Suppose that the Bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
          A. insert
          B. occurrences
          C. remove
          D. TWO of the above are likely to have a constant worst-case time.
          D. ALL of (A), (B), and (C) are likely to have a constant worst-case time.

What is the best C++ statement to use when a program must choose between several alternatives that are controlled by the value of a single variable?
          A. do-while statement
          B. for-statement
          C. if-else statement
          D. switch statement
          E. while statement



Chapter 4 Pointers and Dynamic Arrays

Suppose that p is an int* variable. Write several lines of code that will make p point to an array of 100 integers, place the numbers 0 through 99 into the array components, and return the array to the heap. Do not use malloc.

What happens if you call new but the heap is out of memory?

Draw a picture of memory after these statements:
         int i = 42;
         int k = 80;
         int* p1;
         int* p2;
         p1 = &i;
         p2 = &k;

Draw a picture of memory after these statements:
         int i = 42;
         int k = 80;
         int* p1;
         int* p2;
         p1 = &i;
         p2 = &k;
         *p1 = *p2;

Draw a picture of memory after these statements:
         int i = 42;
         int k = 80;
         int* p1;
         int* p2;
         p1 = &i;
         p2 = &k;
         p1 = p2;

Consider the following statements:
         int *p;
         int i;
         int k;
         i = 42;
         k = i;
         p = &i;
After these statements, which of the following statements will change the value of i to 75?
          A. k = 75;
          B. *k = 75;
          C. p = 75;
          D. *p = 75;
          E. Two or more of the answers will change i to 75.

Consider the following statements:
        int i = 42;
        int j = 80;
        int *p1;
        int *p2;
        p1 = &i;
        p2 = &j;
        *p1 = *p2;
        cout << i << j << endl;
What numbers are printed by the above output statement?
          A. 42 and then another 42
          B. 42 and then 80
          C. 80 and then 42
          D. 80 and then another 80

Consider the following statements:
         int i = 1;
         int k = 2;
         int *p1;
         int *p2;
         p1 = &i;
         p2 = &k;
         p1 = p2;
         *p1 = 3;
         *p2 = 4;
         cout << i;
What is printed by the above output statement?
          A. 1
          B. 2
          C. 3
          D. 4

Consider the following statements:
          int i = 1;
          int k = 2;
          int* p1;
          int* p2;
          p1 = &i;
          p2 = &k;
          p1 = p2;
          *p1 = 3;
          *p2 = 4;
          cout << k;
What is printed by the above output statement?
          A. 1
          B. 2
          C. 3
          D. 4

Consider the following statements:
          int i = 1;
          int k = 2;
          int* p1;
          int* p2;
          p1 = &i;
          p2 = &k;
          *p1 = *p2;
          *p1 = 3;
          *p2 = 4;
          cout << i;
What is printed by the above output statement?
          A. 1
          B. 2
          C. 3
          D. 4

In which location do dynamic variables reside?
          A. The code segment.
          B. The data segment.
          C. The heap.
          D. The run-time stack.

In which location do automatic variables reside?
          A. The code segment.
          B. The data segment.
          C. The heap.
          D. The run-time stack.

When should a pointer parameter p be a reference parameter?
          A. When the function changes p, and you want the change to affect
               the actual pointer argument.
          B. When the function changes p, and you do NOT want the change to
               affect the actual pointer argument.
          C. When the function changes *p, and you want the change to affect the the object that is
               pointed at.
          D. When the function changes *p, and you do NOT want the change to affect the the object
               that is pointed at.
          E. When the pointer points to a large object.

Suppose you have the following function prototype
         void goop(int z[ ]);
and variable declaration:
         int x[10];
     Which is the correct way to call the goop function with x as the argument:
          A. goop(x);
          B. goop(x[ ]);
          C. goop(x[10]);
          D. goop(&x);
          E. goop(&x[ ]);

Suppose that the goop function from the previous question changes the value of z[1]. Does this change effect the value of the actual argument?
          A. Yes
          B. No

Here is a function declaration:
         void goo(int* x)
         {
             *x = 1;
         }
Suppose that a is an int* variable pointing to some integer, and *a is equal to zero. What is printed if you print *a after the function call goo(a)?
          A. 0
          B. 1
          C. address of a
          D. address of x
          E. None of the above

Suppose that a new Foo class has this prototype for an overloaded assignment operator:
         void operator =(const Foo& source);
In an assignment statement a = b, what will be the actual argument for the parameter source?
          A. a
          B. b

When a class uses dynamic memory, what member functions should be provided by the class?
          A. The assignment operator.
          B. The copy constructor.
          C. A destructor.
          D. All of the above.

Which situation does not use the copy constructor?
          A. Calling a function with a reference parameter
          B. Calling a function with a value parameter
          C. Declaring a variable to be a copy of another existing object
          D. Returning a value from a function
          E. All of the above situations use the copy constructor

Suppose that you want to declare an array of characters to hold a null terminated string with exactly 9 letters. Which declaration is best?
          A. char s[8];
          B. char s[9];
          C. char s[10];
          D. char s[11];
          E. char s[12];

Suppose that x and y are two null terminated strings. Which expression will return true when x and y refer to the same sequence of characters?
          A. (x = y)
          B. (x == y)
          C. (x != y)
          D. (strcmp(x, y))
          E. None of the above.

Suppose that you want to develop two different + operators that calculate and return an object of some class. Which statement is correct?
          A. One operator must be a friend and the other must not.
          B. One operator must be public and the other private.
          C. The operators must have a different parameter lists.
          D. It is not possible to have two different + operators.

Given:
    char city[10] = "Rolla";
    char state[10] = "Missouri";
    char city_state[20];
Show how you would get city_state to contain the values in city and state plus the comma ( Rolla, Missouri)  Do not make use of CStrings

Given:
    char czNum[10] = "123";
    int value;
Show how you would get the integer value of czNum stored into value.

The following class is intended to be exactly like your assignment #3.

   Given 
       class CBag 
   { 
   public: 
       CBag(); 
       void Insert(const int a_value); 
       bool Remove(const int a_value); 
       bool Find(const int a_value);
       bool Empty();
   private: 
       int m_MaxSize; 
       int m_CurSize; 
       int m_Data[10]; 
   }; 

Code the constructor function for CBag exactly as it would appear in CBag.cpp.

Code the Find(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Insert(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Remove(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Empty() function for CBag exactly as it would appear in CBag.cpp.

The following class is intended to be exactly like your assignment #4.

Given 
       class CBag 
   { 
   public: 
       CBag(); 
       void Insert(const CString a_value); 
       bool  Remove(const CString a_value); 
       bool Find(const CString a_value); 
   private: 
       int m_MaxSize; 
       int m_CurSize; 
       char * m_Data[10];
   }; 

Code the constructor function for CBag exactly as it would appear in CBag.cpp.

Code the Find(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Insert(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Remove(...) function for CBag exactly as it would appear in CBag.cpp.

Code the Empty() function for CBag exactly as it would appear in CBag.cpp.