Ethical and Social Issues Around Data Collection

数据收集中的伦理与社会问题

Before diving into data structures, consider the ethical implications of collecting and storing data. Every program that handles personal information must prioritize user privacy.

在深入数据结构之前，先思考收集和存储数据所带来的伦理影响。任何处理个人信息的程序都必须把用户隐私放在首位。

Introduction to Using Data Sets

使用数据集入门

A data set is a collection of specific pieces of information or data. Data sets can be manipulated and analyzed to solve a problem or answer a question.

数据集是一组具体的信息或数据。我们可以对数据集进行操作和分析，以解决问题或回答某个问题。

Array Creation and Access

数组的创建与访问

An array stores multiple values of the same type. The values can be either primitive values or object references. An array's length is established at creation and cannot be changed.

数组（array）存储多个相同类型的值。这些值既可以是基本类型的值，也可以是对象引用。数组的长度（length）在创建时就确定，之后不能改变。

Creating Arrays

创建数组

// Method 1: Using the new keyword// 方法 1：使用 new 关键字
int[] numbers = new int[5];          // {0, 0, 0, 0, 0}
double[] grades = new double[3];     // {0.0, 0.0, 0.0}
boolean[] flags = new boolean[4];   // {false, false, false, false}
String[] names = new String[3];     // {null, null, null}

// Method 2: Using an initializer list// 方法 2：使用初始化列表
int[] primes = {2, 3, 5, 7, 11};
String[] days = {"Mon", "Tue", "Wed"};

Accessing & Modifying Elements

访问与修改元素

int[] arr = {10, 20, 30, 40, 50};

// Access using index (0-based)// 使用索引访问（从 0 开始）
int first = arr[0];     // 10
int last = arr[4];      // 50

// Modify an element// 修改一个元素
arr[2] = 99;             // arr is now {10, 20, 99, 40, 50}// arr 现在是 {10, 20, 99, 40, 50}

// Array length (attribute, not method!)// 数组长度（是字段，不是方法！）
int len = arr.length;   // 5

Array Traversals

数组遍历

Traversing an array means using repetition statements to access all or an ordered sequence of elements.

遍历（traverse）数组是指用循环语句访问数组的所有元素或一段有序的元素。

Indexed for Loop

带索引的 for 循环

int[] arr = {3, 7, 1, 9, 5};
for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i] + " ");
}
// Output: 3 7 1 9 5// 输出：3 7 1 9 5

Enhanced for Loop (for-each)

增强 for 循环（enhanced for loop / for-each）

for (int val : arr) {
    System.out.print(val + " ");
}
// Output: 3 7 1 9 5// 输出：3 7 1 9 5

int[] arr = {1, 2, 3};

// Doesn't work, val is a copy// 不起作用，val 是副本
for (int val : arr) {
    val *= 2;
}
// arr is still {1, 2, 3}// arr 仍是 {1, 2, 3}

// Works, indexed for assigns through the array reference// 有效，带索引的 for 通过数组引用赋值
for (int i = 0; i < arr.length; i++) {
    arr[i] *= 2;
}
// arr is now {2, 4, 6}// arr 现在是 {2, 4, 6}

int[] arr = {1, 2, 3};

// Doesn't work, val is a copy// 不起作用，val 是副本
for (int val : arr) {
    val *= 2;
}
// arr is still {1, 2, 3}// arr 仍是 {1, 2, 3}

// Works, indexed for assigns through the array reference// 有效，带索引的 for 通过数组引用赋值
for (int i = 0; i < arr.length; i++) {
    arr[i] *= 2;
}
// arr is now {2, 4, 6}// arr 现在是 {2, 4, 6}

Implementing Array Algorithms

实现数组算法

Standard algorithms that traverse arrays to accomplish common tasks are fundamental to AP CSA.

通过遍历数组完成常见任务的标准算法，是 AP CSA 的基础内容。

public static int findMax(int[] arr) {
    int max = arr[0];
    for (int val : arr) {
        if (val > max) max = val;
    }
    return max;
}

public static double average(int[] arr) {
    int sum = 0;
    for (int val : arr) {
        sum += val;
    }
    return (double) sum / arr.length;
}

// Count elements greater than a threshold// 统计大于阈值的元素
public static int countAbove(int[] arr, int threshold) {
    int count = 0;
    for (int val : arr) {
        if (val > threshold) count++;
    }
    return count;
}

// Check if ALL elements are positive// 判断是否所有元素都为正
public static boolean allPositive(int[] arr) {
    for (int val : arr) {
        if (val <= 0) return false;
    }
    return true;
}

// Check if ANY element is negative// 判断是否存在负数元素
public static boolean hasNegative(int[] arr) {
    for (int val : arr) {
        if (val < 0) return true;
    }
    return false;
}

// Shift left (first element lost, last becomes 0)// 左移（首元素丢失，末位变为 0）
for (int i = 0; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
}
arr[arr.length - 1] = 0;

// Reverse the array// 反转数组
for (int i = 0; i < arr.length / 2; i++) {
    int temp = arr[i];
    arr[i] = arr[arr.length - 1 - i];
    arr[arr.length - 1 - i] = temp;
}

// Check for duplicates// 检测重复元素
public static boolean hasDuplicates(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

// Access consecutive pairs// 访问相邻元素对
for (int i = 0; i < arr.length - 1; i++) {
    System.out.println(arr[i] + " and " + arr[i + 1]);
}

Using Text Files

使用文本文件

A file provides persistent storage, data survives after the program ends. Java uses the File and Scanner classes to read from text files.

文件提供持久化存储，数据在程序结束后依然保留。Java 使用 File 和 Scanner 类来读取文本文件。

Reading from a File

从文件读取内容

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public static void readFile() throws IOException {
    File f = new File("data.txt");
    Scanner sc = new Scanner(f);

    while (sc.hasNext()) {
        String line = sc.nextLine();
        System.out.println(line);
    }
    sc.close();
}

The split() Method

split() 方法

String line = "Alice,90,85,92";
String[] parts = line.split(",");
// parts = {"Alice", "90", "85", "92"}// parts = {"Alice", "90", "85", "92"}

Wrapper Classes

包装类（wrapper class）

The Integer and Double classes wrap primitive types into objects. Both are immutable, once created, their values cannot change.

Integer 和 Double 类把基本类型包装成对象。它们都是不可变的——一旦创建，值就不能再改变。

Autoboxing & Unboxing

自动装箱（autoboxing）与拆箱（unboxing）

// Autoboxing: primitive → wrapper object// 自动装箱：基本类型 → 包装对象
Integer x = 5;          // int → Integer// int → Integer
Double y = 3.14;        // double → Double// double → Double

// Unboxing: wrapper object → primitive// 拆箱：包装对象 → 基本类型
int a = x;              // Integer → int// Integer → int
double b = y;           // Double → double// Double → double

Parsing Strings to Numbers

把字符串解析成数字

int num = Integer.parseInt("42");       // "42" → 42// "42" → 42
double d = Double.parseDouble("3.14"); // "3.14" → 3.14// "3.14" → 3.14

ArrayList Methods

ArrayList 的方法

An ArrayList is a mutable-size collection that stores object references. Unlike arrays, it can grow and shrink dynamically.

ArrayList 是一种大小可变的集合，用来存储对象引用。与数组不同，它可以动态地增大或缩小。

Creating an ArrayList

创建 ArrayList

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<String>();
ArrayList<Integer> nums = new ArrayList<Integer>();

ArrayList<String> list = new ArrayList<String>();
list.add("A");          // ["A"]
list.add("B");          // ["A", "B"]
list.add(1, "X");      // ["A", "X", "B"]
list.set(0, "Z");      // ["Z", "X", "B"]
list.remove(1);        // ["Z", "B"]
String s = list.get(0); // "Z"
int sz = list.size();   // 2

ArrayList Traversals

ArrayList 遍历

Traversing an ArrayList works similarly to arrays but with critical pitfalls when modifying the list during traversal.

遍历 ArrayList 的方式与遍历数组类似，但在遍历过程中修改列表时存在严重的坑。

// Indexed for loop// 带索引的 for 循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Enhanced for loop// 增强 for 循环
for (String s : list) {
    System.out.println(s);
}

Safe Removal During Traversal

遍历过程中的安全删除

// Method 1: Traverse backward// 方法 1：倒序遍历
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("remove me")) {
        list.remove(i);
    }
}

// Method 2: Decrement index after removal// 方法 2：删除后将索引减一
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("remove me")) {
        list.remove(i);
        i--;  // adjust to not skip next element// 调整以免跳过下一个元素
    }
}

Implementing ArrayList Algorithms

实现 ArrayList 算法

The same standard algorithms from arrays apply to ArrayLists, plus the ability to insert and delete elements. Some algorithms require traversing multiple String, array, or ArrayList objects simultaneously.

数组上的那套标准算法同样适用于 ArrayList，并且还可以插入和删除元素。有些算法需要同时遍历多个 String、数组或 ArrayList 对象。

// Remove all even numbers (traverse backward)// 删除所有偶数（倒序遍历）
for (int i = nums.size() - 1; i >= 0; i--) {
    if (nums.get(i) % 2 == 0) {
        nums.remove(i);
    }
}

// Insert separator between consecutive duplicates// 在相邻重复元素之间插入分隔符
for (int i = 0; i < list.size() - 1; i++) {
    if (list.get(i).equals(list.get(i + 1))) {
        list.add(i + 1, "---");
        i++;  // skip the inserted element// 跳过刚插入的元素
    }
}

2D Array Creation and Access

二维数组的创建与访问

A 2D array is stored as an array of arrays, essentially a table with rows and columns. Its size is fixed at creation.

二维数组本质上是数组的数组，相当于一张带行列的表格。它的大小在创建时就已固定。

Creating 2D Arrays

创建二维数组

// Using new (3 rows, 4 columns, all zeros)// 使用 new（3 行 4 列，全为 0）
int[][] grid = new int[3][4];

// Using initializer list// 使用初始化列表
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6}
};  // 2 rows, 3 columns// 2 行 3 列

Accessing Elements

访问元素

int val = matrix[1][2];   // row 1, col 2 → 6// 第 1 行第 2 列 → 6
matrix[0][0] = 99;       // set top-left to 99// 将左上角设为 99

// Dimensions// 维度
int rows = matrix.length;       // 2
int cols = matrix[0].length;   // 3

// Access a single row (it's a 1D array)// 访问单独一行（它本身就是一维数组）
int[] firstRow = matrix[0];     // {99, 2, 3}

2D Array Traversals

二维数组的遍历

2D arrays require nested loops to traverse all elements. Two common orderings are row-major and column-major.

二维数组需要用嵌套循环才能遍历所有元素。常见的两种遍历顺序是行优先（row-major）和列优先（column-major）。

Row-Major Order

行优先顺序

for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length; c++) {
        System.out.print(grid[r][c] + " ");
    }
    System.out.println();
}

Column-Major Order

列优先顺序

for (int c = 0; c < grid[0].length; c++) {
    for (int r = 0; r < grid.length; r++) {
        System.out.print(grid[r][c] + " ");
    }
}

Enhanced for Loop with 2D Arrays

二维数组中的增强 for 循环

for (int[] row : grid) {         // outer: each row (1D array)// 外层：每一行（一维数组）
    for (int val : row) {        // inner: each element// 内层：每一个元素
        System.out.print(val + " ");
    }
}

int[][] g = {
    {1, 2, 3},
    {4, 5, 6}
};

// Row-major prints: 1 2 3 4 5 6// 行优先输出：1 2 3 4 5 6
for (int r = 0; r < g.length; r++)
    for (int c = 0; c < g[0].length; c++)
        System.out.print(g[r][c] + " ");

// Column-major prints: 1 4 2 5 3 6// 列优先输出：1 4 2 5 3 6
for (int c = 0; c < g[0].length; c++)
    for (int r = 0; r < g.length; r++)
        System.out.print(g[r][c] + " ");

int[][] g = {
    {1, 2, 3},
    {4, 5, 6}
};

// Row-major prints: 1 2 3 4 5 6// 行优先输出：1 2 3 4 5 6
for (int r = 0; r < g.length; r++)
    for (int c = 0; c < g[0].length; c++)
        System.out.print(g[r][c] + " ");

// Column-major prints: 1 4 2 5 3 6// 列优先输出：1 4 2 5 3 6
for (int c = 0; c < g[0].length; c++)
    for (int r = 0; r < g.length; r++)
        System.out.print(g[r][c] + " ");

Implementing 2D Array Algorithms

实现二维数组算法

Standard 2D array algorithms extend 1D algorithms to work on the entire grid or specific rows, columns, or subsections.

标准的二维数组算法是把一维算法扩展到整张网格，或者扩展到特定的行、列或子区域上。

// Sum of row r// 第 r 行的和
public static int rowSum(int[][] grid, int r) {
    int sum = 0;
    for (int c = 0; c < grid[r].length; c++)
        sum += grid[r][c];
    return sum;
}

// Sum of column c// 第 c 列的和
public static int colSum(int[][] grid, int c) {
    int sum = 0;
    for (int r = 0; r < grid.length; r++)
        sum += grid[r][c];
    return sum;
}

public static int findMax2D(int[][] grid) {
    int max = grid[0][0];
    for (int[] row : grid) {
        for (int val : row) {
            if (val > max) max = val;
        }
    }
    return max;
}

Searching Algorithms

查找（searching）算法

Linear Search

线性查找（linear search）

Linear search checks each element in order until the target is found or all elements have been checked. Works on both sorted and unsorted data.

线性查找按顺序依次检查每一个元素，直到找到目标或检查完所有元素为止。对有序和无序数据都适用。

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;  // not found// 未找到
}

Linear Search on a 2D Array

在二维数组上的线性查找

public static boolean search2D(int[][] grid, int target) {
    for (int[] row : grid) {
        for (int val : row) {
            if (val == target) return true;
        }
    }
    return false;
}

Sorting Algorithms

排序（sorting）算法

Selection Sort

选择排序

Repeatedly finds the smallest element in the unsorted portion and swaps it into its correct final position.

不断地在未排序部分中找出最小的元素，并将它交换到它最终正确的位置上。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

Insertion Sort

插入排序

Takes each element and inserts it into its correct (but not necessarily final) position in the sorted portion by shifting elements.

取出每个元素，通过移动其他元素，把它插入到已排序部分中正确的位置（但不一定是最终位置）。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Start: [5, 2, 4, 6, 1, 3]

Selection sort, after pass 1: [1, 2, 4, 6, 5, 3]
  ↳ Position 0 holds the global minimum, FINAL position.

Insertion sort, after pass 1: [2, 5, 4, 6, 1, 3]
  ↳ The first two elements are sorted, but 5 is NOT in its final position.
    The 1 and 3 still to come will push it right.

起始: [5, 2, 4, 6, 1, 3]

选择排序，第 1 轮后: [1, 2, 4, 6, 5, 3]
  ↳ 位置 0 已放上全局最小值，处于最终位置。

插入排序，第 1 轮后: [2, 5, 4, 6, 1, 3]
  ↳ 前两个元素已经有序，但 5 还不在它的最终位置。
    后面还会出现的 1 和 3 会把它向右挤。

Recursion

递归（recursion）

A recursive method is a method that calls itself. Every recursive method needs at least one base case (stops the recursion) and at least one recursive call.

递归方法是会调用自身的方法。每个递归方法都至少需要一个基线条件（base case，用来终止递归）和至少一次递归调用（recursive case）。

public static int factorial(int n) {
    if (n == 0)          // base case// 基线条件
        return 1;
    return n * factorial(n - 1);  // recursive call// 递归调用
}
// factorial(4) → 4 * 3 * 2 * 1 * 1 = 24// factorial(4) → 4 * 3 * 2 * 1 * 1 = 24

public static String mystery(int n) {
    if (n <= 0) return "";
    return mystery(n - 1) + n + " ";
}
// mystery(3) returns what?// mystery(3) 返回什么？

mystery(3)
= mystery(2) + 3 + " "
= (mystery(1) + 2 + " ") + 3 + " "
= ((mystery(0) + 1 + " ") + 2 + " ") + 3 + " "
= (("" + 1 + " ") + 2 + " ") + 3 + " "
= ("1 " + 2 + " ") + 3 + " "
= "1 2 " + 3 + " "
= "1 2 3 "

public static String mystery(int n) {
    if (n <= 0) return "";
    return mystery(n - 1) + n + " ";
}
// mystery(3) returns what?// mystery(3) 返回什么？

mystery(3)
= mystery(2) + 3 + " "
= (mystery(1) + 2 + " ") + 3 + " "
= ((mystery(0) + 1 + " ") + 2 + " ") + 3 + " "
= (("" + 1 + " ") + 2 + " ") + 3 + " "
= ("1 " + 2 + " ") + 3 + " "
= "1 2 " + 3 + " "
= "1 2 3 "

Recursive Searching and Sorting

递归查找与排序

Binary Search

二分查找（binary search）

Binary search requires data to be sorted. It starts at the middle and eliminates half of the remaining elements each step.

二分查找要求数据必须有序。它从中间开始，每一步都把剩下的元素排除掉一半。

public static int binarySearch(int[] arr, int lo, int hi, int target) {
    if (lo > hi) return -1;  // base case: not found// 基线条件：未找到
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearch(arr, mid + 1, hi, target);
    else
        return binarySearch(arr, lo, mid - 1, target);
}

Merge Sort

归并排序

Merge sort is a recursive sorting algorithm that divides the array in half, sorts each half, then merges the sorted halves together.

归并排序是一种递归的排序算法：把数组对半分开，分别对两半进行排序，然后再把已排序的两半合并起来。

// Trace: merge sort on [38, 27, 43, 3]// 追踪：对 [38, 27, 43, 3] 进行归并排序
// Split: [38, 27] and [43, 3]// 分解：[38, 27] 和 [43, 3]
// Split: [38] [27]    [43] [3]// 分解：[38] [27]    [43] [3]
// Merge: [27, 38]     [3, 43]// 合并：[27, 38]     [3, 43]
// Merge: [3, 27, 38, 43]// 合并：[3, 27, 38, 43]

Unit 4 MCQ Patterns That Show Up Every Year

单元 4 每年都会出现的选择题套路

Unit 4 carries the most weight on the AP CSA MCQ section. The questions cluster around a handful of operational pitfalls. Knowing the pattern usually beats tracing the whole snippet.

单元 4 在 AP CSA 选择题中占比最大。题目集中考查几类操作上的陷阱。摸清套路往往比从头追踪整段代码更高效。

Flashcards

闪卡

Click each card to flip and reveal the answer.

点击每张卡片翻面查看答案。

Unit 4, Practice Quiz

单元 4 · 练习小测

AP-Style Practice Problems

AP 风格练习题