📚 Edexcel A Level Programming: Computational Thinking, Data Structures and Algorithms | Edexcel A Level 编程：计算思维、数据结构与算法
Welcome to this Edexcel A Level programming revision guide. We will explore the core computational thinking, data structures, algorithms, and object-oriented programming techniques that frequently appear in both Paper 1 and the practical Paper 2. Each section links directly to the Edexcel specification, so use this as a structured revision companion.
欢迎使用本 Edexcel A Level 编程复习指南。我们将探索核心的计算思维、数据结构、算法和面向对象编程技术，这些内容经常出现在 Paper 1 和实际操作 Paper 2 中。每一节都与 Edexcel 考试大纲直接对应，请将其作为结构化的复习伴侣。
1. Computational Thinking and Problem Decomposition | 计算思维与问题分解
Computational thinking involves breaking a complex problem into smaller, manageable parts. Edexcel distinguishes three key skills: abstraction, decomposition, and algorithmic thinking. Abstraction removes unnecessary detail so you can focus on the essential features of a problem.
计算思维涉及将一个复杂问题分解为更小、更易处理的部分。Edexcel 区分了三种关键技能：抽象、分解和算法思维。抽象去除不必要的细节，使你能专注于问题的本质特征。
Decomposition is the process of splitting a large program into modules, functions, or procedures. This makes code easier to write, test, and maintain. Algorithmic thinking then builds a step-by-step solution that can be implemented in a programming language.
分解是将大型程序拆分为模块、函数或过程的过程。这使代码更易于编写、测试和维护。算法思维则构建一个可逐步实施的解决方案，并能用编程语言实现。
In exams, you may be asked to decompose a scenario such as a library management system into input, process, and output stages. This skill is also essential for writing clear pseudocode before coding.
在考试中，你可能会被要求将一个场景（例如图书馆管理系统）分解为输入、处理和输出阶段。这项技能对于在编码前编写清晰的伪代码也至关重要。
2. Data Types, Variables and Constants | 数据类型、变量与常量
Edexcel expects you to understand primitive data types: integer, real/float, Boolean, character, and string. Choosing the correct data type affects memory usage and the operations that can be performed. For example, dividing two integers in Python using / produces a float, while // gives integer division.
Edexcel 要求你理解原始数据类型：整数、实数/浮点数、布尔值、字符和字符串。选择正确的数据类型会影响内存使用和可执行的操作。例如，在 Python 中使用 / 对两个整数进行除法会得到浮点数，而使用 // 则进行整数除法。
Variables are named storage locations whose values can change during execution. Constants are fixed values that cannot be modified after declaration. In pseudocode, constants are often written in uppercase, such as PI = 3.14, to signal that they should not change.
变量是命名的存储位置，其值在程序执行期间可以改变。常量是声明后不可修改的固定值。在伪代码中，常量通常用大写字母表示，例如 PI = 3.14，以表示它们不应改变。
Casting or type conversion is frequently examined. You should know how to convert between types, such as str(42) to produce “42” or int(“7”) to produce 7, and why invalid conversions cause runtime errors.
类型转换是常见考点。你应该知道如何在类型之间转换，例如 str(42) 生成 “42” 或 int(“7”) 生成 7，以及为什么无效转换会导致运行时错误。
3. Control Structures: Sequence, Selection, Iteration | 控制结构：顺序、选择、迭代
All programs are built from three control structures. Sequence means statements execute one after another in order. Selection uses conditions to decide which block of code runs, typically with IF, ELSE IF, and ELSE statements.
所有程序都由三种控制结构组成。顺序意味着语句按顺序逐条执行。选择使用条件来决定执行哪个代码块，通常使用 IF、ELSE IF 和 ELSE 语句。
Iteration repeats a block of code. Edexcel distinguishes count-controlled loops, such as FOR i = 1 TO 10, from condition-controlled loops, such as WHILE score < 100. A REPEAT…UNTIL loop always runs at least once because the condition is checked after the loop body.
迭代重复执行代码块。Edexcel 区分计数控制循环（例如 FOR i = 1 TO 10）和条件控制循环（例如 WHILE score < 100）。REPEAT…UNTIL 循环总是至少执行一次，因为条件在循环体之后检查。
Nested loops and nested selection are common in exam questions. When tracing nested loops, write a trace table to record variable values at each step. This avoids losing marks from off-by-one errors.
嵌套循环和嵌套选择在考试题目中很常见。在追踪嵌套循环时，编写跟踪表来记录每一步的变量值。这可以避免因差一错误而失分。
4. Functions, Procedures and Parameter Passing | 函数、过程与参数传递
Functions and procedures are blocks of reusable code. A function returns a value, while a procedure performs a task without returning a value. In Python, procedures are simply functions that return None, but in pseudocode Edexcel often writes PROCEDURE and ENDPROCEDURE.
函数和过程是可重用的代码块。函数返回一个值，而过程执行任务但不返回值。在 Python 中，过程只是返回 None 的函数，但在伪代码中 Edexcel 通常写 PROCEDURE 和 ENDPROCEDURE。
Parameter passing can be by value or by reference. Passing by value gives the function a copy, so changes inside the function do not affect the original variable. Passing by reference gives the function the actual memory location, so changes do affect the original variable. Edexcel requires you to explain the difference and identify which is used in a given code fragment.
参数传递可以按值或按引用进行。按值传递会给函数一个副本，因此函数内部的更改不会影响原始变量。按引用传递将实际内存位置交给函数，因此更改确实会影响原始变量。Edexcel 要求你解释两者的区别，并识别给定代码片段中使用的是哪一种。
Local and global variables are another common topic. A local variable declared inside a function cannot be accessed outside it, while a global variable is accessible throughout the program. Using too many global variables makes code harder to debug.
局部变量和全局变量是另一个常见主题。在函数内部声明的局部变量无法在外部访问，而全局变量可以在整个程序中访问。使用过多的全局变量会使代码更难调试。
5. Recursion and the Call Stack | 递归与调用栈
Recursion occurs when a function calls itself. Every recursive algorithm needs a base case to stop the recursion, otherwise it will cause a stack overflow. A classic example is factorial: fact(n) = n × fact(n – 1) with base case fact(0) = 1.
递归发生在函数调用自身时。每个递归算法都需要一个基准情形来停止递归，否则将导致栈溢出。一个经典例子是阶乘：fact(n) = n × fact(n – 1)，基准情形为 fact(0) = 1。
When a recursive call is made, the current function state is pushed onto the call stack. Once the base case is reached, calls are popped off the stack and return values are combined. This is why recursion can use more memory than iteration.
当进行递归调用时，当前函数状态被压入调用栈。一旦达到基准情形，调用就会从栈中弹出，返回值被组合起来。这就是递归可能比迭代使用更多内存的原因。
Edexcel questions often ask you to trace a recursive function or compare recursion with iteration. You should be able to identify the base case, the recursive call, and how the stack builds up.
Edexcel 题目经常要求你追踪递归函数或比较递归与迭代。你应该能够识别基准情形、递归调用以及栈是如何累积的。
6. Arrays, Lists and Records | 数组、列表与记录
Arrays and lists are used to store multiple items under one identifier. In Edexcel pseudocode, arrays are usually declared with a fixed size, such as ARRAY scores[5], while lists can grow dynamically. Both are indexed from 0 in most languages, but check the question’s convention.
数组和列表用于在一个标识符下存储多个项目。在 Edexcel 伪代码中，数组通常以固定大小声明，例如 ARRAY scores[5]，而列表可以动态增长。在大多数语言中，两者的索引都从 0 开始，但要检查题目中的约定。
Records allow you to group related data of different types under one name. A student record might contain name as string, age as integer, and averageScore as real. This is similar to a class without methods in object-oriented programming.
记录允许你将不同类型的数据组合到一个名称下。一个学生记录可能包含字符串类型的姓名、整数类型的年龄和实数类型的平均分。这类似于面向对象编程中没有方法的类。
Two-dimensional arrays are often tested with board games or matrices. You should be able to access grid[2][3] and use nested loops to initialise, search, or display the array.
二维数组经常通过棋盘游戏或矩阵进行测试。你应该能够访问 grid[2][3]，并使用嵌套循环来初始化、搜索或显示数组。
7. Abstract Data Types: Stacks and Queues | 抽象数据类型：栈与队列
A stack is a Last In First Out (LIFO) data structure. The main operations are push (add to top), pop (remove from top), and peek or top (view top element without removing). Stacks are used for function calls, undo features, and depth-first search.
栈是一种后进先出（LIFO）的数据结构。主要操作包括 push（添加到顶部）、pop（从顶部移除）以及 peek 或 top（查看顶部元素而不移除）。栈用于函数调用、撤销功能和深度优先搜索。
A queue is a First In First Out (FIFO) data structure. The main operations are enqueue (add to rear) and dequeue (remove from front). Queues are used in printer spooling, keyboard buffers, and breadth-first search.
队列是一种先进先出（FIFO）的数据结构。主要操作包括 enqueue（添加到队尾）和 dequeue（从队首移除）。队列用于打印机假脱机、键盘缓冲区和广度优先搜索。
When implementing stacks or queues with arrays, you need to handle overflow and underflow. In Edexcel exams, you may be asked to draw the data structure after a series of operations or write pseudocode for circular queue logic.
使用数组实现栈或队列时，你需要处理上溢和下溢。在 Edexcel 考试中，你可能会被要求在一系列操作后绘制数据结构，或编写循环队列逻辑的伪代码。
8. Searching Algorithms and Binary Search | 查找算法与二分查找
Linear search checks each element in sequence until the target is found or the list ends. It works on unsorted data and has time complexity O(n) in the worst case. It is simple to implement but inefficient for large lists.
线性查找按顺序检查每个元素，直到找到目标或列表结束。它适用于未排序的数据，最坏情况的时间复杂度为 O(n)。它实现简单，但对于大型列表效率较低。
Binary search requires a sorted list. It repeatedly compares the target with the middle element and discards half of the remaining list. The worst-case time complexity is O(log₂ n), which grows much more slowly than O(n).
二分查找要求列表已排序。它反复将目标值与中间元素进行比较，并丢弃剩余列表的一半。最坏情况的时间复杂度为 O(log₂ n)，其增长速度远慢于 O(n)。
mid = (low + high) ÷ 2
When tracing binary search, show the low, mid, and high indices at each step. Edexcel often asks for the number of comparisons needed to find or fail to find a target in a list of size n.
在追踪二分查找时，展示每一步的 low、mid 和 high 索引。Edexcel 经常要求计算在大小为 n 的列表中查找或未找到目标所需的比较次数。
9. Sorting Algorithms and Complexity Analysis | 排序算法与复杂度分析
Bubble sort compares adjacent pairs and swaps them if they are in the wrong order. After each pass, the largest unsorted element bubbles to the end. Its average and worst-case complexity is O(n²), making it inefficient for large lists.
冒泡排序比较相邻元素对，如果顺序错误则交换。每一轮之后，最大的未排序元素会冒泡到末尾。它的平均和最坏情况复杂度为 O(n²)，对于大型列表效率较低。
Insertion sort builds a sorted portion at the front by inserting each new element into its correct position. It is also O(n²), but it performs well on nearly sorted data and is stable.
插入排序通过将每个新元素插入到正确位置，在前面构建有序部分。它同样是 O(n²)，但在几乎有序的数据上表现良好，并且是稳定的。
Merge sort uses a divide-and-conquer approach: split the list in half recursively, sort each half, then merge the sorted halves. Its time complexity is O(n log n) in all cases, which is significantly better than bubble or insertion sort. Quick sort also uses divide and conquer but has worst-case O(n²) if the pivot is poorly chosen.
归并排序采用分治法：递归地将列表分成两半，对每一半进行排序，然后合并已排序的两半。其时间复杂度在所有情况下都是 O(n log n)，明显优于冒泡或插入排序。快速排序也使用分治法，但如果枢轴选择不当，最坏情况为 O(n²)。
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) |
| Insertion sort | O(n) | O(n²) | O(n²) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) |
In Edexcel exams, you may be asked to complete a pass of bubble sort or show how merge sort splits and merges. Always state the number of comparisons or swaps when required.
在 Edexcel 考试中，你可能会被要求完成冒泡排序的一轮，或展示归并排序如何分割和合并。需要时始终说明比较或交换的次数。
10. Object-Oriented Programming: Encapsulation, Inheritance, Polymorphism | 面向对象编程：封装、继承与多态
Object-oriented programming (OOP) organises code into classes and objects. A class is a blueprint, while an object is an instance of that class. Edexcel focuses on three key principles: encapsulation, inheritance, and polymorphism.
面向对象编程（OOP）将代码组织为类和对象。类是蓝图，而对象是该类的实例。Edexcel 重点关注三个关键原则：封装、继承和多态。
Encapsulation bundles data and the methods that operate on that data into a single unit. Access modifiers such as private and public control how attributes can be accessed or changed. This protects data integrity and reduces unintended interference.
封装将数据和操作这些数据的方法捆绑到一个单元中。私有和公共等访问修饰符控制属性的访问或修改方式。这保护了数据完整性并减少了意外干扰。
Inheritance allows a new class to derive properties and methods from an existing class. The child class can extend or override the parent’s behaviour. For example, a Dog class might inherit from an Animal class and override the speak() method.
继承允许新类从现有类派生属性和方法。子类可以扩展或覆盖父类的行为。例如，Dog 类可以继承 Animal 类并覆盖 speak() 方法。
Polymorphism means “many forms.” It lets the same method call behave differently depending on the object type. In a list of Animal objects, calling speak() might produce “Woof” for a Dog and “Meow” for a Cat.
多态意味着“多种形态”。它让同一个方法调用根据对象类型产生不同行为。在一个 Animal 对象列表中，调用 speak() 可能对 Dog 产生 “Woof”，对 Cat 产生 “Meow”。
11. Testing, Debugging and Error Handling | 测试、调试与错误处理
Testing ensures a program meets its specification. Edexcel distinguishes between white-box testing, where the internal code structure is known, and black-box testing, where only inputs and expected outputs are considered. Both are needed for robust software.
测试确保程序符合其规格说明。Edexcel 区分白盒测试（内部代码结构已知）和黑盒测试（只考虑输入和预期输出）。两者对于健壮的软件都是必需的。
Error types are a key exam topic. Syntax errors occur when code breaks language rules, such as missing colons. Runtime errors happen during execution, such as division by zero. Logic errors produce incorrect results but do not crash the program.
错误类型是重要的考试主题。语法错误发生在代码违反语言规则时，例如缺少冒号。运行时错误在执行期间发生，例如除以零。逻辑错误产生错误结果但不会使程序崩溃。
Debugging techniques include using breakpoints, print statements, and trace tables. You should be able to identify the type of error in a code snippet and suggest a fix. Boundary testing with values at the edge of valid ranges is particularly important.
调试技术包括使用断点、打印语句和跟踪表。你应该能够识别代码片段中的错误类型并提出修复建议。对有效范围边缘的值进行边界测试尤其重要。
12. Computational Complexity and Big O Notation | 计算复杂度与大O表示法
Big O notation describes how an algorithm’s time or space requirements grow as the input size n increases. It focuses on the dominant term and ignores constants and lower-order terms. For example, 3n² + 5n + 2 is simplified to O(n²).
大O表示法描述算法的执行时间或空间需求如何随输入规模 n 增大而增长。它只关注主导项，忽略常数和低阶项。例如，3n² + 5n + 2 简化为 O(n²)。
Common complexity classes from best to worst are: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, and O(2ⁿ) exponential. Edexcel expects you to compare algorithms using these classes.
常见复杂度等级从优到劣依次为：O(1) 常数、O(log n) 对数、O(n) 线性、O(n log n) 线性对数、O(n²) 平方和 O(2ⁿ) 指数。Edexcel 希望你使用这些等级比较算法。
To determine complexity, count the number of primitive operations as a function of n. A simple loop running n times is O(n). A nested loop running n × n times is O(n²). A binary search halves the search space each step, so it is O(log n).
要确定复杂度，计算原始操作数量作为 n 的函数。一个运行 n 次的简单循环是 O(n)。一个运行 n × n 次的嵌套循环是 O(n²)。二分查找每一步将搜索空间减半，所以是 O(log n)。
Understanding Big O
Published by TutorHao | A-Level 编程 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导