Programming Constructs, Data Structures and Algorithms | 编程结构、数据结构与算法

📚 Programming Constructs, Data Structures and Algorithms | 编程结构、数据结构与算法

In Edexcel A-Level Computer Science, programming is assessed through both theory and practical problem solving. This revision guide summarises the essential programming constructs, data structures and algorithms you need to master for Paper 1 and Paper 2.

在 Edexcel A-Level 计算机科学中，编程通过理论和实践问题求解进行考核。本复习指南总结了 Paper 1 和 Paper 2 必须掌握的核心编程结构、数据结构和算法。

---

1. Computational Thinking and Programming Paradigms | 计算思维与编程范式

Computational thinking involves decomposition, pattern recognition, abstraction and algorithm design. Edexcel questions often ask you to break a problem into manageable parts before coding.

计算思维包括分解、模式识别、抽象和算法设计。Edexcel 考题经常要求你在编码前把问题分解成可管理的部分。

Programming paradigms include procedural, object-oriented and functional approaches. At A-Level, you mainly apply procedural and object-oriented techniques using Python or another high-level language.

编程范式包括过程式、面向对象和函数式方法。在 A-Level 中，你主要使用 Python 或其他高级语言应用过程式和面向对象技术。

---

2. Data Types, Variables and Constants | 数据类型、变量与常量

A variable is a named memory location whose value can change during execution. A constant is fixed at compile time or by convention and cannot be changed.

变量是命名的内存位置，其值在执行过程中可以改变。常量在编译时或按约定固定，不能更改。

Common primitive data types include integer, real/float, Boolean and character. Composite types include strings, arrays and records.

常见基本数据类型包括整数、实数/浮点数、布尔值和字符。复合类型包括字符串、数组和记录。

Data Type | 数据类型	Example | 示例	Notes | 说明
Integer | 整数	42, -7, 0	Whole numbers | 整数
Real/Float | 实数/浮点数	3.14, -0.5	Decimal values | 小数值
Boolean | 布尔值	True, False	Logical values | 逻辑值
Character | 字符	‘A’, ‘9’, ‘?’	Single symbol | 单个符号
String | 字符串	‘hello’	Sequence of characters | 字符序列

Correct type selection affects memory usage and the operations available. For example, integer division truncates the result, while real division preserves the fractional part.

正确选择数据类型会影响内存使用和可用的操作。例如，整数除法会截断结果，而实数除法保留小数部分。

---

3. Sequence and Selection | 顺序与选择结构

Sequence means statements execute one after another in order. Every program relies on sequence as its default control flow.

顺序意味着语句一条接一条按顺序执行。每个程序都依赖顺序作为默认控制流。

Selection allows branching using if, elif and else. Nested selection can model complex conditions but must be indented clearly.

选择允许使用 if、elif 和 else 进行分支。嵌套选择可以模拟复杂条件，但必须清晰缩进。

Boolean operators AND, OR and NOT combine conditions. Edexcel expects you to evaluate truth tables for these operators.

布尔运算符 AND、OR 和 NOT 用于组合条件。Edexcel 要求你评估这些运算符的真值表。

Comparison operators such as ==, !=, <, >, <= and >= return Boolean values. A common mistake is using a single equals sign = instead of == in a condition.

比较运算符如 ==、!=、<、>、<= 和 >= 返回布尔值。常见错误是在条件中使用单个等号 = 而不是 ==。

---

4. Iteration: Definite and Indefinite Loops | 迭代：确定与不确定循环

Definite iteration uses a for loop when the number of repetitions is known in advance, often over a range or collection.

确定迭代在重复次数事先已知时使用 for 循环，通常遍历一个范围或集合。

Indefinite iteration uses a while loop, which repeats as long as a condition remains true. Ensure the condition eventually becomes false to avoid infinite loops.

不确定迭代使用 while 循环，只要条件保持为真就重复。确保条件最终变为假以避免死循环。

Loop control statements such as break and continue alter flow, but should be used sparingly for readability.

break 和 continue 等循环控制语句会改变流程，但为了提高可读性应谨慎使用。

Nested loops are useful for processing two-dimensional arrays and tables. The outer loop controls rows, and the inner loop controls columns.

嵌套循环对于处理二维数组和表格非常有用。外层循环控制行，内层循环控制列。

---

5. Arrays, Lists and 2D Structures | 数组、列表与二维结构

A one-dimensional array or list stores elements of the same type in contiguous memory. Indexing usually starts at 0 in Python.

一维数组或列表在连续内存中存储相同类型元素。Python 中索引通常从 0 开始。

A two-dimensional array models tables and grids. Access uses two indices, such as grid[1][2] to locate row 1, column 2.

二维数组模拟表格和网格。访问使用两个索引，例如 grid[1][2] 定位第 1 行第 2 列。

Common operations include traversal, insertion, deletion and searching. Be careful with array bounds to avoid index out-of-range errors.

常见操作包括遍历、插入、删除和搜索。注意数组边界，避免索引越界错误。

Dynamic arrays or lists can grow and shrink at runtime, unlike static arrays whose size is fixed. Python lists are dynamic.

动态数组或列表可以在运行时增缩，而静态数组大小固定。Python 列表是动态的。

---

6. String Handling and Formatting | 字符串处理与格式化

Strings are sequences of characters and support indexing, slicing, concatenation and length functions. In Python, strings are immutable.

字符串是字符序列，支持索引、切片、连接和长度函数。在 Python 中字符串不可变。

Useful string methods include upper(), lower(), split(), strip() and find(). Edexcel may ask you to trace or write code that manipulates text.

常用字符串方法包括 upper()、lower()、split()、strip() 和 find()。Edexcel 可能要求你跟踪或编写操作文本的代码。

String concatenation with + works for joining two strings, but repeated concatenation in loops can be inefficient. Formatting methods such as f-strings produce readable output.

使用 + 进行字符串连接可以将两个字符串合并，但在循环中反复连接可能低效。f-string 等格式化方法可生成易读的输出。

---

7. Functions and Procedures | 函数与过程

A function returns a value; a procedure performs actions without returning a value. Both improve modularity and reuse.

函数返回一个值；过程执行操作但不返回值。两者都提高模块化和可重用性。

Parameters can be passed by value or by reference. In Python, mutable objects such as lists behave like pass-by-reference, while immutable objects behave like pass-by-value.

参数可以按值或按引用传递。在 Python 中，列表等可变对象行为类似按引用传递，而不可变对象行为类似按值传递。

Local and global variables have different scopes. A variable with the same name inside a function refers to a local copy unless declared global.

局部变量和全局变量有不同的作用域。除非声明为 global，否则函数内同名变量指的是局部副本。

Well-designed functions take clear parameters and return a single result. This makes testing easier and reduces side effects.

设计良好的函数接受明确的参数并返回单一结果。这使测试更容易并减少副作用。

---

8. Recursion: How It Works | 递归：工作原理

Recursion is a technique where a function calls itself until a base case is reached. Every recursive algorithm must have a stopping condition.

递归是一种函数调用自身直到达到基准情形的技术。每个递归算法必须有停止条件。

Classic examples include factorial n! = n x (n-1)! and Fibonacci numbers. Recursion often leads to elegant code but can use more stack memory.

经典例子包括阶乘 n! = n x (n-1)! 和斐波那契数列。递归通常产生简洁代码，但可能占用更多栈内存。

Each recursive call creates a new stack frame, storing parameters and local variables. Deep recursion can cause stack overflow, so some problems are better solved iteratively.

每次递归调用都会创建一个新的栈帧，存储参数和局部变量。深度递归可能导致栈溢出，因此有些问题最好用迭代解决。

---

9. Searching Algorithms | 搜索算法

Linear search checks each element in order until the target is found or the list ends. It works on unsorted lists with O(n) time complexity.

线性搜索按顺序检查每个元素，直到找到目标或列表结束。它适用于未排序列表，时间复杂度为 O(n)。

Binary search requires a sorted list and repeatedly divides the search interval in half. Its time complexity is O(log n), making it much faster for large lists.

二分搜索要求列表有序，并反复将搜索区间一分为二。其时间复杂度为 O(log n)，对于大型列表快得多。

Algorithm | 算法	Precondition | 前提	Time Complexity | 时间复杂度
Linear Search | 线性搜索	None | 无	O(n)
Binary Search | 二分搜索	Sorted list | 有序列表	O(log n)

In an exam, you may need to trace binary search by showing low, mid and high indices changing at each step.

在考试中，你可能需要通过展示 low、mid 和 high 索引每一步的变化来跟踪二分搜索。

---

10. Sorting Algorithms | 排序算法

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. It is simple but inefficient, with O(n²) average and worst-case complexity.

冒泡排序反复比较相邻元素，如果顺序错误则交换。它简单但效率低，平均和最坏情况复杂度为 O(n²)。

Merge sort uses a divide-and-conquer approach: split the list into halves, sort each half recursively, then merge sorted halves. It has O(n log n) complexity.

归并排序使用分治法：将列表分成两半，递归排序每一半，然后合并有序半区。复杂度为 O(n log n)。

Sort | 排序	Best | 最好	Average | 平均	Worst | 最坏	Stable? | 稳定?
Bubble Sort | 冒泡排序	O(n)	O(n²)	O(n²)	Yes | 是
Merge Sort | 归并排序	O(n log n)	O(n log n)	O(n log n)	Yes | 是

Edexcel may require you to perform a pass-by-pass trace of bubble sort or to explain how merge sort divides and merges lists.

Edexcel 可能要求你逐趟跟踪冒泡排序，或解释归并排序如何划分和合并列表。

---

11. Algorithm Efficiency and Big-O | 算法效率与大O表示法

Big-O notation describes how the running time or memory use grows as input size n increases. It ignores constant factors and lower-order terms.

大O表示法描述运行时间或内存使用随输入规模 n 增长的变化。它忽略常数因子和低阶项。

Common complexities in increasing order: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Algorithms with exponential growth are impractical for large inputs.

常见复杂度按递增顺序为：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。指数增长的算法对于大型输入不实用。

For example, accessing an array element by index is O(1), while a nested loop over an n x n grid is O(n²).

例如，通过索引访问数组元素是 O(1)，而遍历 n x n 网格的嵌套循环是 O(n²)。

---

12. Debugging and Trace Tables | 调试、测试与跟踪

Published by TutorHao | A-Level 编程 Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）