📚 Edexcel A Level Programming: Algorithms, Data Structures and Computational Thinking | Edexcel A Level 编程：算法、数据结构与计算思维
Welcome to this Edexcel A Level Computer Science revision guide on programming. Programming questions appear in both Paper 1 and Paper 2, often through pseudocode tracing, algorithm design, and coding scenarios. The key to high marks is not just knowing syntax, but being able to analyse a problem, choose an appropriate data structure, and justify efficiency.
欢迎阅读本 Edexcel A Level 计算机科学编程复习指南。编程题在 Paper 1 和 Paper 2 中都会出现，通常以伪代码追踪、算法设计和编码情景题的形式考查。获得高分的关键不只是掌握语法，还要能够分析问题、选择合适的数据结构，并论证算法效率。
This guide works through the whole programming strand in a logical order: control flow, data types, pseudocode conventions, subprograms, data structures, searching and sorting algorithms, computational thinking, complexity, and finally testing and exam technique. Each section ends with the phrases and habits that examiners reward most often.
本指南按逻辑顺序梳理整个编程主线：控制流、数据类型、伪代码规范、子程序、数据结构、查找与排序算法、计算思维、复杂度分析，最后是测试与应试技巧。每一节都会点出考官最常给分的表达方式和答题习惯。
1. Programming Fundamentals and Flow of Control | 编程基础与控制流
Every algorithm can be built from sequence, selection, and iteration. Sequence executes statements in order; selection makes a decision based on a condition; iteration repeats a block while or until a condition changes. These three constructs are sufficient to express any computable algorithm, which is why they are called the basic building blocks of structured programming.
每个算法都可以由顺序、选择和迭代三种结构构建。顺序按先后顺序执行语句；选择根据条件作出判断；迭代在某个条件成立或改变之前重复执行一段代码。这三种结构足以表达任何可计算的算法，因此被称为结构化编程的基本构造块。
In Edexcel pseudocode, selection often uses IF...THEN...ELSE...ENDIF. Iteration can be count-controlled with FOR i ← 0 TO n - 1 or condition-controlled with WHILE...DO...ENDWHILE and REPEAT...UNTIL.
在 Edexcel 伪代码中，选择通常使用 IF...THEN...ELSE...ENDIF。迭代可以是计数控制的 FOR i ← 0 TO n - 1，也可以是条件控制的 WHILE...DO...ENDWHILE 和 REPEAT...UNTIL。
Count-controlled iteration is used when you know in advance how many times the loop body must run, and the loop variable is incremented automatically. Condition-controlled iteration is used when the number of repetitions depends on data, and you must make sure the condition can eventually become false, otherwise the loop never terminates.
计数控制迭代适用于事先已知循环次数的情况，循环变量会自动递增。条件控制迭代适用于重复次数取决于数据的情况，你必须确保条件最终会变为假，否则循环永不终止。
WHILE...DO...ENDWHILE is a pre-condition loop: the test happens before the body executes, so the body may run zero times. REPEAT...UNTIL is a post-condition loop: the body executes at least once, because the test happens at the end. This is the single most commonly examined difference between the two.
WHILE...DO...ENDWHILE 是前置条件循环：测试发生在循环体执行之前，因此循环体可能一次都不执行。REPEAT...UNTIL 是后置条件循环：循环体至少执行一次，因为测试发生在末尾。这是两者之间最常被考查的区别。
Use the Edexcel pseudocode conventions: the left arrow ← n, and MOD/DIV are used for integer remainder and quotient. Write clearly and indent loops and selection blocks.
请使用 Edexcel 伪代码约定：左箭头 ← 表示赋值，= 用于比较，MOD 和 DIV 分别表示整数余数和商。书写要清晰，并对循环和选择块进行缩进。
2. Variables, Data Types and Constants | 变量、数据类型与常量
A variable is a named storage location whose value can change while the program runs. Choosing the correct data type matters because it determines which operations are legal, how much memory is used, and how values are compared or displayed.
变量是一个有名字的存储位置，其值在程序运行期间可以改变。选择正确的数据类型很重要，因为它决定了哪些运算合法、占用多少内存，以及数值如何比较或显示。
The core data types you must know are integer (whole numbers), real or float (decimal numbers), Boolean (TRUE or FALSE), character (a single symbol), and string (a sequence of characters). You may also meet date/time types and user-defined types built from a record.
你必须掌握的核心数据类型包括：整数 integer（整数值）、实数 real 或浮点数 float（带小数的值）、布尔值 Boolean（TRUE 或 FALSE）、字符 character（单个符号）和字符串 string（一串字符）。你还可能遇到日期/时间类型以及由记录构造的用户自定义类型。
Type conversion, sometimes called casting, changes a value from one type to another. Converting a real to an integer truncates or rounds the decimal part, so always check what the question expects. Converting a string such as "42" to an integer is a parsing operation and behaves differently from arithmetic.
类型转换（有时称为强制转换）把值从一种类型变为另一种。把实数转换为整数会截断或四舍五入小数部分，因此一定要看清题目要求。把字符串如 "42" 转换为整数属于解析操作，其行为与算术运算不同。
A constant is a named value that cannot change once it has been set. Constants are declared with CONST and are used for fixed quantities such as the maximum size of an array or a tax rate, which makes the program easier to read and safer to maintain.
常量是一旦设定便不可更改的有名值。常量用 CONST 声明，用于数组最大长度、税率等固定量，这能让程序更易读、更易维护，也更安全。
re. Avoid reserved words and single letters except for short loop counters such as i or j.
好的标识符名称应当有意义、以字母开头、不含空格，并遵循一致的命名风格，例如 totalScore 或 total_score。避免使用保留字，也避免使用单字母名，除非是 i、j 这类短循环计数器。
3. Pseudocode Conventions for Edexcel | Edexcel 伪代码规范
Edexcel does not require a specific real programming language in the examination. Instead, answers are written in the specification's pseudocode, and marks are awarded for logic, structure and correct use of the agreed notation, not for syntax peculiar to Python or Java.
Edexcel 考试并不要求使用某种具体的真实编程语言。答案用考纲规定的伪代码书写，得分点在于逻辑、结构和对约定记号的正确使用，而不在于 Python 或 Java 的语法细节。
Assignment uses a left arrow, for example total ← N. The not-equal operator is ≠ and the other relational operators are <, >, ≤ and ≥.
赋值使用左箭头，例如 total ← total + 1。比较使用单个等号，例如 IF score = 100 THEN。不等运算符是 ≠，其他关系运算符包括 <、>、≤ 和 ≥。
Arithmetic operators are +, -, * and /, while DIV gives the integer quotient and MOD gives the integer remainder. For example, 17 DIV 5 is 3 and 17 MOD 5 is 2. These two operators are essential for tasks such as checking divisibility or converting between number bases.
算术运算符包括 +、-、* 和 /，而 DIV 给出整数商，MOD 给出整数余数。例如 17 DIV 5 得 3，17 MOD 5 得 2。这两个运算符对于判断整除性或进行进制转换之类的任务至关重要。
Arrays are declared with a range, for example scores : ARRAY[0:9] OF INTEGER, and elements are accessed with square brackets as scores[0]. String handling uses built-in operations such as LENGTH(s), SUBSTRING(s, start, length), UCASE(s) and the concatenation operator &.
数组用范围声明，例如 scores : ARRAY[0:9] OF INTEGER，元素用方括号访问，如 scores[0]。字符串处理使用内置操作，如 LENGTH(s)、SUBSTRING(s, start, length)、UCASE(s) 以及连接运算符 &。
Input and output are written as INPUT and OUTPUT, for example INPUT age and OUTPUT "Total: ", total. Subprograms are declared with PROCEDURE name(...) ... ENDPROCEDURE or FUNCTION name(...) ... ENDFUNCTION, and comments use //.
输入输出写为 INPUT 和 OUTPUT，例如 INPUT age、OUTPUT "Total: ", total。子程序用 PROCEDURE name(...) ... ENDPROCEDURE 或 FUNCTION name(...) ... ENDFUNCTION 声明，注释使用 //。
4. Subprograms, Parameters and Scope | 子程序、参数与作用域
A procedure performs an action and does not return a value, while a function performs a calculation and returns exactly one value through its name. If a question asks you to write a subprogram that "calculates and returns" something, a FUNCTION is almost always the expected answer.
过程（procedure）执行一个动作且不返回值，而函数（function）执行计算并通过其名称返回恰好一个值。如果题目要求你写一个"计算并返回"某值的子程序，几乎总是应该用 FUNCTION。
Parameters may be passed by value or by reference. By value copies the data, so changes inside the subprogram do not affect the caller. By reference passes the address, so changes do affect the original variable. In Edexcel pseudocode, by reference is usually written with the keyword REF.
参数可以按值传递或按引用传递。按值传递会复制数据，因此子程序内部的修改不会影响调用者。按引用传递传递地址，因此修改会影响原始变量。在 Edexcel 伪代码中，按引用传递通常用关键字 REF 表示。
Scope describes where an identifier can be seen. A local variable exists only inside the subprogram that declares it and is destroyed when the subprogram ends. A global variable is visible throughout the program and can be modified from anywhere, which makes bugs harder to trace.
作用域描述标识符可以被访问的范围。局部变量只存在于声明它的子程序内部，并在子程序结束后被销毁。全局变量在整个程序中可见，可以被任意位置修改，这会使错误更难追踪。
Recursion is when a subprogram calls itself. Every recursive solution needs a base case that stops the recursion, and a general case that moves the problem closer to the base case. Without a correct base case the recursion causes a stack overflow.
递归是指子程序调用自身。每个递归解法都需要一个终止递归的基础情形，以及一个让问题更接近基础情形的一般情形。如果没有正确的基础情形，递归会导致栈溢出。
Modularity through subprograms improves the program because code is reused rather than duplicated, each module can be tested independently, and changes are localised. When you justify a subprogram in an exam answer, name these three benefits explicitly.
通过子程序实现模块化能改进程序：代码被复用而非重复，每个模块可以独立测试，修改也被局限在局部。在考试答案中论证子程序的好处时，请明确写出这三点。
5. Arrays and Lists | 数组与列表
An array is a fixed-size collection of elements of the same type, accessed by an integer index. A one-dimensional array models a single list; a two-dimensional array models a table or grid with rows and columns.
数组是大小固定、元素类型相同的集合，通过整数下标访问。一维数组建模单个列表；二维数组建模具有行和列的表格或网格。
Edexcel pseudocode usually indexes arrays from 0, so an array declared as ARRAY[0:9] holds ten elements with valid indices 0 to 9. Accessing index 10 is an out-of-range error and is a common cause of runtime failure in exam traces.
Edexcel 伪代码通常从 0 开始给数组编下标，因此声明为 ARRAY[0:9] 的数组含十个元素，合法下标为 0 到 9。访问下标 10 属于越界错误，也是考试追踪题中常见的运行时故障原因。
A standard pattern is iterating with a FOR loop: FOR i ← 0 TO 9 ... NEXT i. Because the loop variable runs from 0 to 9 inclusive, the loop executes exactly ten times for a ten-element array, which is the correct count.
一种标准模式是用 FOR 循环遍历：FOR i ← 0 TO 9 ... NEXT i。由于循环变量从 0 运行到 9（含端点），对于十个元素的数组，循环正好执行十次，这是正确的次数。
Static arrays have a size fixed at compile time and cannot grow. A list is a dynamic structure that can grow or shrink at runtime, which is preferable when the number of items is unknown in advance, though it usually costs extra memory for bookkeeping.
静态数组的大小在编译时固定，不能增长。列表是可以在运行时增长或缩小的动态结构，当事先不知道元素个数时更合适，不过通常需要额外的内存开销来维护结构信息。
A tuple is an ordered, usually immutable sequence of values, useful for returning several related values at once, for example (minValue, maxValue). Because it cannot be modified after creation, it is safe to pass around as a read-only result.
元组是有序的、通常不可变的值序列，适合一次性返回多个相关值，例如 (minValue, maxValue)。由于创建后不能修改，它可以作为只读结果安全传递。
6. Stacks, Queues and Linked Lists | 栈、队列与链表
A stack is a last-in-first-out structure. Elements are added with push and removed with pop, and both operations act on the same end, called the top. Peek (or top) reads the top element without removing it, and isEmpty tests whether the stack holds any data.
栈是后进先出（LIFO）结构。元素用 push 加入、用 pop 移除，两个操作都作用于同一端，称为栈顶。Peek（或 top）读取栈顶元素但不移除，isEmpty 测试栈中是否有数据。
A push onto a full stack causes stack overflow, and a pop from an empty stack causes stack underflow. These two error conditions are frequently worth a mark each, so state them by name rather than describing them loosely.
向已满的栈执行 push 会导致上溢（overflow），从空栈执行 pop 会导致下溢（underflow）。这两种错误情形常常各值一分，因此要写出它们的专有名称，而不要含糊描述。
A queue is a first-in-first-out structure. Elements are added at the rear with enqueue and removed from the front with dequeue. A linear queue wastes space once the front moves forward, so a circular queue reuses freed positions by wrapping the index with MOD.
队列是先进先出（FIFO）结构。元素用 enqueue 从队尾加入，用 dequeue 从队首移除。线性队列在队首前移后会浪费空间，因此循环队列通过用 MOD 让下标回绕，从而复用被释放的位置。
A linked list stores each item in a node that holds the data plus a pointer to the next node; a doubly linked list also points backwards. Inserting or deleting a node only requires changing a few pointers, so it is O(1) once the position is known, but access to the nth item is O(n) because nodes must be followed one by one.
链表把每个数据项存放在一个节点中，节点包含数据以及指向下一个节点的指针；双向链表的节点还指向前一个节点。插入或删除节点只需修改几个指针，因此在已知位置的情况下是 O(1)，但访问第 n 个元素是 O(n)，因为必须逐个跟随节点。
Choosing between them depends on the access pattern. Use a stack for undo history, expression evaluation and depth-first traversal; a queue for print spooling, buffering and breadth-first traversal; a linked list when frequent insertions and deletions dominate.
在它们之间做选择取决于访问模式。栈适合撤销历史、表达式求值和深度优先遍历；队列适合打印队列、缓冲和广度优先遍历；当频繁插入删除占主导时，链表更合适。
7. Records, Sets, Hash Tables and Dictionaries | 记录、集合、哈希表与字典
A record groups related fields of possibly different types under one name. For example, a Student record might hold name : STRING, year : INTEGER and average : REAL. A record models a row in a real-world entity and is often stored inside an array of records.
记录把可能类型不同的相关字段组合在同一个名称下。例如一个 Student 记录可以包含 name : STRING、year : INTEGER 和 average : REAL。记录建模现实实体的一个行，通常存放在记录数组中。
A set is an unordered collection of unique values with no duplicates. Sets support union (∪), intersection (∩) and difference (-), and are useful for membership testing and for removing duplicates from data efficiently.
集合是无序且不含重复值的集合。集合支持并集（∪）、交集（∩）和差集（-），适合做成员测试以及高效地去除数据中的重复项。
A hash table stores key-value pairs in an array of buckets. A hash function converts the key into an index, giving average O(1) insertion and lookup. Because different keys can map to the same index, collisions must be resolved, usually by chaining or by linear probing.
哈希表把键值对存储在桶数组中。哈希函数把键转换为下标，平均可实现 O(1) 的插入与查找。由于不同的键可能映射到同一下标，必须解决冲突，通常用链地址法或线性探测法。
Chaining stores a linked list of colliding items in each bucket, which handles high load factors gracefully. Linear probing searches forward for the next free slot, which is memory-efficient but can create clusters and slow later lookups.
链地址法在每个桶中存放一个由冲突项组成的链表，能较好地应对高装载因子。线性探测向后寻找下一个空槽，节省内存，但可能形成聚集，拖慢后续查找。
A dictionary (or associative array or map) is an abstract key-value structure. Its behaviour is defined by operations such as put(key, value), get(key) and contains(key), while the implementation underneath could be a hash table or a balanced tree.
字典（或称关联数组、映射）是抽象的键值结构。它的行为由 put(key, value)、get(key)、contains(key) 等操作定义，而底层实现可以是哈希表或平衡树。
8. Searching Algorithms: Linear and Binary | 查找算法：线性查找与二分查找
A linear search checks every element from the start until the target is found or the list ends. It works on unsorted data and has a worst-case time complexity of O(n), because in the worst case every element must be inspected.
线性查找从开头逐个检查元素，直到找到目标或列表结束。它适用于未排序数据，最坏时间复杂度为 O(n)，因为最坏情况下需要检查每个元素。
A binary search repeatedly halves the search space. It compares the target with the middle element, then discards the half that cannot contain the target, giving a worst-case time complexity of O(log₂ n).
二分查找不断将查找空间减半。它把目标与中间元素比较，然后丢弃不可能包含目标的那一半，最坏时间复杂度为 O(log₂ n)。
Binary search requires the data to be sorted first, so its true cost includes the sorting step. If you must search unsorted data only once, a linear search is often the better overall choice; if you will search the same data many times, sorting once and then binary searching pays off.
二分查找要求数据先排好序，因此它的真实成本包含排序步骤。如果只对未排序数据查找一次，线性查找总体往往更优；如果要多次查找同一批数据，先排序再二分查找才划算。
classic binary search pseudocode uses low and high indices: while low ≤ high, compute mid ← (low + high) DIV 2, then set low ← mid + 1 or high ← integer midpoint, and the loop must shrink the range each time to avoid an infinite loop.
经典的二分查找伪代码使用 low 和 high 下标：当 low ≤ high 时，计算 mid ← (low + high) DIV 2，然后根据比较结果设置 low ← mid + 1 或 high ← mid - 1。使用 DIV 保证中点为整数，且循环每次都必须收缩区间，以避免死循环。
9. Sorting Algorithms: Bubble, Insertion, Merge and Quick | 排序算法：冒泡、插入、归并与快速
Bubble sort repeatedly compares adjacent pairs and swaps them if they are out of order. After each pass the largest remaining element has bubbled to the end. Its average and worst-case complexity is O(n²), but it can be improved by stopping early if a pass performs no swaps, giving a best case of O(n) on already sorted data.
冒泡排序反复比较相邻元素，若顺序错误就交换。每一轮结束后，剩余元素中的最大值已"冒泡"到末尾。它的平均和最坏复杂度为 O(n²)，但若某一轮没有发生交换就提前结束，则在已排序数据上最好情况可达 O(n)。
Insertion sort builds a sorted portion at the front and inserts each new element into its correct position by shifting larger elements right. It is O(n²) in the worst case but very efficient on small or nearly sorted lists, which makes it a common choice for small partitions inside other algorithms.
插入排序在前部构造已排序部分，通过把较大元素右移，把每个新元素插入到正确位置。它最坏为 O(n²)，但在数据量小或接近有序时非常高效，因此在其他算法内部处理小分区时常用。
Merge sort uses divide and conquer: split the list into halves, sort each half recursively, then merge the two sorted halves. Merging is linear in the total size, and the recursion depth is log₂ n, so the overall complexity is O(n log n) in all cases, at the cost of O(n) extra memory.
归并排序采用分治法：把列表对半分割，递归排序每一半，再合并两个已排序的半区。合并与总规模成线性关系，递归深度为 log₂ n，因此总体在所有情况下都是 O(n log n)，代价是需要 O(n) 的额外内存。
Quick sort chooses a pivot, partitions the list into values smaller and larger than the pivot, then sorts each partition recursively. Its average complexity is O(n log n) and it sorts in place, but a poor pivot choice on already sorted data can degrade it to O(n²).
快速排序选择一个基准值，把列表划分为小于和大于基准的两部分，再递归排序各分区。它的平均复杂度为 O(n log n)，且可原地排序，但在已排序数据上选择糟糕的基准可能退化为 O(n²)。
| Algorithm | 算法 | Best | 最好 | Average | 平均 | Worst | 最坏 | Space | 空间 |
| Bubble | 冒泡 | O(n) | O(n²) | O(n²) | O(1) |
| Insertion | 插入 | O(n) | O(n²) | O(n²) | O(1) |
| Merge | 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick | 快速 | O(n log n) | O(n log n) | O(n²) | O(log n) |
10. Computational Thinking: Decomposition, Abstraction and Pattern Recognition | 计算思维：分解、抽象与模式识别
Computational thinking is the set of problem-solving techniques used to express a solution in a form a computer can execute. Its four pillars are decomposition, abstraction, pattern recognition and algorithmic thinking, and exam questions often ask you to apply them to a stated scenario.
计算思维是一套用于把解法表达成计算机可执行形式的问题求解技术。它的四大支柱是分解、抽象、模式识别和算法思维，考题常要求你把它们应用到给定的情景中。
Decomposition breaks a large problem into smaller sub-problems that can be solved and tested independently. In an exam, list the sub-problems concretely, for example "validate input", "calculate the average", "write results to file", rather than saying vaguely "split it up".
分解把大问题拆成可以独立求解和测试的更小子问题。考试中要具体列出子问题，例如"校验输入""计算平均值""把结果写入文件"，不要笼统地说"把它分开"。
Abstraction removes unnecessary detail and keeps only what matters for the current problem. A route-finding app abstracts away road colour and building shape and keeps junctions, distances and directions. Good abstraction makes a model simpler to compute without losing the behaviour you need.
抽象去除不必要的细节，只保留对当前问题重要的部分。导航应用会忽略道路颜色和建筑外形，只保留路口、距离和方向。好的抽象让模型更易计算，同时不丢失所需的行为。
Pattern recognition identifies
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图