CMSC--341 Data Structures 
FALL 1998 Exam 1 Review Questions

The exam will be a full-period, closed-book, closed-notes exam. 

Use the following class definitions as appropriate 
The Complex class models complex numbers of the form a+bi
where 'a' is the real part, 'b' is the imaginary part
and 'i' is the sqrt(-1);

The class stores the real part in 'realPart' and
the imaginary part in 'imagPart'.

class Complex
{
  private:
    double realPart, imagPart;

  public:
    Complex ();
    Complex (double r, double i = 0);
    Complex (const Complex& z);

    void setReal (double r);
    void setImag (double i);
    int  getReal () const;
    int  getImag () const;

    Complex& operator= (const Complex& rhs);
    friend operator* (const Complex& lhs, const Complex& rhs);
};


The Vector class implements a one-dimensional array type. The contents of the 
array must be of type VectType. The class has a pointer data member which is 
used to point to a stored array. The size of this array is set upon construction, 
but may be modified dynamically by subsequent operations. Subscript checking 
is done. 

typedef double VectType; 
class Vector 
{ 
  public: 
    // Vector of size VectSize, filled with "zeros"
    Vector (unsigned int VectSize); 

    // Vector of size VectSize, filled with InitElem 
    Vector (unsigned int VectSize, VectType & InitElem); 
    Vector (const Vector &); 
    operator const VectType * (); 
    VectType & operator [] (unsigned int) const; 
    VectType & operator = (const Vector &); 
    unsigned int Length() const; // return size of Vector 

private: 
    VectType * data; 
    unsigned int size; 
}; 


Although these questions are numbered, the absence of a number,
or the duplication of a number has no signifigance.  It just
means I can't type or can't count.

1. Define abstract data type

2. Define an ADT for a Stack

3. What is a private class member? a public class member? 

4. What is a member function? a non­member function? a friend function? 

5. Most class operations can be implemented as member, friend, or ordinary
functions. What are the factors which influence your decision on the type 
of function to use? When you have a choice, what type of function do you 
prefer for overloading operators? Why do you have that preference? 

6. When is it not advisable to rely on default constructors, destructors, and 
assignments? Why? 

7. When are destructors called? 

8. When are constructors called? 

9. Explain why the argument to a copy constructor must be a reference. 

10. What is the value of the expression cout << i 
    (a) when i is the int 25? 
    (b) when i is the float 35.5? 

11. Given the declaration int * foo, write C++ statements: 
    (a) to allocate one integer and point foo at it. 
    (b) to allocate contiguous storage for 10 integers,
        and point foo at the first one. 
    (c) to free the storage for the int allocated in part (a).
    (d) to free the storage for the 10 ints allocated in part (b).

12. What is the form of the copy constructor for class FOO, an
arbitary class?


13. Consider the following short sequence of statements: 
    int i = 1; 
    int j = 2; 
    i = test(j); 
    cout << "i: " << i << "j: " << j << endl; 

Which of the following definitions of the function test would compile
without errors? For those that do compile, show what would be printed.
For those that do not compile, indicate the source of error. 

  (a) int test(int x) 
      {
        x = 4;
        return 5; 
      }
 
  (b) int test(int & x) 
      {
        x = 4; 
        return 5; 
      }

  (c) int test(const int & x) 
      { 
        x = 4; 
        return 5; 
      }

14. If a class does not use any dynamically allocated storage,
does it need a destructor? 

15. Object-oriented programming emphasizes the notion of programming with 
objects. An object encapsulates information about itself as well as providing
methods (i.e., functions) which describe the operations which can be done 
on or by an object. Explain why extensive use of friend functions may 
compromise the spirit of object­oriented programming. 

16. Explain why the programmer should provide a copy constructor for a class 
that has a pointer data member (like the Vector class above).

17. What does it mean when a member function is declared to be const?
For example, getReal() of the Complex class. 

18. Given the following function declaration (<type1> and <type2> are
any two types), discuss the reasons why a programmer might have chosen 
const <type2>& for the argument and const <type1>& as the return 
value. 
    const <type1>& Foo (const <type2>&); 

19. What is meant by the declaration const int * foo? 

20. What is meant by the declaration int * const foo? 

21. The following function returns a reference, but it's not a good idea. Why 
not? 
  int & Foo ()
  {  
    int temp = 5; 
    return temp; 
  }

22. Write the code for the constructor Complex (double r, double i = 0)
for the Complex class. 

23. Write the code for the copy constructor for Complex. 

24. The sum of two complex numbers is given by the equation 
    (a + bi) + (c + di) = (a + c) + (b + d)i, 
where a and c are the Real parts and b and d are the imaginary parts
of their respective complex numbers

Write the code for an overloaded + operator for the Rational class. 
  (a) as a member function, 
  (b) as a friend function, 
  (c) as an ordinary (non-member and non­friend) function. 

Show the corresponding declaration, if any, which must appear in the class 
definition.

25. Write the code for the overloaded += operator for the Complex class. 

26. Give the prototypes of the overloaded output operator <<
for Complex (write the definitions without the body).


27. Describe the type conversions (including how the conversion gets
accomplished) that will be done when each of the statements 1, 2, and 3 are 
executed in the following function: 

  float foo(int i) 
  {
    Complex  x(2,3), y(4), z; 
    float f = 3.0; 
    z = x * y;                 // statement 1 
    z = x * i;                 // statement 2 
    z = x * f;                 // statement 3 
  }

29. Write the code for an overloaded insertion operator << for Complex.
The printed form of a complex number should be [a + bi] or [a - bi]
(brackets included.  In particular, DO NOT output [a + -bi].
Show the declaration which must appear in the class definition, if applicable.

30. Write the code for an assignment operator for Complex

31. If a programmer does not write a default constructor for Complex, does 
the compiler supply one? 

32. If a programmer does not write a destructor for Complex, does the
compiler supply one? 

33. If Complex did not have a programmer-defined destructor what could
happen to the execution of a program using the class? 

34. Discuss each of the following lines (what is being done, what constructors 
are being called, what conversions are happening): 

  main ()
  {
    Complex x = 3; 
    Complex z = x; 
    double y = 5; 

    x = y; 

  }

35. Define each of the constructors for the Vector class. 

36. If a programmer does not write a default constructor for Vector, does the 
compiler supply one? 

37. If a programmer does not write a destructor for Vector, does the compiler 
supply one? 

38. If Vector did not have a programmer­defined destructor what could happen 
to the execution of a program using the class? 

39. Write the code for an assignment operator for Vector. 

40. The assignment operator for Vector should test to avoid the assignment 
when the left-hand and right-hand sides of the assignment expression are 
the same object. Why? 

41. Which constructor is at work in the declaration
        Vector * v = new Vector? 

42. Explain: "Overloading the assignment operator is optional for the Complex 
class, but essential for the Vector class."

43. Order the following growth rates from smallest to largest
     n, log(n), 2**n, sqrt(n), nlog(n)

44. Prove the sum of the integers from 1 to n = n(n+1)/2

45.For the following class, write the header line of the definition for
the constructor and for the friend function (write the definition without
the body).

  template <class T>
  class Foo
  {
    public:
      Foo (int);
      friend T *Func(int &, T&);

    private:
      T *data;
      int size;
  };

46. Rewrite the following function as a template function which can take
any (identical) type reference for x and y and which returns the 
appropriate type.

  int Foo (int& x, int& y)
  {
    int temp;

    temp = x;
    x = y;
    y = temp;
    return x + y;
  }



47. Show how the function of question 46 would be called with
f and g as arguments in

  main ()
  {
    float f = 1.2;
    float g = 3.7;

    // call to Foo with f and g as arguments is:

  }

48. Prove O(cf(x)) = O(f(x)) (constant's don't matter)

 

49. Suppose T1(n) = O(f(n) ) and T2(n) = O(f(n)).

Prove: T1(n) + T2(n) = O(f(n))

 

50. Prove that 2n+1 = O(2n)

 

 51. Describe an array implementation for the stack ADT (describe the data structure, cursors, etc.). Show how the operations isEmpty(), isFull(), top(), pop(), and push() are implemented.

top() returns the value of the element at the top of the stack, without removing it.
pop() removes the element at the top of the stack and
push() adds an element to the top of the stack

52. Describe a linked-list implementation for the stack (describe the data structure, pointers, etc.). Show how the operations isEmpty(), isFull(), top(), pop(), and push() are implemented.
top() returns the value of the element at the top of the stack without removing it.
pop() removes the element at the top of the stack and
push() adds an element to the top of the stack

53. Describe the advantages and disadvantages of the array and linked-list implementations of the stack ADT.
Consider the asymptotic behavior for each of the operations isEmpty(), isFull(), top(), pop(), and push().
Also consider the storage requirements for each implementation. 

Consider the following code fragment

  1.    int sum = 0;
  2.    for (int i = 0; i < N; i++)
  3.       for (int j = 0; j <= N; j++)
  4.          sum++;

  5.    for (int p = 0; p < N * N; p++)
  6.       for (int q = 0; q < p; q++)
  7.          sum++

54. How many times is statement 4 executed?
     a. O(N)  b. O(N2) c. O(N3) d. O(N4) e. O(N5)

55. How many times is statement 7 executed?
     a. O(N)  b. O(N2) c. O(N3) d. O(N4) e. O(N5)

56. What is the running time of the fragment?
     a. O(N)  b. O(N2) c. O(N3) d. O(N4) e. O(N5)