📚 Mastering A-Level Programming: Constructs, Data Structures and Algorithms | 掌握 A-Level 编程：结构、数据结构与算法
For Edexcel A-Level Computer Science, programming is not just about writing code; it is about using computational thinking to design, trace, compare, and evaluate algorithms. The specification expects you to read and write pseudocode, understand standard data structures, apply searching and sorting algorithms, and discuss programming paradigms with precision.
对 Edexcel A-Level 计算机科学而言，编程不只是写代码，而是运用计算思维设计、跟踪、比较和评估算法。大纲要求你能够阅读和编写伪代码，理解标准数据结构，应用查找与排序算法，并准确讨论编程范式。
This guide works through every strand of the programming topic in order: the three fundamental constructs, pseudocode conventions, data types, subprograms, static and dynamic data structures, searching, sorting, efficiency, paradigms, and finally the exam skills of tracing and evaluation. Each section pairs the English terminology you must use in the exam with a Chinese explanation so that you can revise in either language.
本文按顺序梳理编程主题的每一条主线：三种基本结构、伪代码规范、数据类型、子程序、静态与动态数据结构、查找、排序、效率、编程范式，最后是跟踪与评估这类考试技能。每个小节都把考试必须使用的英文术语与中文讲解配对呈现，方便你用任意一种语言复习。
1. Programming Constructs | 编程基本结构
All structured programs are built from three fundamental constructs: sequence, selection, and iteration. Sequence means statements execute one after another in order. Selection allows a program to choose between alternative paths using IF, ELSE IF, ELSE, or multi-way SELECT/CASE statements.
所有结构化程序都由三种基本结构组成：顺序、选择和迭代。顺序表示语句按先后依次执行。选择允许程序使用 IF、ELSE IF、ELSE 或多分支 SELECT/CASE 语句在不同路径之间做出选择。
Iteration repeats a block of code. Count-controlled loops such as FOR run a definite number of times, while condition-controlled loops such as WHILE and REPEAT...UNTIL run until a Boolean condition changes. Edexcel pseudocode often asks you to trace these loops or convert between them.
迭代会重复执行一段代码。计数控制循环（如 FOR）以确定的次数运行，而条件控制循环（如 WHILE 和 REPEAT...UNTIL）会一直执行到布尔条件发生变化。Edexcel 伪代码题经常要求你跟踪这些循环或在它们之间进行转换。
The key distinction between WHILE and REPEAT...UNTIL is test position. WHILE tests the condition before the body executes, so the body may run zero times. REPEAT...UNTIL tests after the body, so the body always runs at least once. Also note that REPEAT...UNTIL terminates when the condition becomes TRUE, which is the opposite of WHILE.
WHILE 与 REPEAT...UNTIL 的关键区别在于判断位置。WHILE 在执行循环体之前判断条件，因此循环体可能一次都不执行；REPEAT...UNTIL 在执行之后判断，因此循环体至少执行一次。还要注意 REPEAT...UNTIL 在条件变为 TRUE 时结束，与 WHILE 正好相反。
- Sequence | 顺序: statements execute in the written order, one at a time.
- Selection | 选择: IF...THEN...ELSE, nested IF, and SELECT CASE for multi-way branching.
- Iteration | 迭代: FOR (definite), WHILE (indefinite, pre-tested), REPEAT...UNTIL (indefinite, post-tested).
- Nesting | 嵌套: any construct may contain any other, but indentation must make the structure explicit.
2. Pseudocode Conventions and Program Design | 伪代码规范与程序设计
rogramming language in the written papers; it requires consistent pseudocode. Assignment is normally written with an arrow, for example x ← y and <> for inequality. Comments are written with // and indentation shows the block structure.
Edexcel 笔试并不要求使用特定编程语言，而是要求一致的伪代码。赋值通常用箭头表示，例如 x ← 10；比较中 = 表示相等，<> 表示不等。注释用 // 书写，缩进则体现程序块结构。
Before writing any code, design it. Structure (hierarchy) diagrams break a problem into modules and show which module calls which. Flowcharts show control flow with standard symbols: a parallelogram for input/output, a rectangle for a process, and a diamond for a decision. Top-down design and stepwise refinement take a large problem and split it into smaller, testable subproblems.
在写任何代码之前要先做设计。结构（层次）图把问题拆解为模块，并显示模块之间的调用关系。流程图用标准符号表示控制流：平行四边形表示输入/输出，矩形表示处理，菱形表示判断。自顶向下设计和逐步求精把一个大问题拆解成更小、可测试的子问题。
You should also be able to describe the purpose of a piece of given pseudocode, identify its inputs, processes and outputs, and suggest test data. Test data should include normal, boundary and erroneous (invalid) values, plus the expected outcome of each test.
你还应能描述给定伪代码的功能，识别其输入、处理和输出，并提出测试数据。测试数据应包含正常值、边界值和错误（无效）值，并写明每个测试的预期结果。
3. Variables, Constants and Data Types | 变量、常量与数据类型
A variable is a named store whose value may change while the program runs; a constant is a named value that cannot change once defined. Using constants improves readability and makes maintenance easier, because a single change updates every use of the value.
变量是程序运行期间其值可以改变的命名存储单元；常量是定义后不能改变的命名值。使用常量可以提高可读性并便于维护，因为只改一处就能更新该值的所有引用。
You must know the standard data types and when each is appropriate. Choosing the wrong type wastes memory or causes logic errors, for example storing a phone number as an integer loses the leading zero.
你必须掌握标准数据类型及其适用场景。选错类型会浪费内存或造成逻辑错误，例如把电话号码存为整数会丢失前导零。
| Data type | 数据类型 | Description | 说明 | Example | 示例 |
| Integer | 整数 | Whole numbers, positive or negative | 正负整数 | 42, −7 |
| Real / Float | 实数 | Numbers with a fractional part | 含小数部分的数 | 3.14 |
| Boolean | 布尔型 | TRUE or FALSE only | 只有真或假 | TRUE |
| Char | 字符 | A single character | 单个字符 | 'A' |
| String | 字符串 | A sequence of characters | 字符序列 | "Hao" |
| Date / Time | 日期时间 | Stored in a fixed internal format | 以固定内部格式存储 | 2024-05-01 |
Casting converts a value from one type to another, for example converting a string input into an integer before arithmetic. Scope describes where a variable can be seen: local variables exist only inside a subprogram, while global variables are accessible throughout the program and are generally discouraged because they make programs harder to debug.
类型转换把值从一种类型变为另一种，例如在做算术运算前把字符串输入转换为整数。作用域描述变量在何处可见：局部变量只存在于某个子程序内部，全局变量在整个程序中可访问，但通常不推荐使用，因为它会增加调试难度。
4. Subprograms: Procedures and Functions | 子程序：过程与函数
A procedure performs a task and returns no value; a function performs a task and returns a single value. Both accept parameters, which are passed either by value or by reference. Passing by value copies the data, so changes inside the subprogram do not affect the original. Passing by reference passes the address, so changes do affect the original variable.
过程执行一项任务但不返回值；函数执行任务并返回一个值。两者都可接收参数，参数可以按值传递或按引用传递。按值传递复制数据，因此子程序内部的修改不影响原变量；按引用传递的是地址，因此修改会影响原变量。
Splitting a program into subprograms supports decomposition, makes code reusable, shortens the main routine, and allows individual modules to be tested in isolation. In the exam, when asked why a subprogram is used, always link the benefit to the specific scenario rather than giving a generic list.
把程序拆分为子程序有助于分解问题、提高代码复用性、缩短主程序，并使各模块可以单独测试。考试中被问到"为什么要用子程序"时，一定要把好处与题目情境联系起来，而不是泛泛罗列。
Recursion is a subprogram that calls itself, and it must have a base case that stops the recursion, otherwise a stack overflow occurs. Classic examples are factorial, Fibonacci and binary search. Any recursive algorithm can be rewritten iteratively, and iteration is usually more memory-efficient because it does not add a stack frame per call.
递归是子程序调用自身，必须有一个基准情形来终止递归，否则会发生栈溢出。经典例子有阶乘、斐波那契和二分查找。任何递归算法都可以改写为迭代形式，迭代通常更节省内存，因为它不会为每次调用增加一个栈帧。
factorial(n) = n × factorial(n − 1), with factorial(0) = 1
5. Arrays, Records and Lists | 数组、记录与列表
An array is a set of data items of the same type stored under one identifier and accessed by index. A one-dimensional array is a single list; a two-dimensional array is a table of rows and columns, accessed as array[row, column]. Arrays are static: their size is fixed when declared, which makes access fast (O(1)) but wastes space if the array is not full.
数组是同一类型数据项的集合，使用一个标识符存储并通过下标访问。一维数组是单个列表；二维数组是行列构成的表格，写作 array[row, column]。数组是静态的：声明时长度固定，因此访问很快（O(1)），但若未填满则会浪费空间。
A record groups related fields of different data types into one structure, for example a Student record containing Name (string), Age (integer) and Passed (Boolean). Records model real-world entities and are usually stored inside an array of records.
记录把不同数据类型的相关字段组合成一个结构，例如包含 Name（字符串）、Age（整数）和 Passed（布尔）的 Student 记录。记录能够对现实世界实体建模，通常存放在记录数组中。
A list (or linked list) is dynamic: each node stores a value and a pointer to the next node. Insertion and deletion are efficient because only pointers change, but access is sequential, so finding the nth item is O(n). You should be able to compare the two structures directly.
链表是动态结构：每个节点存储一个值以及指向下一节点的指针。插入和删除效率高，因为只需修改指针；但访问是顺序的，因此查找第 n 项是 O(n)。你应该能够直接比较这两种结构。
- Array | 数组: fixed size, direct index access, O(1) read, inefficient insertion in the middle.
- Record | 记录: heterogeneous fields, models an entity, accessed by field name.
- Linked list | 链表: dynamic size, O(1) insert at a known position, O(n) search.
6. Stacks and Queues | 栈与队列
A stack is a last-in-first-out (LIFO) structure. Items are added with push and removed with pop, and both operations happen at the top of the stack. A peek operation reads the top item without removing it. Stacks are used for function call management, undo facilities, expression evaluation and depth-first traversal.
栈是后进先出（LIFO）结构。元素通过 push 加入、通过 pop 移除，两个操作都发生在栈顶。peek 操作读取栈顶元素但不移除。栈应用于函数调用管理、撤销功能、表达式求值和深度优先遍历。
A queue is a first-in-first-out (FIFO) structure. Items are added with enqueue at the rear and removed with dequeue from the front. Queues are used for print spooling, keyboard buffers, task scheduling and breadth-first traversal.
队列是先进先出（FIFO）结构。元素从队尾 enqueue 加入，从队首 dequeue 移除。队列应用于打印排队、键盘缓冲区、任务调度和广度优先遍历。
Both structures can be implemented statically with an array plus pointer variables, or dynamically with a linked list. A linear queue implemented in an array suffers from wasted space as the front pointer moves forward, so a circular queue is used: when the rear reaches the last position it wraps around to index 0, providing that the queue is not full.
两种结构都可以用数组加指针变量静态实现，也可以用链表动态实现。用数组实现的线性队列会随着队首指针前移而浪费空间，因此要使用循环队列：当队尾到达最后位置时回绕到下标 0，前提是队列未满。
Stack: push A, push B, pop → B | Queue: enqueue A, enqueue B, dequeue → A
7. Trees, Graphs and Hash Tables | 树、图和哈希表
A tree is a hierarchical structure with a root node, parent and child nodes, and leaf nodes that have no children. A binary tree allows at most two children per node. A binary search tree (BST) adds an ordering rule: values smaller than a node go to the left subtree, larger values to the right, giving average search time of O(log n).
树是层次结构，包含根节点、父节点与子节点，以及没有子节点的叶节点。二叉树每个节点最多有两个子节点。二叉查找树（BST）额外规定排序规则：小于该节点的值进入左子树，大于的进入右子树，平均查找时间为 O(log n)。
Traversal visits every node in a defined order: pre-order (node, left, right), in-order (left, node, right) and post-order (left, right, node). In-order traversal of a BST outputs the values in ascending order, a fact examiners like to test.
遍历按指定顺序访问每个节点：前序（节点、左、右）、中序（左、节点、右）和后序（左、右、节点）。对二叉查找树做中序遍历会按升序输出所有值，这是考官喜欢考的一点。
A graph consists of vertices (nodes) and edges (arcs), and may be directed or undirected, weighted or unweighted. Graphs can be represented by an adjacency matrix, which uses O(n²) space but gives O(1) edge lookup, or an adjacency list, which uses less space for sparse graphs but requires traversal to test an edge.
图由顶点（节点）和边（弧）组成，可以是有向或无向、加权或无权。图可以用邻接矩阵表示，占用 O(n²) 空间但边查询为 O(1)；也可以用邻接表表示，对稀疏图更省空间，但判断一条边是否存在需要遍历。
A hash table maps a key to a location using a hashing algorithm. Because different keys can hash to the same address, collisions must be handled, most commonly by linear probing (finding the next free slot) or by chaining (storing a linked list at that index). Hash tables give O(1) average lookup but degrade if the table is too full.
哈希表通过哈希算法把键映射到存储位置。由于不同键可能哈希到同一地址，必须处理冲突，最常见的方法有线性探测（寻找下一个空位）和链地址法（在该下标处存一个链表）。哈希表平均查找为 O(1)，但装载过满时性能会下降。
8. Searching Algorithms | 查找算法
A linear search examines each item in turn from the start until the target is found or the list ends. It works on any list, sorted or unsorted, and has worst-case time complexity O(n). It is the sensible choice for small or unordered data sets.
线性查找从开头起依次检查每一项，直到找到目标或列表结束。它适用于任何列表，无论是否有序，最坏时间复杂度为 O(n)。对于规模较小或无序的数据集，它是合理的选择。
A binary search repeatedly halves the search space. It requires the list to be sorted first, then compares the target with the middle item and discards the half that cannot contain the target. Its time complexity is O(log n), so it is far faster on large sorted lists.
二分查找不断把查找区间减半。它要求列表事先有序，然后把目标与中间项比较，并舍弃不可能包含目标的那一半。其时间复杂度为 O(log n)，因此在大型有序列表上快得多。
The trade-off matters in exam answers: binary search is faster to run but requires the data to be sorted, and sorting itself costs time. If data changes frequently, the cost of re-sorting may outweigh the benefit of faster searching, so a linear search on unsorted data may be preferable.
这一取舍是答题要点：二分查找运行更快，但要求数据有序，而排序本身也要耗时。如果数据频繁变动，重新排序的成本可能超过快速查找带来的收益，此时对无序数据使用线性查找反而更合适。
| Algorithm | 算法 | Precondition | 前提条件 | Best | 最好 | Worst | 最坏 |
| Linear search | 线性查找 | None | 无 | O(1) | O(n) |
| Binary search | 二分查找 | Sorted list | 列表有序 | O(1) | O(log n) |
9. Sorting Algorithms | 排序算法
Bubble sort repeatedly compares adjacent pairs and swaps them if they are in the wrong order, making multiple passes until no swaps occur. It is simple to code but inefficient, with O(n²) time complexity. Insertion sort builds a sorted section one item at a time, placing each new item into its correct position; it is also O(n²) but performs well on nearly sorted data.
冒泡排序反复比较相邻元素，若顺序错误就交换，进行多趟直到不再发生交换。它易于编写但效率低，时间复杂度为 O(n²)。插入排序逐个建立有序区，把每个新元素插入正确位置；同样是 O(n²)，但在近乎有序的数据上表现良好。
Merge sort divides the list into halves, sorts each half recursively, then merges the sorted halves together. It runs in O(n log n) in all cases but needs extra memory for the merge step. Quick sort chooses a pivot, partitions the list into values below and above the pivot, then sorts each partition recursively. Its average case is O(n log n) but its worst case is O(n²), occurring when the pivot choice is consistently poor.
归并排序把列表分成两半，递归排序每一半，再合并两个有序部分。它在所有情况下都是 O(n log n)，但合并步骤需要额外内存。快速排序选取基准值，把列表划分为小于和大于基准的两部分，再递归排序。平均情况为 O(n log n)，最坏情况为 O(n²)，发生在基准值选择始终不佳时。
Exam questions usually ask you to complete a trace of the first two passes of a sort, or to justify which sort is most suitable for a given scenario. Justify with three things: the data size, whether it is partially sorted already, and whether memory is constrained.
考题通常要求你完成某排序算法前两趟的跟踪，或论证哪种排序最适合给定情境。论证时要抓住三点：数据规模、是否部分有序、内存是否受限。
- Bubble sort | 冒泡排序: O(n²), stable, simple, good for teaching.
- Insertion sort | 插入排序: O(n²), efficient on small or nearly sorted lists.
- Merge sort | 归并排序: O(n log n) always, needs extra memory.
- Quick sort | 快速排序: O(n log n) average, O(n²) worst, in-place.
10. Algorithm Efficiency and Big-O Notation | 算法效率与大 O 表示法
Efficiency describes how an algorithm's use of time and memory grows as the input size increases. Time complexity measures the number of operations performed; space complexity measures the memory required. Big-O notation expresses the upper bound of that growth while ignoring constant factors and lower-order terms.
效率描述算法的运行时间和内存使用随输入规模增长的变化方式。时间复杂度衡量执行的运算次数；空间复杂度衡量所需内存。大 O 表示法描述这种增长的上界，并忽略常数因子和低阶项。
The common orders you must recognise, from fastest to slowest growing, are listed below. A useful rule of thumb: a constant-time algorithm does not care how big the data is; a logarithmic algorithm halves the problem each step; a quadratic algorithm has nested loops over the same data.
你必须掌握以下常见复杂度，按增长速度从慢到快排列。一个实用经验：常数时间算法与数据规模无关；对数算法每步把问题规模减半；平方算法通常意味着对同一数据存在嵌套循环。
- O(1) — constant, for example array index access | 常数，如数组下标访问
- O(log n) — logarithmic, for example binary search | 对数，如二分查找
- O(n) — linear, for example linear search | 线性，如线性查找
- O(n log n) — for example merge sort and quick sort average case | 如归并排序与快排平均情况
- O(n²) — quadratic, for example bubble sort and insertion sort | 平方，如冒泡排序与插入排序
- O(2ⁿ) — exponential, for example naive recursive Fibonacci | 指数，如朴素递归斐波那契
When comparing algorithms in the exam, do not only quote a Big-O value; explain what the value means for the scenario, such as "merge sort will still complete quickly when the list doubles in size, whereas bubble sort's runtime will roughly quadruple". This shows understanding rather than memorisation.
考试比较算法时，不要只写一个 O 值；要解释该值在情境中的含义，例如"列表规模翻倍时归并排序仍能快速完成，而冒泡排序的运行时间大约会变为四倍"。这体现的是理解而非背诵。
11. Programming Paradigms | 编程范式
A programming paradigm is a style or approach to structuring programs. Procedural programming organises code into subprograms and follows a step-by-step sequence of instructions. It is straightforward but can become hard to maintain as programs grow, because data is separated from the code that manipulates it.
编程范式是组织程序的一种风格或方法。过程式编程把代码组织为子程序，按步骤依次执行指令。它简单直接，但随着程序变大可能难以维护，因为数据与操作数据的代码是分离的。
Object-oriented programming (OOP) organises a program around classes and objects. A class is a template defining attributes (data) and methods (behaviour); an object is an instance of a class. The four principles you must explain are encapsulation, inheritance, polymorphism and abstraction.
面向对象编程（OOP）围绕类和对象组织程序。类是定义属性（数据）和方法（行为）的模板；对象是类的实例。你必须解释的四项原则是封装、继承、多态和抽象。
- Encapsulation | 封装: attributes are kept private and accessed only through public methods, protecting data integrity.
- Inheritance | 继承: a subclass inherits attributes and methods from a superclass, reducing duplication.
- Polymorphism | 多态: the same method call behaves differently depending on the object's class, for example a Shape superclass with Circle and Square subclasses each defining their own area method.
- Abstraction | 抽象: unnecessary detail is hidden so the programmer works with a simplified model.
Declarative programming describes what the result should be rather than how to compute it. SQL is the standard example: a SELECT statement states the required data and the database engine decides the execution plan. Functional programming, with pure functions and immutable data, is often treated as a related style within the declarative family.
声明式编程描述结果应该是什么，而不是如何计算。SQL 是标准例子：一条 SELECT 语句陈述所需数据，由数据库引擎决定执行计划。函数式编程使用纯函数和不可变数据，通常被视为声明式家族中的相关风格。
12. Tracing, Comparing and Evaluating Algorithms | 跟踪、比较与评估算法
A trace table records the value of each variable after each step of an algorithm, letting you dry-run the code by hand and check that the logic matches expectations. Write one column per variable, one row per iteration or significant step, and always fill the final row before writing the output.
跟踪表记录算法每一步之后各变量的取值，使你能够手工"干跑"代码并验证逻辑是否符合预期。每个变量写一列，每次迭代或关键步骤写一行，并且在写输出之前一定要先把最后一行填完。
When tracing nested loops, remember that the inner loop completes fully for each single iteration of the outer loop. When tracing recursion, draw the call stack and show the unwinding as each call returns its value. Both techniques turn an unfamiliar algorithm into a manageable set of small steps.
跟踪嵌套循环时，要记住外层循环每迭代一次，内层循环就要完整执行一遍。跟踪递归时，画出调用栈，并显示每次调用返回值时的回溯过程。这两种技巧能把陌生的算法转化为一组可控的小步骤。
Evaluation questions carry high marks and require a balanced judgement, not a description. Use a structure such as: state the criterion, compare the alternatives against it, then reach a justified conclusion for the given scenario. Typical criteria include speed and time complexity, memory use, ease of implementation, ease of maintenance, scalability, and whether the data is already sorted or frequently updated.
评估类题目分值高，要求给出平衡的判断，而不是单纯描述。可使用这样的结构：提出评判标准，把各方案按该标准比较，再针对题目情境给出有理由的结论。常见标准包括速度与时间复杂度、内存占用、实现难度、维护难度、可扩展性，以及数据是否已排序或频繁更新。
A final revision routine: for every data structure and algorithm, be able to define it, draw it, state its complexity, give one real application, and name one advantage and one drawback. If you can do all five from memory for arrays, records, linked lists, stacks, queues, trees, graphs, hash tables, linear search, binary search, and the four sorts, you have covered the programming content of the specification in full.
最后一个复习套路：对每一种数据结构和算法，都要能定义它、画出它、说出其复杂度、给出一个真实应用，并指出一个优点和一个缺点。如果对数组、记录、链表、栈、队列、树、图、哈希表、线性查找、二分查找以及四种排序法都能凭记忆完成这五项，你就已经完整覆盖大纲中的编程内容了。
Revise in both languages where it helps, but always answer in precise English terminology: pseudocode, sequence, iteration, LIFO, FIFO, adjacency matrix, collision, encapsulation, O(n log n). Marks are awarded for the correct technical word, not for the length of the sentence.
在需要的时候可以用双语复习，但作答时一定要使用准确的英文术语：pseudocode、sequence、iteration、LIFO、FIFO、adjacency matrix、coll
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图