This is a closed-book exam. Explain your answers clearly. Stay cool.
(12 points) Suppose we are implementing a queue of characters using a circular array with N entries, encapsulated in a class like so:
const int N = ??; class Queue { public: Queue(); virtual ~Queue(); void Add( char ch ); void Delete(); char Front(); bool IsFull(); bool IsEmpty(); private: char mQueue[N]; int mFront; int mBack; };
Suppose we initialize both mFront and mBack to zero to create an empty queue.
(9 points) For each of the following algorithms, describe the running time T(N) in terms of big oh, omega, and theta.
(6 points) The C++ keyword const can appear in several different contexts. Show brief examples of three different kinds of uses of const, and explain what const means in each example.
(6 points) When we overloaded operator<< for the ListString class, we used the following interface:
ostream& operator<<( ostream& out, const ListString& s );
(2 points) What movie should I watch this weekend?
(8 points) Consider the following code:
class Node { char mData; Node *mNext; }; Node *head = NULL; // ...later that very same program... // head now points to a linked list of some unknown length.
(9 points) Show the output produced during the run of the following program. Explain briefly why each function call occurs. (Some explanations will be easy--for example, "ThisFunction() got called explicitly by main()"--but others will be trickier.)
#include <iostream> class Something { private: int mNothing; public: Something(); Something( int N ); Something( const Something& otherThing ); ~Something(); const Something& operator=( const Something& otherThing ); void Print() const; }; Something::Something() { cout << "Something()" << endl; mNothing = 0; } Something::Something( int N ) { cout << "Something( " << N << ")" << endl; mNothing = N; } Something::Something( const Something& otherThing ) { cout << "Something( otherThing : " << otherThing.mNothing << ")" << endl; mNothing = otherThing.mNothing; } Something::~Something() { cout << "~Something(), " << mNothing << endl; } const Something& Something::operator=( const Something& otherThing ) { cout << "operator=" << endl; mNothing = otherThing.mNothing; return( *this ); } void Something::Print() const { cout << "Print: " << mNothing; } void ThisFunction( Something thisThing ) { cout << "This thing has value "; thisThing.Print(); cout << endl; } void ThatFunction( const Something& thatThing ) { Something theOtherThing = thatThing; cout << "That thing has value "; thatThing.Print(); cout << endl; cout << "The other thing has value "; theOtherThing.Print(); cout << endl; } int main() { Something a; Something b( 17 ); Something c = b; ThisFunction( a ); ThatFunction( b ); return( 0 ); }