GCSE Computer Science: Algorithms Key Points | GCSE 计算机：算法考点精讲

📚 GCSE Computer Science: Algorithms Key Points | GCSE 计算机：算法考点精讲

Algorithms are the heart of computer science. This guide covers everything you need to know for GCSE: from writing pseudocode and reading flowcharts to searching, sorting, and evaluating efficiency. Whether you are preparing for exams or building your programming thinking, these clear explanations and side-by-side Chinese translations will help you master every key concept.

算法是计算机科学的核心。本指南涵盖 GCSE 所需的一切内容：从编写伪代码和阅读流程图，到搜索、排序以及效率评估。无论你是在备考还是培养编程思维，这些清晰的讲解和中英双语对照都将帮助你掌握每一个关键概念。

---

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

An algorithm is a step-by-step set of instructions designed to solve a specific problem or perform a task. It must be precise, unambiguous, and finite – meaning it always ends after a limited number of steps. A good algorithm can be implemented in any programming language and should handle valid inputs correctly while clearly defining what to do with invalid ones.

算法是一组逐步执行的指令，旨在解决特定问题或完成任务。它必须精确、无歧义，并且有限 —— 也就是说，它总是在有限的步骤后结束。一个好的算法可以用任何编程语言实现，并且应当正确处有效输入，同时明确定义遇到无效输入时该如何处理。

---

2. Representing Algorithms – Pseudocode | 算法表示——伪代码

Pseudocode uses structured English-like statements to describe an algorithm without strict syntax. GCSE exam boards expect you to write clear, indented pseudocode that uses keywords such as INPUT, OUTPUT, IF…THEN…ELSE, FOR…TO…NEXT, and WHILE…ENDWHILE. This makes the logic easy to follow and independent of any particular programming language.

伪代码使用结构化的、类似英语的语句来描述算法，没有严格的语法。GCSE 考试局希望你写出清晰、带缩进的伪代码，使用诸如 INPUT、OUTPUT、IF…THEN…ELSE、FOR…TO…NEXT 以及 WHILE…ENDWHILE 等关键词。这使得逻辑易于理解，且独立于任何特定的编程语言。

Here is a typical pseudocode example for finding the largest of three numbers:

以下是一个找出三个数中最大值的典型伪代码示例：

INPUT a, b, c
IF a > b AND a > c THEN
  OUTPUT a
ELSE IF b > c THEN
  OUTPUT b
ELSE
  OUTPUT c
ENDIF

---

3. Representing Algorithms – Flowcharts | 算法表示——流程图

Flowcharts use standard symbols to visually represent the flow of an algorithm. Ovals mark the start and end, parallelograms show input/output, rectangles represent processes, diamonds indicate decisions, and arrows show the direction of flow. This visual tool helps you trace logic and spot errors before coding.

流程图使用标准符号来直观地表示算法的流程。椭圆形标记开始和结束，平行四边形表示输入 / 输出，矩形表示处理过程，菱形表示判断，箭头表示流程方向。这种可视化工具能帮助你在编写代码之前追踪逻辑并发现错误。

Symbol | 符号	Meaning | 含义
⬭ (oval)	Start / End
▱ (parallelogram)	Input / Output
▭ (rectangle)	Process
◇ (diamond)	Decision

---

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

A linear search checks each item in a list one by one until it finds the target value or reaches the end. It is simple to implement and works on unsorted data, but it is inefficient for large lists because, in the worst case, it may have to examine every element.

线性搜索逐个检查列表中的每一项，直到找到目标值或到达列表末尾。它实现简单，适用于未排序的数据，但对于大型列表效率较低，因为在最坏情况下可能必须检查每个元素。

Pseudocode for linear search:

线性搜索的伪代码：

INPUT list, target
FOR index ← 0 TO length(list)-1
  IF list[index] = target THEN
    OUTPUT “Found at ” + index
    STOP
  ENDIF
NEXT index
OUTPUT “Not found”

---

5. Binary Search Algorithm | 二分搜索算法

Binary search repeatedly divides a sorted list in half, comparing the middle element with the target. If the target is smaller, the search continues in the left half; if larger, in the right half. This drastically reduces the number of comparisons, giving it a logarithmic time complexity, much faster than linear search on large datasets.

二分搜索不断将已排序的列表分成两半，比较中间元素与目标值。如果目标值较小，就在左半部分继续搜索；如果较大，则在右半部分。这大幅减少了比较次数，使其具有对数时间复杂度，在大数据集上比线性搜索快得多。

Key requirement: the data must be sorted first. The efficiency is often described as O(log₂ n).

关键要求：数据必须先排序。其效率通常用 O(log₂ n) 来描述。

Binary search pseudocode outline:

二分搜索伪代码大纲：

low ← 0
high ← length(list) – 1
WHILE low ≤ high
  mid ← (low + high) // 2
  IF list[mid] = target THEN
    OUTPUT mid
    STOP
  ELSE IF list[mid] < target THEN
    low ← mid + 1
  ELSE
    high ← mid – 1
  ENDIF
ENDWHILE
OUTPUT “Not found”

---

6. Bubble Sort Algorithm | 冒泡排序算法

Bubble sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed. It is easy to understand but inefficient for large lists because its average and worst-case time complexity is O(n²).

冒泡排序反复遍历列表，比较相邻的项，如果顺序错误就交换它们。重复此过程，直到不需要交换为止。它易于理解，但对于大列表效率低，因为其平均和最坏情况时间复杂度为 O(n²)。

A simple optimisation: if a pass completes without any swaps, the list is already sorted and the algorithm can stop early. A GCSE trace table question often asks you to show the list after each pass.

一个简单的优化：如果某轮遍历没有发生任何交换，列表已经有序，算法可以提前终止。GCSE 的跟踪表题目常常要求你展示每一轮遍历后的列表状态。

FOR pass ← 1 TO n-1
  swapped ← false
  FOR i ← 0 TO n-2-pass
    IF list[i] > list[i+1] THEN
      SWAP list[i], list[i+1]
      swapped ← true
    ENDIF
  NEXT i
  IF swapped = false THEN STOP
NEXT pass

---

7. Insertion Sort Algorithm | 插入排序算法

Insertion sort builds the sorted list one element at a time, taking the next unsorted item and inserting it into its correct position within the already sorted part. This algorithm performs well on small or partially sorted lists and is often used as part of more complex algorithms like quicksort for small sub-arrays.

插入排序每次将一个元素插入到已排序部分的正确位置，逐步构建出有序列表。该算法在小列表或部分有序的列表上表现良好，常被用作更复杂算法（如快速排序处理小型子数组时）的一部分。

GCSE often expects you to trace insertion sort step by step and explain why it is more efficient than bubble sort in some cases but still has an average O(n²) time complexity.

GCSE 常常希望你逐步跟踪插入排序的执行，并解释为什么在某些情况下它比冒泡排序更高效，但其平均时间复杂度仍为 O(n²)。

FOR i ← 1 TO n-1
  key ← list[i]
  j ← i – 1
  WHILE j ≥ 0 AND list[j] > key
    list[j+1] ← list[j]
    j ← j – 1
  ENDWHILE
  list[j+1] ← key
NEXT i

---

8. Algorithm Efficiency and Comparison | 算法效率与比较

Algorithm efficiency is about how the time or memory required grows as the input size increases. GCSE uses simple comparisons rather than formal Big O notation, though recognising terms like O(n) and O(n²) is helpful. A linear search takes more steps for bigger lists (linear growth), while a binary search needs far fewer steps (logarithmic growth).

算法效率关注的是随着输入规模增大，所需的时间或内存如何增长。GCSE 使用简单的比较而不是正式的大 O 表示法，但认识 O(n) 和 O(n²) 等术语是有帮助的。线性搜索在列表增大时需要更多步骤（线性增长），而二分搜索所需的步骤则少得多（对数增长）。

When choosing an algorithm, consider whether the data is sorted, how large the data set is, and how often the algorithm will run. For example, if you frequently search a large database, it is worth sorting it once so that binary search can be used repeatedly.

在选择算法时，要考虑数据是否有序、数据集有多大以及算法运行的频率。例如，如果你需要频繁地搜索一个大型数据库，那么值得对它进行一次排序，以便可以反复使用二分搜索。

Algorithm | 算法	Best Case	Worst Case	Requires Sorted Data?
Linear Search	O(1) (found first)	O(n)	No
Binary Search	O(1) (found middle)	O(log n)	Yes
Bubble Sort	O(n) (already sorted)	O(n²)	–
Insertion Sort	O(n) (already sorted)	O(n²)	–

---

9. Testing and Trace Tables | 测试与跟踪表

A trace table is a manual tool used to follow the execution of an algorithm step by step, recording the values of variables at each stage. GCSE exam questions frequently ask you to complete a trace table for a given algorithm or identify logic errors using one. Effective testing also involves selecting normal, boundary, and erroneous test data.

跟踪表是一种手动工具，用于逐步追踪算法的执行过程，记录每个阶段变量的值。GCSE 考试题目经常要求你为给定的算法完成一个跟踪表，或者利用跟踪表找出逻辑错误。有效的测试还包括选择正常数据、边界数据和错误数据。

Normal data: typical values the algorithm is designed to handle. Boundary data: values at the edge of valid ranges, such as the first and last index. Erroneous data: values that should be rejected, like a negative number for an array size.

正常数据：算法旨在处理的典型值。边界数据：位于有效范围边缘的值，例如第一个和最后一个索引。错误数据：应当被拒绝的值，比如一个表示数组大小的负数。

---

10. Boolean Logic and Algorithms | 布尔逻辑与算法

Boolean logic operators AND, OR, and NOT are used in algorithm conditions to combine multiple comparisons. The outcome of an AND is true only if both operands are true; OR is true if at least one operand is true; NOT inverts a Boolean value. Understanding truth tables helps you write correct decision-making code and debug logical errors.

布尔逻辑运算符 AND、OR 和 NOT 用于算法条件中，组合多个比较。AND 只有在两个操作数都为真时结果才为真；OR 只要至少有一个操作数为真结果就为真；NOT 翻转布尔值。理解真值表有助于你编写正确的决策代码并调试逻辑错误。

A	B	A AND B	A OR B
True	True	True	True
True	False	False	True
False	True	False	True
False	False	False	False

Boolean logic often appears in algorithms with compound conditions, such as: IF age ≥ 18 AND hasLicense = True THEN… This ensures both conditions must be satisfied before granting access.

布尔逻辑常出现在具有复合条件的算法中，例如：IF age ≥ 18 AND hasLicense = True THEN……这确保两个条件都必须满足才能授予访问权限。

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

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