Dear AP Computer Science teacher:

The following are my solutions to the AP Computer Science free-response
questions from 1999, the first year the exam was delivered in C++.  You should
feel free to use them in whatever way you wish but realize that they are
provided as a resource for you, the teacher, and, as such, you are not
authorized to publish or distribute them beyond normal class use.  They also
represent my own work as outgoing Chief Reader for AP CS and are not an
official ETS document.

One way to best utilize these programs is to write your own solutions to the
various problems and then compare your solutions to what I have provided.
If you have any comments/questions, please feel free to either write or call
me at the address given above.  Thank you for your interest in AP.  I wish
you much success with your AP courses in this and ensuing years.

				Mark

                       SOLUTION - A Exam Problem #1 (1999)


a)  void ComputeGPA(apvector<StudentInfo> & roster, int numStudents)
    {int i;

        for (i = 0; i < numStudents; i++)
	    if (roster[i].creditHours == 0)
		roster[i].GPA = 0.0;
	    else
		roster[i].GPA = roster[i].gradePoints / roster[i].creditHours;
    }


b)  bool IsSenior(const StudentInfo & student)
    {
	return (student.creditHours >= 125 && student.GPA >= 2.0);
    }


c)  void FillSeniorList(const apvector<StudentInfo> & roster,
	int numStudents, apvector<StudentInfo> & seniors, int & numSeniors)
    {int i;

        numSeniors = 0;
	
        for (i = 0; i < numStudents; i++)
	    if (IsSenior(roster[i]))
	    {
		seniors[numSeniors] = roster[i];
		numSeniors++;
	    }
    }
                       SOLUTION - A Exam Problem #2 (1999)


a)  int WordIndex(const apstring & word,
		  const apvector<apstring> & wordList, int numWords)
    {int i;

	for (i = 0; i < numWords; i++)
	    if (wordList[i] >= word)
		return i;
	return numWords;
    }


    int WordIndex(const apstring & word,
		  const apvector<apstring> & wordList, int numWords)
    {int i=0;

        while (i < numWords && wordList[i] < word)
	    i++;
	return i;
    }


b)  void InsertInOrder(const apstring & word,
			apvector<apstring> & wordList, int & numWords)
    {int position, i;

	position = WordIndex(word, wordList, numWords);

	if (position == numWords)
	{
	    wordList[numWords] = word;
	    numWords++;
	}
	else if (wordList[position] != word)
	{
	    for (i = numWords; i > position; i--)
		wordList[i] = wordList[i-1];
	    wordList[position] = word;
	    numWords++;
	}
}
               SOLUTION - A Exam Problem #3/AB Exam Problem #2 (1999)


a)  void BigInt::Div2()
    {int carryDown = 0, i, d;
	
	for (i = NumDigits() - 1; i >= 0; i--)
	{
	    d = GetDigit(i);
	    ChangeDigit(i, d / 2 + carryDown);
	    carryDown = (d % 2) * 5;
	}
	Normalize();
    }


    void BigInt::Div2()
    {int carryDown = 0, i, d;
	
	for (i = myNumDigits - 1; i >= 0; i--)
	{
	    d = int(myDigits[i] - '0');
	    myDigits[i] = char((d / 2 + carryDown) + '0');
	    carryDown = (d % 2) * 5;
	}
	Normalize();
    }


b)  BigInt DivPos(const BigInt & dividend, const BigInt & divisor)	//A
	or
    BigInt operator/(const BigInt & dividend, const BigInt & divisor)	//AB

    {BigInt low(0), high(dividend), mid;

        while (!(low == high))
	{
	    mid = low + high + 1;
	    mid.Div2();
	    if (mid * divisor > dividend)
		high = mid - 1;
	    else
		low = mid;
	}
	return low;
    }
               SOLUTION - A Exam Problem #4/AB Exam Problem #1 (1999)


a)  Quilt::Quilt(istream & inFile, int rowsOfBlocks, int colsOfBlocks)
    : myBlock(0, 0), myRowsOfBlocks(rowsOfBlocks), myColsOfBlocks(colsOfBlocks)
    {int rows, cols, r, c;

	inFile >> rows >> cols;
	myBlock.resize(rows, cols);
	for (r = 0; r < rows; r++)
	    for (c = 0; c < cols; c++)
		inFile >> myBlock[r][c];
    }


b)  possible loop bodies:

    // reflect about horizontal
    qmat[startRow + r][startCol + c] = myBlock[myBlock.numrows() - r - 1][c];

	OR

    //reflect about horizontal
    qmat[startRow + myBlock.numrows() - r - 1][startCol + c] = myBlock[r][c];

	OR

    // 180 degree rotation
    qmat[startRow + r][startCol + c] = 
	myBlock[myBlock.numrows() - r - 1][myBlock.numcols() - c - 1];

	OR

    // 180 degree rotation
    qmat[startRow+myBlock.numrows()-r-1][startCol+myBlock.numcols()-c-1] = 
	myBlock[r][c];


c)  apmatrix<char> Quilt::QuiltToMat()		// checkerboard alternation
    {int r, c;
     apmatrix<char> mat(myRowsOfBlocks * myBlock.numrows(),
			myColsOfBlocks * myBlock.numcols());

	for (r = 0; r < myRowsOfBlocks; r++)
	    for (c = 0; c < myColsOfBlocks; c++)
		if ((r + c) % 2 == 0)
		    PlaceBlock(r * myBlock.numrows(), c * myBlock.numcols(), mat);
		else
		    PlaceFlipped(r * myBlock.numrows(), c * myBlock.numcols(),
mat);

	return mat;
    }


    apmatrix<char> Quilt::QuiltToMat()	    // another checkerboard alternation
    {int r, c;
     apmatrix<char> mat;

	mat.resize(myRowsOfBlocks * myBlock.numrows(), myColsOfBlocks * myBlock.numcols());

	for (r = 0; r < mat.numrows(); r += myBlock.numrows())
	    for (c = 0; c < mat.numcols(); c += myBlock.numcols())
		if (((r/myBlock.numrows()) % 2) == ((c/myBlock.numcols()) % 2))
		    PlaceBlock(r, c, mat);
		else
		    PlaceFlipped(r, c, mat);
	
	return mat;
    }


    apmatrix<char> Quilt::QuiltToMat()	// possible vertical stripe alternation
    {int r, c;
     bool flip = false;
     apmatrix<char> mat(myRowsOfBlocks * myBlock.numrows(),
 			myColsOfBlocks * myBlock.numcols());

	for (r = 0; r < myRowsOfBlocks; r++)
	    for (c = 0; c < myColsOfBlocks; c++)
	    {
		if (flip)
		    PlaceFlipped(r * myBlock.numrows(), c * myBlock.numcols(), mat);
		else
		    PlaceBlock(r * myBlock.numrows(), c * myBlock.numcols(), mat);
		
		flip = !flip;
	    }
	
	return mat;
    }
                       SOLUTION - AB Exam Problem #3 (1999)


a)  void InsertMember(const apstring & name, int level, Club & anyClub)
    {Member * p;

	p = new Member(name, level, anyClub.memberList);
	anyClub.memberList = p;
    }


b)  int CountLevel(const Club & anyClub, int level)
    {int count = 0;
     Member * list;
 
	list = anyClub.memberList;
	while (list != NULL)
	{
	    if (list->level == level)
 		count++;
	    list = list->next;
	}
 
	return count;
    }


c)  void PrintClubsWithMostInLevel(const apvector<Club> & clubsArray, int level)
    {int i, max = 0;

	for (i = 0; i < clubsArray.length(); i++)
	    if (CountLevel(clubsArray[i], level) > max)
		max = CountLevel(clubsArray[i], level);
	
	for (i = 0; i < clubsArray.length(); i++)
	    if (CountLevel(clubsArray[i], level) == max)
		cout << clubsArray[i].clubName << endl;	
    }
                       SOLUTION - AB Exam Problem #4 (1999)


a)  int PathLength(TreeNode * T, const apstring & someName, int level)
    {int left, right;

	if (T == NULL)
	    return 0;
	else
	{
	    left = PathLength(T->left, someName, level + 1);
	    right = PathLength(T->right, someName, level + 1);

	    if (left > right)
		return left;
	    else if (right > 0)
		return right;
	    else if (someName == T->name)
		return level;
	    else
		return 0;
	}
    }


    int PathLength(TreeNode * T, const apstring & someName, int level)
    {int maxLevel;

	if (T == NULL)
	    return 0;
	maxLevel = Max(PathLength(T->left, someName, level),
		       PathLength(T->right, someName, level));
	if (maxLevel > 0)
	    return (maxLevel + 1);
	else if (T->name == someName)
	    return 1;
	else
	    return 0;
    }


    int PathLength(TreeNode * T, const apstring & someName, int level)
    {
	if (T == NULL)
	    return 0;
	else if (someName == T->name)
	    return Max(Max(PathLength(T->left, someName, level + 1),
			   PathLength(T->right, someName, level + 1)), level);
	else
	    return Max(PathLength(T->left, someName, level + 1), 
		       PathLength(T->right, someName, level + 1));
    }


b)  int RootPath(TreeNode * T)
    {
	if (T == NULL)
	    return 0;
	else
	    return PathLength(T, T->name, 1);
    }