AP Computer Science 1996 Exam in C++

Owen Astrachan

This document is NOT an official translation of the 1996 AP Computer Science Exam free response questions into C++. However, every attempt has been made to be faithful to the proposed C++ subset for use in AP courses.

The A Exam

Question 1 (A Exam)

Assume that two arrays (vectors) are used to store information about student's grades. One array contains the students' numerical scores (integers in the range 0..100). The other array conatins the corresponding letter grades (characters in the range 'A'..'D').

Assume that a constant

   const int NUM_GRADES = some positive integer;

has been defined.

Part A
Write the function LetterAverage, whose header is given below. LetterAverage returns the average (arithmetic mean) of the student scores that correspond to a given letter grade. LetterAverage returns 0.0 if none of the student scores corresponds to the given letter grade.

For example, given the following arrays (vectors)

  StudentScores:   96 72 84 65 89 60 78 86 75 61 85

  StudentLetters:   A  C  B  D  A  D  B  B  C  D  B

LetterAverage(StudentScores,StudentLetters,'B') returns the number 83.25, which is the average of the four scores that correspond to the letter grade B.

LetterAverage(StudentScores,StudentLetters,'A') returns the number 92.5, which is the average of the four scores that correspond to the letter grade A.

Complete function LetterAverage below the following header.

double LetterAverage(const apvector<int> & scores, const apvector<char> & letters, char grade) // postcondition: returns 0.0 if no element of letters == grade // otherwise, returns average of all scores[n], // for all 0 <= n < NUM_GRADES, such that letters[n] == grade Answer

Part B
Write the function Averages, whose header is given below. Averages prints a list of each of the four leter grades ('A'..'D') followed by the average of the student scores that correspond to that letter grade. For the example given in part (a), the call Averages(StudentScores,StudentLetters) prints the following list.

In Writing Averages you may call the function LetterAverage of part (a). Assume that LetterAverage works as specified, regardless of what you wrote in part (a).

Complete function Averages below the following header

void Averages(const apvector<int> & scores, const apvector<char> & letters)

Answer

Question 2 (A Exam)

This is a directory manager (case study) question, not directly translatable to C++.

Question 3 (A Exam)

Consider a class Date used for storing and manipulating dates. The following operators are overloaded for the class Date: <<, ==, <, >, ++ . Only operator ++ is a member function, the other operators are not member functions.

ostream & 
operator<< (ostream & os, Date d);    prints date represented by d

bool 
operator == (Date lhs, Date rhs);     returns true if and only if
                                      lhs and rhs represent same date
bool 
operator < (Date lhs, Date rhs);      returns true if and only if
                                      lhs occurs before rhs

bool 
operator > (Date lhs, Date rhs);      returns true if and only if
                                      lhs occurs after rhs

Date operator ++(int);                increments date by one day

The following statements illustrate the use of these operators, where d1 represents the date October 17, 1953 and d2 represents the date October 31, 1995.

  Statement                    Effect

  cout << d1 << endl;          "October 17, 1953" is printed.

  if (d1 < d2)
     cout << "ok" << endl;     "ok" is printed

  d2++;                        d2 now represents "November 1, 1995"

Part A
Write the function PrintOneWeekLater, whose header is given below. PrintOneWeekLater prints a date that is seven days later than its parameter. For example, if the variable d represents the date February 18, 1991, then PrintOneWeekLater(d) prints February 25, 1991. In writing PrintOneWeekLater, you may use the overloaded (Date) operators <<, ==, <, >, ++. All manipulations of Date variables must be performed using only these operators.

Complete OneWeekLater below the following header

void PrintOneWeekLater(Date d) // postcondition: Prints a date that is seven days later than // the date represented by d answer

Part B
Write the function DaysApart, whose header is given below. DaysApart returns the number of days separating the dates represented by its two parameters, regardless of which date is earlier. (If the two parameters represent the same date, DaysApart returns 0.)

For example:

 Date Represented by d1    Date Represented by d2    Result Returned by DaysApart(d1,d2)

 February 18, 1991         February 18, 1991         0
 Feburary 18, 1991         February 20, 1991         2
 February 20, 1991         February 18, 1991         2
 January 31, 1991          February 5, 1991          5
 December 30, 1991         January 2, 1992           3

In writing DaysApart you may use the overloaded (Date) operators <<, ==, <, >, ++. All manipulations of Date variables must be performed using only these operators.

Complete function DaysApart below the following header

int DaysApart(Date d1, Date d2) // postcondition: returns 0 if d1 and d2 represent the same date; // otherwise, returns the number of days separating // the dates represented by d1 and d2 answer

Part C
Consider two alternative ways to implement the private section of the class Date:

I. Using three integers: one representing the year, one the month, and one the day
II. Using a single integer, representing the total number of days from January 1 of the year 1 to the given date (Assume that an int is large enough to store such a value.)

(i) Which of the the operators <<, <, ++ should require fewer operations when alternative I is used than when alternative II is used? Circle each of the operators that requires fewer operations for its implementation when alternative I is used, and give a brief justification for each one you circle

                             justification
  operator <<           



  operator <


  operator ++

(ii) Which of the the operators <<, <, ++ should require fewer operations when alternative II is used than when alternative I is used? Circle each of the operators that requires fewer operations for its implementation when alternative II is used, and give a brief justification for each one you circle

                             justification
  operator <<           



  operator <


  operator ++

answer

Question 4 (A Exam)

Recall that the class apmatrix has the following member functions (the header file apmatrix.h is included as part of the exam, and is accessible.)

  function                        description

  int numrows();               returns number of rows in matrix
  int numcols();               returns number of columns in matrix

  void resize(int newRows,
              int newCols);    resizes matrix to have newRows rows
                               and newCols columns.  Items in
                               original matrix are retained if matrix
                               "grow", items may be lost if matrix "shrinks"

Part A
Write function SumCross, whose header is given below. SumCross returns the sum of the values in the row with index R and the column with index C from the matrix m. The value in position m[R][C] is included in the sum only once. For example, consider the following matrix m, where m.numRows() == 3 and m.numCols() == 4


               +------+------++----++------+   
	       |      |      ||    ||      |   
	       |  77  |  22  ||  1 ||  33  |   
	       |      |      ||    ||      |   
	       +======+======++====++======+
	       |   5  |   3  || 10 ||  4   |   
	       |      |      ||    ||      |
	       +======+======++====++======+   
	       |      |      ||    ||      |   
	       |  66  |  44  ||  2 ||  55  |   
               |      |      ||    ||      |     
	       +------+------++----++------+

The call SumCross(M,1,2) returns the value 25, which is the sum of the values in the row with index 1 and the column with index 2, including the value 10 only once.

Complete function SumCross below the following header. Assume that SumCross is called only with parameters that satisfy its precondition.

int SumCross(const apmatrix<int> & m, int R, int C) // precondition: 0 <= R < m.numRows(); 0 <= C < m.numCols() answer

Part B
Write the function RemoveCross, whose header is given below. RemoveCross removes the row with index R and the column with index C from matrix m. For example, consider the following matrix m, where m.numRows() == 5 and m.numCols() == 6. After the call RemoveCross(m,2,3), the original row with index 2 and column with index 3 have been removed and m.numRows() == 4 and m.numCols() == 5.

                 
+----+----+----++---++----+----+       +----+----+----+----+----+
| 11 | 22 | 33 || 5 || 44 | 55 |       | 11 | 22 | 33 | 44 | 55 |
+----+----+----++----+----+----+       +----+----+----+----+----+
| 22 | 33 | 44 || 6 || 55 | 66 |       | 22 | 33 | 44 | 55 | 66 |
+====+====+====++===++====+====+       +----+----+----+----+----+
|  4 |  5 |  6 || 7 ||  8 |  9 |       | 33 | 44 | 55 | 66 | 77 |
+====+====+====++===++====+====+       +----+----+----+----+----+
| 33 | 44 | 55 || 8 || 66 | 77 |       | 44 | 55 | 66 | 77 | 88 |
+----+----+----++---++----+----+       +----+----+----+----+----+
| 44 | 55 | 66 || 9 || 77 | 88 |	 
+----+----+----++---++----+----+

Complete the function RemoveCross below the following header. Assume that RemoveCross is called only with parameters that satisfy its precondition.

void RemoveCross(apmatrix<int> & m, int R, int C) // precondition: 0 <= R < m.numRows(); 0 <= C < m.numCols() // postcondition: row with index R and column with index C have been removed from m answer

AB Exam

Question 1 (AB Exam)

Same as A Exam, Question 3

Question 2 (AB Exam)

Same as A Exam, Question 4

Question 3 (AB Exam)

Assume that binary trees are implemented using the following declaration struct TreeNode { int info; TreeNode * left; TreeNode * right; TreeNode(int value, TreeNode * lptr=0, TreeNode * rptr=0) : info(value), left(lptr), right(rptr) {} };

Part A
Write the function ValsLess whose header is given below. ValsLess returns true if its parameter t is NULL/0 or if all values stored in the binary tree pointed to by t are less than k; otherwise ValsLess returns false.

Complete ValsLess below the following header.

bool ValsLess(TreeNode * t, int k) // postcondition: returns true if t is NULL or if // all values stored in tree represented // by t are less than k; otherwise // returns false answer

Part B
Recall that a binary tree T is a search tree that contains no duplicate values if and only if

T is empty or
all of the following are true
- The value stored at the root of T is greater than all of the values stored in T's left subtree.
- The value stored at the root of T is less than all of the values stored in T's right subtree.
- T's left subtree is a binary search tree that contains no duplicate values.
- T's right subtree is a binary search tree that contains no duplicate values.

Write function IsBST whose header is given below. IsBST should return true if the binary tree represented by its parameter t is a binary search tree that contains no duplicate values; otherwise IsBST should return false.

In writing IsBST you may include calls to function ValsLess from part (A). Assume that ValsLess works as specified, regardless of what you wrote in part (A). You may also include calls to function ValsGreater whose specification is given below. (You do not need to write the body of ValsGreater.)

bool ValsGreater(TreeNode * t, int k) // postcondition: returns true if t is NULL or if // all values stored in tree represented // by t are greater than k; otherwise // returns false

Complete function IsBST below the following header.

bool IsBST(TreeNode * t) // postcondition: returns true if t represents a binary search // tree containing no duplicate values; // otherwise, returns false. answer

Question 4 (AB Exam)

This is a directory manager (case study) question, not directly translatable to C++.

I.	Using three integers: one representing the year, one the month, and one the day
II.	Using a single integer, representing the total number of days from January 1 of the year 1 to the given date (Assume that an int is large enough to store such a value.)