For information on the C++ subset, see The College Board APCS web page
(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.
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.
For example, consider the values of a Code variable c shown below.
|myLength||myChars||result of call c.IsValid()|
|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.
Complete member function IsValid below.
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|
|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.
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.
complete class declarations, definitions, and test program
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|
|function call||returned value|
Complete private member function boxIndex below. Assume that no P.O. box number occurs more than once in myBoxes.
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|
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.
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).
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.
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)|
Complete member function ZeroRight below. Assume that the precondition is satisfied whenever ZeroRight is called.
Write the function AddPowerOfTen whose header is given below. AddPowerOfTen should add 10N to its BigInt parameter A.
|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.
(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:
|A||N||A after the call A.Round(N)|
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.
answer not using *this if Round is a free function.
A two dimensional black-and-white screen is represented by the class Screen partially declared below. The constructor is also shown.
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|
Complete member function DrawRectangle below. Assume that DrawRectangle is only called with parameters that satisfy its precondition:
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.
|Screen S||Function call||S after the function call|
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.
Complete class and test program
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.
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.)
|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.
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.)
|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.
complete declarations and test program
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.
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.
Complete declarations and test program