Array: A Complete Exam Guide | 数组：考点精讲

📚 Array: A Complete Exam Guide | 数组：考点精讲

In IB and OCR Computer Science, an array is a fundamental data structure that stores a fixed-size sequential collection of elements of the same data type. Mastering arrays means understanding how they are declared, indexed, traversed, and used in algorithms. This revision guide covers all essential exam topics, from one-dimensional and two-dimensional arrays to sorting, searching, and common pitfalls, ensuring you are fully prepared for both theoretical questions and practical programming tasks.

在 IB 和 OCR 计算机科学课程中，数组是一种基本的数据结构，用于存储固定大小的、相同数据类型的元素序列。掌握数组意味着理解如何声明、索引、遍历以及在算法中使用它们。本复习指南涵盖所有重要的考点，从一维和二维数组到排序、搜索以及常见易错点，确保你为理论题和实际编程任务做好全面准备。

1. What Is an Array? | 什么是数组？

An array is a collection of elements, each identified by an index or a key. The size of a static array is fixed at declaration and cannot change during execution, whereas dynamic arrays can be resized. Arrays allow direct access to any element using its index in O(1) time, making them extremely efficient for read and write operations when the position is known.

数组是由元素组成的集合，每个元素通过索引或键来标识。静态数组的大小在声明时固定，执行期间不可改变，而动态数组可以调整大小。数组支持通过索引以 O(1) 时间复杂度直接访问任意元素，因此在已知位置时，读写操作非常高效。

In most programming languages, array indices start at 0. For an array A of size n, valid indices run from 0 to n−1. Attempting to access an index outside this range causes an ‘index out of bounds’ error, a classic exam topic.

在大多数编程语言中，数组索引从 0 开始。对于大小为 n 的数组 A，有效索引范围是 0 到 n−1。试图访问该范围之外的索引会导致“索引越界”错误，这是考试中的经典考点。

Memory representation: elements are stored in contiguous memory locations. The address of the i-th element can be calculated as base address + i × element size, which explains the O(1) access.

内存表示：元素存储在连续的存储单元中。第 i 个元素的地址可以通过基地址 + i × 元素大小来计算，这解释了 O(1) 访问的原因。

2. Declaring and Initialising Arrays | 声明和初始化数组

Examiners often test the correct syntax for array declaration and initialisation. For example, in pseudocode used by IB and OCR: DECLARE myArray : ARRAY[1:10] OF INTEGER creates an integer array with indices from 1 to 10. In Python-like syntax, arr = [0] * 10 or arr = [0 for _ in range(10)].

考官常考数组声明和初始化的正确语法。例如，IB 和 OCR 使用的伪代码中：DECLARE myArray : ARRAY[1:10] OF INTEGER 创建一个索引从 1 到 10 的整数数组。在类似 Python 的语法中，arr = [0] * 10 或 arr = [0 for _ in range(10)]。

Default values: in many languages, numeric arrays are initialised to zero, but in pseudocode questions you may need to explicitly set values using a loop. Failing to initialise before use leads to undefined behaviour, a common mistake highlighted in mark schemes.

默认值：在许多语言中，数值数组初始化为零，但在伪代码题目中，你可能需要用循环显式设置值。使用前未初始化会导致未定义行为，这是评分标准中强调的常见错误。

You should also know how to declare 2D arrays, e.g., DECLARE grid : ARRAY[1:3, 1:4] OF REAL. The first dimension is often rows, the second columns.

你还应该知道如何声明二维数组，例如 DECLARE grid : ARRAY[1:3, 1:4] OF REAL。第一维通常是行，第二维是列。

3. One-Dimensional Array Operations | 一维数组操作

Traversing a 1D array is a basic required skill. The standard pattern uses a FOR loop from lower bound to upper bound. You must be comfortable reading and writing such loops for tasks like summing elements, finding maximum/minimum, counting occurrences, and linear search.

遍历一维数组是一项基本要求技能。标准模式是使用从下界到上界的 FOR 循环。你必须能熟练读写此类循环，以完成诸如求和、查找最大/最小值、统计出现次数和线性搜索等任务。

Example: summing all elements. Pseudocode:

示例：求所有元素之和。伪代码：

DECLARE total : INTEGER
total ← 0
FOR i ← 1 TO LENGTH(arr)
total ← total + arr[i]
ENDFOR

Note: the loop boundaries must match the declared index range. Off-by-one errors are frequent, so always check whether your loop uses 0 or 1 as the first index.

注意：循环边界必须与声明的索引范围一致。差一错误非常常见，因此务必检查循环是使用 0 还是 1 作为第一个索引。

Updating elements: you can assign a new value to a specific index, e.g., arr[3] ← 42. Arrays are mutable; the original value is overwritten.

更新元素：可以为特定索引赋新值，例如 arr[3] ← 42。数组是可变的，原值将被覆盖。

4. Two-Dimensional Arrays | 二维数组

A 2D array can be visualised as a table with rows and columns. Accessing an element requires two indices: grid[row, column]. Traversal typically involves nested loops. The outer loop iterates over rows, the inner over columns.

二维数组可以可视化为带有行和列的表格。访问元素需要两个索引：grid[row, column]。遍历通常涉及嵌套循环：外层循环遍历行，内层循环遍历列。

Row-major order: elements are stored row by row in memory. This is the default in most languages and affects performance when iterating. In exams, you may be asked to trace code that accesses elements in a specific order.

行优先顺序：在内存中按行逐行存储元素。这是大多数语言的默认方式，并会影响迭代时的性能。考试中可能要求你追踪按特定顺序访问元素的代码。

Common algorithms: summing all elements of a 2D array, finding the smallest element in each row, or manipulating a matrix (e.g., transposition). Be prepared to write nested loops with correct bounds.

常见算法：对二维数组所有元素求和、找出每行最小元素，或操作矩阵（例如转置）。准备好在考试中写出具有正确边界的嵌套循环。

Example: finding the total of all numbers in a 3×4 grid:

示例：求一个 3×4 网格中所有数字的总和：

total ← 0
FOR row ← 1 TO 3
FOR col ← 1 TO 4
total ← total + grid[row, col]
ENDFOR
ENDFOR

5. Sorting Arrays: Bubble Sort | 数组排序：冒泡排序

Bubble sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. It is often examined because of its straightforward logic and the ability to trace passes.

冒泡排序是一种基于比较的简单算法，它反复遍历列表，比较相邻元素，如果顺序错误就交换它们。因其逻辑直白且易于追踪过程，常出现在考题中。

Pseudocode for bubble sort on an array of size n:

对大小为 n 的数组进行冒泡排序的伪代码：

FOR i ← 1 TO n-1
FOR j ← 1 TO n-i
IF arr[j] > arr[j+1] THEN
temp ← arr[j]
arr[j] ← arr[j+1]
arr[j+1] ← temp
ENDIF
ENDFOR
ENDFOR

Time complexity: O(n²) in worst and average cases. Best case O(n) if optimised with a flag to detect no swaps in a pass. Always mention complexity when discussing sorting algorithms.

时间复杂度：最坏和平均情况 O(n²)。如果使用标志检测某一轮无交换来优化，最佳情况下为 O(n)。讨论排序算法时务必提及复杂度。

6. Sorting Arrays: Insertion Sort | 数组排序：插入排序

Insertion sort builds the sorted array one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the already sorted part. It is efficient for small or nearly sorted data sets.

插入排序通过每次取出下一个未排序元素，并将其插入到已排序部分中的正确位置，逐步构建有序数组。它在数据量小或基本有序时效率很高。

Key steps: start from the second element (index 2 or 1 depending on base). Compare it with predecessors and shift larger elements to the right. Insert the selected element in the vacated position.

关键步骤：从第二个元素开始（取决于起始索引）。将其与前面的元素比较，将较大的元素向右移动。将选中的元素插入空出的位置。

Time complexity: O(n²) worst/avg, O(n) best. Often preferred over bubble sort in practice for small n. Exam questions may ask you to show the state of the array after each pass of insertion sort.

时间复杂度：最坏/平均 O(n²)，最佳 O(n)。在实际应用中，对于小的 n 通常优于冒泡排序。考题可能会要求你展示每次插入排序后数组的状态。

7. Searching Arrays: Linear Search | 数组搜索：线性搜索

Linear search scans elements sequentially until the target is found or the end is reached. It works on unsorted data and is straightforward to implement. Complexity: O(n) time, O(1) space.

线性搜索按顺序扫描元素，直到找到目标或到达末尾。它适用于未排序数据，实现简单。时间复杂度 O(n)，空间复杂度 O(1)。

Pseudocode:

伪代码：

found ← FALSE
FOR i ← 1 TO LENGTH(arr)
IF arr[i] = target THEN
OUTPUT i
found ← TRUE
ENDIF
ENDFOR
IF NOT found THEN OUTPUT “Not found”

In the exam, ensure you handle multiple occurrences if required, and always initialise a flag or index to indicate success or failure.

考试中，如有要求，确保处理多个匹配项，并始终初始化一个标志或索引来表示成功或失败。

8. Searching Arrays: Binary Search | 数组搜索：二分查找

Binary search is an efficient O(log n) algorithm that requires a sorted array. It repeatedly divides the search interval in half by comparing the target to the middle element. If the target is lower, search the left half; if higher, the right half.

二分查找是一种高效的 O(log n) 算法，要求数组已排序。它通过将目标与中间元素比较，反复将搜索区间减半。如果目标较小，搜索左半部分；如果较大，搜索右半部分。

Algorithm steps:

算法步骤：

Set low to first index, high to last index.
While low ≤ high: compute mid = (low + high) DIV 2 (integer division).
If arr[mid] = target, return mid.
If arr[mid] < target, set low = mid + 1.
Else set high = mid – 1.

将 low 设为第一个索引，high 设为最后一个索引。
当 low ≤ high 时：计算 mid = (low + high) DIV 2（整数除法）。
如果 arr[mid] = target，返回 mid。
如果 arr[mid] < target，设 low = mid + 1。
否则设 high = mid – 1。

Binary search is a key exam topic; be prepared to trace the values of low, high, and mid for a given array and target.

二分查找是重要的考点；准备好对给定的数组和目标追踪 low、high 和 mid 的值。

9. Arrays vs. Lists: Static vs. Dynamic Structures | 数组与列表：静态与动态结构

A static array has a fixed size determined at compile time. A dynamic array (or list) can grow and shrink at runtime, typically by allocating a larger block of memory and copying elements. In pseudocode, you may encounter ADTs like List or Python’s list, which abstract resizing.

静态数组在编译时确定固定大小。动态数组（或列表）可以在运行时增长和收缩，通常是通过分配更大的内存块并复制元素。在伪代码中，你可能会遇到诸如 List 或 Python 列表的 ADT，它们抽象了调整大小的过程。

Exam questions often ask you to compare these in terms of memory usage, flexibility, and speed. Static arrays waste memory if not fully used but offer guaranteed constant-time access. Dynamic structures use memory efficiently but occasional resizing incurs O(n) cost.

考题常要求从内存使用、灵活性和速度方面比较这两者。静态数组如果未完全使用会浪费内存，但提供保证的常量时间访问。动态结构高效使用内存，但偶尔调整大小会产生 O(n) 开销。

Indexing: both support O(1) read/write. Insertion/deletion in a dynamic list at the end is amortised O(1); at an arbitrary position, O(n) due to shifting.

索引：两者都支持 O(1) 读/写。在动态列表末尾插入/删除均摊 O(1)；在任意位置则为 O(n)，因为需要移动元素。

10. Common Algorithms Involving Arrays | 涉及数组的常见算法

You may be required to write algorithms for finding the minimum or maximum, computing an average, reversing an array in place, or merging two sorted arrays. These test your ability to manipulate indices and understand loop boundaries.

你可能会被要求编写查找最小值或最大值、计算平均值、原地反转数组或合并两个已排序数组的算法。这些题目考查你操作索引和理解循环边界的能力。

Reversing an array in place: swap the first with the last, second with second-last, and so on, using a temporary variable. Loop until the indices meet in the middle.

原地反转数组：使用临时变量将第一个与最后一个交换，第二个与倒数第二个交换，以此类推。循环直到索引在中间相遇。

Merging two sorted arrays A and B into a new array C: maintain three pointers i, j, k. Compare A[i] and B[j], place the smaller into C[k] and advance the respective pointer. After one array is exhausted, copy the remaining elements.

将两个已排序数组合并到新数组 C：维护三个指针 i、j、k。比较 A[i] 和 B[j]，将较小的放入 C[k] 并推进相应指针。当一个数组用尽后，复制剩余元素。

11. Exam Pitfalls and Common Errors | 考试陷阱与常见错误

Off-by-one errors: looping from 0 to n instead of 0 to n-1, or confusing 1-based and 0-based indexing. Always clarify the declared index range in the question.

差一错误：从 0 循环到 n 而不是 0 到 n-1，或混淆基于 1 和基于 0 的索引。务必明确题目中声明的索引范围。

Failing to initialise variables used as accumulators or counters. In pseudocode, total ← 0 before the loop is essential.

未初始化用作累加器或计数器的变量。在伪代码中，循环前 total ← 0 是必不可少的。

Using incorrect bounds in nested loops for 2D arrays: ensure inner loop bound matches the column count, outer matches row count. Reversing rows and columns can lead to logic errors or index out of bounds.

在二维数组的嵌套循环中使用不正确的边界：确保内循环边界与列数匹配，外循环与行数匹配。颠倒行和列会导致逻辑错误或索引越界。

Assuming array elements are automatically sorted; binary search only works on sorted arrays. The exam may ask “why does binary search fail on this array?” – the answer is because it is not sorted.

误认为数组元素自动排序；二分查找仅适用于已排序数组。考题可能会问“为什么在此数组上二分查找失败？”——答案是因为它未排序。

12. Memory and Performance Considerations | 内存与性能考量

Arrays offer excellent cache performance because of contiguous memory. Accessing elements in sequential order is faster than random access due to cache prefetching. This is sometimes asked in higher-level questions related to Big O and real-world performance.

由于连续内存，数组具有出色的缓存性能。由于缓存预取，按顺序访问元素比随机访问更快。这有时会在涉及大 O 表示法和实际性能的高阶问题中出现。

Static vs dynamic memory allocation: exam questions may ask you to describe what happens in memory when a dynamic array resizes. A new, larger block is allocated, elements are copied, and the old block is freed. This has a cost amortised over many operations.

静态与动态内存分配：考题可能要求你描述动态数组调整大小时内存中发生的情况。会分配一个新的、更大的块，复制元素，释放旧块。这样的开销会均摊到多次操作中。

Space complexity: an array of n elements uses O(n) space. When working with multidimensional arrays, remember that a 2D array of size m×n uses O(m×n) space.

空间复杂度：含 n 个元素的数组使用 O(n) 空间。处理多维数组时，记住大小为 m×n 的二维数组使用 O(m×n) 空间。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Array: A Complete Exam Guide | 数组：考点精讲