Fall 2000 PIC 10b Practice Midterm

The real midterm will have five problems of equal value and should be about the same difficulty. It will cover up till what we do in class on Oct 23. One problem from the practice midterm is guaranteed to be on the actual midterm.

1. Define the following terms and if it might be called by the
   run-time system then say when:

   a) copy constructor
   b) friend function
   c) destructor
   d) private variable
   e) public variable

2. Prove using the definition of O(f(N)) that:

NlogN is an element of O(N²).

3. Prove using the definition of O(f(N)) that:

N² is not an element of O(N^3/2).

4. Explain why one might want to wrap a header file with
   the #ifndef / #endif preprocessor instructions. Give an example
   of how to do this wrapping.

5. Explain what the this pointer is and give an example of its use.

6. Consider the recurrence relation:

C₁ = 0
C_N = C_N-1 +log N.

Show C_N is in O(NlogN).

7. Explain with diagrams  and words as examples what a singly linked-list
   is and how to add and delete nodes from one.

8. Explain what the quick-find algorithm is (Ch1 Sedgewick).

9. Recall the class Pair from homework 1. Explain with code how to
   overload the extraction operator << as a friend function
   so that one can output the two int's stored in a Pair each on
   a separate line.

10.Explain with code how to dynamically allocate arrays and objects in C++.
   Then explain how to delete them.