📚 A-Level Edexcel Programming: Data Structures, Algorithms and Computational Thinking | A-Level Edexcel 编程：数据结构、算法与计算思维
Programming is at the heart of the Edexcel A-Level Computer Science specification. This article develops the core ideas you need for the examined papers and the practical programming project, from clear pseudocode to the evaluation of algorithms.
编程是 Edexcel A-Level 计算机科学考试大纲的核心。本文帮你构建笔试与编程项目所需的核心思想，从清晰的伪代码到算法的评估。
1. Computational Thinking and Problem Decomposition | 计算思维与问题分解
Computational thinking is the set of reasoning skills that comes before a single line of code is written. Examiners reward candidates who show how a problem was analysed, not only the finished program.
计算思维是在写下一行代码之前所需的推理能力。考官更欣赏那些展示出"如何分析问题"的考生，而不仅仅是最终程序。
Decomposition reduces complexity by splitting a large problem into smaller subproblems that can be solved, tested and maintained separately. A library system, for example, can be separated into user login, book search, borrowing and fine calculation, each of which becomes a manageable module with its own inputs and outputs.
分解通过把大问题拆成子问题来降低复杂性，这些子问题可以分别解决、测试和维护。例如，图书馆系统可以分为用户登录、图书检索、借阅和罚款计算，每个部分都成为输入输出明确的独立模块。
Pattern recognition finds similarities between the current problem and problems you have solved before, such as recognising that a maze can be modelled as a graph, or that ranking search results is essentially a sorting problem.
模式识别寻找当前问题与你以前解决过的问题之间的相似之处，例如识别出迷宫可以建模为图，或者把搜索结果的排序看成经典的排序问题。
Abstraction keeps only the information that is relevant to the solution. When writing a sorting function you do not need to know how the data is stored internally; you only need a defined interface that returns the ordered sequence. Abstraction therefore lets you reason about the algorithm at the right level of detail.
抽象只保留与解决方案相关的信息。写排序函数时，你不需要知道数据内部如何存储，只需要一个定义好的接口返回有序序列。因此抽象让你能在恰当的细节层级上思考算法。
Algorithmic thinking means expressing a solution as a finite, ordered and unambiguous set of steps, and generalising it so it works for any valid input rather than one specific example.
算法思维意味着把解决方案表达为有限、有序、无歧义的步骤集合，并加以泛化，使其适用于任何合法输入，而不只是某一个具体例子。
2. Pseudocode Conventions and Writing Clear Algorithms | 伪代码规范与清晰算法
Pseudocode is a language-independent way of expressing an algorithm, and in Edexcel questions it is often the only acceptable answer format. It should be readable by a programmer who has never seen your chosen language.
伪代码是一种与语言无关的算法表达方式，在 Edexcel 的题目中往往也是唯一被接受的作答形式。它应当让从没见过你所选语言的程序员也能读懂。
Standard conventions include declaring variables and their data types, for example DECLARE total : INTEGER, using an arrow or equals sign for assignment such as count ← count + 1, and closing every control structure explicitly with ENDIF, ENDFOR, ENDWHILE or UNTIL.
标准规范包括声明变量及其数据类型，例如 DECLARE total : INTEGER；用箭头或等号表示赋值，如 count ← count + 1；并用 ENDIF、ENDFOR、ENDWHILE 或 UNTIL 明确结束每一个控制结构。
Selection uses IF ... THEN ... ELSE ... ENDIF and CASE ... OTHERWISE ... ENDCASE, while iteration uses FOR ... NEXT, WHILE ... ENDWHILE and REPEAT ... UNTIL. Functions and procedures are declared with FUNCTION ... ENDFUNCTION and PROCEDURE ... ENDPROCEDURE.
选择结构使用 IF ... THEN ... ELSE ... ENDIF 以及 CASE ... OTHERWISE ... ENDCASE；循环结构使用 FOR ... NEXT、WHILE ... ENDWHILE 和 REPEAT ... UNTIL。函数与过程用 FUNCTION ... ENDFUNCTION 和 PROCEDURE ... ENDPROCEDURE 声明。
Write one statement per line, indent nested blocks, use meaningful identifiers such as subtotal or isEligible, and avoid mixing real-language syntax into your pseudocode. In the exam, marks are awarded for logic and structure, so clarity beats cleverness.
每行只写一条语句，缩进嵌套代码块，使用有意义的标识符（如 subtotal、isEligible），避免把真实语言的语法混入伪代码。考试中得分点在于逻辑与结构，因此清晰比"炫技"更重要。
3. Data Structures I: Arrays, Lists, Tuples and Records | 数据结构（上）：数组、列表、元组与记录
An array is a fixed-size, indexed collection of elements of the same data type. Once declared, its length cannot change, which makes it fast to access but awkward when the number of items is unknown.
数组是固定长度、可索引、元素数据类型相同的集合。声明之后其长度无法改变，因此访问速度快，但在元素数量未知时不够灵活。
Accessing an array element is a constant-time operation, written in pseudocode as scores[3], while a two-dimensional array such as grid[row][column] is used for tables, images and game boards.
访问数组元素是常数时间操作，伪代码写作 scores[3]；而二维数组如 grid[row][column] 常用于表格、图像和棋盘类场景。
A list, or dynamic array, can grow and shrink at runtime. Inserting or deleting in the middle of a list may require shifting the remaining elements, which affects the efficiency of the operation.
列表（动态数组）可以在运行时增长和收缩。在列表中间插入或删除元素可能需要移动其余元素，这会影响该操作的效率。
A tuple is an ordered but immutable collection, useful for values that must not change, such as coordinates. A record groups related fields of different data types under one name, for example a Student record with name, age and grade.
元组是有序但不可变的集合，适合存放不应改变的值，如坐标。记录则把不同数据类型的相关字段组合在一个名字下，例如包含 name、age、grade 的 Student 记录。
Choosing the right structure matters: arrays give fast random access, records give readable, self-documenting data, and lists give flexibility when the dataset changes size.
选择正确的结构很重要：数组提供快速随机访问，记录让数据可读且自说明，而列表在数据规模变化时提供灵活性。
4. Data Structures II: Stacks, Queues, Linked Lists, Trees, Hash Tables and Graphs | 数据结构（下）：栈、队列、链表、树、哈希表与图
A stack is a last-in-first-out structure with push and pop operations, plus peek to inspect the top item. It models the call stack of a running program, undo facilities in editors, and the evaluation of reverse Polish expressions.
栈是后进先出（LIFO）结构，操作包括 push、pop，以及查看栈顶的 peek。它可模拟程序运行时的调用栈、编辑器中的撤销功能，以及逆波兰表达式的求值。
A queue is first-in-first-out, with enqueue and dequeue operations. It models print spoolers, keyboard buffers and process scheduling. Variations include the circular queue, which reuses freed space, and the priority queue, where the highest-priority item leaves first.
队列是先进先出（FIFO）结构，操作包括 enqueue 与 dequeue。它可模拟打印队列、键盘缓冲区和进程调度。变体包括可循环利用空间的循环队列，以及优先级最高者先出的优先队列。
A linked list stores each item in a node containing data and one or more pointers. Insertion and deletion are efficient because no shifting is required, but access is sequential, so finding the nth item is O(n) rather than O(1).
链表把每个元素存放在包含数据与一个或多个指针的节点中。插入和删除效率高，因为无需移动元素；但访问是顺序的，查找第 n 个元素是 O(n) 而不是 O(1)。
A binary search tree keeps smaller values to the left and larger values to the right, giving O(log n) search when balanced but O(n) when it degenerates into a chain. A hash table maps a key to a position using a hash function, and collisions are resolved by chaining or probing.
二叉搜索树把较小的值放在左子树、较大的值放在右子树：平衡时查找为 O(log n)，退化成链时则变为 O(n)。哈希表用哈希函数把键映射到位置，冲突可通过链地址法或开放探测法解决。
A graph consists of vertices and edges and can be stored as an adjacency matrix, which is fast to query but memory-hungry, or an adjacency list, which is compact for sparse graphs. Graphs model networks, routes and social connections, and are traversed with depth-first or breadth-first search.
图由顶点和边组成，可用邻接矩阵存储（查询快但占内存）或邻接表存储（稀疏图下更紧凑）。图可模拟网络、路线与社交关系，常用深度优先或广度优先搜索进行遍历。
5. Searching and Sorting Algorithms | 查找与排序算法
A linear search examines each item in turn until the target is found or the list ends. It works on unsorted data and is O(n), which is acceptable for small or unordered collections.
线性查找依次检查每一项，直到找到目标或列表结束。它适用于未排序数据，复杂度为 O(n)，对小型或无序集合是可接受的。
A binary search repeatedly halves a sorted list by comparing the target with the middle element. It is O(log n) and therefore much faster on large datasets, but it is only valid when the data is already ordered.
二分查找通过把目标与中间元素比较，不断将有序列表折半。其复杂度为 O(log n)，在大数据集上快得多，但仅在数据已排序时才有效。
Bubble sort repeatedly swaps adjacent items that are out of order, and insertion sort builds a sorted section one item at a time; both are O(n²) on average, though insertion sort approaches O(n) on nearly sorted data. Merge sort splits, sorts and merges, guaranteeing O(n log n) but requiring extra memory.
冒泡排序反复交换相邻的逆序元素，插入排序逐个构建有序区；两者平均为 O(n²)，但插入排序在近乎有序的数据上接近 O(n)。归并排序采用分割、排序、合并，稳定保证 O(n log n)，但需要额外内存。
Quicksort partitions the list around a pivot and is O(n log n) on average with good cache behaviour, but degrades to O(n²) with poor pivot choices. Choosing an algorithm therefore depends on data size, existing order, memory limits and whether stability is required.
快速排序围绕基准值划分列表，平均为 O(n log n) 且缓存友好，但基准选择不佳时会退化为 O(n²)。因此算法选择取决于数据规模、已有顺序、内存限制以及是否需要稳定排序。
6. Algorithm Efficiency and Big-O Notation | 算法效率与大 O 表示法
Big-O notation describes how the running time or memory use of an algorithm grows as the input size n increases. Constant factors and lower-order terms are ignored because they do not affect the long-term growth rate.
大 O 表示法描述算法的运行时间或内存占用随输入规模 n 增长的方式。常数因子和低阶项被忽略，因为它们不影响长期增长趋势。
The table below summarises the complexities you are most likely to be asked about in an Edexcel paper.
下表汇总了 Edexcel 试卷中最常考查的复杂度。
| Complexity | 复杂度 | Name | 名称 | Typical example | 典型例子 |
| O(1) | Constant | 常数 | Array index access | 数组下标访问 |
| O(log n) | Logarithmic | 对数 | Binary search | 二分查找 |
| O(n) | Linear | 线性 | Linear search | 线性查找 |
| O(n log n) | Linearithmic | 线性对数 | Merge sort | 归并排序 |
| O(n²) | Quadratic | 平方 | Bubble sort | 冒泡排序 |
| O(2ⁿ) | Exponential | 指数 | Naive recursive Fibonacci | 朴素递归斐波那契 |
Time complexity is not the whole story: space complexity measures the extra memory an algorithm needs. Merge sort is fast but not in place, whereas quicksort sorts in place, and this trade-off often decides which is preferable on a memory-limited device.
时间复杂度并非全部：空间复杂度衡量算法所需的额外内存。归并排序快但非原地排序，而快速排序是原地排序；在内存受限的设备上，这种权衡常常决定取舍。
Always distinguish best, average and worst case. Exam questions frequently ask why an algorithm with a good average performance still has an unacceptable worst case for a safety-critical system.
务必区分最好、平均与最坏情况。考题常问：为什么平均性能良好的算法，在安全关键系统中仍可能因最坏情况而不可接受。
7. Recursion versus Iteration | 递归与迭代
A recursive subroutine calls itself with a smaller version of the same problem, and must contain a base case that stops the recursion. Without a base case the recursion never terminates and eventually causes a stack overflow.
递归子程序用同一问题的更小版本调用自身，并且必须包含终止递归的基本情况（base case）。若缺少基本情况，递归永不终止，最终导致栈溢出。
Each recursive call adds a frame to the call stack containing parameters and local variables, so recursion usually consumes more memory than an equivalent loop. Converting recursion to iteration often means managing an explicit stack yourself.
每次递归调用都会在调用栈上增加一个包含参数与局部变量的栈帧，因此递归通常比等价的循环占用更多内存。把递归改写为迭代，往往需要自己维护一个显式栈。
Recursion is the natural choice for tree traversal, depth-first search, fractal generation and divide-and-conquer algorithms such as merge sort and quicksort, where the problem structure is itself recursive.
递归是树遍历、深度优先搜索、分形生成，以及归并排序、快速排序等分治算法的自然选择，因为这些问题的结构本身就是递归的。
For simple repetition such as summing an array or counting items, iteration is clearer and cheaper. A strong exam answer justifies the choice using memory use, readability and the shape of the problem.
对于求和、计数这类简单重复任务，迭代更清晰也更省资源。优秀的答卷会从内存占用、可读性和问题结构三方面论证选择理由。
8. Programming Paradigms and Object-Oriented Design | 编程范式与面向对象设计
Procedural or imperative programming organises a solution as a sequence of statements using selection, iteration and subroutines. It is direct and efficient for small, well-defined tasks.
过程式（命令式）编程把解决方案组织为一系列语句，使用选择、循环与子程序。对小型、定义清晰的任务而言，它直接而高效。
Object-oriented programming groups data and the operations on that data into classes, and creates objects as instances of those classes. Attributes store state and methods define behaviour, so the two cannot drift apart.
面向对象编程把数据及其操作封装为类，并把对象作为类的实例。属性保存状态，方法定义行为，两者不会相互脱节。
Encapsulation hides internal state behind a public interface, usually through getters and setters that validate input. Inheritance lets a subclass reuse and extend a superclass, and polymorphism lets one method call behave differently depending on the actual object type at runtime.
封装把内部状态隐藏在公共接口之后，通常通过带校验的 getter 和 setter 实现。继承让子类复用并扩展父类，多态则让同一次方法调用在运行时根据对象的实际类型产生不同行为。
Other paradigms appear in the specification too: functional programming treats computation as the evaluation of functions and uses higher-order operations such as map, filter and reduce, while event-driven programming responds to user or system events through handlers and callbacks.
大纲还涉及其他范式：函数式编程把计算视为函数的求值，使用 map、filter、reduce 等高阶操作；事件驱动编程则通过处理程序和回调响应用户或系统事件。
9. Programming Techniques, Strings and File Handling | 编程技巧、字符串与文件处理
String handling is examined frequently. You should be able to find the length of a string, extract a substring, convert case, concatenate, and search for a character or substring, and then explain the index positions involved.
字符串处理是高频考点。你应能求字符串长度、截取子串、转换大小写、拼接，以及查找字符或子串，并解释其中涉及的索引位置。
File handling allows data to persist between runs of a program. The typical pattern is open, read or write, then close, and when writing you must choose between overwriting and appending to the existing content.
文件处理让数据在程序多次运行之间得以保存。典型模式是打开、读取或写入、关闭；写入时还必须选择覆盖原内容还是追加到末尾。
Structured formats such as CSV and JSON are common in project work because they can be read line by line or parsed into records, but any external data must be validated before it is trusted.
CSV、JSON 等结构化格式在项目中很常见，因为它们可以按行读取或解析为记录；但任何外部数据在被信任之前都必须经过校验。
Validation checks whether data is sensible, using range, type, length, presence and format checks. Verification checks whether data has been entered accurately, for example by double entry or by a check digit. Keep these two terms strictly separate in your answers.
校验（validation）检查数据是否合理，使用范围、类型、长度、非空和格式检查；验证（verification）检查数据是否被准确录入，例如双重录入或校验位。作答时必须严格区分这两个术语。
10. Exam Technique and the Programming Project | 应试技巧与编程项目
Exam questions ask you to write pseudocode, complete a partially written algorithm, draw or fill in a trace table, and explain why one approach is preferable to another. Read the command word carefully: describe, explain and evaluate demand very different levels of detail.
考题要求你编写伪代码、补全残缺算法、绘制或填写追踪表，并解释为何某种方案更优。要仔细阅读指令词：
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图