📚 IB & AQA Computer Science: Algorithm Key Points | IB与AQA计算机：算法考点精讲
Algorithms form the backbone of computational thinking in both the IB and AQA Computer Science specifications. Mastering algorithm design, analysis, and implementation is not only essential for written examinations but also for internal assessments and programming projects. This guide distills the core algorithm topics that appear repeatedly across past papers, empowering you to approach questions with clarity and confidence.
算法是 IB 和 AQA 计算机科学考试体系中计算思维的基石。无论是笔试、内部评估还是编程项目，算法的设计、分析与实现能力都起着决定性作用。本文梳理了历年真题中反复出现的核心算法考点，帮助你在面对各类题目时思路清晰、应答自如。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of unambiguous, well-defined instructions designed to solve a specific problem or perform a computation. Key properties include input, output, finiteness, definiteness, and effectiveness. In both IB and AQA syllabuses, you are expected to recognise that an algorithm can be expressed in natural language, pseudocode, or flowcharts, and that it must terminate after a finite number of steps.
算法是用于解决特定问题或执行计算的一系列有限、明确且定义清晰的指令。核心特征包括输入、输出、有穷性、确定性和有效性。在 IB 与 AQA 的大纲中，你需要认识到算法可以用自然语言、伪代码或流程图表示，并且必须在有限步骤内终止。
Understanding the difference between an algorithm and a computer program is crucial. An algorithm is a logical blueprint, whereas a program is its concrete implementation in a specific programming language. Examiners frequently ask candidates to trace an algorithm step-by-step to verify its correctness or to identify logical errors in a given piece of pseudocode.
理解算法与计算机程序的区别至关重要。算法是逻辑蓝图，而程序是其在特定编程语言中的具体实现。考官经常要求考生逐步追踪算法来验证其正确性，或找出给定伪代码中的逻辑错误。
2. Pseudocode and Flowcharts | 伪代码与流程图
Pseudocode is a high-level, semi-structured description of an algorithm that uses the structural conventions of programming languages but omits language-specific details. IB exam papers use an agreed IB pseudocode style focusing on keywords like IF…THEN…ELSE, WHILE…DO…ENDWHILE, and arrays. Similarly, AQA provides a standardised pseudocode syntax that candidates must be able to interpret and write.
伪代码是一种高层次、半结构化的算法描述方式，它采用编程语言的常用结构，但省略了具体语言的细节。IB 考试使用一套统一的 IB 伪代码风格，重点关注 IF…THEN…ELSE、WHILE…DO…ENDWHILE 及数组等关键词。AQA 同样提供了标准化的伪代码语法，考生必须能够读懂并书写。
Flowcharts use geometrical shapes to represent algorithmic steps: ovals for start/end, parallelograms for input/output, rectangles for processes, and diamonds for decisions. Being able to convert between pseudocode and flowcharts is a fundamental skill. A common exam task is to read a flowchart and either state its output for a given input or translate it into pseudocode.
流程图使用几何图形表示算法步骤：椭圆代表开始与结束，平行四边形代表输入/输出，矩形代表处理过程，菱形代表判断。能够在伪代码与流程图之间相互转换是一项基本功。常见的考试任务是阅读流程图，针对给定输入陈述其输出，或将流程图翻译为伪代码。
3. Searching Algorithms: Linear Search | 搜索算法：线性搜索
The linear search algorithm examines each element of a list sequentially, from the first element to the last, until the target value is found or the end of the list is reached. It works on both sorted and unsorted arrays. In terms of pseudocode, a simple linear search uses a loop that iterates through the array and compares each element with the search key.
线性搜索算法从列表的第一个元素开始，依次逐个检查，直到找到目标值或遍历完整个列表。它既可以用于有序数组，也可以用于无序数组。从伪代码的角度看，一个简单的线性搜索使用循环遍历数组，并将每个元素与搜索键进行比较。
From an efficiency perspective, in the worst case the algorithm will inspect all n items, giving a time complexity of O(n). It is important to memorise this typical exam question: “Explain when a linear search is more appropriate than a binary search.” The answer typically highlights that linear search requires no prior sorting, making it suitable for small or constantly changing datasets.
从效率角度来看，最坏情况下该算法将检查全部 n 个数据项，其时间复杂度为 O(n)。需要熟记一道典型的考试题：“解释线性搜索何时比二分搜索更合适。”答案通常强调线性搜索无需预先排序，因此适合处理较小或频繁变动的数据集。
4. Searching Algorithms: Binary Search | 搜索算法：二分搜索
Binary search is a divide-and-conquer algorithm that operates on sorted arrays by repeatedly dividing the search interval in half. It compares the middle element with the target value; if the target equals the middle element, the search is done. If the target is smaller, the search continues in the left half; otherwise, it continues in the right half.
二分搜索是一种分治算法，它作用在有序数组上，通过不断将搜索区间对半分割来查找。它将中间元素与目标值进行比较；如果目标值等于中间元素，搜索结束。如果目标值较小，则继续在左半部分搜索；否则，继续在右半部分搜索。
Both IB and AQA require you to trace binary search on a concrete list. You must be able to calculate the maximum number of comparisons needed: ⌈log₂(n+1)⌉. The time complexity is O(log n), which makes binary search far more efficient than linear search for large datasets. Nevertheless, the requirement that the data be sorted beforehand must always be mentioned.
IB 与 AQA 都要求你能够在具体列表上追踪二分搜索的执行过程。你必须能够计算所需的最大比较次数：⌈log₂(n+1)⌉。其时间复杂度为 O(log n)，这使得二分搜索在处理大数据集时远比线性搜索高效。但务必提到，数据必须预先排序这一前提条件。
5. Sorting Algorithms: Bubble Sort | 排序算法：冒泡排序
Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted. After each complete pass, the largest unsorted element “bubbles up” to its correct position at the end.
冒泡排序通过反复遍历列表、比较相邻元素并在顺序错误时进行交换来工作。这一过程不断重复，直到没有交换发生，表明列表已排序。每完成一趟完整的遍历，当前未排序部分的最大元素就会“冒泡”到其应在的正确末端位置。
A typical exam question asks you to demonstrate the state of the list after a certain number of passes, or to implement bubble sort using pseudocode. Remember that an optimised version can detect when no swaps occur in a pass and terminate early. In terms of complexity, bubble sort has O(n²) comparisons and swaps in the worst and average cases, and O(n) in the best case when the list is already sorted.
典型的考题要求你展示经过特定趟数后列表的状态，或用伪代码实现冒泡排序。请记住，优化版本可以检测在某趟遍历中是否未发生交换，并提前终止。在复杂度方面，冒泡排序在最坏和平均情况下需要 O(n²) 次比较和交换，而在最好情况（列表已有序）下只需 O(n) 次。
6. Sorting Algorithms: Selection Sort | 排序算法：选择排序
Selection sort divides the list into a sorted and an unsorted portion. It repeatedly finds the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part, thereby extending the sorted portion by one element. This process continues until the entire list is sorted.
选择排序将列表分为已排序部分和未排序部分。它反复从未排序部分找出最小（或最大）元素，并将其与未排序部分的第一个元素进行交换，从而使已排序部分扩大一个元素。这一过程一直持续到整个列表排序完毕。
Candidates often confuse selection sort with bubble sort. The key distinction is that selection sort makes exactly one swap per pass, whereas bubble sort may make many. Its time complexity is O(n²) for all cases, because it always performs the same number of comparisons regardless of the initial arrangement of the data. You should be able to code it and explain why selection sort requires fewer writes than bubble sort.
考生常将选择排序与冒泡排序混淆。关键区别在于，选择排序每趟只进行一次交换，而冒泡排序可能进行多次交换。它在所有情况下的时间复杂度均为 O(n²)，因为无论数据初始排列如何，其比较次数始终相同。你需要能够编写其代码，并解释为什么选择排序的写入操作比冒泡排序更少。
7. Sorting Algorithms: Insertion Sort | 排序算法：插入排序
Insertion sort builds the final sorted array one item at a time. It takes each element from the unsorted portion and inserts it into its correct position within the sorted portion, shifting larger elements one position to the right as necessary. This resembles the way people often sort playing cards in their hands.
插入排序一次一个元素地构建最终的有序数组。它从未排序部分依次取出元素，并将其插入到已排序部分中的正确位置，必要时将较大的元素向右移动一个位置。这个过程类似于人手整理扑克牌的方式。
In terms of performance, insertion sort has a best-case time complexity of O(n) when the list is nearly sorted, but it deteriorates to O(n²) in the worst case of a reverse-sorted list. It is stable and performs well on small datasets. Both IB and AQA often test your understanding of when an insertion sort should be chosen over other sorting algorithms—such as when data is already partially ordered.
在性能方面，插入排序在列表近乎有序时的最佳时间复杂度为 O(n)，但在列表反向排序的最坏情况下退化为 O(n²)。它是稳定的排序算法，并在小数据集上表现良好。IB 和 AQA 都经常会考查你对何时应选择插入排序而非其他排序算法的理解——例如当数据已经部分有序时。
8. Algorithm Efficiency: Time Complexity | 算法效率：时间复杂度
Time complexity is a function describing the amount of computational time an algorithm takes relative to the size of the input, denoted n. The big-O notation is used to express the upper bound of growth. Constant complexity O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), quadratic O(n²), and exponential O(2ⁿ) are the classes you must differentiate.
时间复杂度是一个描述算法运行时间相对于输入规模 n 变化规律的函数。大 O 表示法用于描述增长的上界。你必须能够区分的常见类别包括：常数 O(1)、对数 O(log n)、线性 O(n)、线性对数 O(n log n)、平方 O(n²) 以及指数 O(2ⁿ)。
When comparing algorithms, focus on the dominant term and disregard constant factors. For example, the binary search tree traversal time is often O(log n), while simple nested loops correspond to O(n²). Exam questions frequently provide pseudocode and ask you to determine its time complexity by counting the number of iterations, or to justify why one algorithm is preferable for large data volumes.
比较算法时，应重点关注主导项，忽略常数因子。例如，二叉搜索树遍历常为 O(log n)，而简单的嵌套循环对应 O(n²)。考试题目经常给出伪代码，要求你通过计算迭代次数来确定其时间复杂度，或者论证为什么在处理大数据量时某一算法更具优势。
9. Recursion in Algorithms | 算法中的递归
A recursive algorithm solves a problem by breaking it down into smaller instances of the same problem. The key components are the base case (which stops the recursion) and the recursive case (which divides the problem). Classic examples include calculating factorials, Fibonacci numbers, and traversing tree structures.
递归算法通过将问题分解为同类更小的子问题来求解。其关键组成部分是基线条件（停止递归）和递归步骤（将问题分解）。经典例子包括计算阶乘、斐波那契数列以及遍历树结构。
You should be able to trace a recursive algorithm showing the call stack and the order of evaluation. Understanding how recursion can lead to stack overflow without a correct base case is a common exam pitfall. Also, contrast iterative and recursive solutions; recursion often produces elegant code but may consume more memory due to the call stack, while iteration can be more efficient in terms of space.
你应该能够追踪递归算法，展示调用栈与求值顺序。理解在没有正确基线条件的情况下递归如何导致栈溢出，是考试中常见的易错点。此外，要将迭代与递归解法进行对比；递归通常能产生优雅的代码，但因调用栈可能消耗更多内存，而迭代在空间效率上往往更优。
10. Graph and Tree Traversal Overview | 图与树的遍历概述
Tree and graph traversals are fundamental for exploring connected data structures. The two primary traversal strategies are depth-first search (DFS) and breadth-first search (BFS). DFS explores a branch as far as possible before backtracking, while BFS visits nodes level by level, using a queue to manage the frontier.
树与图的遍历是探索连通数据结构的基础。两种主要的遍历策略是深度优先搜索（DFS）和广度优先搜索（BFS）。DFS 先尽可能深入一个分支，然后回溯；而 BFS 借助队列逐层访问节点。
In the IB and AQA specifications, you are expected to understand the behaviour of these traversals on binary trees. For example, inorder, preorder, and postorder traversals of a binary tree are specific instances of DFS. You might be asked to write down the sequence of nodes visited or to construct a tree from given traversal sequences. Familiarity with applying BFS to find the shortest path in unweighted graphs is also beneficial.
在 IB 和 AQA 的大纲中，你需要理解这些遍历方式在二叉树上的行为。例如，二叉树的中序遍历、先序遍历和后序遍历就是 DFS 的具体实例。考题可能要求你写出访问节点的次序，或根据给定的遍历序列构造树。熟悉将 BFS 应用于无权图中寻找最短路径同样大有裨益。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply