Related Files | 4
Short Page Link
https://www.edufilestorage.com/6lr
Full Page Link
https://www.edufilestorage.com/6lr/PDF_2008_AP_Computer_Science_AB_Practice_Exam_and_Answers_MCQ_Multiple_Choice_Questions_with_Answers_Advanced_Placement.pdf
HTML Code
<a href="https://www.edufilestorage.com/6lr/PDF_2008_AP_Computer_Science_AB_Practice_Exam_and_Answers_MCQ_Multiple_Choice_Questions_with_Answers_Advanced_Placement.pdf" target="_blank" title="Download from eduFileStorage.com"><img src="https://www.edufilestorage.com/cache/plugins/filepreviewer/4393/pdf/150x190_middle_46f4e7862b1eb5bd4935adbbba5d79e8.jpg"/></a>
Forum Code
[url=https://www.edufilestorage.com/6lr/PDF_2008_AP_Computer_Science_AB_Practice_Exam_and_Answers_MCQ_Multiple_Choice_Questions_with_Answers_Advanced_Placement.pdf][img]https://www.edufilestorage.com/cache/plugins/filepreviewer/4393/pdf/150x190_middle_46f4e7862b1eb5bd4935adbbba5d79e8.jpg[/img][/url]
| Filename: | [PDF] 2008 AP Computer Science AB Practice Exam and Answers MCQ Multiple Choice Questions with Answers Advanced Placement.pdf |
| Filesize: | 1.79 MB |
| Keywords: | |
| Description: | Download file or read online AP past exam paper 2008 AP Computer Science AB Practice Exam and Answers MCQ Multiple Choice Questions with Answers and FRQ Free Response Questions with Scoring Guidelines - Collegeboard Advanced Placement. |
[PDF] 2008 AP Computer Science AB Practice Exam and Answers MCQ Multiple Choice Questions with Answers Advanced Placement.pdf | Plain Text
The questions contained in this AP ® Computer Science AB Practice Exam are written to the content specifications of AP Exams for this subject. Taking this practice exam should provide students with an idea of their general areas of strengths and weaknesses in preparing \ for the actual AP Exam. Because this AP Computer Science AB Practice Exam has never been administered as an operational AP Exam, statistical data are not available for calculating potential raw scores or conversions into AP grades. This AP Computer Science AB Practice Exam is provided by the College Board for AP Exam preparation. Teachers are permitted to download the materials and make copies to use with their students in a class - room setting only. To maintain the security of this exam, teachers should collect all materials after their administration and keep them in a secure location. Teachers may not redistribute the files electronically for any reason. © 2008 The College Board. All rights reserved. College Board, Advanced Placement Program, AP, AP Central, SAT, and the acorn logo are registered trademarks of the College Board. PSAT/NMSQT is a registered trade - mark of the College Board and National Merit Scholarship Corporation. All other products and services may be trademarks of their respective owners. Visit the College Board on the Web: www.collegeboard.com. Practice Exam Advanced Placement Program AP ® Computer Science AB
Contents Directions for Administration ........................................................................\ .................... ii Section I: Multiple-C hoice Questions ........................................................................\ ........ 1 Section II: Free-Resp onse Questions ........................................................................\ .......38 Quick Refe rence........................................................................\ .........................................48 Student Answer Sheet for Mu ltiple-Choice Section ...................................................... 75 Multiple-Choice Answer Key ........................................................................\ ................... 76 Free-Response Scori ng Guidelines........................................................................\ .......... 77 The College Board: Connecting Students to College Success The College Board is a not-for-profit membersh ip association whose mission is to connect students to college success and opportunity. Founded in 1900, the association is composed of more than 5, 000 schools, colleges, universiti es, and other educational organizations. Each year, the College Board serves seven million students and their parents, 23,000 high schools, and 3,500 college s through major programs and services in college admissions, guidance, assessment, fi nancial aid, enrollment, and teaching and learning. Among its best-kno wn programs are the SAT ®, the PSAT/NMSQT ®, and the Advanced Placement Program ® (AP ®). The College Board is co mmitted to the principles of excellence and equity, and that commitmen t is embodied in all of its programs, services, activities, and concerns. Visit the College Board on the Web: www.collegeboard.com. AP Central is the official online home fo r the AP Program: apcentral.collegeboard.com. -i-
AP ® Computer Science AB Directions for Administration The AP Computer Science AB Exam is three hours in length and consists of a multiple-choice section and a free- response section. • The 75-minute multiple-choice section contains 40 ques tions and accounts for 50 percent of the final grade. • The 105-minute free-response section contains 4 questions and accounts for 50 percent of the final grade. Students should be given a 10-minute warning prior to the end of each section of the exam. A 10-minute break should be provided after Section I is completed. The actual AP Exam is administered in one session. Student s will have the most realistic experience if a complete morning or afternoon is available to administer this practice exam. If a schedule does not permit one time period for the entire practice exam administration, it would be acceptable to administer Section I one day and Section II on a subsequent day. Many students wonder whether or not to guess the answer s to the multiple-choice questions about which they are not certain. It is improbable that mere guessing will improve a score. However, if a student has some knowledge of the question and is able to eliminate one or more an swer choices as wrong, it may be to the student’s advantage to answer such a question. • The use of calculators, or any other electroni c devices, is not permitted during the exam. • It is suggested that the practice exam be completed using a pencil to simulate an actual administration. • Teachers will need to provide paper for the students to write their free-response answers. Teachers should provide directions to the students indicating how they wish the responses to be labeled so the teacher will be able to associate the student’s response with the question the student intended to answer. • The AP Computer Science AB Exam Appendix is in cluded with the exam materials, and each student should have a copy of this document for use with both Section I and Section II. Previously used copies of the appendix should not be distributed for the practice exam administration because students should not have access to any notes that may have b een previously written into the appendix. • Remember that students are not allowed to remove any materials, including scratch work and the appendix, from the testing site. -ii-
Section I Multiple-Choice Questions -1-
GO ON TO THE NEXT PAGE. COMPUTER SCIENCE AB SECTION I Time — 1 hour and 15 minutes Number of questions — 40 Percent of total grade — 50 Directions: Determine the answer to each of the following questions or incomplete statements, using the available space for any necessary scratch work. Then decide which is the best of the choices given and place the letter of your choice in the corresponding box on the student answer sheet. No credit will be given for anything written in the examination booklet. Do not spend too much time on any one problem. Notes : • Assume that the classes listed in the Quick Refere nce found in the Appendix have been imported where appropriate. • Assume that the implementation classes ListNode and TreeNode (page A4 in the Appendix) are used for any questions referring to linked lists or trees, unless otherwise specified. • ListNode and TreeNode parameters may be null . Otherwise, unless noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied. • Assume that declarations of variables and methods appear within the context of an enclosing class. • Assume that method calls that are not prefixed with an object or class name and are not shown within a complete class definition appear within the context of an enclosing class. -2-
GO ON TO THE NEXT PAGE. 1. Consider the following code segment. int[] arr = {4, 2, 9, 7, 3}; for (int k : arr) { k = k + 10; System.out.print(k + " "); } for (int k : arr) System.out.print(k + " "); What is printed as a result of executing the code segment? (A) 0 1 2 3 4 0 1 2 3 4 (B) 4 2 9 7 3 4 2 9 7 3 (C) 10 11 12 13 14 0 1 2 3 4 (D) 14 12 19 17 13 4 2 9 7 3 (E) 14 12 19 17 13 14 12 19 17 13 2. Consider the following method. public int mystery(int num) { int x = num; while (x > 0) { if (x / 10 % 2 == 0) return x; x = x / 10; } return x; } What value is returned as a result of the call mystery(1034) ? (A) 4 (B) 10 (C) 34 (D) 103 (E) 1034 -3-
GO ON TO THE NEXT PAGE. 3. Consider the following method. public int pick(boolean test, int x, int y) { if (test) return x; else return y; } What value is returned by the following method call? pick(false, pick(true, 0, 1), pick(true, 6, 7)) (A) 0 (B) 1 (C) 3 (D) 6 (E) 7 -4-
GO ON TO THE NEXT PAGE. Questions 4-5 refer to the following classes. public class First { public String name() { return "First"; } } public class Second extends First { public void whoRules() { System.out.print(super.name() + " rules"); System.out.println(" but " + name() + " is even better"); } public String name() { return "Second"; } } public class Third extends Second { public String name() { return "Third"; } } -5-
GO ON TO THE NEXT PAGE. 4. Consider the following code segment. Second varSecond = new Second(); Third varThird = new Third(); varSecond.whoRules(); varThird.whoRules(); What is printed as a result of executing the code segment? (A) First rules but Second is even better First rules but Second is even better (B) First rules but Second is even better First rules but Third is even better (C) First rules but Second is even better Second rules but Second is even better (D) First rules but Second is even better Second rules but Third is even better (E) Second rules but Second is even better Second rules but Second is even better 5. Consider the following code segment. /* SomeType1 */ varA = new Second(); /* SomeType2 */ varB = new Third(); varA.whoRules(); varB.whoRules(); Which of the following could be used to replace /* SomeType1 */ and /* SomeType2 */ so that the code segment will compile without error? /* SomeType1 */ /* SomeType2 */ I. First Third II. Second Second III. Third Third (A) I only (B) II only (C) III only (D) I and II (E) II and III -6-
GO ON TO THE NEXT PAGE. 6. Consider the following classes. public class Base { public Base() { System.out.print("Base" + " "); } } public class Derived extends Base { public Derived() { System.out.print("Derived" + " "); } } Assume that the following statement appears in another class. Derived d1 = new Derived(); What is printed as a result of executing the statement? (A) Nothing is printed because the statement is a variable declaration. (B) Base (C) Derived (D) Base Derived (E) Derived Base -7-
GO ON TO THE NEXT PAGE. 7. Consider the following method. /** @param a a queue of Integer values in nondecreasing order * @param b a queue of Integer values in nondecreasing order * @return a queue containing all values from a and b sorted in nondecreasing order * Postcondition : a and b are empty */ public Queue merge(Queue a, Queue b) { Queue result = new LinkedList(); while (!a.isEmpty() || !b.isEmpty()) { if ( /* missing code */ ) result.add(a.remove()); else result.add(b.remove()); } return result; } Which of the following expressions could be used to replace /* missing code */ so that merge will work as intended? (A) !a.isEmpty() && b.isEmpty() (B) a.peek().intValue() < b.peek().intValue() (C) b.isEmpty() || (a.peek().intValue() < b.peek().intValue()) (D) !b.isEmpty() && (a.peek().intValue() < b.peek().intValue()) \ (E) b.isEmpty() || (!a.isEmpty() && (a.peek().intValue() < b.peek().intValue())\ ) -8-
GO ON TO THE NEXT PAGE. 8. Consider the following method. public int getTheResult(int n) { int product = 1; for (int number = 1; number < n; number++) { if (number % 2 == 0) product *= number; } return product; } What value is returned as a result of the call getTheResult(8) ? (A) 48 (B) 105 (C) 384 (D) 5040 (E) 40320 -9-
GO ON TO THE NEXT PAGE. 9. Consider the following code segment. int[] oldArray = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int[][] newArray = new int[3][3]; int row = 0; int col = 0; for (int index = 0; index < oldArray.length; index++) { newArray[row][col] = oldArray[index]; row++; if ((row % 3) == 0) { col++; row = 0; } } System.out.println(newArray[0][2]); What is printed as a result of executing the code segment? (A) 3 (B) 4 (C) 5 (D) 7 (E) 8 -10-
GO ON TO THE NEXT PAGE. 10. Consider the following code segment. ArrayList nums = new ArrayList(); nums.add(new Integer(37)); nums.add(new Integer(3)); nums.add(new Integer(0)); nums.add(1, new Integer(2)); nums.set(0, new Integer(1)); nums.remove(2); System.out.println(nums); What is printed as a result of executing the code segment? (A) [1, 2, 0] (B) [1, 3, 0] (C) [1, 3, 2] (D) [1, 37, 3, 0] (E) [37, 0, 0] 11. Assume that the boolean variables a, b , c , and d have been declared and initialized. Consider the following expression. !( !( a && b ) || ( c || !d )) Which of the following is equivalent to the expression? (A) ( a && b ) && ( !c && d ) (B) ( a || b ) && ( !c && d ) (C) ( a && b ) || ( c || !d ) (D) ( !a || !b ) && ( !c && d ) (E) !( a && b ) && ( c || !d ) -11-
GO ON TO THE NEXT PAGE. 12. Consider the following class declarations. public class A { private int x; public A() { x = 0; } public A(int y) { x = y; } // There may be instance variables, constructors, and methods that are not shown. } public class B extends A { private int y; public B() { /* missing code */ } // There may be instance variables, constructors, and methods that are not shown. } Which of the following can be used to replace /* missing code */ so that the statement B temp = new B(); will construct an object of type B and initialize both x and y with 0 ? I. y = 0; II. super(0); y = 0; III. x = 0; y = 0; (A) I only (B) II only (C) I and II only (D) II and III only (E) I, II, and III -12-
GO ON TO THE NEXT PAGE. 13. Consider the following method. // Precondition : b > 0 public int surprise(int b) { if ((b % 2) == 0) { if (b < 10) return b; else return ((b % 10) + surprise(b / 10)); } else { if (b < 10) return 0; else return surprise(b / 10); } } Which of the following expressions will evaluate to true ? I. surprise(146781) == 0 II. surprise(7754) == 4 III. surprise(58216) == 16 (A) I only (B) II only (C) III only (D) II and III only (E) I, II, and III -13-
GO ON TO THE NEXT PAGE. 14. Consider the following method that is intended to return true if an array of integers is arranged in decreasing order and return false otherwise. /** @param nums an array of integers * @return true if the values in the array appear in decreasing order * false otherwise */ public static boolean isDecreasing(int[] nums) { /* missing code */ } Which of the following can be used to replace /* missing code */ so that isDecreasing will work as intended? I. for (int k = 0; k < nums.length; k++) { if (nums[k]
GO ON TO THE NEXT PAGE. 15. Assume that TreeNode t refers to the following binary tree that contains String objects. Consider the following method. public void funny(TreeNode p) { if (p.getLeft() != null) { funny(p.getLeft()); } else if (p.getRight() != null) { funny(p.getRight()); } else System.out.print(p.getValue() + "." ); } What is printed as a result of the call funny(t) ? (A) how.now.brown.cow.this.is.only.a.test. (B) how.now.cow.brown.this.only.a.is.test. (C) cow.only.a.test. (D) cow.only.a.is.test. (E) cow. -15-
GO ON TO THE NEXT PAGE. 16. A Web browser must keep track of the sites that you have visited so that when you click the “back” button it will return you to the most recent site. Which of the following data structures has a functionality that best supports the described display of previously visited sites? (A) Stack (B) Queue (C) PriorityQueue (D) TreeNode (E) TreeMap -16-
GO ON TO THE NEXT PAGE. 17. Consider the following class that stores information about temperature readings on various dates. public class TemperatureReading implements Comparable { private double temperature; private int month, day, year; public int compareTo(Object obj) { TemperatureReading other = (TemperatureReading) obj; /* missing code */ } // There may be instance variables, constructors, and methods that are not shown. } Consider the following code segments that are potential replacements for /* missing code */. I. Double d1 = new Double(temperature); Double d2 = new Double(other.temperature); return d1.compareTo(d2); II. if (temperature < other.temperature) return -1; else if (temperature == other.temperature) return 0; else return 1; III. return (int) (temperature - other.temperature); Which of the code segments could be used to replace /* missing code */ so that compareTo can be used to order TemperatureReading objects by increasing temperature value? (A) II only (B) I and II only (C) I and III only (D) II and III only (E) I, II, and III -17-
GO ON TO THE NEXT PAGE. 18. Consider the following method. public String recScramble(String str, int[] positions, int k) { if (str == null || str.length() == 0) return ""; if (str.length() == 1) return str; int pos = positions[k]; String nStr = str.substring(pos, pos + 1); str = str.substring(0, pos) + str.substring(pos + 1); return nStr + recScramble(str, positions, k + 1); } Consider the following code segment. int[] indexes = {2, 1, 1}; System.out.println(recScramble("epic", indexes, 0)); What is printed as a result of executing the code segment? (A) cepi (B) epci (C) iecp (D) iepc (E) ipce -18-
GO ON TO THE NEXT PAGE. 19. Consider the following code segment. Stack stackOne = new Stack(); Stack stackTwo = new Stack(); for (int k = 0; k < 5; k++) { stackOne.push(new Integer(k)); } while (!stackOne.isEmpty()) { stackTwo.push(stackOne.pop()); } for (int k = 5; k < 10; k++) { stackTwo.push(new Integer(k)); } while (!stackTwo.isEmpty()) { System.out.print(stackTwo.pop() + " "); } What is printed as a result of executing the code segment? (A) 0 1 2 3 4 5 6 7 8 9 (B) 0 1 2 3 4 9 8 7 6 5 (C) 5 6 7 8 9 0 1 2 3 4 (D) 9 8 7 6 5 0 1 2 3 4 (E) 9 8 7 6 5 4 3 2 1 0 -19-
GO ON TO THE NEXT PAGE. 20. Consider the following method. public int addFun(int n) { if (n
GO ON TO THE NEXT PAGE. Questions 21-25 refer to the code from the GridWorld case study. A copy of the code is provided in the Appendix. 21. A CornerBug behaves like a Bug except that a CornerBug makes all turns at right angles rather than 45-degree angles. Of the following, which is the best design for the CornerBug class? (A) Create an abstract class called RightAngleBug that is a Bug that only turns 90 degrees, and then create a class CornerBug that inherits from RightAngleBug . (B) Create an interface called RightTurn that includes the specification of a turnRight method, and then create a class CornerBug that implements RightTurn. (C) Create a class CornerBug that inherits from Bug and adds a constructor that has an int parameter that determines if the bug should turn 90 degrees or 45 degrees. (D) Create a class CornerBug that inherits from Bug and overrides the Bug turn method to turn the bug 90 degrees instead of 45 degrees. (E) Create an interface CornerBug that includes the definition of a turnRight method that is automatically used by the Bug act method for objects that are instantiated as CornerBug objects. 22. Consider the following class that inherits from Bug and overrides the turn method. public class LeftTurningBug extends Bug { public void turn() { /* missing code */ } } Which of the following can be used to replace /* missing code */ so that a LeftTurningBug object will always turn 90 degrees to the left? I. setDirection(Location.LEFT); II. setDirection(getDirection() + Location.LEFT); III. setDirection(Location.HALF_LEFT + Location.HALF_LEFT); (A) I only (B) II only (C) III only (D) I and III only (E) I, II, and III -21-
GO ON TO THE NEXT PAGE. 23. Consider the following class declaration. public class MysteryBug extends Bug { private int count; public MysteryBug() { setDirection(Location.NORTHEAST); count = 0; } public void act() { if (count < 3 && canMove()) { move(); count++; } else { turn(); count = 0; } } } Assume that a MysteryBug object has been placed in the center of an otherwise empty grid that is 20 rows by 20 columns. What pattern of flowers is formed if the act method of the MysteryBug is called many times in a row? (A) No pattern is formed because the MysteryBug never puts any flowers into the world. (B) A square pattern is formed just as with a BoxBug object. (C) A diamond pattern is formed (a square that has been rotated 45 degrees). (D) A six-sided pattern is formed. (E) An eight-sided pattern is formed. -22-
GO ON TO THE NEXT PAGE. 24. A PouncingCritter behaves like a Critter except that when it moves, it randomly selects one of the grid locations that contains an Actor and moves to that location. Which of the following methods must be changed to allow a PouncingCritter to behave this way while also preserving the Critter postconditions? I. getMoveLocations II. makeMove III. selectMoveLocation (A) I only (B) II only (C) III only (D) I and III only (E) I, II, and III -23-
GO ON TO THE NEXT PAGE. 25. Consider the following method that is intended to move the parameter anActor to a different grid that is referred to by the parameter newGrid. The location of anActor in newGrid should be the same as the location that anActor had occupied in its original grid. /** Moves anActor to newGrid in the same location it occupied in its original grid. * @param anActor the actor to be moved * @param newGrid the grid in which the actor is to be placed */ public void moveActorToNewGrid(Actor anActor, Grid newGrid) { Grid oldGrid = anActor.getGrid(); Location loc = anActor.getLocation(); /* missing code */ } Which of the following can be used to replace /* missing code */ so that moveActorToNewGrid will work as intended? (A) anActor.putSelfInGrid(newGrid, loc); anActor.removeSelfFromGrid(); (B) oldGrid.remove(loc); anActor.putSelfInGrid(newGrid, loc); (C) anActor.removeSelfFromGrid(); anActor.putSelfInGrid(newGrid, loc); (D) oldGrid.remove(loc); newGrid.put(anActor, loc); (E) newGrid.put(anActor, loc); oldGrid.remove(loc); -24-
GO ON TO THE NEXT PAGE. Questions 26-27 refer to the following method. /** @param count the number of elements to place in the queue * Precondition: count > 0 * @return a queue of integers */ public static Queue fillQ(int count) { Queue intQ = new LinkedList(); int x = 3; int y = 2; int t = 1; if (count == 1) intQ.add(new Integer(y)); else { intQ.add(new Integer(y)); intQ.add(new Integer(t)); for (int k = 2; k < count; k++) { x = y + t - k; y = t; t = x + k; intQ.add(new Integer(t)); // Point A } } return intQ; } -25-
GO ON TO THE NEXT PAGE. 26. What will be printed as a result of executing the following statement? System.out.println(fillQ(6)); (A) [1, 2, 3, 5, 8, 13] (B) [2, 1, 3, 4, 7, 11] (C) [2, 1, 3, 6, 10, 15] (D) [2, 1, 3, 6, 12, 24] (E) [2, 3, 5, 8, 12, 17] 27. Which of the following best describes the value added to the queue at // Point A ? (A) It is the sum of all the previous values that have been added to the queue. (B) It is the sum of all the previous odd values that have been added to the queue. (C) It is the sum of the two immediately previous values that have been added to the queue. (D) It is the sum of the loop index and the immediately previous value that has been added to the queue. (E) It is the square of the loop index. -26-
GO ON TO THE NEXT PAGE. 28. Consider the following method. /** @param t a reference to the root of a binary tree of integers * Precondition: t is not null */ public int mystery(TreeNode t) { int keep = ((Integer) t.getValue()).intValue(); int leftKeep = keep; int rightKeep = keep; if (t.getLeft() != null) leftKeep = mystery(t.getLeft()); if (t.getRight() != null) rightKeep = mystery(t.getRight()); if (keep >= leftKeep) keep = leftKeep; if (keep >= rightKeep) keep = rightKeep; return keep; } Assume that TreeNode root is a reference to a nonempty binary tree of integers. Which of the following best describes the value returned by the call mystery(root) ? (A) The smallest integer in the tree (B) The largest integer in the tree (C) The value in the root of the tree (D) The value in the rightmost leaf of the tree (E) The value in the leftmost leaf of the tree -27-
GO ON TO THE NEXT PAGE. 29. Consider the following partial implementation of a ListNodeIterator that can be used to iterate over a linked list that has been constructed with ListNode objects. public class ListNodeIterator implements Iterator { private ListNode current; // the next item to be returned from the list public ListNodeIterator(ListNode first) { current = first; } public Object next() { Object value = current.getValue(); current = current.getNext(); return value; } public boolean hasNext() { /* missing code */ } // There may be fields, constructors, and methods that are not shown. } Which of the following can be used to replace /* missing code */ so that method hasNext() will work as specified in the Iterator interface? (A) return current == null; (B) return current != null; (C) return current.getValue() != null; (D) return current.getNext() != null; (E) return current.getNext().getValue() != null; -28-
GO ON TO THE NEXT PAGE. 30. Consider the following method. /** Removes all occurrences of nameToRemove from nameList . * @param nameList a list of names * @param nameToRemove a name to be removed from nameList */ public void removeName(List nameList, String nameToRemove) { /* missing implementation */ } Which of the following can be used to replace /* missing implementation */ so that removeName will work as intended? I. for (String name : nameList) { if (name.equals(nameToRemove)) name.remove(); } II. for (int k = 0; k < nameList.size(); k++) { if (nameList.get(k).equals(nameToRemove)) nameList.remove(k); } III. for (int k = nameList.size() - 1; k >= 0; k--) { if (nameList.get(k).equals(nameToRemove)) nameList.remove(k); } (A) I only (B) II only (C) III only (D) II and III only (E) I, II, and III -29-
GO ON TO THE NEXT PAGE. 31. Assume that an inorder traversal of a particular binary tree of letters produces the following output. T C L S O N A D A preorder traversal of the same binary tree produces the following output. S C T L O A N D Which of the following letters is in the right child of the root of the tree? (A) A (B) L (C) N (D) O (E) S -30-
GO ON TO THE NEXT PAGE. 32. Consider the following method. /** @param nums a reference to a linked list of Integer objects * Precondition: nums is not null * @return the sum of all values in nums */ public int sum(ListNode nums) { if (nums.getNext() == null) return 0; else return ((Integer) nums.getValue()).intValue() + sum(nums.ge\ tNext()); } For which of the following lists will the call sum(values) return the correct total of all the values in the list values ? I. II. III. (A) I only (B) I and II only (C) I and III only (D) II and III only (E) I, II, and III -31-
GO ON TO THE NEXT PAGE. 33. Assume that the map instantiated below is used to organize information about employees such that the employee number is the key and the employee name is the associated value. Map empMap = new TreeMap(); Which of the following code segments will correctly print the employee number and name of each employee? I. for (String key : empMap.keySet()) { System.out.println(key + " " + empMap.get(key)); } II. Set keys = empMap.keySet(); Iterator itr = keys.iterator(); while (itr.hasNext()) { System.out.println(keys + " " + itr.next()); } III. Set keys = empMap.keySet(); Iterator itr = keys.iterator(); while (itr.hasNext()) { System.out.println(itr.next() + " " + empMap.get(itr.next()))\ ; } (A) I only (B) II only (C) III only (D) I and II (E) I and III -32-
GO ON TO THE NEXT PAGE. 34. Assume that the boolean variables a and b have been declared and initialized. Consider the following expression. (a && (b || !a)) == a && b Which of the following best describes the conditions under which the expression will evaluate to true? (A) Only when a is true (B) Only when b is true (C) Only when both a and b are true (D) The expression will never evaluate to true. (E) The expression will always evaluate to true. 35. When a mergesort is used to sort 5,000 items on a particular computer, the code executes for 45 time units. Approximately how long would the mergesort on the computer take to sort 20,000 items? (A) 90 time units (B) 150 time units (C) 220 time units (D) 500 time units (E) 720 time units -33-
GO ON TO THE NEXT PAGE. 36. The following letters are inserted into an empty binary search tree in the following order. T R U L Y B A S I C Which of the following will be printed by a preorder traversal of the tree? (A) A B C I L R S T U Y (B) A C I B L S R Y U T (C) T R L B A I C S U Y (D) T R U L S Y B A I C (E) Y U S C I A B L R T 37. Assume that variables firstList and secondList of type ListNode have been initialized to refer to the following lists of Integer objects. Consider the following code segment. firstList.getNext().setNext(secondList.getNext()); secondList.setNext(firstList.getNext()); firstList.setNext(secondList); secondList = null; Which of the following represents the list referenced by firstList as a result of executing the code segment? (A) (B) (C) (D) (E) -34-
GO ON TO THE NEXT PAGE. 38. Consider the following code segment. PriorityQueue pq = new PriorityQueue(); pq.add("to"); pq.add("be"); pq.add("or"); pq.add("not"); pq.add("to"); pq.add("be"); while (!pq.isEmpty()) { System.out.print(pq.remove() + " "); } What is printed as a result of executing the code segment? (A) to to or not be be (B) to be or not to be (C) be to not or be to (D) be not or to (E) be be not or to to -35-
GO ON TO THE NEXT PAGE. 39. Consider the following method. public int computeSum(int num) { int sum = 0; int delta = 2; while (delta < 2 * num) { for (int k = delta / 2; k
40. Consider the following code segment. Set cities = new TreeSet(); String[] stringArray = {"Philadelphia", "Minneapolis", "Houston"}; for (String str : stringArray) { cities.add(str); } String[] stringArray2 = {"Philadelphia", "Chicago"}; for (String str : stringArray2) { cities.remove(str); } String[] stringArray3 = {"Des Moines", "Houston"}; for (String str : stringArray3) { cities.add(str); } System.out.println(cities); What is printed as a result of executing the code segment? (A) [Chicago, Des Moines, Houston, Minneapolis, Philadelphia] (B) [Des Moines, Houston, Houston, Minneapolis] (C) [Des Moines, Houston, Houston, Minneapolis, Philadelphia] (D) [Des Moines, Houston, Minneapolis] (E) [Houston, Minneapolis, Philadelphia] END OF SECTION I IF YOU FINISH BEFORE TIME IS CALLED, YOU MAY CHECK YOUR WORK ON THIS SECTION. DO NOT GO ON TO SECTION II UNTIL YOU ARE TOLD TO DO SO. -37-
Section II Free-Response Questions -38-
GO ON TO THE NEXT PAGE. COMPUTER SCIENCE AB SECTION II Time — 1 hour and 45 minutes Number of questions — 4 Percent of total grade — 50 Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA. Notes : • Assume that the classes listed in the Quick Refe rence found in the Appendix have been imported where appropriate. • The java.util.Stack and java.util.PriorityQueue classes and the java.util.Queue interface (page A2 in the Appendix) each inherit methods that access elements in a way that violates their abstract data structure definitions. Solutions that use objects of types Stack, Queue , and PriorityQueue should use only the methods listed in the Appendix for accessing and modifying those objects. The use of other methods may not receive full credit. • Assume that the implementation classes ListNode and TreeNode (page A4 in the Appendix) are used for any questions referring to linked lists or trees, unless otherwise specified. • ListNode and TreeNode parameters may be null. Otherwise, unless 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 may not receive full credit. • When Big-Oh running time is required for a response, you must use the most restrictive Big-Oh expression. For example, if the running time is () On , a response of 2() On will not be given credit. -39-
GO ON TO THE NEXT PAGE. 1. The class Gradebook is used by a teacher to record and process student scores. One of the instance variables in the Gradebook class is a map that associates each student name with a score. You will implement two methods of the Gradebook class. public class Gradebook { private Map scores; // key is student name, value is score /** @return a map that is the inverse of the scores map. In the returned map, each key * is a score, and the associated value is a Set containing the names of those * students who earned that score. */ private Map inverseMap() { /* to be implemented in part (a) */ } /** Precondition : scores.size() > 0 * @return a set of students who earned the mode score. The mode score is the score earned * by the largest number of students. If there is more than one score tied for the * mode, any one of those scores can be chosen as the mode. */ public Set modeSet() { /* to be implemented in part (b) */ } // There may be instance variables, constructors, and methods that are not shown. } -40-
GO ON TO THE NEXT PAGE. (a) Write the Gradebook method inverseMap , which returns a map that is the inverse of the scores map. Each score from the original map becomes a key in the inverse map. In the inverse map, the value associated with a score is a Set containing the names of the students who received that score. Complete method inverseMap below. /** @return a map that is the inverse of the scores map. In the returned map, each key * is a score, and the associated value is a Set containing the names of those * students who earned that score. */ private Map inverseMap() (b) Write the Gradebook method modeSet , which returns the Set of students who received the mode score. The mode score is the score received by the largest number of students. If there is more than one score tied for the mode, any one of those scores can be chosen as the mode. In writing modeSet , you may assume that inverseMap works as specified, regardless of what you wrote in part (a). Complete method modeSet below. /** Precondition : scores.size() > 0 * @return a set of students who earned the mode score. The mode score is the score earned * by the largest number of students. If there is more than one score tied for the * mode, any one of those scores can be chosen as the mode. */ public Set modeSet() -41-
GO ON TO THE NEXT PAGE. 2. A bag is a generalization of the Set container. A Set contains at most one occurrence of a particular element, whereas a Bag can contain any number of occurrences of each element. The following declaration specifies the interface for a StringBag , a bag that holds elements of type String . In part (a) of this question, you will analyze a particular implementation of the StringBag interface. In part (b) of this question, you will write an implementation of the StringBag interface that must satisfy certain performance specifications. public interface StringBag { /** Adds element into this StringBag */ public void add(String element); /** @return an array of the unique elements from this StringBag , arranged in sorted order */ public String[] getUniqueElements(); /** @return the number of times that element has been added into this StringBag */ public int getNumOccurrences(String element); } (a) One implementation of the StringBag interface uses an ArrayList to hold the elements that have been added into the bag. Each unique String value will appear only once and a count is maintained for the number of times that the String has been added into the bag. Information about the elements in this implementation of the StringBag interface will be represented by objects of the Entry class, as shown below. public class Entry { private String element; private int count; public Entry(String str) { element = str; count = 1; } public String getElement() { return element; } public int getCount() { return count; } public void increment() { count++; } } -42-
GO ON TO THE NEXT PAGE. The class ListStringBag below correctly implements the StringBag interface. public class ListStringBag implements StringBag { private ArrayList entries; public ListStringBag() { entries = new ArrayList(); } /** Adds element into this StringBag */ public void add(String element) { for (Entry cur : entries) { if (cur.getElement().equals(element)) { cur.increment(); return; } } entries.add(new Entry(element)); } /** @return an array of the unique elements from this StringBag , arranged in sorted order */ public String[] getUniqueElements() { String[] result = new String[entries.size()]; for (int k = 0; k < entries.size(); k++) result[k] = entries.get(k).getElement(); sortArray(result); return result; } -43-
GO ON TO THE NEXT PAGE. /** Uses a Mergesort algorithm to sort stringArray in alphabetical order. * Postcondition : stringArray is in sorted order */ private void sortArray(String[] stringArray) { /* implementation not shown */ } /** @return the number of times that element has been added into this StringBag */ public int getNumOccurrences(String element) { for (Entry cur : entries) { if (cur.getElement().equals(element)) return cur.getCount(); } return 0; } } Give the average-case Big-Oh running time for the ListStringBag methods add and getUniqueElements in terms of n , the number of unique elements. Average-case Big-Oh add getUniqueElements (b) A potential client requests an efficient implementation of the StringBag interface that meets the following Big-Oh running time specifications. Average-case Big-Oh add O (log n) getUniqueElements O (n) Write a class FastStringBag that correctly implements the StringBag interface and meets the requested running time specifications outlined in the table. You are not required to use the Entry class in your solution. -44-
GO ON TO THE NEXT PAGE. 3. This question involves reasoning about the code from the GridWorld case study. A copy of the code is provided as part of the exam. A TimidCritter is a Critter that prefers to stay close to its original location within the grid. For the first ten calls to act , a TimidCritter moves in the same manner as an ordinary Critter . In the next ten calls to act , the TimidCritter retraces its movement back to its original location. Retracing means that the critter moves to the locations that it occupied before each of the first ten moves, but in the opposite order. After the ten retracing moves have been completed, the TimidCritter ends up at its original location. The TimidCritter will repeat the cycle indefinitely; that is, it will move normally for ten steps, retrace to its original location in the ten steps that follow, then move again normally for ten steps, and so on. When the TimidCritter is retracing, it will move even if the desired location is occupied. (This will cause the other occupant to be removed from the grid.) Before moving, the TimidCritter processes its neighbors in the same way as a Critter . Write the complete TimidCritter class, including all instance variables, a constructor, and the getMoveLocations and makeMove methods. Do NOT override the act method. Note : The getMoveLocations method has as a postcondition that the state of all actors is unchanged. Be sure not to change the state of your TimidCritter in that method. You may update the state in the makeMove method. -45-
GO ON TO THE NEXT PAGE. 4. A retail store maintains a list of items that it has in stock. The items are represented by objects of the Item class as declared below. public class Item { /** @return the name of this Item */ public String getName() { /* implementation not shown */ } /** @return the price of this Item */ public double getPrice() { /* implementation not shown */ } /** @return true if this Item is in stock; false otherwise */ public boolean isInStock() { /* implementation not shown */ } // There may be instance variables, constructors, and methods that are not shown. } The Inventory class stores Item objects in a linked list that is implemented using the standard ListNode class. Each Item object is stored as the data value in a ListNode object. The Inventory class has an instance variable called front that stores a reference to the first node in the list. An empty list is represented as null . A partial declaration of the Inventory class is as follows. You will implement two methods in the Inventory class. public class Inventory { private ListNode front; // a reference to first node in the list /** Constructs an empty list of items */ public Inventory() { front = null; } /** @param newItem an Item to add to this Inventory */ public void addItem(Item newItem) { /* to be implemented in part (a) */ } /** Removes from this Inventory all items that are not in stock */ public void removeUnavailableItems() { /* to be implemented in part (b) */ } // There may be instance variables, constructors, and methods that are not shown. } -46-
(a) Write the Inventory method addItem . A new node containing the Item is added to the front of the existing list of items. Complete method addItem below. /** @param newItem an Item to add to this Inventory */ public void addItem(Item newItem) (b) Write the Inventory method removeUnavailableItems . The method should remove all nodes from the list that contain items that are not currently in stock. Complete method removeUnavailableItems below. /** Removes from this Inventory all items that are not in stock */ public void removeUnavailableItems() STOP END OF EXAM -47-
. . . . . .