满分 100 分。语言环境为 C++。

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 启动计算机引导操作系统是将操作系统： {{ select(1) }}

• 从磁盘调入中央处理器
• 从内存储器调入高速缓冲存储器
• 从软盘调入硬盘
• 从系统盘调入内存储器

2. Windows 9x 是一种（　）操作系统。 {{ select(2) }}

• 单任务字符方式
• 单任务图形方式
• 多任务字符方式
• 多任务图形方式

3. 在 24×24 点阵的字模中，汉字"一"与"编"的字模占用字节数分别是： {{ select(3) }}

• 72　72
• 32　32
• 32　72
• 72　32

4. 计算机的运算速度取决于给定时间内其处理器所能处理的数据量。处理器一次能处理的数据量称为字长。已知 64 位的奔腾处理器一次能处理 64 位，相当于（　）字节。 {{ select(4) }}

• 8
• 1
• 16
• 2

5. 算式 (2047)₁₀ − (3FF)₁₆ + (2000)₈ 的结果是： {{ select(5) }}

• (2048)₁₀
• (2049)₁₀
• (3746)₈
• (1AF7)₁₆

6. 计算机的运算速度可以用 MIPS 来描述，它的含义是： {{ select(6) }}

• 每秒执行百万条指令
• 每秒处理百万个字符
• 每秒执行千万条指令
• 每秒处理千万个字符

7. 设栈 S 的初始状态为空，现有 5 个元素组成的序列 {1,2,3,4,5}，对该序列在栈 S 上依次进行如下操作（从序列中的 1 开始，出栈后不再进栈）：进栈、出栈、进栈、进栈、出栈、进栈、出栈、进栈。出栈的元素序列是： {{ select(7) }}

• {5,4,3,2,1}
• {2,3}
• {2,3,4}
• {1,3,4}

8. 在有 n 个叶节点的哈夫曼树中，节点总数为： {{ select(8) }}

• 不确定
• 2n − 1
• 2n + 1
• 2n

9. 电线上停着两种鸟（A 和 B），可以看出相邻的两只鸟将电线划分为一个线段。这些线段可分为两类：一类是线段两端的鸟种类相同，另一类是线段两端的鸟种类不同。已知电线的两个端点处恰好停着种类相同的鸟，那么两端的鸟种类不同的线段数目一定是： {{ select(9) }}

• 奇数
• 偶数
• 可奇可偶
• 数目固定

10. 从未排序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为： {{ select(10) }}

• 插入排序
• 归并排序
• 选择排序
• 快速排序

11. 对于一棵满二叉树，若其叶节点数为 m、分支点数为 L、总节点数为 n，则下列关系式恒成立的是： {{ select(11) }}

• n = L + m
• L + m = 2n
• m = L − 1
• n = 2L − 1

12. 以下不是操作系统名字的是： {{ select(12) }}

• Windows XP
• Arch/Info
• Linux
• OS/2

13. 以下不是个人计算机的硬件组成部分的是： {{ select(13) }}

• 主板
• 虚拟内存
• 总线
• 硬盘

14. 已知元素 (8,25,14,87,51,90,6,19,20)，这些元素以（　）的顺序全部入栈，再全部出栈，可使栈的出栈顺序满足：8 在 51 之前；90 在 87 之后；20 在 14 之后；25 在 6 之前；19 在 90 之后。 {{ select(14) }}

• 20,6,8,51,90,25,14,19,87
• 51,6,19,20,14,8,87,90,25
• 19,20,90,8,6,25,51,14,87
• 6,25,51,8,20,19,90,87,14

15. 假设我们用向量 d=(a₁,a₂,⋯,a₅) 表示无向连通图 G 的 5 个顶点的度数，下面给出的（　）组 d 值合理。 {{ select(15) }}

• (2,2,2,2,2)
• (1,2,2,1,1)
• (3,3,3,2,2)
• (5,4,3,2,1)

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填"正确"、错误填"错误"；除特殊说明外，判断题每题 2 分，选择题每题 3 分，共计 40 分）

(1)

#include <iostream>
#include <cmath>
using namespace std;
bool IsPrime(int num) {
    for (int i=2; i<=sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}
int main() {
    int num = 0;
    cin >> num;
    if (IsPrime(num)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

■ 判断题

16. 输入 97 时，输出为 NO。 {{ select(16) }}

• 正确
• 错误

17. 输入 119 时，输出为 YES。 {{ select(17) }}

• 正确
• 错误

18. 若将第 5 行的 <= 改成 <，程序输出不会改变。 {{ select(18) }}

• 正确
• 错误

19. 当程序执行第 8 行时，i 的值为 sqrt(num)。 {{ select(19) }}

• 正确
• 错误

■ 选择题

20. 最坏情况下，此程序的时间复杂度是： {{ select(20) }}

• O(num)
• O(num²)
• O(√num)
• O(log num)

21. 若输入为 20 以内的正整数，则输出 YES 的概率是： {{ select(21) }}

• 0.45
• 0.4
• 0.5
• 0.35

(2)

#include <bits/stdc++.h>
using namespace std;
const int mod = 2048;
long long c,n;
long long kasumi(long long x,long long mi) {
    long long res=1;
    while (mi) {
        if (mi & 1) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        mi >>= 1;
    }
    return res;
}
int main() {
    cin >> n >> c;
    if (n == 3) {
        printf("%lld", c * (c - 1));
        return 0;
    }
    long long ans = ((kasumi(c-1,n) + (c-1) * kasumi(-1,n)) % mod + mod) % mod;
    cout << ans << endl;
    return 0;
}

■ 判断题

22. 将第 9 行和第 11 行中的圆括号去掉，程序输出不会改变。 {{ select(22) }}

• 正确
• 错误

23. 将第 12 行的 mi >>= 1 改为 mi *= 0.5，程序输出不会改变。 {{ select(23) }}

• 正确
• 错误

24. 若输入 4 4，输出为 78。 {{ select(24) }}

• 正确
• 错误

25. 此程序的时间复杂度为 O(log n)。 {{ select(25) }}

• 正确
• 错误

■ 选择题

26.（4分）若输入 3 4，输出为： {{ select(26) }}

• 8
• 12
• 18
• 19

(3)

#include <cstdio>
int n,r,num[10000];
bool mark[10000];
void print() {
    for (int i=1; i<=r; i++)
        printf("%d ", num[i]);
    printf("\n");
}
void search(int x) {
    for (int i=1; i<=n; i++)
        if (!mark[i]) {
            num[x] = i;
            mark[i] = true;
            if (x == r) print();
            search(x + 1);
            mark[i] = false;
        }
}
int main() {
    scanf("%d%d", &n, &r);
    search(1);
}

■ 判断题

27. 程序结束时，对任意 1≤i≤n，都有 mark[i]=0。 {{ select(27) }}

• 正确
• 错误

28. 若 n<r，则程序无输出。 {{ select(28) }}

• 正确
• 错误

29. 若输入 4 3，则输出中数字 1 和 2 的个数不同。 {{ select(29) }}

• 正确
• 错误

30. 此程序的时间复杂度为 O(n)。 {{ select(30) }}

• 正确
• 错误

■ 选择题

31. 若输入 6 3，则函数 print 的执行次数为： {{ select(31) }}

• 60
• 120
• 6
• 720

32. 若输入 7 4，则输出的最后一行为： {{ select(32) }}

• 4 5 6 7
• 7 6 5 4
• 4 3 2 1
• 1 2 3 4

三、完善程序（单选题，每小题 3 分，共计 30 分）

(1)

Kruskal 求最小生成树的思想：首先将 n 个点看作 n 个独立的集合，将所有边排序（从小到大）。然后按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于同一集合。若不属于同一集合，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若属于同一集合，则跳过。直到找到 n−1 条边为止。

#include <iostream>
#include <algorithm>
using namespace std;
struct point { int x, y, v; } a[10000];
int cmp(const point &a, const point &b) {
    if ( ① ) return 1;
    return 0;
}
int fat[101];
int father(int x) {
    if (fat[x] != x) return fat[x] = ② ;
    return fat[x];
}
void unionn (int x, int y){
    int fa = father(x), fb = father(y);
    if (fa != fb) fat[fa] = fb;
}
int main() {
    int i,j,n,m, k=0, ans=0, cnt=0;
    cin >> n;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++) {
            cin >> m;
            if (m != 0) {
                k++; a[k].x=i; a[k].y=j; a[k].v=m;
            }
        }
    sort(a+1, a+1+k, ③ );
    for (i=1; i<=n; i++) fat[i] = i;
    for (i=1; i<=k; i++){
        if (father(a[i].x) != ④ ) {
            ans += a[i].v;
            unionn(a[i].x, a[i].y);
            cnt++;
        }
        if ( ⑤ ) break;
    }
    cout << ans << endl;
    return 0;
}

33. ① 处应填： {{ select(33) }}

• a.v < b.v
• a.v > b.v
• a.v >= b.v
• a.v <= b.v

34. ② 处应填： {{ select(34) }}

• father(x)
• father(fat[x])
• fat[father(x)]
• x

35. ③ 处应填： {{ select(35) }}

• algorithm
• point
• cmp
• sizeof(a)

36. ④ 处应填： {{ select(36) }}

• a[i].y
• father(a[i].y)
• fat[a[i].y]
• a[i].x

37. ⑤ 处应填： {{ select(37) }}

• cnt > 0
• i == 1
• ans == n-1
• cnt == n-1

(2)

欧拉路径问题是指从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边（一次且仅一次）。算法代码如下。

#include <iostream>
using namespace std;
int G[5][5];
int visited[5][5];
int n = 5;
void euler(int u) {
    for (int v=0; v<n; v++) {
        if (G[u][v] && ① ) {
            cout << u << "->" << v << endl;
            visited[u][v] = visited[v][u] = ② ;
            ③
        }
    }
}
int main() {
    G[1][2] = G[2][1] = G[1][3] = ④ = 1;
    G[2][4] = G[4][2] = G[3][4] = ⑤ = 1;
    euler(1);
    return 0;
}

38. ① 处应填： {{ select(38) }}

• G[v][u]
• !visited[u][v]
• visited[u][v]
• visited[v][u]

39. ② 处应填： {{ select(39) }}

• 1
• 0
• u
• v

40. ③ 处应填： {{ select(40) }}

• euler(v);
• euler(u);
• G[u][v]=0;
• G[v][u]=0;

41. ④ 处应填： {{ select(41) }}

• G[0][1]
• G[1][0]
• G[3][1]
• G[0][3]

42. ⑤ 处应填： {{ select(42) }}

• G[0][2]
• G[2][0]
• G[2][1]
• G[4][3]