📚 Edexcel A-Level Programming: Algorithms, Data Structures and Exam Skills | 爱德思A-Level编程：算法、数据结构与考试技巧
In Edexcel A-Level Computer Science, programming is not just about writing code; it is about solving problems with a clear, rigorous method. This revision guide covers the programming core: computational thinking, data representation in code, control structures, data structures, algorithms, efficiency, object-oriented programming and exam techniques.
在爱德思A-Level计算机科学中，编程不仅仅是编写代码，更是用清晰、严谨的方法解决问题。本复习指南涵盖编程核心：计算思维、代码中的数据表示、控制结构、数据结构、算法、效率、面向对象编程以及考试技巧。
1. Computational Thinking and Problem Decomposition | 计算思维与问题分解
Computational thinking has four pillars: decomposition, pattern recognition, abstraction and algorithm design. Decomposition breaks a large problem into smaller, manageable subproblems.
计算思维有四大支柱：分解、模式识别、抽象和算法设计。分解将大问题拆分为更小、可管理的子问题。
Abstraction removes unnecessary detail so you can focus on what matters. For example, a sat-nav models roads as a graph and ignores road surface colour.
抽象去除不必要的细节，使你能专注于关键内容。例如，卫星导航将道路建模为图，忽略路面颜色。
In exams, show decomposition by listing subproblems before coding. Write inputs, processes and outputs clearly in pseudocode.
在考试中，通过在编码前列出子问题来展示分解能力。在伪代码中清晰写出输入、处理过程和输出。
2. Programming Paradigms and Language Translators | 编程范式与语言翻译器
Edexcel expects you to understand procedural, object-oriented and declarative paradigms. Procedural programming organises code into functions and procedures that operate on data.
爱德思要求你理解面向过程、面向对象和声明式范式。面向过程编程将代码组织成对数据进行操作的函数和过程。
Object-oriented programming bundles data and behaviour into classes and objects, supporting encapsulation, inheritance and polymorphism.
面向对象编程将数据和行为封装到类和对象中，支持封装、继承和多态。
Compilers translate the whole source code into machine code before execution; interpreters translate and execute line by line. Know the trade-offs of each.
编译器在执行前将整个源代码翻译成机器码；解释器逐行翻译并执行。要了解两者的权衡。
3. Data Types, Variables and Constants | 数据类型、变量与常量
Use integer, real/float, Boolean, character and string types correctly. Choosing the right type affects memory use and the operations that are valid.
正确使用整数、实数/浮点数、布尔型、字符型和字符串类型。选择正确的类型会影响内存使用和有效操作。
Variables can change during program execution; constants are fixed at compile time or declared with a const keyword. Constants improve maintainability.
变量在程序执行期间可以改变；常量在编译时固定或用 const 关键字声明。常量提高可维护性。
Casting converts one data type to another, such as integer division or int('7'). Be careful with implicit versus explicit casting.
强制类型转换将一种数据类型转换为另一种，如整数除法或 int('7')。注意隐式和显式转换的区别。
4. Control Structures: Sequence, Selection, Iteration | 控制结构：顺序、选择、迭代
Every algorithm can be built from sequence, selection and iteration. Sequence executes statements in order; selection chooses paths with IF or CASE statements.
每种算法都可以由顺序、选择和迭代构建。顺序按次序执行语句；选择使用 IF 或 CASE 语句选择路径。
Iteration repeats code using FOR, WHILE or REPEAT...UNTIL loops. A FOR loop is count-controlled; WHILE and REPEAT are condition-controlled.
迭代使用 FOR、WHILE 或 REPEAT...UNTIL 循环重复代码。FOR 循环是计数控制；WHILE 和 REPEAT 是条件控制。
Trace tables are a powerful way to check loops and selection. Update variable values after each statement to find logic errors.
跟踪表是检查循环和选择的有力工具。在每条语句之后更新变量值，以发现逻辑错误。
5. Functions, Procedures and Recursion | 函数、过程与递归
A function returns a value; a procedure performs a task without returning a value. Use parameters to pass data into subroutines.
函数返回一个值；过程执行任务但不返回值。使用参数将数据传入子程序。
Recursion is when a subroutine calls itself. It needs a base case to stop and a recursive case that moves toward the base case.
递归是指子程序调用自身。它需要一个基本情况来停止，以及一个向基本情况推进的递归情况。
factorial(n) = n × factorial(n - 1), with factorial(0) = 1
with factorial(0) = 1. Recursion is elegant but can use more stack memory than iteration.
示例：factorial(n) = n × factorial(n - 1)，其中 factorial(0) = 1。递归优雅，但可能比迭代使用更多栈内存。
6. Arrays, Lists, Stacks and Queues | 数组、列表、栈与队列
Arrays store elements of the same data type in contiguous memory, accessed by index. 2D arrays model grids such as boards or images.
数组在连续内存中存储相同数据类型的元素，通过索引访问。二维数组可建模棋盘或图像等网格。
Lists are dynamic and can hold mixed types in high-level languages. Operations include append, insert, remove and search.
列表是动态的，在高级语言中可以容纳混合类型。操作包括追加、插入、删除和搜索。
Stacks are LIFO structures with push and pop. Queues are FIFO structures with enqueue and dequeue. Know typical uses: undo stacks, print queues, breadth-first traversal.
栈是后进先出结构，使用压入和弹出。队列是先进先出结构，使用入队和出队。要了解典型用途：撤销栈、打印队列、广度优先遍历。
7. Searching and Sorting Algorithms | 查找与排序算法
Linear search checks each element until the target is found; it works on unsorted data and has O(n) time complexity.
线性查找逐一检查每个元素直到找到目标；它适用于未排序数据，时间复杂度为 O(n)。
Binary search repeatedly halves a sorted array. It has O(log n) complexity. You must be able to write the pseudocode and trace midpoint calculations.
二分查找反复将已排序数组折半。时间复杂度为 O(log n)。你必须能够编写伪代码并跟踪中点的计算。
Sorting algorithms include bubble sort, insertion sort and merge sort. Bubble sort compares adjacent items; merge sort uses divide-and-conquer and has O(n log n) complexity.
排序算法包括冒泡排序、插入排序和归并排序。冒泡排序比较相邻项；归并排序使用分治法，时间复杂度为 O(n log n)。
| Algorithm 算法 | Best 最佳 | Average 平均 | Worst 最坏 | Space 空间 | Stable? 稳定? |
|---|---|---|---|---|---|
| Bubble sort 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | Yes 是 |
| Insertion sort 插入排序 | O(n) | O(n²) | O(n²) | O(1) | Yes 是 |
| Merge sort 归并排序 | O(n log n) | <
