📚 Edexcel A-Level Programming: Control Structures, Data Structures and Algorithm Efficiency | 爱德思A-Level编程：控制结构、数据结构与算法效率
In Edexcel A Level Computer Science, programming questions test both your ability to write clear pseudocode and your understanding of how data structures and algorithms behave under different conditions. A strong revision method is to learn the theory first and then apply it through hand tracing, because examiners reward precise use of terminology and systematic problem solving rather than lucky answers.
在爱德思 A Level 计算机科学中，编程题既考查你编写清晰伪代码的能力，也考查你对数据结构和算法在不同条件下表现的理解。有效的复习方法是先掌握理论，再通过手工跟踪来应用，因为考官奖励的是准确使用术语和系统化解决问题，而不是靠运气得出的答案。
1. Why Constructs, Data Structures and Efficiency Matter | 为什么控制结构、数据结构与效率如此重要
The programming paper is not a memory test. A question might ask you to write an algorithm, to complete a partially written algorithm, to trace the contents of a stack after a series of operations, or to compare the efficiency of two sorting methods on a large data set. In each case the marks come from three skills: choosing the right construct, choosing the right data structure, and justifying your choice with reference to time and space.
编程卷不是记忆测试。题目可能要求你编写算法、补全部分给出的算法、跟踪一系列操作后栈中的内容，或者比较大数量数据下两种排序方法的效率。每一种情况下，分数都来自三项技能：选择正确的控制结构、选择正确的数据结构，并引用时间与空间来论证你的选择。
Data structures and algorithms are examined together because they are two halves of one idea. A queue makes a breadth-first traversal natural; a stack makes recursion and depth-first traversal natural; a hash table makes average O(1) lookup possible but destroys ordering. If you can explain that relationship in one or two precise sentences, you are answering at the top of the mark scheme.
数据结构与算法总是一起考查，因为它们是同一个想法的两半。队列让广度优先遍历变得自然；栈让递归和深度优先遍历变得自然；哈希表让平均 O(1) 查找成为可能，却破坏了顺序。如果你能用一两句准确的话解释这种关系，你的答案就处在评分标准的顶端。
2. Programming Constructs: Sequence, Selection and Iteration | 编程结构：顺序、选择和迭代
All programs are built from three fundamental constructs: sequence, selection and iteration. Sequence means statements are executed one after another in the order written, from top to bottom. Selection allows the program to choose between alternative paths using conditions, such as IF, ELSE IF and ELSE statements, or CASE/SWITCH for multiple exclusive branches.
所有程序都由三种基本结构组成：顺序、选择和迭代。顺序指语句按照书写顺序由上到下一条接一条执行。选择使程序能够使用条件在多个路径之间进行选择，例如 IF、ELSE IF 和 ELSE 语句，或者使用 CASE/SWITCH 处理多个互斥分支。
Iteration repeats a block of code. Definite iteration uses FOR loops when the number of repetitions is known in advance, while indefinite iteration uses WHILE or REPEAT...UNTIL loops when the loop must continue until a condition changes. Edexcel pseudocode expects you to identify which type is most appropriate for a given problem, and to justify that decision in terms of the problem statement.
迭代重复执行一段代码。当重复次数事先已知时，使用 FOR 循环进行确定迭代；当循环必须持续到某个条件改变时，使用 WHILE 或 REPEAT...UNTIL 循环进行不定迭代。爱德思伪代码要求你能够识别对于给定问题哪种类型最合适，并根据题目描述论证这一决定。
- Sequence - instructions run once, in order, with no branching.
顺序 - 指令按顺序执行一次，没有分支。 - Selection - one path is chosen only if its condition evaluates to TRUE.
选择 - 只有当条件为 TRUE 时才执行对应路径。 - Definite iteration - repetition count is fixed before the loop starts.
确定迭代 - 循环开始前重复次数已固定。 - Indefinite iteration - repetition continues while a condition holds, or until it becomes true.
不定迭代 - 只要条件成立就继续，或者持续到条件变为真。
A common exam trap is the choice between WHILE and REPEAT...UNTIL. A WHILE loop tests the condition before the body, so the body may execute zero times. A REPEAT...UNTIL loop tests after the body, so the body always executes at least once. If a question says 'the user must enter at least one value', REPEAT...UNTIL is the correct structure, and stating that reason earns the mark.
一个常见的考试陷阱是 WHILE 与 REPEAT...UNTIL 的选择。WHILE 循环在循环体之前测试条件，因此循环体可能一次都不执行；REPEAT...UNTIL 循环在循环体之后测试条件，因此循环体至少执行一次。如果题目说"用户必须至少输入一个值"，正确结构是 REPEAT...UNTIL，并说明这一理由才能拿分。
3. Edexcel Pseudocode Conventions and Syntax | 爱德思伪代码规范与语法
Edexcel uses its own documented pseudocode, not Python and not Java. Marks are awarded for readable, unambiguous logic, and answers written in a language that ignores the conventions can still lose marks for unclear assignment or output. Learn the keyword list properly and use it consistently in every practice answer.
爱德思使用自己规定的伪代码，而不是 Python 或 Java。得分点在于逻辑可读、无歧义，而使用忽略这些约定的语言作答，仍可能因为赋值或输出表述不清而失分。请认真学习关键字表，并在每一次练习作答中保持一致使用。
| Purpose 用途 | Edexcel pseudocode 爱德思伪代码 |
| Declare a variable 声明变量 | DECLARE Count : INTEGER |
| Assign a value 赋值 | Count ← 0 |
| Input and output 输入输出 | INPUT Name / OUTPUT Score |
| Selection 选择 | IF ... THEN ... ELSE ... ENDIF |
| Multiple branches 多分支 | CASE OF ... OTHERWISE ... ENDCASE |
| Counted loop 计数循环 | FOR i ← 1 TO 10 ... NEXT i |
| Pre-condition loop 前测循环 | WHILE ... DO ... ENDWHILE |
| Post-condition loop 后测循环 | REPEAT ... UNTIL ... |
Two syntax habits protect marks. First, always declare variables with a type before using them, and use INTEGER, REAL, CHAR, STRING and BOOLEAN correctly. Second, indent consistently inside every conditional and loop body, so the marker can see exactly which statements belong to which block.
两个语法习惯可以保住分数。第一，使用变量前总是先声明并给出类型，正确使用 INTEGER、REAL、CHAR、STRING 和 BOOLEAN。第二，在每个条件和循环体内保持一致缩进，让阅卷人清楚看到哪些语句属于哪个代码块。
4. Nested Loops, Loop Control and Common Pitfalls | 嵌套循环、循环控制与常见错误
example, executes the innermost body N × N = N² times, which is exactly why nested loops are the standard source of quadratic time complexity.
循环可以相互嵌套，循环体总执行次数是各层迭代次数的乘积。例如对 N 个元素的双重循环，最内层循环体执行 N × N = N² 次，这正是嵌套循环成为二次时间复杂度标准来源的原因。
There are four errors that examiners see most often. An off-by-one error occurs when a loop runs one time too many or too few, for example FOR i ← 0 TO 9 when the array is indexed 1 to 10. An infinite loop occurs when the loop variable is never updated inside the body, or when the condition can never become false. A loop that modifies the counter inside the body can skip elements or terminate early. Finally, using a WHILE loop where the body must run at least once produces a logic error that only appears with particular input data.
考官最常看到四类错误。差一错误出现在循环多执行或少执行一次时，例如数组下标为 1 到 10，却写 FOR i ← 0 TO 9。死循环出现在循环变量在循环体内从不更新，或者条件永远无法变为假时。在循环体内修改计数器会跳过元素或提前结束。最后，在循环体必须至少执行一次时使用 WHILE 循环，会产生只在特定输入数据下才出现的逻辑错误。
Loop control also covers early exit. A linear search should stop as soon as the target is found, which is usually done with a Boolean flag such as Found ← TRUE plus an exit condition in the loop header. Writing the search so that it always scans the whole array wastes comparisons and loses the efficiency mark, even if the final answer is correct.
循环控制还包括提前退出。线性查找应在找到目标后立即停止，通常使用布尔标志，例如 Found ← TRUE，并在循环头中加入退出条件。如果让查找总是扫描整个数组，就浪费了比较次数，即使最终结果正确也会失掉效率分。
5. Subprograms, Parameters and Scope | 子程序、参数传递与作用域
Subprograms break a problem into reusable, testable units. A function returns a single value and is called inside an expression, while a procedure performs an action and may return nothing, or may return several values through its parameters. Decomposition is what makes a large algorithm traceable and a mark scheme generous.
子程序把问题拆分为可复用、可测试的单元。函数返回单一值，可在表达式内部调用；过程执行一个动作，可能不返回值，也可能通过参数返回多个值。正是分解让大型算法可跟踪，也让评分标准更宽容。
Parameters may be passed by value or by reference. Passing by value copies the data, so changes inside the subprogram do not affect the caller's variable. Passing by reference passes the address of the variable, so changes persist, which is useful when a procedure must update an array or return several results. In Edexcel answers, state the method explicitly and explain the consequence: 'passed by reference so the array is updated in place and no copy of the large data structure is made'.
参数可以按值传递或按引用传递。按值传递复制数据，因此子程序内部的改动不会影响调用者的变量。按引用传递传递变量的地址，因此改动会被保留，这在过程需要更新数组或返回多个结果时很有用。在爱德思作答时，要明确指出传递方式并解释后果："按引用传递，使数组被就地更新，同时不必复制这个大型数据结构"。
Scope describes where an identifier can be seen. Local variables exist only while the subprogram runs, protecting them from accidental change elsewhere; global variables are visible everywhere and make debugging harder because any part of the program may modify them. Prefer local variables with parameters, and say why in a discuss question.
作用域描述标识符在哪些位置可见。局部变量只在子程序运行期间存在，从而避免被其他地方意外修改；全局变量到处可见，会让调试更困难，因为程序的任何部分都可能修改它们。应优先使用局部变量加参数，并在论述题中说明理由。
6. Arrays, Records and Lists | 数组、记录与列表
An array stores a fixed number of elements of the same data type in contiguous positions, and elements are reached by index in constant time. Because the size is fixed at declaration, inserting or deleting in the middle requires shifting the remaining elements, which costs extra operations.
数组在连续位置中存储固定数量、同一数据类型的元素，通过下标可在常数时间内访问元素。由于大小在声明时固定，在中间插入或删除需要移动其余元素，会带来额外的操作开销。
A record groups related fields of different data types under one name, which is ideal for modelling an entity such as a student with a name, an ID and a mark. A list is usually implemented as a dynamic structure that can grow and shrink, so its length is not fixed in advance, but it is normally accessed sequentially rather than by index.
记录把不同数据类型的相关字段组合在一个名称下，非常适合为实体建模，例如含姓名、学号和分数的学生。列表通常实现为可增长和缩减的动态结构，其长度不必事先固定，但一般需要顺序访问而不是按下标访问。
Two-dimensional arrays are examined frequently because they model grids, tables and game boards. Access requires two indices, for example Grid[Row][Column], and a full traversal needs a nested loop. When you write one, state clearly whether the outer loop is over rows or columns, and keep the indices consistent with the declaration, since reversed indices are a common source of lost marks.
二维数组经常被考查，因为它们可以建模网格、表格和棋盘。访问需要两个下标，例如 Grid[Row][Column]，完整遍历需要嵌套循环。书写时要说清外层循环遍历行还是列，并保持下标与声明一致，因为下标颠倒是很常见的失分点。
7. Stacks, Queues and LIFO/FIFO Behaviour | 栈、队列与后进先出/先进先出
A stack is a last-in-first-out structure: the most recently pushed item is the first to be popped. Its core operations are push, pop, peek or top, and isEmpty. Because items are added and removed at one end only, the top pointer is the only position that changes.
栈是后进先出的结构：最后压入的元素最先弹出。其核心操作包括 push、pop、peek（或 top）以及 isEmpty。由于只在同一端添加和删除，只有栈顶指针会发生变化。
A queue is a first-in-first-out structure: the earliest enqueued item is the first to be dequeued. Operations are enqueue, dequeue, front and isEmpty, with separate front and rear pointers. In a circular queue, the rear pointer wraps back to index 0 when it reaches the end, so freed space at the front is reused instead of wasted.
队列是先进先出的结构：最早入队的元素最先出队。操作包括 enqueue、dequeue、front 和 isEmpty，拥有独立的前端与后端指针。在循环队列中，当后端指针到达末尾时回绕到下标 0，前端被释放的空间因此得到复用而不会浪费。
| Operation 操作 | Stack 栈 | Queue 队列 |
| Add 添加 | push to top 压入栈顶 | enqueue at rear 从后端入队 |
| Remove 删除 | pop from top 从栈顶弹出 | dequeue from front 从前端出队 |
| Order 顺序 | LIFO 后进先出 | FIFO 先进先出 |
| Pointer check 指针判断 | isEmpty tests top = -1 | isEmpty tests front = rear |
| Typical use 典型用途 | undo, recursion, DFS 撤销、递归、深度优先 | print jobs, BFS 打印任务、广度优先 |
Hand-tracing stack and queue questions is mechanical but unforgiving: draw the structure as boxes, label the pointers, and process one operation at a time. If a question says 'the queue is circular and has a maximum size of 5', check whether the queue is full before every enqueue and report the error condition rather than silently overwriting data.
栈和队列的手工跟踪题虽然机械，却很严格：把结构画成方格，标出指针，每次只处理一个操作。如果题目说"该队列为循环队列，最大容量为 5"，要在每次入队前检查队列是否已满，并报告错误状态，而不是悄悄覆盖数据。
8. Linked Lists, Hash Tables, Trees and Graphs | 链表、哈希表、树与图
A linked list stores each item in a node that also holds a pointer to the next node, and often to the previous one in a doubly linked list. Insertion and deletion are efficient because only pointers change, but access is sequential, so finding the nth item costs n steps.
链表把每个元素存放在节点中，节点还保存指向下一个节点的指针，在双向链表中往往还保存指向前一个节点的指针。插入和删除很高效，因为只需修改指针；但访问是顺序的，因此查找第 n 个元素需要 n 步。
A hash table applies a hash function to a key to compute a storage index, giving average constant-time insertion and lookup. Collisions are inevitable and are handled by chaining, where several keys share a bucket through a linked list, or by probing to the next free slot. Its weakness is that hash tables do not maintain order, so they cannot support range queries efficiently.
哈希表对键应用哈希函数计算出存储下标，从而实现平均常数时间的插入和查找。冲突不可避免，可用链地址法处理，即多个键通过链表共享一个桶，也可以探测下一个空槽。其缺点是哈希表不维持顺序，因此无法高效支持区间查询。
A binary search tree keeps smaller values in the left subtree and larger values in the right, so search, insertion and deletion take O(log n) time when the tree is balanced. If values are inserted in sorted order the tree degenerates into a linked list and performance falls back to O(n), which is why self-balancing variants exist. A graph represents arbitrary relationships as vertices and edges, and can be stored as an adjacency matrix or an adjacency list, the latter being more space-efficient for sparse graphs.
二叉搜索树把较小的值放在左子树、较大的值放在右子树，因此当树平衡时查找、插入和删除的时间复杂度为 O(log n)。如果按排序顺序插入，树会退化成链表，性能回落到 O(n)，这正是存在自平衡变体的原因。图用顶点和边表示任意关系，可用邻接矩阵或邻接表存储，对于稀疏图，邻接表更节省空间。
9. Measuring Algorithm Efficiency: Big-O and Time/Space Complexity | 衡量算法效率：大O记号与时间/空间复杂度
Efficiency describes how the number of operations grows as the input size n grows. Big-O notation gives an upper bound on that growth and ignores constants and lower-order terms, because they become irrelevant for large inputs. Writing O(2n + 5) is not wrong arithmetic, but the accepted answer is O(n).
效率描述当输入规模 n 增长时操作次数如何增长。大 O 记号给出该增长的上界，并忽略常数项和低阶项，因为它们在输入很大时变得无关紧要。写成 O(2n + 5) 在算术上并没有错，但被接受的答案是 O(n)。
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
| Complexity 复杂度 | Typical algorithm 典型算法 | Behaviour 表现 |
| O(1) 常数 | Array index, hash lookup 数组下标、哈希查找 | Independent of n 与 n 无关 |
| O(log n) 对数 | Binary search, balanced tree 二分查找、平衡树 | Halves the search space 每次减半 |
| O(n) 线性 | Linear search, one pass 线性查找、单次遍历 | One operation per item 每项一次操作 |
| O(n log n) | Merge sort, quick sort average 归并排序、快排平均 | Efficient comparison sorting 高效比较排序 |
| O(n²) 二次 | Bubble sort, insertion sort 冒泡、插入排序 | Nested loops over n |
Space complexity measures the extra memory an algorithm needs beyond the input. Merge sort is fast but requires an auxiliary array of size n, so its space complexity is O(n), whereas bubble sort sorts in place with O(1) extra space. Exam questions that say 'the device has limited memory' are asking you to trade time for space deliberately, and you must state both sides of that trade-off.
空间复杂度衡量算法在输入之外额外需要的内存。归并排序很快，但需要一个大小为 n 的辅助数组，因此空间复杂度为 O(n)；而冒泡排序就地排序，额外空间为 O(1)。题目一旦说"该设备内存有限"，就是要求你有意地在时间与空间之间取舍，你必须把取舍的两面都写出来。
10. Searching Algorithms: Linear vs Binary Search | 查找算法：线性查找与二分查找
A linear search checks each element in turn until the target is found or the list ends. It works on any list, sorted or not, and its worst-case time complexity is O(n), because the target may be the last element or absent entirely.
线性查找依次检查每个元素，直到找到目标或列表结束。它适用于任何列表，无论是否排序，最坏情况时间复杂度为 O(n)，因为目标可能是最后一个元素，或者根本不存在。
A binary search repeatedly halves a sorted list by comparing the target with the middle element. Its worst-case complexity is O(log n), so for one million items it needs at most about 20 comparisons, whereas a linear search could need one million. The price is that the data must be sorted first, and sorting itself costs O(n log n).
二分查找通过把目标与中间元素比较，反复将已排序列表减半。其最坏情况复杂度为 O(log n)，因此对一百万个元素最多约需 20 次比较，而线性查找可能需要一百万次。代价是数据必须先排序，而排序本身需要 O(n log n)。
Comparisons in binary search ≈ log₂n
A strong exam answer compares the two algorithms for the specific scenario given, rather than in general. For a list searched once, a linear search is better because sorting is unnecessary. For a large list searched many times, binary search wins overall because the one-off sorting cost is paid back quickly by the smaller number of comparisons per search.
优秀的考试答案会针对题目给出的具体场景比较两种算法，而不是泛泛而谈。对于只查找一次的列表，线性查找更好，因为无需排序。对于需要多次查找的大型列表，二分查找总体上更优，因为一次性排序成本会被每次查找更少的比较次数迅速抵消。
11. Sorting Algorithms: Bubble, Insertion, Merge and Quick Sort | 排序算法：冒泡、插入、归并
广告 / Sponsored剑桥国际化学考试备考练习Chemistry for Cambridge International AS & A Le…化学 备考教辅 · 正版现货 · 学习备考通用查看详情 / View on Taobao参考价 ¥288.0广告 / Sponsored英文原版 Oxford IB Diploma Programme Course Preparation: Physic…物理 备考教辅 · 正版现货 · 学习备考通用查看详情 / View on Taobao参考价 ¥254.0
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图