IGCSE计算机科学：伪代码题常考算法总结（排序、查找、遍历）

在IGCSE计算机科学考试中，伪代码题是必考的重点题型，分值占比高、难度大。很多同学面对伪代码题时，要么看不懂，要么写不出来。今天，我们就来总结伪代码题中常考的三大类算法：排序、查找、遍历，帮助你在考试中轻松拿分！

一、排序算法

1. 冒泡排序（Bubble Sort）

算法思想：重复地走访要排序的数列，一次比较两个元素，如果顺序错误就交换它们。
伪代码：

FOR i ← 0 TO n-2

    FOR j ← 0 TO n-2-i

        IF list[j] > list[j+1] THEN

            temp ← list[j]

            list[j] ← list[j+1]

            list[j+1] ← temp

        END IF

    END FOR

END FOR

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

2. 选择排序（Selection Sort）

算法思想：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。
伪代码：

FOR i ← 0 TO n-2

    minIndex ← i

    FOR j ← i+1 TO n-1

        IF list[j] < list[minIndex] THEN

            minIndex ← j

        END IF

    END FOR

    IF minIndex ≠ i THEN

        temp ← list[i]

        list[i] ← list[minIndex]

        list[minIndex] ← temp

    END IF

END FOR

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

3. 插入排序（Insertion Sort）

算法思想：将待排序的元素插入到已经排好序的序列中，直到全部插入完成。
伪代码：

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

    END WHILE

    list[j+1] ← key

END FOR

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

二、查找算法

1. 线性查找（Linear Search）

算法思想：从列表的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个列表。
伪代码：

FUNCTION linearSearch(list, target)

    FOR i ← 0 TO LEN(list)-1

        IF list[i] = target THEN

            RETURN i

        END IF

    END FOR

    RETURN -1

END FUNCTION

时间复杂度：O(n)
空间复杂度：O(1)

2. 二分查找（Binary Search）

算法思想：在有序列表中，每次将查找范围缩小一半，直到找到目标元素或查找范围为空。
伪代码：

FUNCTION binarySearch(list, target)

    low ← 0

    high ← LEN(list)-1

    

    WHILE low <= high

        mid ← (low + high) DIV 2

        IF list[mid] = target THEN

            RETURN mid

        ELSE IF list[mid] < target THEN

            low ← mid + 1

        ELSE

            high ← mid - 1

        END IF

    END WHILE

    RETURN -1

END FUNCTION

时间复杂度：O(log n)
空间复杂度：O(1)
前提条件：列表必须有序

三、遍历算法

1. 数组遍历

伪代码：

FOR i ← 0 TO LEN(list)-1

    OUTPUT list[i]

END FOR

2. 二维数组遍历

伪代码：

FOR i ← 0 TO rows-1

    FOR j ← 0 TO cols-1

        OUTPUT matrix[i][j]

    END FOR

END FOR

3. 字符串遍历

伪代码：

FOR i ← 0 TO LEN(str)-1

    OUTPUT str[i]

END FOR

四、其他常考算法

1. 求最大值/最小值

伪代码：

max ← list[0]

FOR i ← 1 TO LEN(list)-1

    IF list[i] > max THEN

        max ← list[i]

    END IF

END FOR

OUTPUT max

2. 求平均值

伪代码：

sum ← 0

FOR i ← 0 TO LEN(list)-1

    sum ← sum + list[i]

END FOR

average ← sum / LEN(list)

OUTPUT average

3. 统计频率

伪代码：

count ← 0

FOR i ← 0 TO LEN(list)-1

    IF list[i] = target THEN

        count ← count + 1

    END IF

END FOR

OUTPUT count

五、伪代码语法规范

1. 变量声明

DECLARE variableName : DATA_TYPE

2. 输入输出

INPUT variableName

OUTPUT variableName

3. 条件语句

IF condition THEN

    statements

ELSE

    statements

END IF

4. 循环语句

FOR counter ← start TO end

    statements

END FOR



WHILE condition

    statements

END WHILE



REPEAT

    statements

UNTIL condition

5. 函数定义

FUNCTION functionName(parameters)

    statements

    RETURN value

END FUNCTION

6. 数组操作

DECLARE list : ARRAY[1..n] OF INTEGER

list[index] ← value

六、考试技巧

1. 理解算法思想

不要死记硬背伪代码，要理解算法的核心思想。

2. 掌握时间空间复杂度

了解各种算法的时间空间复杂度，能够分析算法效率。

3. 注意边界条件

特别注意循环的起始和结束条件，避免数组越界。

4. 书写规范

伪代码要书写规范，使用正确的语法和缩进。

5. 测试验证

写完伪代码后，用简单的测试数据验证是否正确。

七、常见错误

1. 数组越界

FOR i ← 0 TO LEN(list)  // 错误，应该到LEN(list)-1

2. 死循环

WHILE condition  // 条件永远为真，导致死循环

3. 变量未初始化

DECLARE sum : INTEGER

FOR i ← 0 TO n-1

    sum ← sum + list[i]  // sum未初始化

END FOR

4. 数据类型错误

DECLARE name : STRING

name ← 123  // 错误，应该赋值字符串

八、备考建议

1. 多写多练

每天至少写一道伪代码题，保持手感。

2. 分类整理

将算法分类整理，建立自己的知识体系。

3. 做真题

练习历年真题，熟悉考试题型和难度。

4. 限时训练

在规定时间内完成伪代码题，提高答题速度。

5. 错题整理

将做错的题目整理到错题本上，定期复习。

结语

伪代码题是IGCSE计算机科学考试的重点和难点，但只要掌握核心算法、理解算法思想、多写多练，就能在考试中取得优异成绩。记住：理解比死记硬背更重要，实践比理论更有效。希望这篇文章能帮助你在IGCSE计算机科学考试中取得优异成绩！
祝各位同学考试顺利，金榜题名！