APCS Exam 1997 in C++

This document is NOT an official translation of the 1997 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.

A Exam
[Question 1 | Question 2 | Question 2 (class version) | Question 3 | Question 4]

AB Exam
[Question 1 | Question 2 | Question 3 | Question 4 | Question 4 (class version)]

The A Exam

Question 1 (A Exam)

A sequence of three Boolean values can be translated to an integer value by first translating each of the Boolean values according to the rules given below, and then adding those three translations.

For example,

bool values Individual Translations Final Translations
true true true 4 2 1 7
true false false 4 0 0 4
false true true 0 2 1 3

Part A

Write function Translate, whose header is given below. The function should translate three bool values from its array (apvector) parameter (starting at the specified position in the array) into the corresponding integer value by using the algorithm described above. For example, if array info is as pictured below

*

then the following illustrates several calls to Translate.

Call to Translate info (relevant values shown in bold) Return Value
Translate(info,3) true false false true true false true 6
Translate(info,1) true false false true true false true 1
Translate(info,0) true false false true true false true 4

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

int Translate(const apvector<bool> & info, int index) // precondition: info contains info.length() entries, // 0 <= index < info.length() - 2

Answer

Part B

Write function TranslateAll whose header is given below. TranslateAll should translate each successive sequence of three bool values in its parameter info, storing the integer values in its parameter result. Assume that the number of elements in info is a multiple of 3.

The following shows the effect of the call TranslateAll(info,result) for two different versions of info.

info result
true false true false false false true true false 5 0 6
false false true true false false true true true 1 4 7

In writing TranslateAll, you may call the function Translate of part (a). Assume that Translate works as specified, regardless of what you wrote in part (a).

Complete function TranslateAll below the following header

void TranslateAll(const apvector<bool> & info, apvector<int> & result) // precondition: info has info.length() entries // info.length() % 3 == 0 // [number of elements is a multiple of 3] // result.length() >= info.length()/3, // i.e., the capacity of result is large enough

Answer

Question 2 (A Exam)

(I am writing two versions of this question. One is a reasonably fair translation of the problem as given on the 1997 exam. The other is my interpretation of how the problem could/should be written using a class approach.

Consider the problem of storing and displaying information about students' letter grades (A-D).

Part A

Write function GradeDistribution, whose header is given below. GradeDistribution reads students' letter grades (characters in the range 'A'..'D') from a file gradeFile, and determines how many times each letter grade occurs. GradeDistribution stores the information about grade occurrences, as well as the total number of grades read, in a Grade struct (declared below).

struct Grade { apvector<int> freq; // # occurrences of each grade int count; // total # of grades Grade() // constructor : freq(4), count(0) {} };

In the Grade struct, freq[0] represents the number of times a grade of 'A' occurs, freq[1] represents the 'B' occurrences, freq[2] the 'C' occurrences, and freq[3] the 'D' occurrences.

(Recall that the value of 'A' - 'A' is 0, the value of 'B' - 'A' is 1, the value of 'C' - 'A' is 2, and the value of 'D' - 'A' is 3).

Assume that grades are stored in gradeFile one per line with no blank lines. For example, consider the following file gradeFile. 

  gradeFile

  A
  A
  B
  B
  C
  B
  D
  A
  D
  D
  C
  B
  B
  B
  C
  B
  A
  B
  B
  C

Consider the sequence of statements:

Grade grades; ifstream input("gradeFile"); GradeDistribution(input,grades); After the call GradeDistribution(input,grades) the variable grades contains the following information.

*

Assume that input is bound to a correctly formatted file of grades.

Complete function GradeDistribution below the following header.

void GradeDistribution(istream & input, Grade & grades) // precondition: input is open for reading // grades.freq.length() >= 4 // postcondition: grades.freq contains the frequency count of // each grade in input, // grades.count contains the total number of grades // in input

Answer

Part B

Write function PrintAllGrades, whose header is given below. PrintAllGrades prints a bar graph that represents the grades stored in the freq field of its Grade parameter along with the total number of grades. For example, the call PrintAllGrades(grades) where grades contains the data from the example of part (a) should produce the following output. 

   AAAA
   BBBBBBBBB
   CCCC
   DDD

   Total Grades = 20
Complete function PrintAllGrades below the following header. void PrintAllGrades(const Grade & grades) Answer

Question 2 (A Exam) Class Version

Consider the problem of storing and displaying information about students' letter grades (A-D).

The class GradeInfo, whose declaration is shown below, is used to keep track of student grades.

#include "apvector.h" #include "apstring.h" const int NUM_GRADES = 4; // # different grades class GradeInfo { public: GradeInfo(); // constructor void Read(istream & input); // read grades from input void PrintBarGraph(); // print bar graph of grades private: int CharToIndex(char ch); // convert char to index apvector<int> myGrades; // # occurrences of each grade int myCount; // total # of grades }; GradeInfo::GradeInfo() : myGrades(NUM_GRADES,0), myCount(0) { // myGrades initialized to NUM_GRADES cells, all equal to 0 } int GradeInfo::CharToIndex(char ch) // precondition: 'A' <= ch <= 'D' // postcondition: returns int index corresponding to ch { return ch - 'A'; } Part A Write the member function Read whose header is given below. Read reads students' letter grades (characters in the range 'A'..'D') from a file whose name is specified by filename, and determines how many times each letter grade occurs. Read stores the information about grade occurrences and the total number of grades in private variables myGrades and myCount, respectively.

The value of myGrades[0] represents the number of times a grade of 'A' occurs, myGrades[1] represents the 'B' occurrences, myGrades[2] the 'C' occurrences, and myGrades[3] the 'D' occurrences.

The private member function CharToIndex, shown above, should be used to convert a character representing a grade to an index into myGrades.

Assume that grades are stored in a file one per line with no blank lines. For example, consider the following text filegradeFile. 

  gradeFile

  A
  A
  B
  B
  C
  B
  D
  A
  D
  D
  C
  B
  B
  B
  C
  B
  A
  B
  B
  C

If the three statements below are executed

GradeInfo grades; ifstream input("gradeFile"); grades.Read(input); then grades contains the following information.

*

Assume that input is bound to a correctly formatted file of grades.

Complete member function Read below the following header

void GradeInfo::Read(istream & input) // precondition: input is open for reading // postcondition: myGrades contains the frequency count of // each grade in input, // myCount contains the total number of grades // in input

Answer

Part B Write member function PrintBarGraph, whose header is given below. PrintBarGraph prints a bar graph that represents the grades as read by a call of member function Read, i.e., as stored in the private section of a GradeInfo variable. For example, executing the three statements below

GradeInfo grades; ifstream input("gradeFile"); grades.Read(input); grades.PrintBarGraph(); where gradeFile contains the data from the example of part (a) should produce the following output. 

   AAAA
   BBBBBBBBB
   CCCC
   DDD

   Total Grades = 20
Complete member function PrintBarGraph below the following header. void GradeInfo::PrintBarGraph()

Answer

Entire GradeInfo class

Question 3 (A Exam)

(case study question)

Question 4 (A Exam)

A matrix of characters represents a puzzle containing horizontal and vertical words. By definition, a word is any sequence of 2 or more uppercase letters. Each entry in the matrix contains either an uppercase letter or a space. The border of the matrix (first row, last row, first column, last column) contains only spaces.

For example, a character matrix puzzle with 8 rows and 12 columns (where puzzle.numrows() == 8 and puzzle.numcols() == 12) is shown below.

*

Write function NumSpaces, whose header is given below. NumSpaces returns the number of positions in the puzzle (including the border) that contain the character ' ' (a space). For example, in the puzzle above, there are 12 spaces in the row with index 0, there are 4 spaces in the row with index 3, and the entire puzzle contains 66 spaces.

Complete function NumSpaces below the following header.

int NumSpaces(const apmatrix<char> & crossWord) // precondition: crossWord contains only uppercase letters or spaces // # of rows = crossWord.numrows(), // # of columns = crossWord.numcols(); // postcondition: returns the number of positions in crossWord // that contain the space character ' '

Answer

Part B

Write function PrintWordsInRow, whose header is given below. PrintWordsInRow prints the words in the row with index given by parameter r, one word per line. In the example puzzle above, PrintWordsInRow(puzzle,1) produces the following output: 

    CLASS
Note that C is not printed because, by definition, words are at least 2 characters long.

PrintWordsInRow(puzzle,3) produces the following output: 

    FALSE
    FOR

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

void PrintWordsInRow(const apmatrix<char> & crossWord, int r) // precondition: crossWord contains only uppercase letters or spaces // 0 <= r < crossWord.numrows() // postcondition: prints the words in row with index r of crossWord, // one word per line

Answer

Part C

Write function PrintAllWords, whose header is given below. PrintAllWords prints all the words (both horizontal and vertical) in the puzzle, one word per line. The words in the puzzle can be printed in any order.

In writing PrintAllWords, you may call function PrintWordsInRow of part (b). Assume that PrintWordsInRow works as specified, regardless of what you wrote in part (b).

You may also call function PrintWordsInColumn, declared below. (You do not need to write the body of PrintWordsInColumn.)

void PrintWordsInColumn(const apmatrix<char> & crossWord, int c) // precondition: crossWord contains only uppercase letters or spaces // 0 <= c < crossWord.numcols() // postcondition: prints the words in column with index c of crossWord, // one word per line

Complete function PrintAllWords below the following header.

void PrintAllWords(const apmatrix<char> & crossWord) // precondition: crossWord contains only uppercase letters or spaces // # of rows in puzzle = puzzle.numrows() // # of columns in puzzle = puzzle.numcols() // postcondition: prints the words from all rows and all columns of // crossWord, one word per line

Answer

The AB Exam

Question 1 (AB Exam)

Same as Question 4, A exam

Question 2 (AB Exam)

Same as Question 3, A exam

Question 3 (AB Exam)

Assume that binary trees are implemented using the following declarations

struct Tree { int info; Tree * left; Tree * right; // provide constructor Tree(int val, Tree * lchild = 0, Tree * rchild = 0) : info(val), left(lchild), right(rchild) { } };

Part A

Write function CountNum whose header is given below. CountNum returns the number of nodes in tree T that contain the value key.

For example, if T is as pictured below, CountNum(T,0) returns 2, CountNum(T,1) returns 3, and CountNum(T,2) returns 0.

*

Complete function CountNum below the following header

int CountNum(Tree * T, int key) // precondition: returns the number of nodes in Tree T // with the value key. Returns 0 if no // nodes contain key or if the tree is empty

Answer

Part B

Write function Insert whose header is given below. Insert creates a new node containing the value key and inserts this new node between the node pointed to by P and either P's right child (if the direction is 'R') or P's left child (if the direction is 'L'). If direction is 'R', the right child of P becomes the right child of the new node and the new node becomes the right child of P. If direction is 'L', the left child of P becomes the left child of the new node and the new node becomes the left child of P.

For example

*

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

void Insert(Tree * p, int key, char direction) // precondition: P is not NULL/0. If direction is 'R', // P has a right child; if direction is 'L', // P has a left child. // postcondition: If direction is 'R', a node containing the // value key is created and inserted between P and // P's right child. // If direction is 'L', a node containing the // value key is created and inserted between P and // P's left child.

Answer

Part C

Write function Separate, whose header is given below. Separate modifies tree T in the following way: for each occurrence of a parent and child that contain the same value n, a new node is inserted between them containing the value n-1.

For example:

*

In writing Separate you may call the function Insert of part (b). Assume that Insert works as specified, regardless of what you wrote in part (b).

void Separate(Tree * t)

Answer

Question 4 (AB Exam)

This question concerns the design of a hash table to be used to store names. Assume that a class Name has been declared as shown below. class Name { public: Name(); // constructor Name(const apstring & s); // construct from string // accessor functions int length() const; // returns # characters in name char operator [](int k) const; // return k-th character of name bool Equal(const Name & rhs) const; // check equality private: // declarations here }; // commented prototypes // int Name::length() const; // postcondition: returns # characters in self // char Name::operator[](int k) const; // postcondition: if 0 <= k < length(), returns k-th character // otherwise returns space // bool Name::Equal(const Name & rhs) const; // postcondition: returns true if rhs == self, otherwise returns false bool operator == (const Name & lhs, const Name & rhs) // postcondition: returns true if lhs == rhs, otherwise returns false { return lhs.Equal(rhs); } Also assume the following global constant has been declared 
   const int SIZE = some positive integer;

Part A

Write function Hash, whose header is given below. Hash returns the hash value of its parameter nn. The hash value is an integer in the range 0..SIZE-1, computed as follows:

  1. Compute the sum of the first and last characters of the given name (treat the characters as ints).

  2. Convert the sum to an integer in the range 0..SIZE-1 by finding the remainder when sum is divided by SIZE

For example, if SIZE = 5:

Values of first Value returned by
value of nn and last chars sum Hash(nn)
Ken 75, 110 185 0
Susan 83, 110 193 3
Mark 77, 107 184 4
Cary 67, 121 188 3
Don 68, 110 178 3
X 90, 90 180 0

Complete the function Hash below the following header. In writing Hash you may call member functions of the class Name (Name::length, Name::operator[], Name::Equal) and the overloaded operator == . You will not receive full credit if your code relies on a particular implementation of Name. Assume that function Hash is called only with parameters that satisfy its precondition.

int Hash(const Name & nn) // preconditon: 0 < nn.length() // postcondition: returns hash value of nn

Answer

Part B

Assume that the hash table will be implemented using an apvector of linked lists, indexed from 0 to SIZE-1. The list in the kth element of the vector will hold all names with hash value k that have been inserted into the hash table. If no inserted name has hash value k, then the kth element of the vector will be NULL/0. For example, if SIZE is 5 and the names Ken, Susan, Mark, Cary, Don, and X have been inserted into the hash table, then the vector will be as shown below.

*

Assume that nodes for the linked list have been declared as follows:

struct Node { Name info; Node * next; };

Write function Lookup, whose header is given below. Lookup should return true if the parameter nn is in the hash table table; otherwise it should return false. Lookup should use the hash value of nn to identify the list that might contain nn; then it should search for nn in the list. For example, if variable Table represents the hash table shown on the previous page:

Value returned by Value returned by
value of nn Hash(nn) Lookup(Table,nn)
Susan 4 true
Gail 5 false
Chris 3 false

In writing Lookup you may call member functions of the class Name and the overloaded operator == for Name values. You will not receive full credit if your code relies on a particular implementation of Name. You may also call the function Hash of part (a). Assume that Hash works as specified, regardless of what you wrote in part (a). Assume that function Lookup is called only with parameters that satisfy its precondition.

Complete function Lookup below the following header.

bool Lookup(const apvector<Node *> & table, const Name & nn) // precondition: for all 0 <= k < SIZE, either table[k] == NULL/0 // or table[k] is a pointer to a linked list of names // all of which have hash value k // postcondition: returns true if nn is in table; // otherwise returns false

Answer

Question 4 (AB Exam) Class Version

This question concerns the design of a templated hash table class. In this problem the hash table class is used to store names. Assume that a class Name has been declared as shown below. class Name { public: Name(); // constructor Name(const apstring & s); // construct from string // accessor functions int length() const; // returns # characters in name char kthChar(int k) const; // returns k-th character of name char operator [](int k) const; // returns k-th character of name bool Equal(const Name & rhs) const; // check equality int HashValue() const; // return hash value of name private: // declarations here }; // commented prototypes // int Name::length() const; // postcondition: returns # characters in self // char Name::kthChar(int k) const; // postcondition: if 0 <= k < length(), returns k-th character // otherwise returns space // char Name::operator[](int k) const; // postcondition: if 0 <= k < length(), returns k-th character // otherwise returns space // bool Name::Equal(const Name & rhs) const; // postcondition: returns true if rhs == self, otherwise returns false // int Name::HashValue() const; // postcondition: returns a hash value for name bool operator == (const Name & lhs, const Name & rhs) // postcondition: returns true if lhs == rhs, otherwise returns false { return lhs.Equal(rhs); } A simple hash table class is used in this problem. Any type that supports comparisons using operator == and that has a member function HashValue can be used with the templated hash table class. Because the class Name has a member function HashValue and an overloaded operator == it can be used with the hash table class.

Part A

Write member function HashValue, whose header is given below. HashValue returns the hash value of a Name object. The hash value is computed as follows:

  1. Compute a number for each character in the Name object. The number is the value of the character (treat the character as an int) multiplied by the position in which the character occurs where the first character has position 1 and the last character has position length().

  2. The sum of the all the numbers is the hash value, return this value.

For example:

Number for each Value returned by
value of Name character HashValue()
Ken 75*1 + 101*2 + 110*3 607
Susan 83*1 + 117*2 + 115*3 + 97*4 + 110*5 1600
Mark 77*1 + 97*2 + 114*3 + 107*4 1041
Cary 67*1 + 97*2 + 114*3 + 121*4 1087
Don 68*1 + 111*2 + 110*3 620
Y 89*1 89

Complete the member function HashValue below the following header. In writing HashValue you may call member functions of the class Name (Name::length, Name::kthChar, Name::operator[], Name::Equal) and the overloaded operator == . You will not receive full credit if your code relies on a particular implementation of Name. Assume that the precondition of member function HashValue is satisfied whenever it is called.

int Name::HashValue() const // preconditon: 0 < length() // postcondition: returns hash value

Answer

Part B

Assume that the hash table will be implemented using an apvector of linked lists. The list in the kth element of the vector will hold all names that have been inserted into the hash table and that have a hash value that when divided by the size of the vector is equal to k. The kth element of the vector will be NULL/0 if no values have been inserted into the k-th linked list. For example, if the size of the vector is 5, and the names Ken, Susan, Mark, Cary, Don, and Y have been inserted into the hash table, then the vector will be as shown below.

*

The declaration for templated class hashTable is shown below:

template <class Type> class HashTable { public: HashTable(int size); // size of hashtable bool Contains(const Type & key) const; // is key in hashtable? void Insert(const Type & key); // insert key into table // other member functions as needed private: // node for linked list struct Node { Type info; Node * next; Node(const Type & val, Node * link = NULL) : info(val), next(link) { } }; apvector<Node *> myTable; // vector linked lists int mySize; // size of myTable };

Write member function Contains, whose header is given below. Contains should return true if the parameter key is in the hash table; otherwise it should return false. Contains should use the hash value of key to identify the list that might contain key; the index of the linked list in myTable is the remainder when key.HashValue() is divided by mySize. For example, if variable Table represents the hash table shown on the previous page (so that mySize has the value 5):

index of linked list Value returned by
value of key key.HashValue() in myList Table.Contains(key)
Susan 1600 0 true
Gail 1044 4 false
Chris 1612 2 false

In writing Contains you may call member functions of the class Name and the overloaded operator == for Name values. You will not receive full credit if your code relies on a particular implementation of Name. Assume that function Name::HashValue from part (a) works as specified, regardless of what you wrote in part (a).

Complete function Contains below the following header.

template <class Type> bool HashTable<Type>::Contains(const Type & key) const // postcondition: returns true if key is in hash table // otherwise returns false

Answer

Complete HashTable class

Owen L. Astrachan
Last modified: Thu Jul 24 08:59:54 EDT 1997