2019
AP® Computer Science A Free-Response Questions
© 2019 The College Board. College Board, Advanced Placement, AP, AP Central, and the acorn logo are registered trademarks of the College Board. Visit the College Board on the web: collegeboard.org.
AP Central is the official online home for the AP Program: apcentral.collegeboard.org.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
COMPUTER SCIENCE A SECTION II
Time—1 hour and 30 minutes Number of questions—4 Percent of total score—50
Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.
Notes:
• Assume that the interface and classes listed in the Java Quick Reference have been imported where appropriate.
• Unless otherwise noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied.
• In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-2-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
1. The APCalendar class contains methods used to calculate information about a calendar. You will write two methods of the class.
public class APCalendar
{
/** Returns true if year is a leap year and false otherwise. */ private static boolean isLeapYear(int year)
{ /* implementation not shown */ }
/** Returns the number of leap years between year1 and year2, inclusive. * Precondition: 0 <= year1 <= year2
*/
public static int numberOfLeapYears(int year1, int year2)
{ /* to be implemented in part (a) */ }
/** Returns the value representing the day of the week for the first day of year, * where 0 denotes Sunday, 1 denotes Monday, ..., and 6 denotes Saturday. */
private static int firstDayOfYear(int year)
{ /* implementation not shown */ }
/** Returns n, where month, day, and year specify the nth day of the year.
* Returns 1 for January 1 (month = 1, day = 1) of any year.
* Precondition: The date represented by month, day, year is a valid date. */
private static int dayOfYear(int month, int day, int year)
{ /* implementation not shown */ }
/** Returns the value representing the day of the week for the given date
* (month, day, year), where 0 denotes Sunday, 1 denotes Monday, ...,
* and 6 denotes Saturday.
* Precondition: The date represented by month, day, year is a valid date. */
public static int dayOfWeek(int month, int day, int year)
{ /* to be implemented in part (b) */ }
// There may be instance variables, constructors, and other methods not shown. }
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-3-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the static method numberOfLeapYears, which returns the number of leap years between year1 and year2, inclusive.
In order to calculate this value, a helper method is provided for you.
• isLeapYear(year) returns true if year is a leap year and false otherwise.
Complete method numberOfLeapYears below. You must use isLeapYear appropriately to receive full credit.
/** Returns the number of leap years between year1 and year2, inclusive. * Precondition: 0 <= year1 <= year2
*/
public static int numberOfLeapYears(int year1, int year2)
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-4-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the static method dayOfWeek, which returns the integer value representing the day of the week for the given date (month, day, year), where 0 denotes Sunday, 1 denotes Monday, ..., and 6 denotes Saturday. For example, 2019 began on a Tuesday, and January 5 is the fifth day of 2019. As a result, January 5, 2019, fell on a Saturday, and the method call dayOfWeek(1, 5, 2019)
returns 6.
As another example, January 10 is the tenth day of 2019. As a result, January 10, 2019, fell on a Thursday,
and the method call dayOfWeek(1, 10, 2019) returns 4.
In order to calculate this value, two helper methods are provided for you.
• firstDayOfYear(year) returns the integer value representing the day of the week for the first day of year, where 0 denotes Sunday, 1 denotes Monday, ..., and 6 denotes Saturday. For example, since 2019 began on a Tuesday, firstDayOfYear(2019) returns 2.
• dayOfYear(month, day, year) returns n, where month, day, and year specify the nth day of the year. For the first day of the year, January 1 (month = 1, day = 1), the value 1 is returned. This method accounts for whether year is a leap year. For example, dayOfYear(3, 1, 2017) returns 60, since 2017 is not a leap year, while dayOfYear(3, 1, 2016) returns 61, since 2016 is a leap year.
Class information for this question
public class APCalendar
private static boolean isLeapYear(int year)
public static int numberOfLeapYears(int year1, int year2)
private static int firstDayOfYear(int year)
private static int dayOfYear(int month, int day, int year)
public static int dayOfWeek(int month, int day, int year)
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-5-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method dayOfWeek below. You must use firstDayOfYear and dayOfYear appropriately to receive full credit.
/** Returns the value representing the day of the week for the given date
* (month, day, year), where 0 denotes Sunday, 1 denotes Monday, ...,
* and 6 denotes Saturday.
* Precondition: The date represented by month, day, year is a valid date. */
public static int dayOfWeek(int month, int day, int year)
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-6-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
2. This question involves the implementation of a fitness tracking system that is represented by the StepTracker class. A StepTracker object is created with a parameter that defines the minimum number of steps that must be taken for a day to be considered active.
The StepTracker class provides a constructor and the following methods.
• addDailySteps, which accumulates information about steps, in readings taken once per day
• activeDays, which returns the number of active days
• averageSteps, which returns the average number of steps per day, calculated by dividing the total number of steps taken by the number of days tracked
The following table contains a sample code execution sequence and the corresponding results.
Statements and Expressions
Value Returned (blank if no value)
Comment
StepTracker tr = new
StepTracker(10000);
Days with at least 10,000 steps are considered active. Assume that the parameter is positive.
0 No data have been recorded yet.
When no step data have been recorded, the
averageSteps method returns 0.0.
This is too few steps for the day to be considered
active.
This is too few steps for the day to be considered active.
0 No day had at least 10,000 steps.
7000.0 The average number of steps per day is (14000 / 2).
This represents an active day.
Of the three days for which step data were entered, one day had at least 10,000 steps.
tr.activeDays(); tr.averageSteps(); 0.0
tr.addDailySteps(9000);
tr.addDailySteps(5000);
tr.activeDays();
tr.averageSteps();
tr.addDailySteps(13000);
tr.activeDays(); 1
tr.averageSteps();
tr.addDailySteps(23000);
tr.addDailySteps(1111);
tr.activeDays(); 2
tr.averageSteps();
10222.2 The average number of steps per day is (51111 / 5).
9000.0 The average number of steps per day is (27000 / 3). This represents an active day.
This is too few steps for the day to be considered active.
Of the five days for which step data were entered, two days had at least 10,000 steps.
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-7-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Write the complete StepTracker class, including the constructor and any required instance variables and methods. Your implementation must meet all specifications and conform to the example.
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-8-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
3. Many encoded strings contain delimiters. A delimiter is a non-empty string that acts as a boundary between different parts of a larger string. The delimiters involved in this question occur in pairs that must be balanced, with each pair having an open delimiter and a close delimiter. There will be only one type of delimiter for each string. The following are examples of delimiters.
Example 1
Expressions in mathematics use open parentheses "(" and close parentheses ")" as delimiters. For each open parenthesis, there must be a matching close parenthesis.
(x + y) * 5 is a valid mathematical expression.
(x + (y) is NOT a valid mathematical expression because there are more open delimiters
than close delimiters.
HTML uses and as delimiters. For each open delimiter , there must be a matching close
Example 2 delimiter .
Make this text bold
Make this text bold
is valid HTML.
is NOT valid HTML because there is one open delimiter and no matching close delimiter.
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-9-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
In this question, you will write two methods in the following Delimiters class. public class Delimiters
{
/** The open and close delimiters. */ ;
;
/** Constructs a Delimiters object where open is the open delimiter and close is the
* close delimiter.
* Precondition: open and close are non-empty strings. */
public Delimiters(String open, String close)
{
openDel = open;
closeDel = close;
private String openDel
private String closeDel
}
/** Returns an ArrayList of delimiters from the array tokens, as described in part (a). */ public ArrayList
{ /* to be implemented in part (a) */ }
/** Returns true if the delimiters are balanced and false otherwise, as described in part (b). * Precondition: delimiters contains only valid open and close delimiters.
*/
public boolean isBalanced(ArrayList
{ /* to be implemented in part (b) */ }
// There may be instance variables, constructors, and methods that are not shown. }
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-10-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) A string containing text and possibly delimiters has been split into tokens and stored in String[]tokens. Eachtokeniseitheranopendelimiter,aclosedelimiter,orasubstringthatisnota delimiter. You will write the method getDelimitersList, which returns an ArrayList containing all the open and close delimiters found in tokens in their original order.
The following examples show the contents of an ArrayList returned by getDelimitersList for different open and close delimiters and different tokens arrays.
Example 1
openDel: closeDel:
tokens: ArrayList
of delimiters:
openDel: closeDel:
tokens:
ArrayList
of delimiters:
“(” “)”
“(” “x+y” “)” “*5” “(” “)”
Example 2
“” “
”
“” “yy” “
” “zz” “” “” “
” “”
Class information for this question
public class Delimiters
private String openDel
private String closeDel
public Delimiters(String open, String close)
public ArrayList
public boolean isBalanced(ArrayList
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-11-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method getDelimitersList below.
/** Returns an ArrayList of delimiters from the array tokens, as described in part (a). */
public ArrayList
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-12-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the method isBalanced, which returns true when the delimiters are balanced and returns false otherwise. The delimiters are balanced when both of the following conditions are satisfied; otherwise, they are not balanced.
1. When traversing the ArrayList from the first element to the last element, there is no point at which there are more close delimiters than open delimiters at or before that point.
2. The total number of open delimiters is equal to the total number of close delimiters.
Consider a Delimiters object for which openDel is “” and closeDel is ““. The examples below show different ArrayList objects that could be returned by calls to getDelimitersList and the value that would be returned by a call to isBalanced.
Example 1
The following example shows an ArrayList for which isBalanced returns true. As tokens are examined from first to last, the number of open delimiters is always greater than or equal to the number of close delimiters. After examining all tokens, there are an equal number of open and close delimiters.
“” “” “” “” “” “”
Example 2
The following example shows an ArrayList for which isBalanced returns
“” “” “” “”
↑
When starting from the left, at this point, condition 1 is violated.
Example 3
The following example shows an ArrayList for which isBalanced returns
“”
↑
At this point, condition 1 is violated.
Example 4
The following example shows an ArrayList for which isBalanced returns
second condition is violated. After examining all tokens, there are not an equal number of open and close delimiters.
“” “” “”
false.
false.
false because the
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-13-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Class information for this question
public class Delimiters
private String openDel
private String closeDel
public Delimiters(String open, String close)
public ArrayList
public boolean isBalanced(ArrayList
Complete method isBalanced below.
/** Returns true if the delimiters are balanced and false otherwise, as described in part (b). * Precondition: delimiters contains only valid open and close delimiters.
*/
public boolean isBalanced(ArrayList
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-14-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
4. The LightBoard class models a two-dimensional display of lights, where each light is either on or off, as represented by a Boolean value. You will implement a constructor to initialize the display and a method to evaluate a light.
public class LightBoard
{
/** The lights on the board, where true represents on and false represents off.
*/
private boolean[][] lights;
/** Constructs a LightBoard object having numRows rows and numCols columns.
* Precondition: numRows > 0, numCols > 0
* Postcondition: each light has a 40% probability of being set to on.
*/
public LightBoard(int numRows, int numCols)
{ /* to be implemented in part (a) */ }
/** Evaluates a light in row index row and column index col and returns a status
* as described in part (b).
* Precondition: row and col are valid indexes in lights. */
public boolean evaluateLight(int row, int col)
{ /* to be implemented in part (b) */ }
// There may be additional instance variables, constructors, and methods not shown. }
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-15-
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the constructor for the LightBoard class, which initializes lights so that each light is set to on with a 40% probability. The notation lights[r][c] represents the array element at row r and column c.
Complete the LightBoard constructor below.
/** Constructs a LightBoard object having numRows rows and numCols columns.
* Precondition: numRows > 0, numCols > 0
* Postcondition: each light has a 40% probability of being set to on.
*/
public LightBoard(int numRows, int numCols)
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-16-
GO ON TO THE NEXT PAGE.
lights
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the method evaluateLight, which computes and returns the status of a light at a given row and column based on the following rules.
1. If the light is on, return false if the number of lights in its column that are on is even, including the current light.
2. If the light is off, return true if the number of lights in its column that are on is divisible by three.
3. Otherwise, return the light’s current status.
For example, suppose that LightBoard sim = new LightBoard(7, 5) creates a light board with the initial state shown below, where true represents a light that is on and false represents a light that is off. Lights that are off are shaded.
0 true
1 true
2 true
3 true
4 true
5 true
6
true
true
true true
true true true true true true
Explanation
The light is on, and the number of lights that are on in its column is even.
The light is off, and the number of lights that are on in its column is divisible by 3.
Returns the light’s current status. Returns the light’s current status.
01234
true
false
false
false
false
false
false
false
false
false
false
false
false
false
Sample calls to evaluateLight are shown below.
false
false
false
false
Call to evaluateLight sim.evaluateLight(0, 3); sim.evaluateLight(6, 0); sim.evaluateLight(4, 1);
sim.evaluateLight(5, 4);
Value Returned
false true false true
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-17-
false
GO ON TO THE NEXT PAGE.
2019 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Class information for this question
public class LightBoard
private boolean[][] lights
public LightBoard(int numRows, int numCols)
public boolean evaluateLight(int row, int col)
Complete the evaluateLight method below.
/** Evaluates a light in row index row and column index col and returns a status
* as described in part (b).
* Precondition: row and col are valid indexes in lights. */
public boolean evaluateLight(int row, int col)
STOP END OF EXAM
© 2019 The College Board.
Visit the College Board on the web: collegeboard.org.
-18-
2018
AP Computer Science A Free-Response Questions
© 2018 The College Board. College Board, Advanced Placement Program, AP, AP Central, and the acorn logo are registered trademarks of the College Board. Visit the College Board on the Web: www.collegeboard.org.
AP Central is the official online home for the AP Program: apcentral.collegeboard.org.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
COMPUTER SCIENCE A SECTION II Time—1 hour and 30 minutes Number of questions—4 Percent of total score—50
Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.
Notes:
• Assume that the interface and classes listed in the Java Quick Reference have been imported where appropriate.
• Unless otherwise noted in the question, assume that parameters in method calls are not nulland that methods are called only when their preconditions are satisfied.
• In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-2-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
1. This question involves reasoning about a simulation of a frog hopping in a straight line. The frog attempts to hop to a goal within a specified number of hops. The simulation is encapsulated in the following FrogSimulation class. You will write two of the methods in this class.
public class FrogSimulation
{
/** Distance, in inches, from the starting position to the goal. */ private int goalDistance;
/** Maximum number of hops allowed to reach the goal. */ private int maxHops;
/** Constructs a FrogSimulation where dist is the distance, in inches, from the starting
* position to the goal, and numHops is the maximum number of hops allowed to reach the goal.
* Precondition: dist > 0; numHops > 0 */
public FrogSimulation(int dist, int numHops)
{
goalDistance = dist;
maxHops = numHops;
}
/** Returns an integer representing the distance, in inches, to be moved when the frog hops. */
private int hopDistance()
{ /* implementation not shown */ }
/** Simulates a frog attempting to reach the goal as described in part (a).
* Returns true if the frog successfully reached or passed the goal during the simulation; * false otherwise.
*/
public boolean simulate()
{ /* to be implemented in part (a) */ }
/** Runs num simulations and returns the proportion of simulations in which the frog
* successfully reached or passed the goal.
* Precondition: num > 0 */
public double runSimulations(int num)
{ /* to be implemented in part (b) */ } }
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-3-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the simulate method, which simulates the frog attempting to hop in a straight line to a goal from the frog’s starting position of 0 within a maximum number of hops. The method returns true if the frog successfully reached the goal within the maximum number of hops; otherwise, the method returns false.
The FrogSimulation class provides a method called hopDistance that returns an integer representing the distance (positive or negative) to be moved when the frog hops. A positive distance represents a move toward the goal. A negative distance represents a move away from the goal. The returned distance may vary from call to call. Each time the frog hops, its position is adjusted by the value returned by a call to the hopDistance method.
The frog hops until one of the following conditions becomes true:
• The frog has reached or passed the goal.
• The frog has reached a negative position.
• The frog has taken the maximum number of hops without reaching the goal.
The following example shows a declaration of a FrogSimulation object for which the goal distance is 24 inches and the maximum number of hops is 5. The table shows some possible outcomes of calling the simulate method.
FrogSimulation sim = new FrogSimulation(24, 5);
Example 1 Example 2 Example 3 Example 4 Example 5
Values returned by
hopDistance() 5, 7,-2, 8, 6 6, 7, 6, 6
6, -6, 31
4, 2, -8
5, 4, 2, 4, 3
Final position of frog
24 25 31 -2 18
Return value of
sim.simulate()
true
true
true
false
false
Class information for this question
public class FrogSimulation
private int goalDistance
private int maxHops
private int hopDistance()
public boolean simulate()
public double runSimulations(int num)
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-4-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method simulate below. You must use hopDistance appropriately to receive full credit.
/** Simulates a frog attempting to reach the goal as described in part (a).
* Returns true if the frog successfully reached or passed the goal during the simulation; * false otherwise.
*/
public boolean simulate()
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-5-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the runSimulations method, which performs a given number of simulations and returns the proportion of simulations in which the frog successfully reached or passed the goal. For example, if the parameter passed to runSimulations is 400, and 100 of the 400 simulate method calls returned true, then the runSimulations method should return 0.25.
Complete method runSimulations below. Assume that simulate works as specified, regardless of what you wrote in part (a). You must use simulate appropriately to receive full credit.
/** Runs num simulations and returns the proportion of simulations in which the frog
* successfully reached or passed the goal.
* Precondition: num > 0 */
public double runSimulations(int num)
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-6-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
2. This question involves reasoning about pairs of words that are represented by the following WordPair class. public class WordPair
{
/** Constructs a WordPair object. */
public WordPair(String first, String second) { /* implementation not shown */ }
/** Returns the first string of this WordPair object. */ public String getFirst()
{ /* implementation not shown */ }
/** Returns the second string of this WordPair object. */ public String getSecond()
{ /* implementation not shown */ }
}
You will implement the constructor and another method for the following WordPairList class.
public class WordPairList
{
/** The list of word pairs, initialized by the constructor. */ private ArrayList
/** Constructs a WordPairList object as described in part (a). * Precondition: words.length >= 2
*/
public WordPairList(String[] words)
{ /* to be implemented in part (a) */ }
/** Returns the number of matches as described in part (b). */
public int numMatches()
{ /* to be implemented in part (b) */ } }
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-7-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the constructor for the WordPairList class. The constructor takes an array of strings words as a parameter and initializes the instance variable allPairs to an ArrayList of WordPair objects.
A WordPair object consists of a word from the array paired with a word that appears later in the array. The allPairs list contains WordPair objects (words[i], words[j]) for every i and j, where 0 £ i < j < words.length . Each WordPair object is added exactly once to the list.
The following examples illustrate two different WordPairList objects. Example 1
String[] wordNums = {"one", "two", "three"};
WordPairList exampleOne = new WordPairList(wordNums);
After the code segment has executed, the allPairs instance variable of exampleOne will contain the following WordPair objects in some order.
("one", "two"), ("one", "three"), ("two", "three")
Example 2
String[] phrase = {"the", "more", "the", "merrier"};
WordPairList exampleTwo = new WordPairList(phrase);
After the code segment has executed, the allPairs instance variable of exampleTwo will contain the following WordPair objects in some order.
("the", "more"), ("the", "the"), ("the", "merrier"),
("more", "the"), ("more", "merrier"), ("the", "merrier")
Class information for this question
public class WordPair
public WordPair(String first, String second)
public String getFirst()
public String getSecond()
public class WordPairList
private ArrayList
public WordPairList(String[] words)
public int numMatches()
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-8-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete the WordPairList constructor below.
/** Constructs a WordPairList object as described in part (a). * Precondition: words.length >= 2
*/
public WordPairList(String[] words)
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-9-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the WordPairList method numMatches. This method returns the number of WordPair objects in allPairs for which the two strings match.
For example, the following code segment creates a WordPairList object. String[] moreWords = {“the”, “red”, “fox”, “the”, “red”};
WordPairList exampleThree = new WordPairList(moreWords);
After the code segment has executed, the allPairs instance variable of exampleThree will contain the following WordPair objects in some order. The pairs in which the first string matches the second string are shaded for illustration.
(“the”, “red”), (“the”, “fox”), (“the”, “the”),
(“the”, “red”), (“red”, “fox”), (“red”, “the”),
(“red”, “red”), (“fox”, “the”), (“fox”, “red”),
(“the”, “red”)
The call exampleThree.numMatches() should return 2.
Class information for this question
public class WordPair
public WordPair(String first, String second)
public String getFirst()
public String getSecond()
public class WordPairList
private ArrayList
public WordPairList(String[] words)
public int numMatches()
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-10-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method numMatches below.
/** Returns the number of matches as described in part (b). */
public int numMatches()
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-11-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
3. The StringChecker interface describes classes that check if strings are valid, according to some criterion.
public interface StringChecker
{
/** Returns true if str is valid. */
boolean isValid(String str);
}
A CodeWordChecker is a StringChecker. A CodeWordChecker object can be constructed with three parameters: two integers and a string. The first two parameters specify the minimum and maximum code word lengths, respectively, and the third parameter specifies a string that must not occur in the code word.
A CodeWordChecker object can also be constructed with a single parameter that specifies a string that must not occur in the code word; in this case the minimum and maximum lengths will default to 6 and 20, respectively.
The following examples illustrate the behavior of CodeWordChecker objects. Example 1
StringChecker sc1 = new CodeWordChecker(5, 8, “$”); Valid code words have 5 to 8 characters and must not include the string “$”.
Method call
sc1.isValid(“happy”)
sc1.isValid(“happy$”)
sc1.isValid(“Code”)
sc1.isValid(“happyCode”)
Example 2
Return value
true
false
false
false
Explanation Thecodewordisvalid. Thecodewordcontains”$”. Thecodewordistooshort. Thecodewordistoolong.
StringChecker sc2 = new CodeWordChecker(“pass”);
Valid code words must not include the string “pass”. Because the bounds are not specified, the length
bounds are 6 and 20, inclusive. Method call
sc2.isValid(“MyPass”)
sc2.isValid(“Mypassport”)
sc2.isValid(“happy”)
sc2.isValid(“1,000,000,000,000,000″)
Return value
true
false
false
false
Explanation Thecodewordisvalid. Thecodewordcontains”pass”. Thecodewordistooshort.
The code word is too long.
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-12-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Write the complete CodeWordChecker class. Your implementation must meet all specifications and conform to all examples.
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-13-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
4. This question involves reasoning about arrays of integers. You will write two static methods, both of which are in a class named ArrayTester.
public class ArrayTester
{
/** Returns an array containing the elements of column c of arr2D in the same order as
* they appear in arr2D.
* Precondition: c is a valid column index in arr2D.
* Postcondition: arr2D is unchanged.
*/
public static int[] getColumn(int[][] arr2D, int c)
{ /* to be implemented in part (a) */ }
/** Returns true if and only if every value in arr1 appears in arr2.
* Precondition: arr1 and arr2 have the same length.
* Postcondition: arr1 and arr2 are unchanged.
*/
public static boolean hasAllValues(int[] arr1, int[] arr2)
{ /* implementation not shown */ }
/** Returns true if arr contains any duplicate values;
* false otherwise. */
public static boolean containsDuplicates(int[] arr)
{ /* implementation not shown */ }
/** Returns true if square is a Latin square as described in part (b); * false otherwise.
* Precondition: square has an equal number of rows and columns. * square has at least one row.
*/
public static boolean isLatin(int[][] square)
{ /* to be implemented in part (b) */ } }
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-14-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write a static method getColumn, which returns a one-dimensional array containing the elements of a single column in a two-dimensional array. The elements in the returned array should be in the same order as they appear in the given column. The notation arr2D[r][c] represents the array element at row r and column c.
The following code segment initializes an array and calls the getColumn method.
int[][] arr2D = { { 0, 1, 2 },
{ 3, 4, 5 },
{ 6, 7, 8 },
{ 9, 5, 3 } };
int[] result = ArrayTester.getColumn(arr2D, 1);
When the code segment has completed execution, the variable result will have the following contents. result: {1, 4, 7, 5}
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-15-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method getColumn below.
/** Returns an array containing the elements of column c of arr2D in the same order as they * appear in arr2D.
* Precondition: c is a valid column index in arr2D.
* Postcondition: arr2D is unchanged.
*/
public static int[] getColumn(int[][] arr2D, int c)
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-16-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the static method isLatin, which returns true if a given two-dimensional square array is a Latin square, and otherwise, returns false.
A two-dimensional square array of integers is a Latin square if the following conditions are true.
• The first row has no duplicate values.
• All values in the first row of the square appear in each row of the square.
• All values in the first row of the square appear in each column of the square.
Examples of Latin Squares
1 2 3 2 3 1 3 1 2
103020 0 0 20 30 10 30 0 10 20 20 10 0 30
1 2 1 2 1 1 1 1 2
Not a Latin square because the first row contains duplicate values
Examples that are NOT Latin Squares
12 3 31 2 78 9
Not a Latin square because the elements of the first row do not all appear in the third row
1 2 1 2
Not a Latin square because the elements of the first row do not all appear in either column
The ArrayTester class provides two helper methods: containsDuplicates and hasAllValues. The method containsDuplicates returns true if the given one-dimensional array arr contains any duplicate values and false otherwise. The method hasAllValues returns true if and only if every value in arr1 appears in arr2. You do not need to write the code for these methods.
Class information for this question
public class ArrayTester
public static int[] getColumn(int[][] arr2D, int c)
public static boolean hasAllValues(int[] arr1, int[] arr2)
public static boolean containsDuplicates(int[] arr)
public static boolean isLatin(int[][] square)
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-17-
GO ON TO THE NEXT PAGE.
2018 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method isLatin below. Assume that getColumn works as specified, regardless of what you wrote in part (a). You must use getColumn, hasAllValues, and containsDuplicates appropriately to receive full credit.
/** Returns true if square is a Latin square as described in part (b); * false otherwise.
* Precondition: square has an equal number of rows and columns. * square has at least one row.
*/
public static boolean isLatin(int[][] square)
STOP END OF EXAM
© 2018 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-18-
GO ON TO THE NEXT PAGE.
2017
AP Computer Science A Free-Response Questions
© 2017 The College Board. College Board, Advanced Placement Program, AP, AP Central, and the acorn logo are registered trademarks of the College Board. Visit the College Board on the Web: www.collegeboard.org.
AP Central is the official online home for the AP Program: apcentral.collegeboard.org.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
COMPUTER SCIENCE A SECTION II Time—1 hour and 30 minutes Number of questions—4 Percent of total score—50
Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.
Notes:
• Assume that the interface and classes listed in the Java Quick Reference have been imported where appropriate.
• Unless otherwise noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied.
• In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-2
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
1. This question involves identifying and processing the digits of a non-negative integer. The declaration of the Digits class is shown below. You will write the constructor and one method for the Digits class.
public class Digits
{
/** The list of digits from the number used to construct this object.
* The digits appear in the list in the same order in which they appear in the original number. */
private ArrayList
/** Constructs a Digits object that represents num. * Precondition: num >= 0
*/
public Digits(int num)
{ /* to be implemented in part (a) */ }
/** Returns true if the digits in this Digits object are in strictly increasing order; * false otherwise.
*/
public boolean isStrictlyIncreasing()
{ /* to be implemented in part (b) */ } }
Part (a) begins on page 4.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-3
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the constructor for the Digits class. The constructor initializes and fills digitList with the digits from the non-negative integer num. The elements in digitList must be Integer objects representing single digits, and appear in the same order as the digits in num. Each of the following examples shows the declaration of a Digits object and the contents of digitList as initialized by the constructor.
Example 1
Digits d1 = new Digits(15704);
d1:
01234
digitList: 1 5 7 0 4
Example 2
Digits d2 = new Digits(0);
d2:
0
digitList: 0
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-4
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete the Digits constructor below.
/** Constructs a Digits object that represents num. * Precondition: num >= 0
*/
public Digits(int num)
Part (b) begins on page 6.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-5
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the Digits method isStrictlyIncreasing. The method returns true if the elements of digitList appear in strictly increasing order; otherwise, it returns false. A list is considered strictly increasing if each element after the first is greater than (but not equal to) the preceding element.
The following table shows the results of several calls to isStrictlyIncreasing.
Method call
new Digits(7).isStrictlyIncreasing()
new Digits(1356).isStrictlyIncreasing()
new Digits(1336).isStrictlyIncreasing()
new Digits(1536).isStrictlyIncreasing()
new Digits(65310).isStrictlyIncreasing()
Value returned
true
true
false
false
false
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-6
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method isStrictlyIncreasing below.
/** Returns true if the digits in this Digits object are in strictly increasing order; * false otherwise.
*/
public boolean isStrictlyIncreasing()
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-7
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
2. This question involves the design of a class that will be used to produce practice problems. The following
StudyPractice interface represents practice problems that can be used to study some subject.
public interface StudyPractice
{
/** Returns the current practice problem. */ String getProblem();
/** Changes to the next practice problem. */
void nextProblem();
}
The MultPractice class is a StudyPractice that produces multiplication practice problems. A MultPractice object is constructed with two integer values: first integer and initial second integer. The first integer is a value that remains constant and is used as the first integer in every practice problem. The initial second integer is used as the starting value for the second integer in the practice problems. This second value is incremented for each additional practice problem that is produced by the class.
For example, a MultPractice object created with the call new MultPractice(7, 3) would be used to create the practice problems “7 TIMES 3”, “7 TIMES 4”, “7 TIMES 5”, and so on.
In the MultPractice class, the getProblem method returns a string in the format of “first integer TIMES second integer”. The nextProblem method updates the state of the MultPractice object to represent the next practice problem.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-8
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
The following examples illustrate the behavior of the MultPractice class. Each table shows a code segment and the output that would be produced as the code is executed.
Example 1
Code segment
StudyPractice p1 = new MultPractice(7, 3);
System.out.println(p1.getProblem());
p1.nextProblem();
System.out.println(p1.getProblem());
p1.nextProblem();
System.out.println(p1.getProblem());
p1.nextProblem();
System.out.println(p1.getProblem());
Example 2
Code segment
StudyPractice p2 = new MultPractice(4, 12);
p2.nextProblem();
System.out.println(p2.getProblem());
System.out.println(p2.getProblem());
p2.nextProblem();
p2.nextProblem();
System.out.println(p2.getProblem());
p2.nextProblem();
System.out.println(p2.getProblem());
Output produced
7 TIMES 3
7 TIMES 4
7 TIMES 5
7 TIMES 6
Output produced
4 TIMES 13
4 TIMES 13
4 TIMES 15
4 TIMES 16
Question 2 continues on page 10.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-9
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Interface information for this question
public interface StudyPractice
String getProblem()
void nextProblem()
Write the complete MultPractice class. Your implementation must be consistent with the specifications and the given examples.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-10
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
3. This question involves analyzing and modifying a string. The following Phrase class maintains a phrase in an instance variable and has methods that access and make changes to the phrase. You will write two methods of the Phrase class.
public class Phrase
{
private String currentPhrase;
/** Constructs a new Phrase object. */ public Phrase(String p)
{ currentPhrase = p; }
/** Returns the index of the nth occurrence of str in the current phrase;
* returns -1 if the nth occurrence does not exist.
* Precondition: str.length() > 0 and n > 0
* Postcondition: the current phrase is not modified.
*/
public int findNthOccurrence(String str, int n)
{ /* implementation not shown */ }
/** Modifies the current phrase by replacing the nth occurrence of str with repl.
* If the nth occurrence does not exist, the current phrase is unchanged.
* Precondition: str.length() > 0 and n > 0 */
public void replaceNthOccurrence(String str, int n, String repl)
{ /* to be implemented in part (a) */ }
/** Returns the index of the last occurrence of str in the current phrase;
* returns -1 if str is not found.
* Precondition: str.length() > 0
* Postcondition: the current phrase is not modified.
*/
public int findLastOccurrence(String str)
{ /* to be implemented in part (b) */ }
/** Returns a string containing the current phrase. */ public String toString()
{ return currentPhrase; }
}
Part (a) begins on page 12.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-11
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(a) Write the Phrase method replaceNthOccurrence, which will replace the nth occurrence of the string str with the string repl. If the nth occurrence does not exist, currentPhrase remains unchanged.
Several examples of the behavior of the method replaceNthOccurrence are shown below.
Code segments
Phrase phrase1 = new Phrase(“A cat ate late.”);
phrase1.replaceNthOccurrence(“at”, 1, “rane”);
System.out.println(phrase1);
Phrase phrase2 = new Phrase(“A cat ate late.”);
phrase2.replaceNthOccurrence(“at”, 6, “xx”);
System.out.println(phrase2);
Phrase phrase3 = new Phrase(“A cat ate late.”);
phrase3.replaceNthOccurrence(“bat”, 2, “xx”);
System.out.println(phrase3);
Phrase phrase4 = new Phrase(“aaaa”);
phrase4.replaceNthOccurrence(“aa”, 1, “xx”);
System.out.println(phrase4);
Phrase phrase5 = new Phrase(“aaaa”);
phrase5.replaceNthOccurrence(“aa”, 2, “bbb”);
System.out.println(phrase5);
Class information for this question
public class Phrase
Output produced
A crane ate late.
A cat ate late.
A cat ate late.
xxaa
abbba
private String currentPhrase
public Phrase(String p)
public int findNthOccurrence(String str, int n)
public void replaceNthOccurrence(String str, int n, String repl)
public int findLastOccurrence(String str)
public String toString()
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-12
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
The Phrase class includes the method findNthOccurrence, which returns the nth occurrence of a given string. You must use findNthOccurrence appropriately to receive full credit.
Complete method replaceNthOccurrence below.
/** Modifies the current phrase by replacing the nth occurrence of str with repl.
* If the nth occurrence does not exist, the current phrase is unchanged.
* Precondition: str.length() > 0 and n > 0 */
public void replaceNthOccurrence(String str, int n, String repl)
Part (b) begins on page 14.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-13
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write the Phrase method findLastOccurrence. This method finds and returns the index of the last occurrence of a given string in currentPhrase. If the given string is not found, -1 is returned. The following tables show several examples of the behavior of the method findLastOccurrence.
Phrase phrase1 = new Phrase(“A cat ate late.”);
Method call
phrase1.findLastOccurrence(“at”)
phrase1.findLastOccurrence(“cat”)
phrase1.findLastOccurrence(“bat”)
Class information for this question
public class Phrase
Value returned
11 2 -1
private String currentPhrase
public Phrase(String p)
public int findNthOccurrence(String str, int n)
public void replaceNthOccurrence(String str, int n, String repl)
public int findLastOccurrence(String str)
public String toString()
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-14
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
You must use findNthOccurrence appropriately to receive full credit. Complete method findLastOccurrence below.
/** Returns the index of the last occurrence of str in the current phrase;
* returns -1 if str is not found.
* Precondition: str.length() > 0
* Postcondition: the current phrase is not modified.
*/
public int findLastOccurrence(String str)
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-15
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
4. This question involves reasoning about a two-dimensional (2D) array of integers. You will write two static
methods, both of which are in a single enclosing class named Successors (not shown). These methods process a 2D integer array that contains consecutive values. Each of these integers may be in any position
in the 2D integer array. For example, the following 2D integer array with 3 rows and 4 columns contains the integers 5 through 16, inclusive.
2D Integer Array 0123
0 15 5 9 10 1 12 16 11 6 2 14 8 13 7
The following Position class is used to represent positions in the integer array. The notation (r,c) will be used to refer to a Position object with row r and column c.
public class Position
{
/** Constructs a Position object with row r and column c. */ public Position(int r, int c)
{ /* implementation not shown */ }
// There may be instance variables, constructors, and methods that are not shown. }
(a) Write a static method findPosition that takes an integer value and a 2D integer array and returns the position of the integer in the given 2D integer array. If the integer is not an element of
the 2D integer array, the method returns null.
For example, assume that array arr is the 2D integer array shown at the beginning of the question.
• The call findPosition(8, arr) would return the Position object (2,1) because the
value 8 appears in arr at row 2 and column 1.
• The call findPosition(17, arr) would return null because the value 17 does not appear in arr.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-16
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Complete method findPosition below.
/** Returns the position of num in intArr;
* returns null if no such element exists in intArr. * Precondition: intArr contains at least one row. */
public static Position findPosition(int num, int[][] intArr)
Part (b) begins on page 18.
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-17
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
(b) Write a static method getSuccessorArray that returns a 2D successor array of positions created from a given 2D integer array.
The successor of an integer value is the integer that is one greater than that value. For example,
the successor of 8 is 9. A 2D successor array shows the position of the successor of each element in a given 2D integer array. The 2D successor array has the same dimensions as the given 2D integer array. Each element in the 2D successor array is the position (row, column) of the corresponding 2D integer array element’s successor. The largest element in the 2D integer array does not have a successor in the
2D integer array, so its corresponding position in the 2D successor array is null.
The following diagram shows a 2D integer array and its corresponding 2D successor array. To illustrate the successor relationship, the values 8 and 9 in the 2D integer array are shaded. In the 2D successor array, the shaded element shows that the position of the successor of 8 is (0,2) in the 2D integer array. The largest value in the 2D integer array is 16, so its corresponding element in the 2D successor array is null.
2D Integer Array 2D Successor Array 0123 0123
0 15
1 12
2 14
5 10 16 11 6 13 7
0 (1,1) (1,3) (0,3) (1,2)
1 (2,2) null (1,0) (2,3)
2 (0,0) (2,0) (2,1)
9
8
Class information for this question
public class Position
public Position(int r, int c)
public class Successors
public static Position findPosition(int num, int[][] intArr)
public static Position[][] getSuccessorArray(int[][] intArr)
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-18
(0,2)
GO ON TO THE NEXT PAGE.
2017 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
Assume that findPosition works as specified, regardless of what you wrote in part (a). You must use findPosition appropriately to receive full credit.
Complete method getSuccessorArray below.
/** Returns a 2D successor array as described in part (b) constructed from intArr.
* Precondition: intArr contains at least one row and contains consecutive values.
* Each of these integers may be in any position in the 2D array.
*/
public static Position[][] getSuccessorArray(int[][] intArr)
STOP END OF EXAM
© 2017 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-19
AP® Computer Science A
2016 Free-Response Questions
© 2016 The College Board. College Board, Advanced Placement Program, AP, AP Central, and the acorn logo are registered trademarks of the College Board.
Visit the College Board on the Web: www.collegeboard.org.
AP Central is the official online home for the AP Program: apcentral.collegeboard.org.
2016 AP® COMPUTER SCIENCE A FREE-RESPONSE QUESTIONS
COMPUTER SCIENCE A SECTION II Time—1 hour and 30 minutes Number of questions—4 Percent of total score—50
Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.
Notes:
• Assume that the classes listed in the Java Quick Reference have been imported where appropriate.
• Unless otherwise noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied.
• In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.
1. This question involves the implementation and extension of a RandomStringChooser class.
(a) A RandomStringChooser object is constructed from an array of non-null String values. When the object is first constructed, all of the strings are considered available. The RandomStringChooser class has a getNext method, which has the following behavior. A call to getNext returns a randomly chosen string from the available strings in the object. Once a particular string has been returned from
a call to getNext, it is no longer available to be returned from subsequent calls to getNext. If no strings are available to be returned, getNext returns “NONE”.
The following code segment shows an example of the behavior of RandomStringChooser.
String[] wordArray = {“wheels”, “on”, “the”, “bus”};
RandomStringChooser sChooser = new RandomStringChooser(wordArray);
for (int k = 0; k < 6; k++)
{
System.out.print(sChooser.getNext() + " ");
}
One possible output is shown below. Because sChooser has only four strings, the string "NONE" is printed twice.
bus the wheels on NONE NONE
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-2-
GO ON TO THE NEXT PAGE.
Write the entire RandomStringChooser class. Your implementation must include an appropriate constructor and any necessary methods. Any instance variables must be private. The code segment in the example above should have the indicated behavior (that is, it must compile and produce a result like the possible output shown). Neither the constructor nor any of the methods should alter the parameter passed to the constructor, but your implementation may copy the contents of the array.
Part (b) begins on page 4.
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-3-
GO ON TO THE NEXT PAGE.
(b) The following partially completed RandomLetterChooser class is a subclass of the RandomStringChooser class. You will write the constructor for the RandomLetterChooser class.
public class RandomLetterChooser extends RandomStringChooser
{
/** Constructs a random letter chooser using the given string str. * Precondition: str contains only letters.
*/
public RandomLetterChooser(String str)
{ /* to be implemented in part (b) */ }
/** Returns an array of single-letter strings.
* Each of these strings consists of a single letter from str. Element k
* of the returned array contains the single letter at position k of str.
* For example, getSingleLetters("cat") returns the
* array { "c", "a", "t" }. */
public static String[] getSingleLetters(String str)
{ /* implementation not shown */ } }
The following code segment shows an example of using RandomLetterChooser.
RandomLetterChooser letterChooser = new RandomLetterChooser("cat");
for (int k = 0; k < 4; k++)
{
System.out.print(letterChooser.getNext());
}
The code segment will print the three letters in "cat" in one of the possible orders. Because there are only three letters in the original string, the code segment prints "NONE" the fourth time through the loop. One possible output is shown below.
actNONE
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-4-
GO ON TO THE NEXT PAGE.
Assume that the RandomStringChooser class that you wrote in part (a) has been implemented correctly and that getSingleLetters works as specified. You must use getSingleLetters appropriately to receive full credit.
Complete the RandomLetterChooser constructor below.
/** Constructs a random letter chooser using the given string str. * Precondition: str contains only letters.
*/
public RandomLetterChooser(String str)
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-5-
GO ON TO THE NEXT PAGE.
{
2. This question involves two classes that are used to process log messages. A list of sample log messages is given below.
CLIENT3:security alert – repeated login failures
Webserver:disk offline
SERVER1:file not found
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2
Webserver:error on /dev/disk
Log messages have the format machineId:description, where machineId identifies the computer and description describes the event being logged. Exactly one colon (":") appears in a log message. There are no blanks either immediately before or immediately after the colon.
The following LogMessage class is used to represent a log message. public class LogMessage
private String machineId
;
;
private String description
/** Precondition: message is a valid log message. */ public LogMessage(String message)
{ /* to be implemented in part (a) */ }
/** Returns true if the description in this log message properly contains keyword; * false otherwise.
*/
public boolean containsWord(String keyword)
{ /* to be implemented in part (b) */ } public String getMachineId()
{ return machineId; }
public String getDescription()
{ return description; }
// There may be instance variables, constructors, and methods that are not shown. }
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-6-
GO ON TO THE NEXT PAGE.
(a) Write the constructor for the LogMessage class. It must initialize the private data of the object so that getMachineId returns the machineId part of the message and getDescription returns the description part of the message.
Complete the LogMessage constructor below.
/** Precondition: message is a valid log message. */
public LogMessage(String message)
Part (b) begins on page 8.
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-7-
GO ON TO THE NEXT PAGE.
(b) Write the LogMessage method containsWord, which returns true if the description in the log message properly contains a given keyword and returns false otherwise.
A description properly contains a keyword if all three of the following conditions are true.
o thekeywordisasubstringofthedescription;
o thekeywordiseitheratthebeginningofthedescriptionoritisimmediatelyprecededbyaspace; o thekeywordiseitherattheendofthedescriptionoritisimmediatelyfollowedbyaspace.
The following tables show several examples. The descriptions in the left table properly contain the keyword "disk". The descriptions in the right table do not properly contain the keyword "disk".
Descriptions that properly contain "disk" "disk"
"error on disk"
"error on /dev/disk disk" "error on disk DSK1"
Descriptions that do not properly contain "disk" "DISK"
"error on disk3"
"error on /dev/disk"
"diskette"
WRITE YOUR SOLUTION ON THE NEXT PAGE.
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-8-
GO ON TO THE NEXT PAGE.
Assume that the LogMessage constructor works as specified, regardless of what you wrote in part (a). Complete method containsWord below.
/** Returns true if the description in this log message properly contains keyword; * false otherwise.
*/
public boolean containsWord(String keyword)
Part (c) begins on page 10.
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-9-
GO ON TO THE NEXT PAGE.
(c) The SystemLog class represents a list of LogMessage objects and provides a method that removes and returns a list of all log messages (if any) that properly contain a given keyword. The messages in the returned list appear in the same order in which they originally appeared in the system log. If no message properly contains the keyword, an empty list is returned. The declaration of the SystemLog class is shown below.
public class SystemLog
{
/** Contains all the entries in this system log.
* Guaranteed not to be null and to contain only non-null entries. */
private List
/** * *
Removes from the system log all entries whose descriptions properly contain keyword, and returns a list (possibly empty) containing the removed entries.
Postcondition:
* – Entries in the returned list properly contain keyword and
* are in the order in which they appeared in the system log.
* – The remaining entries in the system log do not properly contain keyword and * are in their original order.
* – The returned list is empty if no messages properly contain keyword.
*/
public List
{ /* to be implemented in part (c) */ }
// There may be instance variables, constructors, and methods that are not shown.
}
Write the SystemLog method removeMessages, which removes from the system log all entries whose descriptions properly contain keyword and returns a list of the removed entries in their original order. For example, assume that theLog is a SystemLog object initially containing six LogMessage objects representing the following list of log messages.
CLIENT3:security alert – repeated login failures
Webserver:disk offline
SERVER1:file not found
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2
Webserver:error on /dev/disk
The call theLog.removeMessages(“disk”) would return a list containing the LogMessage objects representing the following log messages.
Webserver:disk offline
SERVER2:read error on disk DSK1
SERVER1:write error on disk DSK2
After the call, theLog would contain the following log messages.
CLIENT3:security alert – repeated login failures
SERVER1:file not found
Webserver:error on /dev/disk
© 2016 The College Board.
Visit the College Board on the Web: www.collegeboard.org.
-10-
GO ON TO THE NEXT PAGE.