BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 16 题

阅读程序（判断题正确填 A，错误填 B，选择题每题有且仅有一个正确选项；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

第一题

#include <iostream>
using namespace std;
int main() {
    int n, a[105], avg = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        avg += a[i];
    }
    avg /= n;
    for (int i = 1; i < n; i++)
        if (a[i] < avg) {
            a[i + 1] -= (avg - a[i]);
            ans += (avg - a[i]);
        } 
        else if (a[i] > avg) {
            a[i + 1] += (a[i] - avg);
            ans += (a[i] - avg);
        }
    cout << ans << endl;
    return 0;
}

假设输入的所有数是不超过 $100$ 的正整数，完成下面的判断题和单选题。

判断题

1. 该程序的算法时间复杂度为 $O(n)$。（ ） 2. 若将第 004 行的代码改为 int n, a[105], avg, ans;（声明变量时不赋值），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 3. 若将第 004 行的代码改为 int n, a[100], avg = 0, ans = 0;（更改数组 a 的大小），程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 4. 若将第 011 行的 for 循环执行条件改为 i <= n，程序仍可以被正常执行，

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

本题考查排序算法的基本概念和特性，包括稳定性、时间复杂度等。

常见误区：混淆稳定排序与不稳定排序，误以为冒泡和选择排序速度相同，不清楚基数排序不需要比较。

核心概念：稳定排序：相等元素的相对顺序不变（冒泡、插入、归并、计数、基数）。不稳定排序：相等元素相对顺序可能改变（选择、快速、希尔、堆排序）。

推导分析：基数排序按位分配，不涉及关键字比较；选择排序比较次数始终为n(n-1)/2，与初始状态无关。

避坑指南：计数排序不是比较排序，是桶排序思想。

解题技巧：熟记常见排序算法的时间复杂度、稳定性和适用场景。