A-Level CIE Computer Science: Algorithm Key Points Explained | A-Level CIE 计算机：算法考点精讲

📚 A-Level CIE Computer Science: Algorithm Key Points Explained | A-Level CIE 计算机：算法考点精讲

This article provides a focused revision of key algorithm concepts required for the CIE A-Level Computer Science syllabus. It covers algorithm definition, expression using pseudocode and flowcharts, common search and sort algorithms, recursion, algorithm efficiency analysis with Big O notation, abstract data types (stacks, queues, linked lists), and graph algorithms such as Dijkstra’s shortest path. Each section pairs a clear English explanation with a Chinese version to support bilingual learners and reinforce understanding of examination points.

本文为 CIE A-Level 计算机科学教学大纲中算法部分的核心考点提供精讲。内容涵盖算法定义、伪代码与流程图表示、常见搜索和排序算法、递归、基于大 O 表示法的算法效率分析、抽象数据类型（栈、队列、链表）以及 Dijkstra 最短路径等图算法。每个小节都将英文讲解与对应的中文释义配对呈现，帮助双语学习者巩固考试要点。

1. What is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of well-defined, unambiguous steps designed to solve a specific problem or perform a computation. It must have a clear start and end, produce an output, and be feasible within available resources. A recipe, a set of driving directions, or the procedure for calculating the greatest common divisor are all examples of algorithms in everyday life.

算法是一个由明确定义且无歧义步骤构成的有限序列，旨在解决特定问题或执行计算。它必须有明确的起点和终点，产生输出，并且在可用资源内可行。日常生活中的食谱、驾驶导航指令集或计算最大公约数的过程都是算法的实例。

In computing, algorithms form the backbone of software. They can be expressed in natural language, pseudocode, or flowcharts before implementation. The efficiency of an algorithm—both time and space complexity—is a primary concern at A-Level, as it determines whether a solution scales well for large inputs.

在计算机科学中，算法是软件的基石。在实现之前，可以用自然语言、伪代码或流程图来表达算法。算法的效率（时间复杂度和空间复杂度）是 A-Level 阶段关注的重点，因为它决定了解决方案在大规模输入下是否依然表现良好。

2. Expressing Algorithms: Pseudocode and Flowcharts | 算法表达：伪代码与流程图

Pseudocode is a structured, English-like shorthand used to outline an algorithm without worrying about the syntax of a particular programming language. CIE provides a standard pseudocode scheme that includes assignment (←), conditional statements (IF … THEN … ELSE … ENDIF), iteration (FOR … TO … NEXT, WHILE … DO … ENDWHILE, REPEAT … UNTIL), and input/output (INPUT, OUTPUT). This consistency helps examiners and students communicate algorithmic logic clearly.

伪代码是一种结构化的、类似英语的简写形式，用于勾勒算法逻辑，而不必拘泥于某种具体编程语言的语法。CIE 提供了标准的伪代码规范，包括赋值（←）、条件语句（IF … THEN … ELSE … ENDIF）、循环（FOR … TO … NEXT、WHILE … DO … ENDWHILE、REPEAT … UNTIL）以及输入/输出（INPUT、OUTPUT）。这种一致性有助于考官和学生清晰地交流算法逻辑。

Flowcharts use geometric shapes to represent steps: ovals for start/end, parallelograms for input/output, rectangles for processes, and diamonds for decisions. Arrows show the flow of control. They are especially useful for visualising branching and loops in an algorithm, making it easier to trace execution and identify logical errors.

流程图用几何图形表示步骤：椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理过程，菱形表示判断。箭头指示控制流。流程图特别适用于可视化算法中的分支和循环，有助于跟踪执行过程并发现逻辑错误。

When describing an algorithm for an exam answer, you may be asked to write pseudocode, draw a flowchart, or both. Ensure you are familiar with the CIE pseudocode constructs and the standard flowchart symbols to communicate your solution effectively.

在考试答题中描述算法时，你可能需要编写伪代码、绘制流程图或二者均需。务必要熟悉 CIE 的伪代码结构和标准流程图符号，以便有效传达你的解决方案。

3. Linear Search Algorithm | 线性搜索算法

The linear search is the simplest searching method: it sequentially checks each element in an array or list until the target value is found or the end is reached. Its time complexity is O(n) in the worst case, as it may need to examine all n elements.

线性搜索是最简单的搜索方法：它按顺序检查数组或列表中的每个元素，直到找到目标值或到达末尾。最坏情况下的时间复杂度为 O(n)，因为它可能需要检查全部 n 个元素。

Despite being less efficient on large sorted datasets, linear search does not require the data to be sorted. It is useful for small lists or when sorting overhead is not justified. In pseudocode, a linear search might look like:

FOR i ← 0 TO LENGTH(list)-1
  IF list[i] = target THEN
    OUTPUT i
    STOP
  ENDIF
NEXT i
OUTPUT “Not found”

尽管对大型有序数据集效率较低，线性搜索不要求数据事先排序。对于小列表或排序开销不合理的情形，它非常实用。在伪代码中，线性搜索可能如下所示：

FOR i ← 0 TO LENGTH(list)-1
  IF list[i] = target THEN
    OUTPUT i
    STOP
  ENDIF
NEXT i
OUTPUT “Not found”

In CIE exams, you may be asked to trace a linear search or write the algorithm from scratch. Pay attention to boundary conditions, such as an empty list or the element being found at the first index.

在 CIE 考试中，可能会要求你追踪线性搜索的执行过程，或从头编写该算法。注意边界条件，例如空列表或目标元素恰在第一个索引位置的情况。

4. Binary Search Algorithm | 二分查找算法

Binary search is a much more efficient algorithm for sorted arrays. It repeatedly divides the search interval in half, comparing the target with the middle element. If they are not equal, the half in which the target cannot lie is eliminated. The worst-case time complexity is O(log₂ n), making it far faster than linear search for large datasets.

二分查找对于有序数组来说是一种高效得多的算法。它反复将搜索区间对半分，将目标值与中间元素进行比较。如果不等，则排除目标不可能存在的那一半。最坏情况时间复杂度为 O(log₂ n)，在大型数据集上远比线性搜索快速。

The pseudocode for iterative binary search maintains two pointers, low and high. While low ≤ high, it calculates mid = (low + high) DIV 2. If the target equals the middle element, the search stops. If the target is smaller, high becomes mid − 1; if larger, low becomes mid + 1. If low > high, the item is not present.

迭代版二分查找的伪代码维护两个指针 low 和 high。当 low ≤ high 时，计算 mid = (low + high) DIV 2。若目标值与中间元素相等，搜索停止；若目标值较小，则 high 更新为 mid − 1；若较大，则 low 更新为 mid + 1。若 low > high，则元素不存在。

A common exam mistake is forgetting that the array must be sorted before binary search can be applied. Also, students must correctly update low and high to avoid infinite loops. Recursive implementations are also accepted, provided they clearly show the base case.

考生常犯的错误是忘记数组必须提前排序才能使用二分查找。此外，必须正确更新 low 和 high，以避免死循环。递归实现也可接受，但必须清楚展示基线条件。

5. Sorting Algorithms: Bubble Sort | 排序算法：冒泡排序

Bubble sort works by repeatedly stepping through the list, comparing adjacent items and swapping them if they are in the wrong order. After each full pass, the largest unsorted element “bubbles up” to its correct position at the end. The algorithm terminates when a complete pass is made with no swaps.

冒泡排序通过反复遍历列表，比较相邻元素并在顺序错误时交换它们来工作。每完成一次完整遍历，最大的未排序元素就会“冒泡”到其末尾的正确位置。当某次遍历中没发生任何交换时，算法终止。

Its time complexity is O(n²) in the worst and average cases, but it can achieve O(n) in the best case (already sorted list) if an optimisation flag is used to detect no swaps. Pseudocode uses nested loops: the outer loop controls the number of passes, and the inner loop performs comparisons and swaps up to the unsorted portion.

最坏和平均情况的时间复杂度均为 O(n²)，但如果使用优化标志检测无交换发生，最佳情况（列表已排序）可达到 O(n)。伪代码使用嵌套循环：外层循环控制遍历次数，内层循环在未排序部分进行比较和交换。

Bubble sort is rarely used in real-world applications due to its poor performance on large lists, but it is an excellent pedagogical tool. CIE often asks students to step through a bubble sort or to write the algorithm, paying attention to swap count and efficiency.

冒泡排序因在大列表上性能较差而很少用于实际应用，但它是一个极好的教学工具。CIE 经常要求学生逐步追踪冒泡排序，或编写该算法，并关注交换次数与效率。

6. Sorting Algorithms: Insertion Sort | 排序算法：插入排序

Insertion sort builds the final sorted array one element at a time. It takes each element from the unsorted part and inserts it into its correct position within the sorted part, shifting larger elements one position to the right as needed. This is similar to how you might sort playing cards in your hand.

插入排序一次一个元素地构建最终有序数组。它从未排序部分取出每个元素，并将其插入已排序部分中的正确位置，必要时将较大元素向右移动一个位置。这类似于你对手中的扑克牌进行排序的方式。

Insertion sort also has a worst-case time complexity of O(n²), but it is efficient for small datasets and is adaptive: it runs in O(n) time when the list is nearly sorted. The pseudocode typically involves an outer loop starting from the second element and an inner WHILE loop to shift elements.

插入排序同样具有 O(n²) 的最坏时间复杂度，但它在小数据集上效率较高，且具有自适应性：当列表接近有序时，可在 O(n) 时间内完成。伪代码通常包含一个从第二个元素开始的外层循环，以及一个用于移动元素的内层 WHILE 循环。

When tracing insertion sort in an exam, students should clearly indicate the current element being inserted and how the sorted portion expands. It is often compared with bubble sort for stability (it is stable) and overhead.

在考试中追踪插入排序时，学生应清楚指明当前待插入元素以及已排序部分如何扩展。常与冒泡排序进行稳定性（它是稳定的）和开销方面的比较。

7. Sorting Algorithms: Merge Sort | 排序算法：归并排序

Merge sort is a divide-and-conquer algorithm with guaranteed O(n log₂ n) time complexity. It recursively splits the list into two halves until each sublist contains only one element (which is trivially sorted), then merges the sublists back together in sorted order. The merge step combines two sorted lists by repeatedly taking the smaller first element.

归并排序是一种分治算法，具有保证的 O(n log₂ n) 时间复杂度。它递归地将列表分成两半，直到每个子列表仅含一个元素（平凡有序），然后再将子列表以有序方式合并回来。合并步骤通过反复取两个有序子列表首元素中较小者来完成。

Because merge sort requires additional memory proportional to the size of the list for the merging process, its space complexity is O(n). It is stable and particularly well-suited for sorting linked lists and large datasets stored on external media.

由于归并排序在合并过程中需要与列表大小成比例的额外内存，其空间复杂度为 O(n)。它是稳定的，尤其适合对链表和存储在外部介质上的大型数据集进行排序。

In CIE questions, you may be required to apply merge sort to an array, showing each recursive split and the subsequent merge steps. Be prepared to write an algorithm for merging two sorted arrays, as this is a sub-routine often tested separately.

在 CIE 考题中，你可能需要对一个数组应用归并排序，展示每次递归拆分和随后的合并步骤。准备好编写合并两个有序数组的算法，因为这是常被单独考查的子例程。

8. Recursion in Algorithms | 算法中的递归

Recursion is a technique in which a function calls itself to solve smaller sub-problems of the original problem. Every recursive solution must have a base case that stops the recursion and a recursive case that breaks the problem into smaller instances. Classic examples include factorial calculation, Fibonacci sequence generation, and tree traversals.

递归是一种函数调用自身以解决原问题更小子问题的技术。每个递归解决方案必须拥有一个停止递归的基线条件，以及一个将问题分解为更小实例的递归条件。经典示例包括阶乘计算、斐波那契数列生成和树的遍历。

Understanding recursion is crucial for A-Level, especially when tracing recursive calls and evaluating the call stack. Infinite recursion occurs if the base case is missing or unreachable. Recursion can lead to elegant, concise code but may cause stack overflow if the recursion depth is excessive.

理解递归对 A-Level 至关重要，尤其是在追踪递归调用和评估调用栈时。如果缺失或无法抵达基线条件，就会发生无限递归。递归可以产生优雅简洁的代码，但若递归深度过大，可能导致栈溢出。

When writing recursive pseudocode for CIE, clearly label the base case and the recursive call. E.g., for factorial:
FUNCTION Factorial(n)
  IF n = 0 THEN
    RETURN 1
  ELSE
    RETURN n * Factorial(n-1)
  ENDIF
ENDFUNCTION

在为 CIE 编写递归伪代码时，要清楚地标明基线条件和递归调用。例如，计算阶乘：
FUNCTION Factorial(n)
  IF n = 0 THEN
    RETURN 1
  ELSE
    RETURN n * Factorial(n-1)
  ENDIF
ENDFUNCTION

9. Analysing Algorithm Efficiency: Big O Notation | 算法效率分析：大 O 表示法

Big O notation describes the upper bound of an algorithm’s time or space complexity as the input size n grows. It focuses on the dominant term and disregards constants and lower-order terms. Common complexities include O(1) (constant), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ).

大 O 表示法描述了随着输入规模 n 增长，算法时间复杂度或空间复杂度的上界。它关注主导项，并忽略常数和低阶项。常见的复杂度有 O(1)（常数）、O(log n)、O(n)、O(n log n)、O(n²) 和 O(2ⁿ)。

For example, a single loop that iterates n times is O(n); nested loops with n iterations each are O(n²). Binary search is O(log n) because the search space halves each time. Merge sort is O(n log n) due to the logarithmic split and linear merge. The analysis is a fundamental skill tested in exam questions where students must determine the efficiency of given pseudocode or compare algorithms.

例如，一个迭代 n 次的单层循环为 O(n)；每个循环迭代 n 次的嵌套循环为 O(n²)。二分查找为 O(log n)，因为每次搜索空间减半。归并排序因对数级拆分和线性合并，复杂度为 O(n log n)。这种分析是一项基本技能，考试中常要求学生判断给定伪代码的效率，或比较不同算法。

Remember that big O notation describes the worst-case scenario unless stated otherwise. Space complexity is also important, especially for recursive algorithms that consume call stack memory. Always justify your answer by identifying the number of basic operations as a function of n.

请注意，除非另有说明，大 O 表示法描述的是最坏情况。空间复杂度同样重要，尤其是对于消耗调用栈内存的递归算法。始终要通过确定基本操作次数与 n 的函数关系来给你的答案提供依据。

10. Abstract Data Types: Stacks and Queues | 抽象数据类型：栈与队列

A stack is a Last-In-First-Out (LIFO) data structure. Key operations are push (add to top), pop (remove from top), and peek (inspect top). Stacks can be implemented using arrays or linked lists. They are used in function call management, undo mechanisms, and expression evaluation.

栈是一种后进先出（LIFO）的数据结构。关键操作包括 push（压入栈顶）、pop（弹出栈顶）和 peek（查看栈顶）。栈可用数组或链表实现，常用于函数调用管理、撤销机制和表达式求值。

A queue is a First-In-First-Out (FIFO) structure, with operations enqueue (add to rear) and dequeue (remove from front). Circular queues and priority queues are common variations. Queues are used in job scheduling, breadth-first search, and buffering.

队列是一种先进先出（FIFO）的结构，操作包括 enqueue（在队尾加入）和 dequeue（从队首移除）。循环队列和优先队列是常见变体。队列用于作业调度、广度优先搜索和缓冲处理。

In CIE exams, you must be able to write pseudocode for the basic operations and understand how pointers (front, rear, or top) are managed. Be mindful of overflow and underflow conditions. Typical questions involve tracing the contents of a stack or queue after a sequence of operations.

在 CIE 考试中，你必须能编写基本操作的伪代码，并理解指针（如 front、rear 或 top）如何管理。注意溢出和下溢条件。典型题目涉及在一系列操作后追踪栈或队列的内容。

11. Graph Algorithms: Dijkstra’s Shortest Path | 图算法：Dijkstra 最短路径

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It maintains a set of unvisited nodes and a distance value for each, initially infinite except the source which is 0. It repeatedly selects the unvisited node with the smallest tentative distance, marks it as visited, and updates the distances of its neighbours if a shorter path is found.

Dijkstra 算法用于在具有非负边权重的加权图中找到从源节点到所有其他节点的最短路径。它维护一个未访问节点集合，并为每个节点记录一个距离值（源节点为 0，其余初始为无穷大）。算法反复选择具有最小暂定距离的未访问节点，将其标记为已访问，并在发现更短路径时更新其邻居的距离。

The algorithm uses a priority queue to efficiently select the minimum-distance node, contributing to a time complexity of O((V + E) log V) with a binary heap. Tracing Dijkstra’s algorithm by hand on a small graph is a regular exam task; students must show the update of distance values and the final shortest path tree.

该算法使用优先队列来高效地选取最小距离节点，若配合二叉堆，时间复杂度可达 O((V + E) log V)。在小规模图上手动追踪 Dijkstra 算法是常见考试任务：学生必须展示距离值的更新过程以及最终的最短路径树。

Important note: Dijkstra’s algorithm does not work correctly if any edge weight is negative. For graphs with negative edges, the Bellman-Ford algorithm is used, but CIE focuses on Dijkstra. Ensure you can apply it step by step and record results clearly.

重要提示：如果有任何边的权值为负，Dijkstra 算法将无法正确工作。对于含负边权重的图，需使用 Bellman-Ford 算法，但 CIE 主要考查 Dijkstra。确保你能逐步应用该算法并清晰地记录结果。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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

A-Level CIE Computer Science: Algorithm Key Points Explained | A-Level CIE 计算机：算法 考点精讲