AP CSA — Unit 4: Data Collections

Q1MEDIUM AP MC 4.3 / 4.8 length vs size [1]

Consider the following code segment.考虑以下代码段。

int[] arr = {1, 2, 3, 4};
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println(arr.length + " " + list.size());

What is printed?输出是什么？（注意：数组用 length（字段），ArrayList 用 size()（方法调用）。）

(A) 4 3
(B) 3 3
(C) 4 4
(D) A compile-time error: arrays do not have a length field.编译错误：数组没有 length 字段。

Q2MEDIUM AP MC 4.3 Out-of-Bounds [1]

Consider the following code segment.考虑以下代码段。

int[] vals = {10, 20, 30};
System.out.println(vals[3]);

What is the result of executing the code segment?运行此代码段的结果是什么？（提示：数组有效索引为 0 到 length - 1。）

(A) 0 is printed (the default value).打印 0（默认值）。
(B) 30 is printed (the last element).打印 30（最后一个元素）。
(C) An ArrayIndexOutOfBoundsException is thrown.抛出 ArrayIndexOutOfBoundsException（数组越界 out-of-bounds）。
(D) A compile-time error occurs.出现编译错误。

Q3MEDIUM AP MC 4.4 Enhanced for-loop [1]

Consider the following code segment.考虑以下代码段。

int[] vals = {1, 2, 3, 4};
for (int v : vals) {
  v *= 10;
}
System.out.println(vals[0] + " " + vals[3]);

What is printed?输出是什么？（提示：增强 for 循环 enhanced for-loop 中的循环变量 v 是元素的副本，修改 v 不会影响原数组。）

(A) 10 40
(B) 1 4
(C) 1 40
(D) A compile-time error: cannot reassign the loop variable.编译错误：不能给循环变量重新赋值。

Q4HARD AP MC 4.4 Array aliasing + == on references [1]

Consider the following code segment.考虑以下代码段。

int[] a = {1, 2, 3};
int[] b = a;
b[1] = 99;
int[] c = {1, 99, 3};
System.out.println(a[1] + " " + (a == b) + " " + (a == c));

What is printed?输出是什么？（注意：b = a; 让 a 与 b 成为别名 aliasing；== 比较引用地址，而不是数组内容。）

(A) 1 true false
(B) 99 false false
(C) 99 true true
(D) 99 true false

Q5HARD AP MC 4.9 ArrayList Remove + Shift [1]

Consider the following code segment.考虑以下代码段。

ArrayList<Integer> list = new ArrayList<>();
list.add(20); list.add(20); list.add(30); list.add(40);
for (int i = 0; i < list.size(); i++) {
  if (list.get(i) % 20 == 0) {
    list.remove(i);
  }
}
System.out.println(list);

What is printed?输出是什么？（经典陷阱：在向前遍历时 list.remove(i) 会让后续元素左移一位，导致跳过元素。）

(A) [30]
(B) [20, 30]
(C) []
(D) [20, 20, 30]

Q6HARD AP MC 4.12 2D anti-diagonal sum [1]

Consider the following code segment.考虑以下代码段。

int[][] g = { {1, 2, 3},
              {4, 5, 6},
              {7, 8, 9} };
int sum = 0;
for (int r = 0; r < g.length; r++) {
  for (int c = 0; c < g[r].length; c++) {
    if (r + c == 2) sum += g[r][c];
  }
}
System.out.println(sum);

What is printed?输出是什么？（条件 r + c == 2 选出反对角线 anti-diagonal 上的元素。）

(A) 9
(B) 12
(C) 15
(D) 18

Q7HARD AP MC 4.12 In-place 2D transpose [1]

Consider the following code segment.考虑以下代码段。

public static void transpose(int[][] m) {
  for (int r = 0; r < m.length; r++) {
    for (int c = r + 1; c < m[r].length; c++) {
      int tmp = m[r][c];
      m[r][c] = m[c][r];
      m[c][r] = tmp;
    }
  }
}

// in main:
int[][] g = { {1, 2, 3},
              {4, 5, 6},
              {7, 8, 9} };
transpose(g);
System.out.println(g[0][2] + " " + g[2][0] + " " + g[1][1]);

What is printed?输出是什么？（注意内层循环从 c = r + 1 开始，避免双重交换——这是原地转置 in-place transpose 的关键。）

(A) 3 7 5
(B) 7 3 5
(C) 3 3 5
(D) 6 8 5

Q8HARD AP MC 4.8 ArrayList aliasing through set + add [1]

Consider the following code segment.考虑以下代码段。

ArrayList<Integer> a = new ArrayList<>();
a.add(1); a.add(2); a.add(3);
ArrayList<Integer> b = a;
b.set(0, 99);
b.add(4);
System.out.println(a.size() + " " + a.get(0) + " " + a.get(3));

What is printed?输出是什么？（b = a; 之后两者是别名；通过 b 的 set 与 add 都会影响同一个底层列表。）

(A) 3 1 ?
(B) 3 99 4
(C) 4 1 4
(D) 4 99 4

Q9HARD AP MC 4.14 Linear "Find" — No Break [1]

Consider the following code segment.考虑以下代码段。

int[] arr = {3, 7, 5, 7, 9, 7};
int idx = -1;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 7) {
    idx = i;
  }
}
System.out.println(idx);

What is printed?输出是什么？（提示：循环没有 break，会一直更新到最后一个匹配位置——线性"查找"的"最后一次出现 last occurrence"模式。）

(A) -1
(B) 1
(C) 3
(D) 5

Q10HARD AP MC 4.15 Selection Sort — 2 Passes [1]

A selection sort (ascending) is applied to the array {5, 3, 8, 1, 9, 2}. What is the state of the array after the second complete pass of the outer loop (i.e., after the two smallest elements are placed at indices 0 and 1)?对数组 {5, 3, 8, 1, 9, 2} 进行选择排序（selection sort，升序）。完成外层循环的前两轮后（即最小的两个元素被放到下标 0 和 1 处之后），数组的状态是什么？

(A) {1, 2, 3, 5, 8, 9}
(B) {1, 2, 8, 5, 9, 3}
(C) {1, 3, 8, 5, 9, 2}
(D) {3, 5, 8, 1, 9, 2}

Q11HARD AP MC 4.15 Insertion Sort — 2 Passes [1]

An insertion sort (ascending) is applied to the array {5, 2, 8, 1, 9, 3}. What is the state of the array after the second complete pass of the outer loop (i.e., after the elements at indices 1 and 2 have each been inserted into the sorted prefix)?对数组 {5, 2, 8, 1, 9, 3} 进行插入排序（insertion sort，升序）。完成外层循环的前两轮后（即下标 1 和 2 处的元素分别被插入到已排序的前缀里之后），数组的状态是什么？

(A) {2, 5, 8, 1, 9, 3}
(B) {1, 2, 5, 8, 9, 3}
(C) {2, 5, 8, 9, 1, 3}
(D) {5, 2, 8, 1, 9, 3}

Q12HARD AP MC 4.17 Binary Search Trace [1]

A binary search is performed on the sorted array {2, 5, 7, 12, 18, 23, 31, 42, 56} searching for the value 19. Which element of the array is examined last before the search terminates? (Use mid = (lo + hi) / 2 with integer division.)对已排序数组 {2, 5, 7, 12, 18, 23, 31, 42, 56} 进行二分查找（binary search），目标值为 19。在查找终止之前，数组中最后被检查的元素是哪一个？（使用 mid = (lo + hi) / 2 整数除法。）

(A) 18
(B) 23
(C) 31
(D) 56

Q13HARD AP MC 4.16 Recursion — exponential branching [1]

Consider the following method.考虑以下方法。

public static String mystery(int n) {
  if (n == 0) return "X";
  return mystery(n - 1) + mystery(n - 1);
}

What is the value of mystery(4).length()?mystery(4).length() 的值是多少？（提示：每次递归调用两次 mystery(n - 1)——指数级分支 exponential branching，结果长度为 2^n。）

(A) 4
(B) 8
(C) 16
(D) 32

Q14HARD AP MC 4.16 Recursion — Halving [1]

Consider the following method.考虑以下方法。

public static int g(int n) {
  if (n < 2) return 0;
  return 1 + g(n / 2);
}

What is the value of g(17)?g(17) 的值是多少？（提示：每次递归 n 整除以 2，本质是 ⌊log₂ n⌋ 的计数。）

(A) 3
(B) 4
(C) 5
(D) 17

Q15HARD AP MC 4.4 Array — rebind vs mutate in method [1]

Consider the following code segment.考虑以下代码段。

public static void modify(int[] a) {
  a[0] = 99;
  a = new int[]{100, 200, 300};
  a[0] = 999;
}

// in main:
int[] vals = {1, 2, 3, 4, 5};
modify(vals);
System.out.println(vals[0] + " " + vals[2] + " " + vals.length);

What is printed?输出是什么？（关键：a[0] = 99 是通过引用就地修改 mutate，能被调用方看到；a = new int[]{...} 只是重新绑定 rebind 本地引用，对原数组无影响。）

(A) 1 3 5
(B) 99 3 5
(C) 999 300 3
(D) 100 300 3

FRQ 3HARD DATA ANALYSIS WITH ARRAYLIST 4.8 / 4.9 / 4.10 [5 pts]

This question involves a neighbourhood recycling depot. Each drop-off is represented by a Deposit object recording what material was left and how many kilograms of it. A RecyclingDepot object stores its drop-offs in an ArrayList. You will write one method of the RecyclingDepot class.本题涉及一个社区回收站。每一次投放由一个 Deposit 对象表示，记录所投放的材料类别及其公斤数。RecyclingDepot 对象用一个 ArrayList 保存这些投放记录。你需要编写 RecyclingDepot 类中的一个方法。

public class Deposit
{
    /** Returns the material of this deposit, such as "glass" or "paper". */
    public String getMaterial()
    { /* implementation not shown */ }

    /** Returns the number of kilograms in this deposit; always greater than 0. */
    public int getKilograms()
    { /* implementation not shown */ }
}

public class RecyclingDepot
{
    /** The deposits taken in by this depot. Contains no null elements. */
    private ArrayList<Deposit> deposits;

    /**
     * Removes the light deposits from deposits and returns how many
     * were removed, as described below.
     * Precondition: minKg > 0
     */
    public int removeLightLoads(int minKg)
    { /* to be implemented */ }

    /* There may be instance variables, constructors, and methods
       that are not shown. */
}

public class Deposit
{
    /** 返回本次投放物的材料类别，例如 "glass"（玻璃）或 "paper"（纸张）。 */
    public String getMaterial()
    { /* 实现未给出 */ }

    /** 返回本次投放物的公斤数；该值恒大于 0。 */
    public int getKilograms()
    { /* 实现未给出 */ }
}

public class RecyclingDepot
{
    /** 本回收站已接收的投放物。其中不含 null 元素。 */
    private ArrayList<Deposit> deposits;

    /**
     * 从 deposits 中移除较轻的投放物，并返回被移除的数量，
     * 具体规则见下文。
     * 前置条件 Precondition: minKg > 0
     */
    public int removeLightLoads(int minKg)
    { /* 待实现 */ }

    /* 可能还存在未列出的实例变量、构造方法与方法。 */
}

In the examples below, deposits contains the following five elements, in this order.在下面的例子中，deposits 按此顺序包含以下五个元素。

Index下标	0	1	2	3	4
`getMaterial()getMaterial()`	"glass"	"paper"	"glass"	"metal"	"paper"
`getKilograms()getKilograms()`	12	3	7	20	9

5 pts分 Write the removeLightLoads method. The method removes from deposits every deposit of fewer than minKg kilograms, and returns how many deposits were removed. A deposit of exactly minKg kilograms is not removed. The deposits that remain must be left in their original relative order. If nothing is light enough to remove, the method returns 0 and leaves deposits unchanged.编写 removeLightLoads 方法。该方法从 deposits 中移除所有公斤数小于 minKg 的投放物，并返回被移除的数量。公斤数恰好等于 minKg 的投放物不被移除。保留下来的投放物必须维持其原有的相对顺序。若没有任何投放物足够轻而需被移除，方法返回 0 且 deposits 保持不变。

Call on the original list对原始列表的调用	Returns返回值	Kilograms left in `deposits`, in order调用后 `deposits` 中依次剩下的公斤数
`removeLightLoads(10)`	3	12, 20
`removeLightLoads(9)`	2	12, 20, 9
`removeLightLoads(3)`	0	12, 3, 7, 20, 9
`removeLightLoads(100)`	5	(empty)（空）

The second row is the boundary case: with minKg equal to 9, the 3-kilogram and 7-kilogram deposits go but the 9-kilogram deposit stays, and it stays after the 20-kilogram deposit, where it started.第二行是边界情形：当 minKg 为 9 时，3 公斤与 7 公斤的投放物被移除，而 9 公斤的那件保留下来，并且仍位于 20 公斤那件之后，与其原先的位置一致。

The method must work for a deposits list of any size, including an empty one and a list in which every deposit qualifies for removal.该方法必须能处理任意长度的 deposits 列表，包括空列表，以及所有投放物都应被移除的列表。

Check solution →查看解析 →

FRQ 4HARD 2D ARRAYS 4.11 / 4.12 / 4.13 [6 pts]

This question involves a solar farm. The farm is laid out as rows of panels, and each row’s energy production is recorded once per time slot during the day. You will write one method of the SolarFarm class.本题涉及一座太阳能电站。该电站按行排布光伏板，当天每个时段都会记录一次各行的发电量。你需要编写 SolarFarm 类中的一个方法。

public class SolarFarm
{
    /**
     * output[r][c] is the energy, in whole kilowatt-hours, produced by
     * panel row r during time slot c.
     * The array is rectangular, has at least one row and at least one
     * column, and every entry is greater than or equal to 0.
     * The array need not be square.
     */
    private int[][] output;

    /**
     * Returns the index of the best time slot, as described below.
     */
    public int bestSlot()
    { /* to be implemented */ }

    /* There may be instance variables, constructors, and methods
       that are not shown. */
}

public class SolarFarm
{
    /**
     * output[r][c] 表示第 r 行光伏板在第 c 个时段所发出的电量
     * （单位：整数千瓦时）。
     * 该数组为矩形数组，至少有一行且至少有一列，每个元素均
     * 大于或等于 0。该数组不一定是方阵。
     */
    private int[][] output;

    /**
     * 返回最佳时段的下标，具体规则见下文。
     */
    public int bestSlot()
    { /* 待实现 */ }

    /* 可能还存在未列出的实例变量、构造方法与方法。 */
}

In the examples below, output holds the following values — three panel rows and five time slots.在下面的例子中，output 保存以下数值 — 共三行光伏板、五个时段。

	slot 0时段 0	slot 1时段 1	slot 2时段 2	slot 3时段 3	slot 4时段 4
row 0第 0 行	4	9	2	7	1
row 1第 1 行	3	8	5	6	0
row 2第 2 行	6	1	4	9	2
slot total时段总量	13	18	11	22	3

6 pts分 Write the bestSlot method. The method returns the index of the time slot whose total output, summed down every panel row, is the greatest. If two or more slots tie for the greatest total, the method returns the smallest such index.编写 bestSlot 方法。该方法返回总发电量最大的时段的下标，其中总发电量指该时段沿所有光伏板行求和所得之值。若有两个或多个时段的总量并列最大，则返回其中最小的下标。

For the table above the slot totals are 13, 18, 11, 22, and 3, so bestSlot() returns 3 — the index of the slot, not its total of 22. If the entry 9 in row 2, slot 3 were instead a 5, slots 1 and 3 would both total 18 and bestSlot() would return 1.对于上表，各时段的总量分别为 13、18、11、22、3，因此 bestSlot() 返回 3 — 即时段的下标，而非其总量 22。若把第 2 行第 3 时段的元素 9 改为 5，则时段 1 与时段 3 的总量都是 18，此时 bestSlot() 返回 1。

The method must work for any rectangular output with at least one row and one column, including a single-row array, a single-column array, an array with more rows than columns, and an array with more columns than rows.该方法必须能处理任意至少含一行一列的矩形 output 数组，包括只有一行的数组、只有一列的数组、行数多于列数的数组，以及列数多于行数的数组。

Check solution →查看解析 →

Data Collections数据集合

Multiple Choice选择题（`Multiple Choice`）

Free-Response Questions自由回答题（`Free Response`）

Data Collections数据集合

Multiple Choice选择题（Multiple Choice）

Free-Response Questions自由回答题（Free Response）

Multiple Choice选择题（`Multiple Choice`）

Free-Response Questions自由回答题（`Free Response`）