📚 A-Level Edexcel Programming: Essential Algorithms and Data Structures | 爱德思A-Level编程：核心算法与数据结构
This revision guide covers the core programming topics examined in the Edexcel A-Level Computer Science specification. You will learn how to design, analyse, and implement algorithms using pseudocode and Python-style thinking, with a strong focus on data structures, searching, sorting, complexity, and object-oriented principles. The aim is to build both exam technique and real programming fluency.
本复习指南涵盖爱德思 A-Level 计算机科学考试中的核心编程主题。你将学习如何使用伪代码和 Python 风格思维来设计、分析和实现算法，重点关注数据结构、查找、排序、复杂度以及面向对象原则。目标是同时培养考试技巧和真实的编程能力。
1. Programming Fundamentals and Pseudocode | 编程基础与伪代码
In the Edexcel A-Level programming exam, candidates must be fluent in fundamental constructs such as variables, data types, assignment, selection (IF…THEN…ELSE…ENDIF), iteration (FOR…ENDFOR, WHILE…ENDWHILE, REPEAT…UNTIL), and subroutines (procedures and functions). Pseudocode is used to express algorithms clearly, so markers expect logical accuracy rather than language-specific syntax.
在爱德思 A-Level 编程考试中，考生必须熟练运用变量、数据类型、赋值、选择结构（IF…THEN…ELSE…ENDIF）、循环结构（FOR…ENDFOR、WHILE…ENDWHILE、REPEAT…UNTIL）以及子程序（过程和函数）等基本构造。考试使用伪代码清晰表达算法，因此评分者关注的是逻辑准确性，而不是特定语言的语法。
Common data types you need to recognise and use correctly in trace tables and code writing include:
在跟踪表和代码编写中，你需要正确识别和使用的常见数据类型包括：
| Data Type | Example | Used For |
|---|---|---|
| Integer | 42, -7 | Whole numbers, counts |
| Real / Float | 3.14, -0.5 | Decimal numbers, measurements |
| Boolean | TRUE, FALSE | Conditions, flags |
| Char | ‘A’, ‘9’ | Single symbols |
| String | “TutorHao” | Text, sequences of characters |
A typical pseudocode construct for validating input might look like this:
一个用于验证输入的典型伪代码结构如下：
REPEAT
INPUT score
UNTIL score >= 0 AND score <= 100
This loop keeps asking for a score until the value falls within the valid range. Understanding such constructs is vital because many Edexcel questions ask you to complete, correct, or write pseudocode from a given scenario.
这个循环会一直要求输入分数，直到数值落在有效范围内。理解这类结构至关重要，因为爱德思的许多题目要求你根据给定场景补全、修正或编写伪代码。
2. Searching Algorithms: Linear and Binary Search | 查找算法：线性查找与二分查找
A linear search examines each item in turn from the first to the last element. It works on unsorted data and is simple to implement, but in the worst case it must inspect every element. The maximum number of comparisons for a list of size n is:
线性查找从第一个元素到最后一个元素依次检查每一项。它适用于未排序的数据，并且实现简单，但在最坏情况下必须检查每一个元素。对于大小为 n 的列表，最大比较次数为：
Maximum comparisons = n
A binary search is far more efficient, but it requires the list to be sorted in ascending or descending order. It works by repeatedly dividing the search interval in half: compare the target value with the middle element, discard the half that cannot contain the target, and repeat until the item is found or the interval is empty. The worst-case number of comparisons is approximately:
二分查找的效率要高得多，但它要求列表按升序或降序排列。它的工作原理是不断将查找区间减半：将目标值与中间元素比较，丢弃不可能包含目标的那一半，重复直到找到目标或区间为空。最坏情况下的比较次数大约为：
Maximum comparisons = ⌈log₂(n+1)⌉
For example, searching a sorted array of 1,000,000 items with binary search requires at most about 20 comparisons, whereas linear search may need 1,000,000. In exam questions, you may be asked to perform a binary search step by step on a small list and record the middle index, the comparison, and the new search boundaries.
例如，对包含 1,000,000 个元素的有序数组进行二分查找最多只需约 20 次比较，而线性查找可能需要 1,000,000 次。在考试题目中，你可能需要在一个小列表上逐步执行二分查找，并记录中间索引、比较过程以及新的查找边界。
3. Sorting Algorithms: Bubble, Insertion, Merge Sort | 排序算法：冒泡、插入、归并排序
Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each full pass, the largest unsorted element ‘bubbles’ to its final position. It is easy to understand but inefficient for large datasets. The average and worst-case time complexity is O(n²).
冒泡排序反复比较相邻元素，如果顺序错误就交换它们。每完成一轮完整遍历，最大的未排序元素就会“冒泡”到它的最终位置。它容易理解，但对于大数据集效率较低。其平均和最坏情况时间复杂度为 O(n²)。
Insertion sort builds the sorted list one item at a time by taking the next item and inserting it into its correct place among the already sorted items. It is efficient for small or nearly sorted lists and is stable. Its average and worst-case time complexity is also O(n²), but its best case is O(n) when the input is already sorted.
插入排序通过每次取出下一个元素并将其插入到已排序部分的正确位置，逐步构建有序列表。它对于小型或基本有序的列表效率较高，而且是稳定排序。其平均和最坏情况时间复杂度也是 O(n²)，但当输入已经有序时，最好情况为 O(n)。
Merge sort is a divide-and-conquer algorithm: it splits the list into two halves, recursively sorts each half, and then merges the two sorted halves back together. It guarantees O(n log n) time complexity in all cases, but it requires additional memory for the merging process. Edexcel questions often ask you to compare these algorithms in terms of efficiency, stability, and memory usage.
归并排序是一种分治算法：它将列表分成两半，递归地对每一半进行排序，然后将两个已排序的一半合并在一起。它在所有情况下都能保证 O(n log n) 的时间复杂度，但在合并过程中需要额外的内存。爱德思的题目经常要求你从效率、稳定性和内存使用方面比较这些算法。
| Algorithm | Best Case | Average Case | Worst Case | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(n²) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
4. Time and Space Complexity | 时间与空间复杂度
Big O notation describes how the running time or memory usage of an algorithm grows as the input size n increases. It ignores constant factors and lower-order terms, focusing on the dominant term that determines scalability. For Edexcel, you need to identify the order of complexity from pseudocode, especially loops and nested loops.
大 O 表示法描述算法的运行时间或内存使用量如何随着输入规模 n 的增长而增长。它忽略常数因子和低阶项，重点关注决定可扩展性的主导项。对于爱德思考试，你需要从伪代码中识别复杂度的阶，尤其是循环和嵌套循环。
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
A single loop that runs n times has O(n) complexity. Two nested loops, each running n times, give O(n²). A loop that halves the problem each time, such as in binary search, has O(log n). Recursive algorithms often have logarithmic or exponential complexity depending on whether the problem is split or duplicated.
一个运行 n 次的单层循环具有 O(n) 复杂度。两个各运行 n 次的嵌套循环产生 O(n²)。每次将问题规模减半的循环（例如二分查找）具有 O(log n) 复杂度。递归算法可能具有对数或指数复杂度，具体取决于问题是拆分还是复制。
Space complexity is also important: merge sort needs O(n) extra space for merging, while bubble sort and insertion sort need only O(1) additional space because they sort in place. Exam questions may ask you to justify why one algorithm is preferred over another given a memory constraint.
空间复杂度也很重要：归并排序在合并时需要 O(n) 的额外空间，而冒泡排序和插入排序只需要 O(1) 的额外空间，因为它们是原地排序。考试题目可能会要求你在给定内存限制的情况下，说明为什么优先选择某种算法而不是另一种。
5. Abstract Data Types: Stacks and Queues | 抽象数据类型：栈和队列
A stack is a Last-In-First-Out (LIFO) data structure. The main operations are push (add an item to the top), pop (remove and return the top item), and peek (look at the top item without removing it). Stacks are used in program call stacks, undo features, and evaluating expressions.
栈是一种后进先出（LIFO）的数据结构。主要操作是 push（将元素添加到栈顶）、pop（移除并返回栈顶元素）以及 peek（查看栈顶元素但不移除）。栈用于程序调用栈、撤销功能以及表达式求值。
A queue is a First-In-First-Out (FIFO) data structure. The main operations are enqueue (add an item to the rear), dequeue (remove and return the front item), and sometimes isFull / isEmpty checks. Queues model waiting lines, keyboard buffers, and printer spooling.
队列是一种先进先出（FIFO）的数据结构。主要操作是 enqueue（将元素添加到队尾）、dequeue（移除并返回队首元素），有时还有 isFull / isEmpty 检查。队列用于模拟排队、键盘缓冲区和打印机假脱机。
In pseudocode, a stack can be represented with an array and a top pointer, while a queue needs front and rear pointers. You should be able to trace the contents after a series of push, pop, enqueue, or dequeue operations, and to identify underflow (trying to remove from an empty structure) and overflow (trying to add to a full structure).
在伪代码中，栈可以用一个数组和一个顶端指针表示，而队列需要前端指针和尾端指针。你应该能够在一系列 push、pop、enqueue 或 dequeue 操作之后跟踪数据结构的内容，并能识别下溢（试图从空结构中删除）和上溢（试图向已满结构中添加）。
6. Linked Lists and Arrays | 链表与数组
Arrays store elements in contiguous memory locations and allow direct access by index in O(1) time. However, inserting or deleting an element in the middle requires shifting subsequent elements, taking O(n) time. Array size is usually fixed at creation in lower-level implementations.
数组将元素存储在连续的内存位置中，并且允许通过索引在 O(1) 时间内直接访问。然而，在中间插入或删除元素需要移动后续元素，耗时 O(n)。在较低级别的实现中，数组大小通常在创建时固定。
A linked list stores each element in a node that contains the data and a pointer to the next node. It does not require contiguous memory and can grow dynamically. Insertion and deletion at a known position take O(1) time if you have a pointer to that position, but accessing an element by index takes O(n) because you must traverse from the head.
链表将每个元素存储在一个节点中，该节点包含数据和指向下一个节点的指针。它不需要连续内存，并且可以动态增长。如果已知位置的指针，在该位置插入和删除的时间为 O(1)，但按索引访问元素需要 O(n)，因为必须从头开始遍历。
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Contiguous | Non-contiguous |
| Access time | O(1) | O(n) |
| Insert/delete at known position | O(n) | O(1) |
| Memory overhead | None | Pointer per node |
| Size flexibility | Usually fixed | Dynamic |
7. Recursion and Iteration | 递归与迭代
Recursion is a technique where a subroutine calls itself to solve a smaller instance of the same problem. Every correct recursive algorithm must have at least one base case that stops the recursion and at least one recursive step that moves towards that base case. Without a base case, the recursion continues until stack overflow.
递归是一种技术，子程序调用自身来解决同一问题的较小实例。每个正确的递归算法必须至少有一个停止递归的基本情况，以及至少一个向基本情况靠近的递归步骤。没有基本情况，递归会一直持续到栈溢出。
A classic example is the factorial function. The recursive definition is:
一个经典的例子是阶乘函数。其递归定义如下：
n! = n × (n-1)! for n > 1, and 1! = 1
Iteration uses loops such as FOR or WHILE to repeat a block of code. It is generally more memory-efficient because it does not add a new stack frame for each call. Recursion, however, can make some algorithms much easier to express, especially divide-and-conquer algorithms like merge sort and tree traversals.
迭代使用 FOR 或 WHILE 等循环重复执行一段代码。它通常更节省内存，因为不会为每次调用添加新的栈帧。然而，递归可以使一些算法表达起来简单得多，尤其是诸如归并排序和树遍历这样的分治算法。
In the exam, you may be asked to convert a simple recursive routine into an iterative one, or to trace a recursive call with a stack. Always identify the base case first, then check how parameters change in each recursive call.
在考试中，你可能需要将一个简单的递归例程转换为迭代例程，或者用栈跟踪一个递归调用。务必先找出基本情况，然后检查参数在每次递归调用中如何变化。
8. Object-Oriented Programming Concepts | 面向对象编程概念
Object-oriented programming (OOP) organises code into classes that define attributes (data) and methods (behaviour). An object is an instance of a class. Edexcel expects you to understand classes, objects, inheritance, polymorphism, and encapsulation, and to interpret simple class diagrams.
面向对象编程（OOP）将代码组织为类，类定义了属性（数据）和方法（行为）。对象是类的一个实例。爱德思考试要求你理解类、对象、继承、多态和封装，并能解读简单的类图。
Encapsulation means bundling data and the methods that operate on that data within one class, and hiding internal details by making attributes private. Access is provided through public methods such as getters and setters. This protects data integrity and reduces coupling.
封装指将数据和操作这些数据的方法捆绑在一个类中，并通过将属性设为私有来隐藏内部细节。访问通过 getter 和 setter 等公共方法提供。这保护了数据完整性并降低了耦合。
Inheritance allows a new class (subclass) to acquire the attributes and methods of an existing class (superclass). For example, a Dog class and a Cat class could both inherit from an Animal class. Polymorphism lets objects of different subclasses respond differently to the same method call, such as each animal making its own sound.
继承允许新类（子类）获取现有类（超类）的属性和方法。例如，Dog 类和 Cat 类都可以继承自 Animal 类。多态性允许不同子类的对象对同一方法调用作出不同响应，例如每个动物发出自己的叫声。
A typical Edexcel question might give you a class definition and ask you to identify the constructor, private attributes, public methods, or to write a subclass. Pay close attention to the syntax used in the question paper, which is often simplified pseudocode or Python-like.
典型爱德思题目可能给出一个类定义，要求你确定构造函数、私有属性、公共方法，或编写一个子类。请密切注意试卷中使用的语法，通常是简化的伪代码或类似 Python 的语法。
9. File Handling and Exception Handling | 文件处理与异常处理
Programs often need to read from and write to external text files. The standard sequence is open the file in the correct mode, perform read or write operations, and then close the file. In pseudocode, you may see commands such as OPENFILE, READFILE, WRITEFILE, and CLOSEFILE.
程序通常需要从外部文本文件读取数据和向其中写入数据。标准顺序是以正确的模式打开文件，执行读取或写入操作，然后关闭文件。在伪代码中，你可能会看到 OPENFILE、READFILE、WRITEFILE 和 CLOSEFILE 等命令。
Exception handling is used to manage runtime errors such as trying to open a missing file, dividing by zero, or converting an invalid string to a number. A TRY…EXCEPT block lets the program catch the error and take a controlled action instead of crashing. Edexcel questions may ask you to identify which exception could occur and how to handle it.
异常处理用于管理运行时错误，例如试图打开不存在的文件、除以零或将无效字符串转换为数字。TRY…EXCEPT 块允许程序捕获错误并采取可控措施，而不是崩溃。爱德思题目可能会要求你判断可能发生哪种异常以及如何处理它。
For example, when reading a file of student scores, you should check that the file exists before opening it, and when converting each line to an integer, you should handle the possibility of a non-numeric value. This demonstrates robust programming, which is a recurring theme in the specification.
例如，在读取学生成绩文件时，你应在打开文件前检查文件是否存在；在将每一行转换为整数时，应处理可能出现的非数字值。这体现了健壮编程，也是考试大纲中反复出现的主题。
10
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply