📚 Edexcel A-Level Programming: Core Constructs, Data Structures and Algorithms | Edexcel A-Level 编程：核心结构、数据结构与算法
In Edexcel A-Level Computer Science, programming is not just about writing code; it is about developing computational thinking, selecting appropriate data structures and algorithms, and evaluating efficiency and correctness. This article reviews the core programming concepts assessed in the specification, from basic constructs and data structures to searching, sorting, recursion, Big O notation and object-oriented programming.
在 Edexcel A-Level 计算机科学中，编程不仅是写代码，更是发展计算思维、选择合适的数据结构和算法，并评估效率与正确性。本文回顾考试大纲中评估的核心编程概念，从基本结构、数据结构到查找、排序、递归、大 O 表示法和面向对象编程。
1. Programming Constructs: Sequence, Selection, Iteration | 程序结构：顺序、选择、迭代
Every imperative program is built from three control constructs: sequence, selection (if, else, switch/case) and iteration (for, while, repeat-until). Sequence executes statements one after another; selection chooses between paths based on Boolean conditions; iteration repeats a block while a condition is true or for a fixed number of times.
每个命令式程序都由三种控制结构组成：顺序、选择（if、else、switch/case）和迭代（for、while、repeat-until）。顺序让语句依次执行；选择根据布尔条件在不同路径间选择；迭代在条件为真或固定次数内重复某一代码块。
Nested constructs are allowed, so an if can appear inside a loop, and a loop can appear inside another loop. Correct indentation and consistent use of logical conditions make nested constructs easier to trace during an exam.
嵌套结构是允许的，因此 if 可以出现在循环内部，循环也可以出现在另一个循环内部。正确的缩进和一致的逻辑条件使用可使嵌套结构在考试中更容易跟踪。
2. Data Types, Variables and Operators | 数据类型、变量与运算符
Primitive data types include integer, real/float, Boolean, character and string. Variables have an identifier, type and value; constants are declared once and cannot be modified. Operators enable arithmetic (+, -, *, /, MOD, DIV), comparison (=, <, >, <=, >=, <>) and logic (AND, OR, NOT).
基本数据类型包括整型、实数/浮点型、布尔型、字符型和字符串。变量由标识符、类型和值组成；常量一经声明不可修改。运算符支持算术运算（+、-、*、/、MOD、DIV）、比较运算（=、<、>、<=、>=、<>）和逻辑运算（AND、OR、NOT）。
Operator precedence determines the order of evaluation. In many languages NOT is evaluated before AND, and AND before OR. Parentheses should be used to make complex expressions unambiguous and to reduce logic errors.
运算符优先级决定求值顺序。在许多语言中 NOT 先于 AND 求值，AND 先于 OR。应使用括号使复杂表达式无歧义并减少逻辑错误。
3. Arrays and Lists | 数组与列表
Arrays store a fixed number of elements of the same data type, and elements are accessed by an index, usually starting from 0. Lists or dynamic arrays can grow and shrink, allowing insertion and deletion. Two-dimensional arrays represent tables and grids, such as a chessboard or spreadsheet.
数组存储固定数量且类型相同的元素，通过下标访问，下标通常从 0 开始。列表或动态数组可增长和收缩，支持插入和删除。二维数组用于表示表格和网格，如棋盘或电子表格。
Common array operations include traversal with a loop, searching for a value, updating an element, and calculating aggregate values such as sum, minimum and maximum. Bounds checking is essential because accessing an index outside the valid range causes an error.
常见数组操作包括使用循环遍历、查找值、更新元素以及计算总和、最小值和最大值等聚合值。边界检查非常重要，因为访问超出有效范围的下标会导致错误。
4. Stacks and Queues | 栈与队列
A stack follows LIFO (Last In First Out) behaviour; operations push, pop and peek. A queue follows FIFO (First In First Out) behaviour; operations enqueue and dequeue. Stacks support recursion, undo features and expression evaluation; queues are used in print spooling and CPU scheduling.
栈遵循后进先出（LIFO）规则；操作包括入栈、出栈和查看栈顶。队列遵循先进先出（FIFO）规则；操作包括入队和出队。栈支持递归、撤销功能和表达式求值；队列用于打印假脱机和 CPU 调度。
Both structures can be implemented using arrays or linked lists. In an array-based stack, a pointer tracks the top; in an array-based queue, front and rear pointers are needed to avoid shifting all elements after each dequeue.
两种结构都可以用数组或链表实现。在基于数组的栈中，一个指针跟踪栈顶；在基于数组的队列中，需要 front 和 rear 指针，以避免每次出队时移动所有元素。
5. Linear and Binary Search | 线性查找与二分查找
Linear search scans each element from the start until the target is found or the list ends. It works on unsorted data and has average time O(n). Binary search works only on sorted data: examine the middle element, then discard half of the remaining range. Binary search has time O(log n), requiring far fewer comparisons for large n.
线性查找从开头逐个扫描元素，直到找到目标或列表结束。它适用于未排序数据，平均时间复杂度为 O(n)。二分查找仅适用于有序数据：检查中间元素，然后舍弃剩余范围的一半。二分查找时间复杂度为 O(log n)，对于大数据量比较次数少得多。
Binary search: O(log n) vs linear search: O(n)
When the data is sorted and no insertions or deletions occur often, binary search is preferred. If the data is frequently updated, linear search may be simpler because maintaining sorted order adds overhead.
当数据已排序且不经常插入或删除时，优先使用二分查找。如果数据频繁更新，线性查找可能更简单，因为维护有序状态会增加额外开销。
6. Bubble, Insertion and Merge Sort | 冒泡、插入与归并排序
Bubble sort compares adjacent pairs and swaps if out of order; after each pass, the largest unsorted element ‘bubbles’ to its correct position. Insertion sort builds a sorted sublist by taking the next element and inserting it into the correct position. Merge sort uses divide and conquer: split the list into halves, sort each recursively, then merge the two sorted halves.
冒泡排序比较相邻元素并交换逆序对；每轮过后，未排序部分中的最大元素 “冒泡” 到正确位置。插入排序通过取出下一个元素并将其插入已排序子列表的正确位置来构建有序结果。归并排序采用分治策略：将列表分成两半，分别递归排序，然后合并两个有序子列表。
| Algorithm | Best | Average | Worst | 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 |
7. Recursion and the Call Stack | 递归与调用栈
A recursive subroutine calls itself with a smaller or simpler input. Every recursion must have a base case that stops the calls, otherwise infinite recursion causes a stack overflow. The call stack stores return addresses, parameters and local variables for each active call.
递归子程序用更小或更简单的输入调用自身。每次递归必须有一个基本情况来停止调用，否则无限递归会导致栈溢出。调用栈为每个活跃调用存储返回地址、参数和局部变量。
A classic example is factorial: factorial(n) = n × factorial(n-1) with factorial(0) = 1. Each recursive call pushes a new frame onto the stack; when the base case is reached, the frames pop off and return values multiply together.
经典示例是阶乘：factorial(n) = n × factorial(n-1)，且 factorial(0) = 1。每次递归调用将一个新帧压入栈中；到达基本情况后，这些帧弹出，返回值依次相乘。
factorial(n) = n × factorial(n-1), factorial(0) = 1
8. Big O Notation and Efficiency | 大 O 表示法与效率
Big O notation gives an upper bound for how time or space grows with input size n. Common classes are O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ). When analysing an algorithm, focus on the dominant term and ignore constants and lower-order terms.
大 O 表示法给出时间或空间随输入规模 n 增长的上界。常见类别有 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 和 O(2ⁿ)。分析算法时，关注主导项，忽略常数和低阶项。
Dominant term: 3n² + 5n + 2 = O(n²)
For example, a loop that visits every element once is O(n); two nested loops over the same array are O(n²). Space complexity is analysed in the same way, measuring additional memory used by an algorithm.
例如，访问每个元素一次的循环是 O(n)；对同一数组进行两个嵌套循环则是 O(n²)。空间复杂度以相同方式分析，衡量算法使用的额外内存。
9. Object-Oriented Programming Basics | 面向对象编程基础
Object-oriented programming organises code around classes and objects. A class is a blueprint with attributes and methods; an object is an instance. Encapsulation hides internal state behind an interface; inheritance allows a subclass to extend a superclass; polymorphism lets different classes respond to the same method call in their own way.
面向对象编程围绕类和对象组织代码。类是包含属性和方法的蓝图；对象是类的实例。封装将内部状态隐藏在接口之后；继承允许子类扩展父类；多态让不同类以各自方式响应同一方法调用。
These principles improve maintainability and reuse. For example, a superclass Vehicle can have method move(), while subclasses Car and Bicycle override move() with specific behaviour, demonstrating polymorphism.
这些原则提高了可维护性和复用性。例如，父类 Vehicle 可以有方法 move()，而子类 Car 和 Bicycle 用特定行为重写 move()，这就是多态。
10. Testing, Debugging and Trace Tables | 测试、调试
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课程辅导，国外大学本科硕士研究生博士课程论文辅导