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

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

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

二、查找算法

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

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

三、遍历算法

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. 错题整理

结语