CSE2050 Final Exam, open book, open notes.  Name _______ (Fall 2001)

1. What does the following print? (3 points each)
     int a[]={2,4,6,8};
a.   cout << a[1]+8 / 5;      // 5 (/ has precedence)
b.   cout << &a[3] - a;       // 3 (subtraction of pointers)
c.   int* p=a+1; cout << *p;  // 4
d.   cout << p[1];            // 6
e.   cout << *p++;            // 4 (post-increment of p after printing)

2. Write a declaration for a vector of int, v, such that its elements
are initialized to a copy of the array a above (6 pts).

  vector<int> v(a, a+4);

3. True or false? (3 points each)
a. A protected data member is accessible to a derived class.            T
b. A copy constructor parameter should be passed by value.              F
     (it should be passed by const reference
     or else infinite recursion results)
c. A const method cannot modify data members.                           T
d. If an exception is not caught, the program terminates.               T
e. A derived object may be used where a base object is expected.        T
f. An array created with new[] is automatically deleted when
     the pointer pointing to it goes out of scope.                      F
       (there is no garbage collection)
g. Passing by const reference is faster than passing by reference.      F
     (they are the same, but both are faster than pass by value)
h. Returning a reference to a local non-static variable is unsafe.      T
     (because the reference is to an object that no longer exists)
i. A derived constructor should initialize inherited data members.      F
     (it should initialize the base class, and the base class should
     initialize the data members)
j. Overridden methods should be declared virtual in the base class.     T
k. If a base class needs a copy constructor, then the derived does too. F
     (the default copy constructor is to call the copy constructor of
     the base class, which is adequate even if the base allocates memory)
l. The classes string, vector, and ostream are all in namespace std.    T
m. Only templated or inlined functions should be defined in a header.   T
     (ordinary functions should not be defined in headers because the
     code is duplicated by each .cpp file that includes it)

4. Given the following, write code to print an alphabetical list of
all words that occur exactly 3 times in the input (10 pts).

  map<string, int> dict;
  string s;
  while (cin >> s)
    dict[s]++;

  // Answer - the map is already sorted alphabetically
  for (map<string, int>::const_iterator p=dict.begin(); p!=dict.end(); ++p)
    if (p->second == 3)
      cout << p->first << endl;

  // You can also use iterator instead of const_iterator

5. Below is a templated interface for a Stack class, and an example of
how one derived implementation might be used.  On the back, write the
derived templated class Stack using your choice of representation (30 pts).

  template <class T>
  class StackInterface {
  public:
    virtual void push(const T&) = 0;  // Add an item
    virtual T pop() = 0;  // Remove last pushed item and return it
    virtual bool empty() const = 0;  // true if nothing left to pop
    virtual ~Stack() {}  // corrected in class: virtual ~StackInterface() {}
  };
  main() {  // Read words from input and print them in reverse order
    Stack<string> st; string s;
    while (cin >> s) st.push(s);
    while (!st.empty()) cout << st.pop() << endl;
  }

Answer: there are many possible answers, but all require some
private data structure to represent the stack contents (such as
a vector, list, or array), and StackInterface<T> as an (abstract)
base class.  pop() differs from pop_back() in that it returns a value.

  template <class T>
  class Stack: public StackInterface<T> {
  private:
    vector<T> v;  // stack contents with the top at the back
  public:
    void push(const T& x) {v.push_back(x);}
    T pop() {
      T tmp = v.back();  // or v[v.size()-1]
      v.pop_back();
      return tmp;
    }
    bool empty() const {return v.empty();}  // or v.size()==0
  };

The default constructor works fine for this implementation, although
it may not for others.  It would be

    Stack(): v() {}

The code would be similar using list<T>.  If you use an array allocated
with new[], you would need a destructor, copy constructor, operator=, and
some way to handle stack full.