This is a closed-book exam. Explain your answers clearly. Stay cool.

1. (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.

   • Let N be 4, and start with an empty queue. Draw the state of the queue after the operations Add(A), Add(B), Add(C), Delete(), Delete(), Add(D), Add(E).
   • Implement the functions IsFull, IsEmpty, Add, Delete, and Front. (Do not assume that N is 4.)

2. (9 points) For each of the following algorithms, describe the running time T(N) in terms of big oh, omega, and theta.

   • Using the usual scan from one end to the other, find the maximum value in an unsorted array of N integers.
   • Search for a given integer in a sorted array of N integers using binary search.
   • Sort an array of N integers using Insertion Sort.

3. (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.

4. (6 points) When we overloaded operator<< for the ListString class, we used the following interface:

   ostream& operator<<( ostream& out, const ListString& s );

   • Why does this operator need to return an ostream object instead of void?
   • Why does this operator return a reference to the ostream object rather than a copy of the object as is more usual with return values?

5. (2 points) What movie should I watch this weekend?

6. (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.
   

   • Write a code fragment that will add a new node containing the letter 'B' to the beginning of the linked list.
   • Write a code fragment that will add a new node containing the letter 'A' to the end of the linked list.

7. (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 );
       }