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

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

Algorithms are the heart of computer science. In the CIE IGCSE Computer Science syllabus (0478/0984), understanding how to design, represent and evaluate algorithms is essential. This guide covers the key concepts from pseudocode and flowcharts to searching and sorting algorithms, helping you master the topic for your exams.

算法是计算机科学的核心。在 CIE IGCSE 计算机科学大纲 (0478/0984) 中，理解如何设计、表示和评估算法至关重要。本篇指南涵盖从伪代码和流程图到搜索与排序算法的关键概念，帮助你掌握该主题以应对考试。

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

An algorithm is a precise, step-by-step set of instructions to solve a problem or perform a task. In computing, algorithms must be unambiguous, finite, and have a clearly defined input and output. A recipe, a set of directions, or a program are all examples of algorithms.

算法是一组精确的、逐步执行的指令，用于解决问题或完成任务。在计算领域，算法必须明确无误、有限，且具有定义清晰的输入和输出。食谱、导航路线或程序都是算法的例子。

2. Pseudocode and Flowcharts | 伪代码与流程图

Algorithms can be represented using pseudocode or flowcharts. Pseudocode is a structured, human-readable description using keywords like IF, WHILE, OUTPUT. Flowcharts use standard symbols to visualise the flow of control.

算法可以用伪代码或流程图表示。伪代码是一种结构化的、人类可读的描述，使用 IF、WHILE、OUTPUT 等关键字。流程图使用标准符号来可视化控制流程。

Symbol	Meaning	含义
Oval	Start / End	开始 / 结束
Rectangle	Process / Assignment	处理 / 赋值
Parallelogram	Input / Output	输入 / 输出
Diamond	Decision (Yes/No)	判断 (是/否)
Arrow	Flow of control	控制流方向

3. Sequence, Selection and Iteration | 顺序、选择与迭代

All algorithms can be built using three basic constructs. Sequence means executing instructions one after another. Selection makes decisions using IF statements. Iteration repeats steps using loops.

所有算法都可以通过三种基本结构构建。顺序意味着一条接一条地执行指令。选择使用 IF 语句进行判断。迭代使用循环重复执行步骤。

In CIE pseudocode, the key structures are:

在 CIE 伪代码中，关键结构是：

// Sequence
x ← 5
y ← x + 2
OUTPUT y

// Selection
IF x > 10 THEN
   OUTPUT "Large"
ELSE
   OUTPUT "Small"
ENDIF

// Iteration (FOR loop)
FOR i ← 1 TO 5
   OUTPUT i
NEXT i

4. Variables, Constants and Assignment | 变量、常量与赋值

A variable is a named memory location that stores data which can change during program execution. A constant holds a value that does not change. Assignment uses the ← symbol to give a value to a variable.

变量是一个命名的内存位置，存储在程序执行期间可以改变的数据。常量保存的值不会改变。赋值使用 ← 符号将值赋予变量。

Example: total ← 0 (assigns 0 to total), CONSTANT Pi ← 3.142. Always remember to declare and initialise variables before using them.

示例：total ← 0（将 0 赋给 total），CONSTANT Pi ← 3.142。请始终在使用变量前声明和初始化它们。

5. Input, Output and Basic Operators | 输入、输出与基本运算符

To interact with the user, algorithms use INPUT and OUTPUT statements. Common operators include arithmetic (+, -, *, /, MOD, DIV), relational (=, ≠, <, >, ≤, ≥) and logical (AND, OR, NOT).

为了与用户交互，算法使用 INPUT 和 OUTPUT 语句。常用运算符包括算术运算符（+、-、*、/、MOD、DIV）、关系运算符（=、≠、<、>、≤、≥）和逻辑运算符（AND、OR、NOT）。

MOD returns the remainder of division, while DIV returns the integer quotient. For example, 17 MOD 5 gives 2, and 17 DIV 5 gives 3.

MOD 返回除法的余数，而 DIV 返回整数商。例如，17 MOD 5 得到 2，17 DIV 5 得到 3。

6. Conditional Statements: IF…THEN…ELSE | 条件语句

Conditional statements allow an algorithm to take different paths based on a Boolean condition. A simple IF…THEN…ENDIF executes code only when the condition is true. IF…THEN…ELSE…ENDIF handles two branches.

条件语句允许算法根据布尔条件采取不同路径。简单的 IF…THEN…ENDIF 只在条件为真时执行代码。IF…THEN…ELSE…ENDIF 处理两个分支。

You can nest IF statements inside each other, and CIE also recognises the CASE…OF…ENDCASE structure for multi-way branching, which is clearer than multiple ELSE IF blocks.

你可以嵌套 IF 语句，且 CIE 也认可用于多路分支的 CASE…OF…ENDCASE 结构，这比多个 ELSE IF 块更清晰。

7. Loops: FOR, WHILE, REPEAT | 循环结构

Loops repeat a block of code. The three loop types in CIE pseudocode are count-controlled (FOR), pre-condition (WHILE) and post-condition (REPEAT…UNTIL).

循环重复执行一段代码。CIE 伪代码中的三种循环类型是计数控制 (FOR)、前置条件 (WHILE) 和后置条件 (REPEAT…UNTIL)。

FOR i ← 1 TO 10 … NEXT i: repeats exactly 10 times.
FOR i ← 1 TO 10 … NEXT i：精确重复 10 次。
WHILE condition DO … ENDWHILE: checks condition before each iteration; may run zero times.
WHILE condition DO … ENDWHILE：每次迭代前检查条件；可能运行零次。
REPEAT … UNTIL condition: runs at least once, then checks condition at the end.
REPEAT … UNTIL condition：至少运行一次，然后在末尾检查条件。

8. Linear Search | 线性搜索

A linear search checks each element of a list in turn until the target value is found or the end is reached. It works on unsorted lists and is easy to implement, but can be slow for large data sets.

线性搜索依次检查列表中的每个元素，直到找到目标值或到达末尾。它适用于未排序的列表，易于实现，但对于大型数据集可能很慢。

Pseudocode for linear search on an array of size n:

在大小为 n 的数组上进行线性搜索的伪代码：

PROCEDURE LinearSearch(A, target)
   found ← FALSE
   index ← -1
   FOR i ← 0 TO LEN(A)-1
      IF A[i] = target THEN
         found ← TRUE
         index ← i
         EXIT FOR
      ENDIF
   NEXT i
   OUTPUT index
END PROCEDURE

In the worst case, the algorithm examines every item, so the number of comparisons is proportional to the size of the list, n.

在最坏的情况下，算法检查每一个项目，因此比较次数与列表大小 n 成正比。

9. Binary Search | 二分搜索

Binary search is much faster but only works on a sorted list. It repeatedly divides the search interval in half, comparing the middle value with the target. If the target is larger, it searches the right half; if smaller, the left half.

二分搜索要快得多，但仅适用于已排序的列表。它反复将搜索区间分成两半，将中间值与目标进行比较。如果目标值更大，则搜索右半部分；如果更小，则搜索左半部分。

This algorithm reduces the number of comparisons drastically: a list of 1000 items needs at most about 10 comparisons (because 2¹⁰ ≈ 1000).

该算法大幅减少了比较次数：一个 1000 项的列表最多需要大约 10 次比较（因为 2¹⁰ ≈ 1000）。

PROCEDURE BinarySearch(A, target)
   low ← 0
   high ← LEN(A)-1
   found ← FALSE
   WHILE low ≤ high AND found = FALSE
      mid ← (low + high) DIV 2
      IF A[mid] = target THEN
         found ← TRUE
      ELSE IF A[mid] < target THEN
         low ← mid + 1
      ELSE
         high ← mid - 1
      ENDIF
   ENDWHILE
   IF found THEN OUTPUT mid ELSE OUTPUT -1
END PROCEDURE

10. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent items and swaps them if they are in the wrong order. The largest values ‘bubble’ to the end of the list after each pass. CIE IGCSE requires you to understand and write this algorithm.

冒泡排序反复遍历列表，比较相邻项并在顺序错误时交换它们。每轮遍历后，最大的值会“冒泡”到列表末尾。CIE IGCSE 要求你理解并能编写此算法。

Basic bubble sort pseudocode:

基本冒泡排序伪代码：

PROCEDURE BubbleSort(A)
   n ← LEN(A)
   FOR i ← 1 TO n-1
      FOR j ← 0 TO n-2
         IF A[j] > A[j+1] THEN
            temp ← A[j]
            A[j] ← A[j+1]
            A[j+1] ← temp
         ENDIF
      NEXT j
   NEXT i
END PROCEDURE

An improved version uses a flag (`swapped`) to detect if any swaps occurred in a pass; if none, the list is already sorted and the algorithm can terminate early.

改进版本使用标志位 (`swapped`) 检测某轮遍历中是否发生过交换；如果没有，列表已经有序，算法可以提前终止。

11. Trace Tables and Algorithm Testing | 追踪表与算法测试

A trace table is a manual tool used to test an algorithm by tracking the values of variables step by step. It helps identify logic errors and is a common exam question. You write the initial values, then update them after each line of code.

追踪表是一种手动工具，通过逐步跟踪变量值来测试算法。它有助于识别逻辑错误，是常见的考试题型。你写下初始值，然后在每行代码后更新它们。

For example, tracing a simple loop that calculates the sum of the first 3 positive integers:

例如，追踪一个计算前 3 个正整数之和的简单循环：

Statement	i	sum
Initial	–	0
i ← 1	1	0
sum ← sum + i	1	1
i ← 2	2	1
sum ← sum + i	2	3
i ← 3	3	3
sum ← sum + i	3	6

Using trace tables ensures you fully understand how an algorithm works and is an essential skill for the written papers.

使用追踪表可以确保你完全理解算法的工作原理，这是笔试中的一项基本技能。

12. Algorithm Efficiency: Comparing Search and Sort | 算法效率比较

Efficiency tells us how fast an algorithm runs and how much memory it uses. In CIE IGCSE, you are expected to describe the performance of basic algorithms without using formal big-O notation.

效率告诉我们算法运行的速度以及占用的内存量。在 CIE IGCSE 中，你需要描述基本算法的性能，而无需使用正式的大 O 记号。

Linear search checks every element in the worst case (n comparisons for a list of n items). Binary search, because it halves the search space each time, takes far fewer comparisons – roughly log₂n. For a list of 1000 items, linear search averages 500 comparisons, while binary search needs at most about 10.

线性搜索在最坏情况下检查每个元素（n 个项目的列表需要 n 次比较）。二分搜索由于每次将搜索空间减半，所需的比较次数少得多——大约 log₂n 次。对于 1000 个项目的列表，线性搜索平均需要 500 次比较，而二分搜索最多需要约 10 次。

Bubble sort compares adjacent pairs repeatedly, leading to roughly n² comparisons in total. It is simple but slow for large lists. Remember that binary search requires a sorted list, so sometimes it is worth sorting first if many searches will be performed.

冒泡排序重复比较相邻对，总共大约需要 n² 次比较。它简单，但对于大型列表速度较慢。记住，二分搜索要求列表已排序，因此如果要进行多次搜索，有时先排序是值得的。

Understanding these trade-offs helps you choose the right algorithm for a given problem and explain your choice in exam questions.

理解这些权衡有助于你为给定问题选择合适的算法，并在考题中解释你的选择。

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

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

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