题目配置

---

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,\dots,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. 小写字母 $^{1}\mathrm{m}^{1}$ 的十六进制的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 = \text{true}$ , $B = D = \text{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
• 8
• 以上都不可能

---

阅读程序（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. （1分）代码存在死循环风险。 {{ 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) }}

• bxtT4fu
• 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. （1分）程序输出的一定是一个正整数。 {{ 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. （1分）将所有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）：

#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）：

#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

---