This is a closed-book, in-class exam. Put your answers in the blue book, and label your work appropriately. Explain your answers clearly.

1. (20 points) What output does the following program produce? I will grade the five sections separately. Make sure to label your answers by section. You may assume the program compiles and runs (it does--I checked it).

   
   #include	
   
   #define		salmon(a)	(a=b)
   
   int guppy( int, int );
   void walleye( int, char * );
   void carp( char *, char * );
   int herring( int, int );
   int flounder( int, int );
   
   void main()
   {
   	char	this[100] = "wish";
   	char	that[100] = "clam";
   	char	theOther[100] = "oyster";
   	int	someNumber;
   
      /* Section 1 */
   	printf( "guppy: %d\n", guppy( 1, 2 ) );
   	
      /* Section 2 */
   	someNumber = 5;
   	walleye( someNumber, this );
   	printf( "walleye: %d %s\n", someNumber, this );
   	
      /* Section 3 */
   	carp( that, theOther );
   	printf( "carp: %s %s\n", that, theOther );
   	
      /* Section 4 */
   	printf( "herring: %d\n", herring( 3, 4 ) );
   	
      /* Section 5 */
   	printf( "flounder: %d\n", flounder( 5, 6 ) );
   	
   }
   
   
   int guppy( int a, int b )
   {
   	return( a == b );
   }
   
   void walleye( int a, char *b )
   {
   	a = 6;
   	b[0] = 'f';
   }
   
   void carp( char *a, char *b )
   {
   	a = b;
   }
   
   int herring( int a, int b )
   {
   	return( (a > b) ? 0 : 1 );
   }
   
   int flounder( int a, int b )
   {
   	salmon( b );
   	return( a + b );
   }
   
   
   

2. (8 points) Suppose we use a 6-element array called queue[] to implement a queue of characters (it's a small queue), using the circular array approach. Suppose the indices front and back start out with values 0 and 5, respectively (that is, the queue is empty). If we then do the following:

   Add('A'), Add('N'), Delete, Add('O'), Delete, Add('S'), Add('T'),
   Delete, Add('R'), Add('I'), Delete, Add('C'), Add('H')

   what is the state of the queue? That is, show the contents of each of the 6 slots in the array, and the values of front and back.

3. (10 points) Suppose we implement character strings as linked lists of CharNode's, where CharNode is defined by

   
   typdef struct CharNode
   {
   	char		c;
   	struct CharNode	*next;
   } CharNode;
   

   Write the function int StringLength( CharNode *string ) that returns the length of the given string.

4. (8 points) Suppose we have a stack of characters available to us, with the operations Initialize, Push, Pop, and IsEmpty. We don't know how the stack data type is implemented, nor do we care. All we care is that we can declare a stack, initialize it to empty, push and pop at will, and test for emptiness.

   Consider the following function.

   
   void MysteryFunction( char s[] )
   {
   	int	i;
   	char	c;
   	stack	theStack;
   
   	Initialize( &theStack );
   	for( i=0; s[i] != '\0'; i++ )
   		Push( &theStack, s[i] );
   
   	while( !IsEmpty( theStack ) )
   	{
   		c = Pop( &theStack );
   		putchar( c );
   	}
   }
   

   • What does MysteryFunction() do?
   • Why would Initialize(), Push(), and Pop() require us to pass the address of the stack, while IsEmpty() would not?
5. (2 points) I'm going to a conference in sunny Philadelphia next week. What should I read on the plane?
6. (6 points) If you start with an empty Binary Search Tree (BST) and add to it nodes with the keys 5, 2, 1, 8, 7, 6, 10, 9 in that order, what does the resulting tree look like?
7. (6 points) Consider the following traversal routine for BST's, assuming a BSTNode is a structure with an integer key and pointers to a left subtree and a right subtree.

   
   void Traverse( BSTNode *root )
   {
   	if( root != NULL )
   	{
   		Traverse( root->left );
   		Traverse( root->right );
   		printf( "%d ", root->key );
   	}
   }
   

   If you call Traverse with the root of the tree you built in the previous problem as its argument, what output do you get? I will grade this problem based on the tree you actually wrote down on the previous problem, whether that problem was correct or not.