APCS Exam 1998 in C++

This translation of the 1998 AP exam to C++ has been done by the former chief reader of the APCS exam, Owen Astrachan and the current chair of the APCS development committee Susan Rodger in consultation with the APCS development committee.

For information on the C++ subset, see The College Board APCS web page

A Exam
[Question 1 | Question 2 | Question 3 | Question 4]

AB Exam
[ Question 3 | Question 4]

The A Exam

Question 1 (A exam)

(Note to reader: the member functions IsValid() and Length() below should be const, but the current AP C++ subset says that students in the A course are not required to write const functions. This may change in the future.)

Assume that registration codes, each consisting of a sequence of characters, are implemented using the constants and class declaration below.

const int MINLEN = 5; const int MAXLEN = 15; class Code { public: Code(); // length is 0, capacity is MAXLEN chars Code(const apstring & s); // code has chars in s, length is s.length() bool IsValid(); // returns true if code is valid, else false int Length(); // returns # characters in the code void AppendCheckSum(); // adds appropriate check sum to the code // other member functions not shown private: int myLength; // # characters in code apvector<char> myChars; // the characters in the code }; Part A

Write the member function IsValid, whose header is given below. IsValid returns true if a code is valid and returns false otherwise. A code is valid if it satisfies the following criteria.

  1. The length is greater than or equal to MINLEN and less than or equal to MAXLEN - 2, i.e., MINLEN <= Length() <= MAXLEN - 2

  2. Each character is either a digit ('0'..'9') or a capital letter ('A'..'Z').

For example, consider the values of a Code variable c shown below.

myLength    myChars result of call c.IsValid()
 7   120H056 true
 5   ABCDE true
 9   ABCDE9999 true
 3   AB1 false (Length() is too small)
14   ABCDEF00FEDCBA false (Length() is too large)
 8   ab?XX123 false (characters a, b, ? are all invalid)

In writing IsValid you may call the functions isdigit and isupper whose headers are shown below. You do not need to write isdigit or isupper.

bool isdigit(char ch) // postcondition: returns true if and only if ch // is a digit: '0' .. '9' bool isupper(char ch) // postcondition: returns true if and only if ch // is an upper case letter: 'A' .. 'Z'

Complete member function IsValid below.

bool Code::IsValid() // postcondition: returns true if MINLEN <= Length() < MAXLEN - 2 // and for every k, 0 <= k < Length(), // myChars[k] is a digit '0'--'9' or a char 'A' -- 'Z'

answer

Part B

Consider the problem of appending a checksum to the end of a registration code. The checksum is computed as follows:

Write the member function AppendCheckSum, whose header is given below. If a Code value is valid as specified in part (a), then AppendCheckSum should calculate the checksum and append the character '-' followed by the character for the checksum to the original Code value; otherwise AppendCheckSum should leave the original Code value unchanged.

For example, if c is a variable of type Code

Before the call c.AppendCheckSum() After the call c.AppendCheckSum()
c.Length() c.myChars sum of digits       c.Length() c.myChars
7    120H056 14             9 120H056-4
5    ABCDE 0 7 ABCDE-0
9    ABCDE9999 36 11 ABCDE9999-6
3    AB1 (code not valid) 3 AB1
14    ABCDEF00FEDCBA (code not valid) 14 ABCDEF00FEDCBA
8    ab?XX123 (code not valid) 8 ab?XX123

The functions digitToInt and intToDigit convert from a digit character to the equivalent integer and from a one-digit integer to the equivalent character, respectively.

int digitToInt(char d) // precondition: isdigit(d) == true // postcondition: returns the value 0 to 9 corresponding // to character d char intToDigit(int val) // precondition: 0 <= val <= 9 // postcondition: returns the character from // '0'..'9' corresponding to val

In writing AppendCheckSum, you may call the functions intToDigit, digitToInt, isupper and isdigit specified above and in part (a) (you do not have to write the bodies of these functions.) You may also call member function IsValid specified in part (a). Assume that IsValid works as specified, regardless of what you wrote in part (a).

Complete member function AppendCheckSum below.

void Code::AppendCheckSum() // postcondition: if IsValid() then myLength is updated and // myChars contains the original characters followed // by a dash and the appropriate checksum; otherwise // myLength and myChars are unchanged

answer

complete class declarations, definitions, and test program

Question 2 (A exam)

 Consider the following constants and declarations which are used to represent information about the number of pieces of mail to be delivered to each of a list of post-office boxes (P.O. boxes).

const int MAX_BOXES = 100; struct MailInfo { int POBox; int mailCount; // number pieces of mail for this po box }; class MailBoxes { public: MailBoxes(); // initial capacity = MAX_BOXES, zero boxes stored void processMail(istream & input); // process stream of po boxes // other member functions not shown private: int boxIndex(int box); // helper function, returns index apvector<MailInfo> myBoxes; // list of all poboxes and counts int myBoxCount; // number of items stored in myBoxes };

Part A

Write the private member function boxIndex, whose header is given below. boxIndex returns the index in myBoxes of the first MailInfo element whose POBox field is equal to box. If there is no MailInfo element in myBoxes with a POBox field equal to box then the function should return -1.

For example, assume myBoxCount = 3 and myBoxes contains the POBox values shown below.

index in myBoxes POBox field
[0] 151
[1] 234
[2] 185

function call returned value
boxIndex(185)  2
boxIndex(234)  1
boxIndex(100) -1

Complete private member function boxIndex below. Assume that no P.O. box number occurs more than once in myBoxes.

int MailBoxes::boxIndex(int box) //postcondition: returns the index of the element in myBoxes // whose POBox field equals box if there is such an element; // otherwise, returns -1. { }

answer
alternate answer

Part B

Assume that a file contains P.O. box numbers, one per line. Write member function processMail, whose header is given below. processMail should read the input file; for each line of the file it should add 1 to the mailCount field for the element of myBoxes with the corresponding value in its POBox field. If the P.O. box number does not appear in myBoxes, then processMail should add an entry to myBoxes with this new P.O. box number and a mailCount field of 1.

For example, assume that for MailBoxes variable c, the value of myBoxes is initially empty, and that input contains the five lines shown below. 

    151
    234
    151
    185
    234

After the call c.processMail(input), the value of myBoxCount will be 3 and myBoxes will have the values shown below.

apvector index POBox field mailCount field
[0] 151 2
[1] 234 2
[2] 185 1

In writing function processMail, you may call the member function boxIndex specified in part (a). Assume that boxIndex works as specified, regardless of what you wrote in part (a). Also assume that the input file is formatted correctly, and that there are no more than MAX_BOXES different P.O. box numbers in the file.

Complete member function processMail below.

void MailBoxes::processMail(istream & input) // precondition: input is formatted correctly, is open for reading, // and is positioned at the beginning of the file; // the file contains no more than MAX_BOXES different // P.O. box numbers { }

answer

Complete class declarations, definitions, and test program

Alternate complete class declarations, definitions, and test program containing more member functions and struct constructors (these declarations don't fit the given wording of the problem, but might fit an alternative wording).

Question 3 (A exam)

 ( Note to reader: these problems are much simpler using the C++ version of BigInt than using the Pascal Large Integer code. Most likely questions asked on the C++ exam will require solutions more complicated than these C++ solutions. )

This question involves reasoning about the code from the BigInt case study. A copy of the code is provided as part of this examination (and for this online version is accessible at the bigint web page). In answering this question, you may use any of the existing BigInt member functions. When manipulating the digits of a number you MUST use the private helper functions, e.g., GetDigit, AddSigDigit, and ChangeDigit. You will not receive full credit if your solution relies on a particular method for storing digits or if your solution manipulates the field myDigits directly.

Part A

Write the member function ZeroRight, whose header is given below. ZeroRight(N) should change the N rightmost digits of a BigInt to the digit 0. Note that N is a count of the number of digits so that if N = 1, the rightmost digit (and only the rightmost digit) will be set to zero.

For example, for the BigInt variable b:

BigInt b N after the call b.ZeroRight(N)
123456789 3 123456000
1234567 5 1200000
120000 2 120000

Complete member function ZeroRight below. Assume that the precondition is satisfied whenever ZeroRight is called.

void BigInt::ZeroRight(int N) // precondition: 1 <= N <= NumDigits() // postcondition: the N rightmost digits of A are 0; // the other digits are unchanged { }

answer

Part B

Write the function AddPowerOfTen whose header is given below. AddPowerOfTen should add 10N to its BigInt parameter A.

For example:

A N A after the call AddPowerOfTen(A,N)
4560 0 4561 (1 was added)
1234 1 1244 (10 was added)
1234567 2 1234667 (100 was added)
199999 3 200999 (1,000 was added)
789 5 100789 (100,000 was added)

Complete function AddPowerOfTen below the following header.

void AddPowerOfTen(BigInt & A, int N) // postcondition: A contains the value of A + 10^N { }

answer

Part C

(Note to reader: as written this solution uses *this in the code. Students in the APCS A course must recognize the use of *this, but are not required to write code using *this. An alternate solution can be written not using *this --- the alternate solution is shown. )

Write member function Round, whose header is given below. Round should round a BigInt to the power of ten indicated by parameter N, an integer greater than or equal to 1.

An algorithm for rounding a number to the Nth power is:

(So changing the rightmost 2 digits means changing the digit with index 0 and the digit with index 1).

For example:

A N A after the call A.Round(N)
345 1 350
12345678 3 12346000
12345378 3 12345000
987646789 5 987600000
9999999 5 10000000

In writing Round, you mall call the member function ZeroRight and the function AddPowerOfTen specified in parts (a) and (b). Assume that ZeroRight and AddPowerOfTen work as specified, regardless of what you wrote in parts (a) and (b).

Complete member function Round below.

void BigInt::Round(int N) // postcondition: bigint has been rounded to the Nth power of 10 { }

answer
answer not using *this if Round is a free function.

Question 4 (A exam)

A two dimensional black-and-white screen is represented by the class Screen partially declared below. The constructor is also shown.

class Screen { public: enum Color {white, black}; // legal pixel values Screen(int size); // all white screen, size X size void DrawRectangle(int row, int col, // draw rectangle on screen int height, int width); void FillRectangle(int row, int col); // fill a rectangle int Size() const; // size of screen // other member functions private: int mySize; apmatrix<Color> myPixels; }; Screen::Screen(int size) : mySize(size), myPixels(size,size,Screen::white) // postcondition: size X size screen is all white { } Each apmatrix element represents one pixel on the screen. A blank screen is represented by a matrix that contains only Screen::white values. A rectangle is drawn on a blank screen by setting the matrix elements that correspond to the borders of the rectangle to Screen::black.

Part A

Write the member function DrawRectangle, whose header is given below. DrawRectangle should draw the border of a rectangle with the given height and width, starting from the given upper left corner (the upper left corner is specified by parameters row and col). The rectangle's border is drawn by setting the appropriate elements of myPixels to Screen::black. The specified rectangle may not entirely fit on the screen; in that case, only those parts of the rectangle's border that fit on the screen should be drawn.

For example, for the variable Screen s(8) (assuming s is blank before each function call):

Function Call Value of myPixels after the call
s.DrawRectangle(1,2,5,4) *
s.DrawRectangle(4,3,10,5) *
s.DrawRectangle(4,4,8,9) *

Complete member function DrawRectangle below. Assume that DrawRectangle is only called with parameters that satisfy its precondition:

void Screen::DrawRectangle(int row, int col, int height, int width) // precondition: screen is blank/all white, // 0 <= row < Size() and 0 <= col < Size(), // height > 0, and width > 0 { } answer

Part B

Write member function FillRectangle, whose header is given below. FillRectangle is given the position of a pixel that is inside (not on the border of) a rectangle that has been drawn in a Screen object. If the position is on the screen, then FillRectangle should change all of the array elements that represent pixels inside the rectangle from Screen::white to Screen::black.

For example:
Screen S Function call S after the function call
* S.FillRectangle(3,4) *
* S.FillRectangle(6,6) *
* S.FillRectangle(6,8) *

One possible algorithm for filling in a rectangle, given a position P = (row, col) inside the rectangle is as follows. 

   if position P is on the screen then
       if the pixel at position P is Screen::white then
          - change the pixel at point P from Screen::white to Screen::black
          - call FillRectangle recursively on the point above P;
          - call FillRectangle recursively on the point below P;
          - call FillRectangle recursively on the point to the left of P;
          - call FillRectangle recursively on the point to the right of  P;

Complete member function FillRectangle below. Assume that FillRectangle is initially called for a screen on which a single rectangle has been drawn, and with values (row, col) that represent the position of a pixel inside the rectangle.

void Screen::FillRectangle(int row, int col) { } answer

Complete class and test program

The AB Exam

Question 3

 Assume that linked lists of integers are implemented using the following declarations.

struct ListNode { int info; ListNode * next; ListNode(int val, ListNode * ptr) // constructor : info(val), next(ptr) { } };

Part A

Write function FirstMin, whose header is given below. FirstMin determines the value of the smallest integer in its list parameter and returns a pointer to the first node in the list that contains that value. (If the list is empty, FirstMin returns NULL.)

For example, if L and p are ListNode * variables:
linked list L Result of executing p = FirstMin(L)
* *
* *
* *

Complete function FirstMin below.

ListNode * FirstMin(ListNode * list) { }

answer

Part B

Write the function RemoveNext, whose header is given below. RemoveNext has one parameter p, a non-NULL pointer to a node of a linked list. RemoveNext removes the node after the one pointed to by p from the list, returning that node to the heap/to free storage. (If the node pointed to be p is the last node on the list, RemoveNext does nothing.)

For example:

Before the call RemoveNext(p) After the call RemoveNext(p)
* *
* *
* *

Complete function RemoveNext below. Assume that RemoveNext is called only with values that satisfy its precondition.

void RemoveNext(ListNode * ptr) // precondition: ptr != NULL { }

answer

Part C

Write the function RemoveDupMins, whose header is given below. RemoveDupMins determines the value of the smallest integer in its list parameter and removes from the list all nodes containing that value EXCEPT the first such node. (If the list is empty, RemoveDupMins does nothing.)

For example:

List L before the call RemoveDupMins(L) List L after the call RemoveDupMins(L)
* *
* *
* *
* *

In writing RemoveDupMins, you may call FirstMin and RemoveNext of parts (a) and (b). Assume that FirstMin and RemoveNext work as specified, regardless of what you wrote in parts (a) and (b).

Complete RemoveDupMins below.

void RemoveDupMins(ListNode * list) { }

answer
complete declarations and test program

Question 4

 Assume that binary trees are implemented using the following declarations.

struct TreeNode { int info; // data stored int size; // size of subtree (root included) TreeNode * left; // left subtree TreeNode * right; // right subtree TreeNode(int val, TreeNode * lptr, TreeNode * rptr) : info(val), size(1), left(lptr), right(rptr) { } };

Part A

Write function SetSize, whose header is given below. SetSize should set the size field of every node in its tree parameter to the number of nodes in that node's subtree (including itself). The number of nodes in a tree is equal to the number of nodes in its left subtree plus the number of nodes in its right subtree plus one.

For example, the following picture shows the result of the call SetSize(root)

*

Complete function SetSize below.

void SetSize(TreeNode * t) // precondition: t != NULL // postcondition: The size field of every node in the tree t // has been set to the size of that node's subtree { }

answer

Part B

Assume that tree T is a binary search tree ordered by the values in the nodes' info fields, and that there are no duplicate info values. The kth value in a binary search tree is the kth smallest value in the tree. For example, the tree shown in part (a) includes the data values 12, 25, 30, 37, 50, 62, 75, 88. 

 The 1st value is 12.
 The 4th value is 37.
 The 7th value is 75.
 The 8th value is 88.

Write function FindKth, whose header is given below. FindKth returns the kthe value in a binary search tree. Assume that the size fields in all nodes of the tree have been correctly initialized. One way to determine the location of the kthe value is as follows: 

    Consider the size of the left subtree of the current node
      If k is equal to the size of the left subtree + 1, the kth value is in the current node.
      If k is less than the size of the left subtree + 1, the kth value is in the left subtree.
      Otherwise, the kth value is in the right subtree.

Complete function KthValue below.

int FindKth(TreeNode * t, int k) // precondition: t is not NULL, the size fields of all nodes in t // are correctly initialized. // 1 <= k <= t->size // postcondition: returns the kth value in t { }

answer
Complete declarations and test program

Owen L. Astrachan
Last modified: Sat Jul 4 01:07:50 EDT 1998