Data Structures数据结构

How to use this guide如何使用本指南

Data structures appear in every curriculum mapped here, but with different emphasis. Ontario ICS3U (Grade 11) requires one-dimensional arrays with full CRUD operations; ICS4U (Grade 12) adds 2D arrays and abstract types such as stacks, queues, and dictionaries — those sections carry the Honors flag. Alberta CSE2120 (Intermediate, Grade 11-12) is the dedicated data-structures module, requiring static arrays, dynamic arrays, and records. BC Computer Programming 12 names "Uses of pre-built data structures" — grade-12 only. CSTA 3B-AP-12 (Level 3B, grades 11-12) asks students to compare and contrast fundamental structures. AP CSP Big Idea 3 Topic 3.10 covers lists at the exam level (AAP-2.K). Sections 1–3 (arrays, indexing, list operations) are the floor for all curricula; Sections 4–7 (2D arrays, dictionaries, tuples/sets, choosing) are core for honors/AP-track students and clearly flagged.所有对照大纲均涉及数据结构，但侧重点各有不同。安大略 ICS3U（11 年级）要求对一维数组进行完整的增删改查操作；ICS4U（12 年级）增加了二维数组和栈、队列、字典等抽象类型——这些节标有 Honors 标志。阿尔伯塔 CSE2120（中级，11-12 年级）是专门的数据结构模块，要求掌握静态数组、动态数组和记录。BC Computer Programming 12 命名"预构建数据结构的使用"——仅限 12 年级。CSTA 3B-AP-12（3B 级，11-12 年级）要求学生比较和对比基本结构。AP CSP 大概念 3 主题 3.10 在考试层面涵盖列表（AAP-2.K）。第 1–3 节（数组、索引、列表操作）是所有大纲的基础；第 4–7 节（二维数组、字典、元组/集合、选择）是荣誉/AP 轨道学生的核心内容，并有明确标注。

Once you have located your row, use the two cards below to gauge how quickly you should work through the recommended sections.找到所在行后，用下面两张卡片决定推进速度。

Arrays and Lists数组与列表

# Pseudocode
DECLARE scores AS ARRAY OF 5 INTEGERS
SET scores TO [88, 74, 92, 65, 81]
OUTPUT scores[0]   # first element: 88
OUTPUT scores[4]   # last element: 81

# Python
scores = [88, 74, 92, 65, 81]
print(scores[0])   # 88
print(scores[4])   # 81
print(len(scores)) # 5  — number of elements

Indexing and Traversal索引与遍历

# Pseudocode
SET total TO 0
FOR EACH score IN scores:
    SET total TO total + score
OUTPUT total   # 402

# Python
scores = [82, 74, 91, 68, 87]
total = 0
for score in scores:
    total += score
print(total)   # 402

# Pseudocode
SET max_val TO scores[0]
FOR i FROM 1 TO LENGTH(scores) - 1:
    IF scores[i] > max_val THEN
        SET max_val TO scores[i]
OUTPUT max_val   # 91

# Python
max_val = scores[0]
for i in range(1, len(scores)):
    if scores[i] > max_val:
        max_val = scores[i]
print(max_val)   # 91

List Operations: Append, Insert, Remove列表操作：追加、插入、删除

# Pseudocode
DECLARE cart AS LIST
APPEND "apples" TO cart       # cart = ["apples"]
APPEND "bread" TO cart        # cart = ["apples", "bread"]
INSERT "milk" AT INDEX 1 IN cart  # cart = ["apples", "milk", "bread"]
REMOVE "bread" FROM cart      # cart = ["apples", "milk"]
OUTPUT LENGTH(cart)           # 2

# Python
cart = []
cart.append("apples")         # cart = ["apples"]
cart.append("bread")          # cart = ["apples", "bread"]
cart.insert(1, "milk")        # cart = ["apples", "milk", "bread"]
cart.remove("bread")          # cart = ["apples", "milk"]
print(len(cart))              # 2

2D Arrays and Nested Lists Honors二维数组与嵌套列表 Honors

# Pseudocode
DECLARE grades AS 2D ARRAY [3][3]
SET grades TO [[85, 90, 78],
               [72, 88, 94],
               [91, 67, 83]]
# Access student 0, test 1: grades[0][1]
OUTPUT grades[0][1]   # 90

# Sum all grades
SET total TO 0
FOR row FROM 0 TO 2:
    FOR col FROM 0 TO 2:
        SET total TO total + grades[row][col]
OUTPUT total   # 748

# Python
grades = [[85, 90, 78],
          [72, 88, 94],
          [91, 67, 83]]

print(grades[0][1])   # 90  (student 0, test 1)

total = 0
for row in grades:
    for score in row:
        total += score
print(total)   # 748

Dictionaries and Maps (Key-Value Pairs) Honors字典与映射（键值对） Honors

# Pseudocode
DECLARE grades AS DICTIONARY
SET grades["Alice"] TO 91
SET grades["Bob"] TO 78
OUTPUT grades["Bob"]   # 78
SET grades["Dave"] TO 88
FOR EACH name, score IN grades:
    OUTPUT name, score

# Python
grades = {}
grades["Alice"] = 91
grades["Bob"] = 78
print(grades["Bob"])    # 78
grades["Dave"] = 88
for name, score in grades.items():
    print(name, score)

Tuples and Sets元组与集合

# Tuple — immutable record
point = (3, 7)
print(point[0])   # 3
# point[0] = 5    # ERROR: tuples are immutable!
a, b = 10, 20
a, b = b, a       # swap using tuple unpacking
print(a, b)       # 20 10

# Set — unique elements only
scores = [85, 90, 85, 74, 90, 65]
unique = set(scores)
print(unique)         # {65, 74, 85, 90}
print(85 in unique)   # True
print(100 in unique)  # False

classA = {"Alice", "Bob", "Carol"}
classB = {"Bob", "Dave", "Carol"}
print(classA & classB)   # {"Bob", "Carol"}
print(classA | classB)   # all four
print(classA - classB)   # {"Alice"}

Choosing the Right Data Structure选择合适的数据结构

Exam Strategy and Common Pitfalls考试策略与常见陷阱

Flashcards闪卡

Practice Quiz综合测验

Readiness Checklist准备就绪清单

Tick each item when you can do it cold, without notes, on a first attempt.能在无笔记、首次尝试下完成，再勾选每一项。

• ✓Declare, initialise, and access elements of a 1D array by index; state the last valid index for an array of given length; explain what out-of-bounds means. 🇨🇦 ON ICS3U A1.5-A1.6 / AB CSE2120 1.2.1声明、初始化并通过索引访问一维数组元素；说明给定长度数组的最后有效索引；解释越界的含义。🇨🇦 ON ICS3U A1.5-A1.6 / AB CSE2120 1.2.1
• ✓Write traversal loops for three patterns: sum all elements, find the maximum value, and linear search (return index or −1). 🇺🇸 AP CSP AAP-2.K / 🇨🇦 ON ICS3U A2.3为三种模式编写遍历循环：求所有元素之和、找最大值、线性搜索（返回索引或 −1）。🇺🇸 AP CSP AAP-2.K / 🇨🇦 ON ICS3U A2.3
• ✓Use append(), insert(i, x), remove(value), and pop(index) correctly; predict the state of a list after a sequence of these operations. 🇺🇸 AP CSP AAP-2.K / 🇨🇦 AB CSE2120 1.3.2正确使用 append()、insert(i, x)、remove(value) 和 pop(index)；预测一系列操作后列表的状态。🇺🇸 AP CSP AAP-2.K / 🇨🇦 AB CSE2120 1.3.2
• ✓Access any element of a 2D array using grid[row][col]; write nested loops to traverse all elements; sum all values in a given 2D array. 🇨🇦 ON ICS4U A3.5使用 grid[row][col] 访问二维数组的任意元素；编写嵌套循环遍历所有元素；求给定二维数组中所有值的和。🇨🇦 ON ICS4U A3.5
• ✓Create a Python dict, look up a value by key, add a new key-value pair, and iterate over all pairs using .items(). Explain why dict lookup is faster than list search. 🇨🇦 ON ICS4U C1.1 / AB CSE2120 1.2.1创建 Python 字典，通过键查找值，添加新键值对，并用 .items() 遍历所有对。解释为何字典查找比列表搜索更快。🇨🇦 ON ICS4U C1.1 / AB CSE2120 1.2.1
• ✓Explain what makes a tuple different from a list (immutability); create a set from a list to remove duplicates; use in to test membership in a set; perform union, intersection, and difference on two sets. 🇺🇸 CSTA 3B-AP-12 / 🇨🇦 BC CP12解释元组与列表的区别（不可变性）；从列表创建集合以去重；用 in 测试集合的成员关系；对两个集合执行并集、交集和差集操作。🇺🇸 CSTA 3B-AP-12 / 🇨🇦 BC CP12
• ✓For a given problem, justify which data structure (list, 2D array, dict, set, tuple) is the best fit and explain why, citing ordered/mutable/duplicate properties. 🇺🇸 CSTA 3B-AP-12对于给定问题，说明哪种数据结构（列表、二维数组、字典、集合、元组）最合适并解释原因，引用有序性/可变性/重复性属性。🇺🇸 CSTA 3B-AP-12
• ✓State verbatim CSTA 3B-AP-12 ("Compare and contrast fundamental data structures and their uses") and its Descriptive Statement example list. 🇺🇸 CSTA Level 3B逐字陈述 CSTA 3B-AP-12（"比较和对比基本数据结构及其用途"）及其描述性声明示例列表。🇺🇸 CSTA Level 3B
• ✓Explain the AP CSP pseudocode list notation (1-indexed, APPEND/INSERT/REMOVE/LENGTH) and correctly re-index a Python-indexed answer when translating to AP CSP pseudocode. 🇺🇸 AP CSP AAP-2.K Topic 3.10解释 AP CSP 伪代码列表表示法（从 1 开始索引，APPEND/INSERT/REMOVE/LENGTH），并在翻译为 AP CSP 伪代码时正确重新索引 Python 索引的答案。🇺🇸 AP CSP AAP-2.K 主题 3.10
• ✓Name the Alberta CSE module for data structures (CSE2120) and state its level (Intermediate) and prerequisite (CSE2110). Cite at least one verbatim outcome. 🇨🇦 AB CSE2120说明阿尔伯塔数据结构的 CSE 模块（CSE2120）、其级别（中级）和先修要求（CSE2110）。引用至少一个逐字结果。🇨🇦 AB CSE2120
• ✓Honors — ICS4U / CSE2120 Implement insert and delete at an arbitrary index in a 1D array using a loop (shift elements); write a nested-loop algorithm to find the sum of all elements in a 2D array. 🇨🇦 ON ICS4U A3.3 & A3.5 / AB CSE2120 1.3.2荣誉 — ICS4U / CSE2120 使用循环（移动元素）在一维数组的任意索引处实现插入和删除；编写嵌套循环算法求二维数组所有元素之和。🇨🇦 ON ICS4U A3.3 & A3.5 / AB CSE2120 1.3.2

What This Feeds Into本单元的去向

Data structures are the bridge between introductory programming (variables, loops, functions) and higher-level course work in AP CSA and university CS. Every algorithm you will write at the AP level manipulates one or more of the structures covered in this guide. The feeder link below points to the AP CSA Data Collection guide (ArrayList, arrays) which builds directly on this unit.数据结构是初级编程（变量、循环、函数）与 AP CSA 和大学 CS 高阶课程之间的桥梁。你在 AP 层次编写的每个算法都操作本指南中涵盖的一种或多种结构。以下衔接链接指向 AP CSA 数据收集指南（ArrayList、数组），它直接建立在本单元基础上。