For this exam, you may use your textbook and a language reference, my sample code, and your own programs and notes. You may not use other books, web pages, or code. If you get stuck, talk to me, but please don't talk to anyone else (not even Jeremy Carr or the lab assistants) about the exam. You may discuss syntax and system problems with Jeremy or the lab assistants, but you must tell them that you are working on an exam.

1. (8 points) Add an implementation of the following function to the CString class.

   
   	// Erase removes from the string the character at
   	// the given 0-based index.  If the index is out of
   	// range (i.e. < 0 or >= the length of the string),
   	// Erase does nothing.
   
   	void CString::Erase( int index )
   	{
   	}
   

2. (8 points) Suppose you have two stacks, with Push, Pop, Size, and Top operations available to you. Show how you can use those two stacks to implement a single queue. In particular, show implementations of Enqueue, Front, and Dequeue in terms of Push, Pop, and Top. Pseudo-code is sufficient.

3. (8 points) Write iterative and recursive versions of the CString::Length() function. (Actually, since I already wrote the iterative version, you only need to write a recursive version.) Discuss the complexity of the running time and the memory use of each version of Length.

4. (10 points) Consider the following code (also found in something.cpp). List all the functions that get called during the run of this program, in the order in which they get called. Explain why each function call occurs. (Some explanations will be easy--"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()
   	{
   		mNothing = 0;
   	}
   
   	Something::Something( int N )
   	{
   		mNothing = N;
   	}
   
   	Something::Something( const Something& otherThing )
   	{
   		mNothing = otherThing.mNothing;
   	}
   
   	Something::~Something()
   	{
   	}
   
   	const Something& Something::operator=( const Something& otherThing )
   	{
   		mNothing = otherThing.mNothing;
   		return( *this );
   	}
   
   	void Something::Print() const
   	{
   		cout << 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 ";
   		thatThing.Print();
   		cout << endl;
   	}
   
   	int main()
   	{
   		Something	a;
   		Something	b( 17 );
   		Something	c = b;
   
   		ThisFunction( a );
   		ThatFunction( b );
   
   		return( 0 );
   	}
   

5. (3 points) Tell me a joke, if you wish.

6. (8 points) Write an iterative tree traversal for a binary tree whose nodes are of the form

   
   	struct Node
   	{
   		char	mData;
   		Node	*mLeftChild;
   		Node	*mRightChild;
   	};
   

   Your traversal should print the mData field when visiting a node.

   You may find the following fragment of pseudo-code helpful. (On the other hand, you may not. In any case, I used this idea in my own solution to this problem.)

   
   	current = &node
   	while( current != NULL )
   	{
   		push current
   		current = current->mLeftChild
   	}