一、单项选择题

1. 设根节点的深度为 $0$，若 $k>1$，则一棵深度为 $h$ 的满 $k$ 叉树共有（ ）个节点。

{{ select(1) }}

• $(k^{h+1}-1)/k$
• $(k^h-1)/(k-1)$
• $(k^{h+1}-1)/(k-1)$
• $(k^h-1)/k$

2. 微型计算机中，控制器的基本功能是（ ）。

{{ select(2) }}

• 控制机器各个部件协调工作
• 实现算术运算和逻辑运算
• 存储各种控制信息
• 获取外部信息
• 存放程序和数据

3. 设栈 $S$ 和队列 $Q$ 的初始状态为空，元素 $e_1,\cdots,e_6$ 依次通过栈 $S$，一个元素出栈后即进入队列 $Q$，若出队的顺序为 $e_2,e_4,e_3,e_6,e_5,e_1$，则栈 $S$ 的容量至少应该为（ ）。

{{ select(3) }}

• 1
• 3
• 4
• 6

4. 完全二叉树共有 2019 个节点，则它的叶节点数是（ ）。

{{ select(4) }}

• 1019
• 1009
• 1000
• 1010

5. 将数组 $\{8,23,4,16,77,-5,53,100\}$ 中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。

{{ select(5) }}

• 5
• 6
• 7
• 9

6. 设栈 $S$ 的初始状态为空，元素 $a,b,c,d,e,f$ 依次入栈 $S$，$S$ 的最大容量为 3，则有（ ）种可能的出栈顺序。

{{ select(6) }}

• 80
• 85
• 89
• 90

7. 与十进制数 $28.5625$ 相等的四进制数是（ ）。

{{ select(7) }}

• 131.20
• 131.21
• 130.20
• 130.21

8. 小写字母 'm' 的十六进制 ASCII 码值是（ ）。

{{ select(8) }}

• 6A
• 6B
• 6C
• 6D

9. 在有 $N$ 个叶节点的哈夫曼树中，节点总数为（ ）。

{{ select(9) }}

• $2N-1$
• $2N$
• $2N+1$
• $2N+3$

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

{{ select(10) }}

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

11. 下列关于图灵奖的说法中，错误的是（ ）。

{{ select(11) }}

• 图灵奖是美国计算机协会于 1966 年设立的，专门奖励那些为计算机事业做出重要贡献的个人
• 图灵奖有“计算机界诺贝尔奖”之称
• 迄今为止，还没有华裔计算机科学家获此殊荣
• 图灵奖的名称取自计算机科学先驱、英国科学家阿兰·图灵

12. 若计算机在工作过程中突然断电，（ ）中的信息不会丢失。

{{ select(12) }}

• 寄存器
• CPU
• ROM
• RAM

13. 设 $A=C=\mathrm{true}$，$B=D=\mathrm{false}$，逻辑运算表达式（ ）的值为真。

{{ select(13) }}

• $(A\land B)\lor((C\land D)\lor A)$
• $((A\land B)\lor C)\land D$
• $(B\lor(C\land D))\lor(D\land A)$
• $A\land(D\lor C)\land B$

14. 二叉树 $T$，已知其前序遍历序列是 1243576，后序遍历序列是 4275631，则该二叉树的中序遍历序列不可能是（ ）。

{{ select(14) }}

• 4217536
• 2417536
• 4217563
• 2415736

15. 2-3 树是一种特殊的树，它满足两个条件：（1）每个非叶节点有两个或三个子节点；（2）所有叶节点到根节点的路径长度相同。如果一棵 2-3 树有 10 个叶节点，那么它可能有（ ）个非叶节点。

{{ select(15) }}

• 6
• 7
• 9
• 13

二、阅读程序

阅读程序（1）

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s; // 如无特殊说明，保证输入字符串只有小写字母，且长度小于 10
    for (int i,j;;) {
        for (i=1; i<s.size(); i++)
            if (s[i] >= 'a' && s[i] <= 'z' && s[i] == s[i-1]) break;
        if (i == s.size()) break;
        for (j=i; j<s.size(); j++)
            if (s[j] != s[j-1]) break;
        string t = "";
        if (j < s.size()) t = s.substr(j);
        t += s[i]-'a'+'A';
        t += '0'+j-i+1;
        t += s.substr(0,i-1);
        s = t;
    }
    cout << s << endl;
    return 0;
}

16. （判断题）代码存在死循环风险。

{{ select(16) }}

• 正确
• 错误

17. （判断题）将第 7 行中的 i<s.size() 改成 i<=s.size()-1，程序运行正常且输出没有变化。

{{ select(17) }}

• 正确
• 错误

18. （判断题）记 $s$ 的长度为 $n$，第 8 行中的 if 会被执行的总次数在最坏情况下是 $O(n^2)$。

{{ select(18) }}

• 正确
• 错误

19. 假如强行输入长度大于 10 的字符串，则以下说法中正确的是（ ）。

{{ select(19) }}

• 程序可能报错并异常退出
• 程序仍可运行，但输出的内容可能不只有小写字母和数字
• 程序可能出现死循环
• 以上都不对

20. 输入 bxttttfu，输出为（ ）。

{{ select(20) }}

• bxT4fu
• FUT4BX
• BXT4fu
• fuT4bx

21. 输入 aabbccdd，输出为（ ）。

{{ select(21) }}

• A2B2C2D2
• D2C2B2A2
• AABBCCDD
• a2b2c2d2

阅读程序（2）

#include <iostream>
using namespace std;
const int V = 100;
int n,m,ans,e[V][V];
bool visited[V];

void dfs(int x, int len) {
    visited[x] = true;
    if (len > ans) ans = len;
    for (int i=1; i<=n; i++)
        if (!visited[i] && ~e[x][i])
            dfs(i, len + e[x][i]);
    visited[x] = false;
}

int main() { // 保证所有输入都是小于 100 的正整数
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) e[i][j] = -1;
    for (int i=1,a,b,c; i<=m; i++) {
        cin >> a >> b >> c;
        e[a][b] = e[b][a] = c;
    }
    for (int i=1; i<=n; i++) dfs(i, 0);
    cout << ans << endl;
    return 0;
}

22. （判断题）程序输出的一定是一个正整数。

{{ select(22) }}

• 正确
• 错误

23. （判断题）~e[x][i] 等价于 e[x][i] != -1。

{{ select(23) }}

• 正确
• 错误

24. （判断题）输入允许 $n$ 最大为 100，但实际上，在 1 秒的时限内无法运行完 $n=100$ 规模的输入数据。

{{ select(24) }}

• 正确
• 错误

25. （判断题）如果输入的图是连通的，那么当 ans 最后一次被赋值时，visited[1..n] 一定全都是 true。

{{ select(25) }}

• 正确
• 错误

26. 该程序的时间复杂度为（ ）。

{{ select(26) }}

• $O(n+m)$
• $O(n^2+m)$
• $O(2^n+m)$
• $O(n!+m)$

27. 输入如下数据，输出为（ ）。

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

{{ select(27) }}

• 100
• 150
• 180
• 210

阅读程序（3）

#include <iostream>
using namespace std;
typedef unsigned int ui;
ui work(ui x) {
    ui s = x & (-x), r = s + x;
    return r | (((x ^ r) >> 2) / s);
}
int main() {
    ui n, k;
    cin >> n >> k; // 保证输入在 1..1000000 范围内
    for (int i=1; i<=k; i++) n = work(n);
    cout << n << endl;
    return 0;
}

28. （判断题）将所有 ui 类型变量改为 int 类型，程序运行结果不变。

{{ select(28) }}

• 正确
• 错误

29. （判断题）假如强制输入 n=0，程序会发生死循环。

{{ select(29) }}

• 正确
• 错误

30. （判断题）假设不发生数值范围溢出的情况，那么主函数里的 n 只会单调变大。

{{ select(30) }}

• 正确
• 错误

31. （判断题）r | (((x ^ r) >> 2) / s) 这个表达式有三组括号，它们都是必需的，即去掉任何一组都可能造成输出不同。

{{ select(31) }}

• 正确
• 错误

32. 输入 1 100，输出为（ ）。

{{ select(32) }}

• 0
• 某个数值确定但很大的数
• 运行可能会报错
• 不确定的某个随机数值

33. 输入 3 14，输出为（ ）。

{{ select(33) }}

• 45
• 46
• 48
• 47

三、完善程序

完善程序（1）

对于一个给定的两两不等的正整数序列，笛卡儿树是这样的一棵二叉树：首先它是一个最小堆，即除了根节点，每个节点的权值都大于其父节点的权值；其次，它的中序遍历序列恰好就是给定的序列。现输入序列 $a_1,\cdots,a_n$（$1\le n\le 100$），试求其对应的笛卡儿树的深度 $d$（设根节点的深度为 1），以及有多少个叶节点的深度等于 $d$。

#include <iostream>
using namespace std;
const int SIZE = 100+5;
const int INFINITY = 1000000;
int n, a[SIZE], maxDeep, num;
void solve(int left, int right, int deep) {
    int i,j;
    if (deep > maxDeep) {
        maxDeep = deep;
        num = 1;
    } else if (deep == maxDeep)
        /* ① */;
    int min = INFINITY;
    for (int i=left; i<=right; i++)
        if (min > a[i]) {
            min = a[i];
            /* ② */;
        }
    if (left < j) /* ③ */;
    if (j < right) /* ④ */;
}
int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    /* ⑤ */;
    cout << maxDeep << ' ' << num << endl;
    return 0;
}

34. ① 处应填（ ）。

{{ select(34) }}

• num = 0
• num++
• num = INFINITY
• num--

35. ② 处应填（ ）。

{{ select(35) }}

• i = j
• j++
• j = min(i,j)
• j = i

36. ③ 处应填（ ）。

{{ select(36) }}

• solve(left, j-1, deep+1)
• solve(left, j, deep+1)
• solve(left, j, deep)
• solve(left, j-1, deep)

37. ④ 处应填（ ）。

{{ select(37) }}

• solve(j, right, deep+1)
• solve(j+1, right, deep)
• solve(j+1, right, deep+1)
• solve(j, right, deep)

38. ⑤ 处应填（ ）。

{{ select(38) }}

• solve(1,n,1)
• solve(1,n,0)
• solve(0,n-1,1)
• solve(1,n+1,1)

完善程序（2）

基环树是一个具有 $n$ 个顶点和 $n$ 条边、无重边且连通的无向图。基环树上有且只有唯一的一个环（可能是自环）。输入一棵基环树，输出环的大小。

输入数据：第一行一个整数 $n$，表示节点数，随后 $n$ 行每行两个数 $u,v$，表示节点 $u$ 和 $v$ 之间有一条无向边。输入数据保证无重边且连通。

输出要求：一个正整数，表示环的大小。

#include <iostream>
using namespace std;
int n, d[109], hd[109], tot;
struct edge {int t, nxt;} es[509];
void add(int u, int v) {
    es[++tot] = (edge) {/* ① */};
    hd[u] = tot;
}
void dfs(int u, int fa) {
    for (int i = hd[u]; /* ② */; i = es[i].nxt) {
        int v = es[i].t;
        if (/* ③ */) {
            if (d[v] == 0) {
                d[v] = d[u] + 1;
                dfs(v, u);
            } else {
                cout << /* ④ */ << endl;
                exit(0);
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i=1,u,v; i<=n; i++) {
        cin >> u >> v;
        add(u,v); add(v,u);
    }
    d[1] = 1;
    dfs(/* ⑤ */);
    return 0;
}

39. ① 处应填（ ）。

{{ select(39) }}

• v, hd[v]
• v, hd[u]
• u, hd[v]
• v, nxt[u]

40. ② 处应填（ ）。

{{ select(40) }}

• !i
• ~i
• i
• i >= 0

41. ③ 处应填（ ）。

{{ select(41) }}

• v
• v != fa
• v == 0
• fa != -1

42. ④ 处应填（ ）。

{{ select(42) }}

• d[u]-d[v]
• d[fa]-d[v]
• d[u]-d[v]+1
• u-v

43. ⑤ 处应填（ ）。

{{ select(43) }}

• 0,-1
• 0,0
• 1,1
• 1,-1