一、单项选择题（共15题，每题2分，共计30分）

1. 十六进制数 9A 在（ ）进制下是 232。

{{ select(1) }}

• 四
• 八
• 十
• 十二

2. 我们约定布尔表达式只能包含 $p,q,r$ 三个布尔变量，以及三种布尔运算。如果无论 $p,q,r$ 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，$(p\land q)\lor r$ 和 $p\lor(q\lor r)$ 等价，$p\lor\lnot p$ 和 $q\lor\lnot q$ 也等价；$p\lor q$ 和 $p\land q$ 不等价。那么，两两不等价的布尔表达式最多有（ ）个。

{{ select(2) }}

• $32$
• $64$
• $128$
• $256$

3. 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 $16$ 位，其最大的可寻址空间为 $64\mathrm{KB}$。如果地址总线是 $32$ 位，则理论上最大可寻址的内存空间为（ ）。

{{ select(3) }}

• $128\mathrm{KB}$
• $1\mathrm{MB}$
• $1\mathrm{GB}$
• $4\mathrm{GB}$

4. 一棵二叉树一共有 $19$ 个节点，其叶子节点不可能有（ ）个。

{{ select(4) }}

• $1$
• $9$
• $10$
• $11$

5. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 $1$ 有 $5$ 个不同的独立集（$1$ 个双点集合、$3$ 个单点集合、$1$ 个空集），图 $2$ 有 $14$ 个不同的独立集。那么，图 $3$ 有（ ）个不同的独立集。

{{ select(5) }}

• $3280$
• $5536$
• $6560$
• $6866$

6. 如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 $\Theta(2^n)$。

{{ select(6) }}

• $\Theta(2^{n+1})$
• $\Theta(3^n)$
• $\Theta(n\times2^n)$
• $\Theta(2^{2n})$

7. 已知一棵二叉树有 $10$ 个节点，则其中至多有（ ）个节点有 $2$ 个子节点。

{{ select(7) }}

• $4$
• $5$
• $6$
• $7$

8. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

{{ select(8) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

9. 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符 AAABBBCCC 共有（ ）个不同的非空子串。

{{ select(9) }}

• $3$
• $12$
• $36$
• $45$

10. 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 $1$ 个逆序对，因此序列 $5,4,3,2,1$ 需要执行（ ）次操作，才能完成冒泡排序。

{{ select(10) }}

• $0$
• $5$
• $10$
• $15$

11. 将 $2,6,10,17$ 分别存储到某个地址区间为 $0\sim10$ 的哈希表中，如果哈希函数 $h(x)=$（ ）将不会产生冲突，其中 $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。

{{ select(11) }}

• $x\bmod11$
• $x^2\bmod11$
• $(2x)\bmod11$
• $\lfloor\sqrt{x}\rfloor\bmod11$

12. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 $5$ 个顶点、$8$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

{{ select(12) }}

• $2$
• $3$
• $4$
• $5$

13. 一场盛大的晚宴，有 $5$ 名本校选手和 $5$ 外校选手共同进膳。为了增进交流，他们决定相隔就坐，即每个本校选手左右旁都是外校选手，每个外校选手左右旁都是本校选手。那么，这一桌一共有（ ）种不同的就坐方案。

注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。

{{ select(13) }}

• $120$
• $2680$
• $2880$
• $3360$

14. 下面函数，它所计算的是 $a$ 和 $b$ 的（ ）。

int cal(int a, int b)
{
    if (b == 0)
        return a;
    else
        return cal(b, a % b);
}

{{ select(14) }}

• 最小公倍数
• 最大公因数
• 最大公共质因子
• 最小公共质因子

15. 在计算机显示器所使用的 RGB 颜色模型中，（ ）是三原色。

{{ select(15) }}

• 红色、黄色、绿色
• 红色、黄色、蓝色
• 黄色、蓝色、绿色
• 红色、蓝色、绿色

二、阅读程序（判断题1分，选择题3分，共计40分）

判断题正确填 T，错误填 F。

第1题

#include<iostream>
int main() {
    int n;
    std::cin >> n;
    long long s = 1;
    int i = 2;
    while (i*i < n) {
        if (n % i == 0) {
            s += i;
            s += n / i;
        }
        ++i;
    }
    if (i*i == n) s += i;
    if (s < n)
        std::cout << "Deficient\n";
    else if (s > n)
        std::cout << "Abundant\n";
    else
        std::cout << "Perfect\n";
}

16. 当输入 $n=1$ 时，程序输出 Deficient。

{{ select(16) }}

• 正确
• 错误

17. 如果 $n$ 是质数，程序总是输出 Perfect。

{{ select(17) }}

• 正确
• 错误

18. 程序能正确处理完全平方数（如 $n=4,9,16$）的因子计算。

{{ select(18) }}

• 正确
• 错误

19. 程序的时间复杂度为 $\Theta(\log n)$。

{{ select(19) }}

• 正确
• 错误

20. 程序的主要功能是（ ）。

{{ select(20) }}

• 质数的判定
• 计算因子个数
• 因数的分类
• 质因数分解

第2题

#include<iostream>
int main()
{
    int q[2000] = {10};
    int s[2000] = {0};
    int size = 1;
    char c;
    while (std::cin >> c) {
        int d = c - '0';
        int r = 0;
        for (int i = 0; i < size; ++i) {
            r = r * 10 + q[i];
            q[i] = r / 8;
            r = r % 8;
        }
        while (r > 0) {
            r = r * 10;
            q[size] = r / 8;
            size++;
            r = r % 8;
        }
        for (int i = 0; i < size; ++i)
            s[i] += q[i] * d;
        for (int i = size; i > 0; --i) {
            s[i-1] += s[i] / 10;
            s[i] %= 10;
        }
    }
    while (size > 0 and s[size-1] == 0)
        size --;
    for (int i = 0; i < size; ++i)
        std::cout << s[i];
    std::cout << "\n";
}

21. 如果输入数据 0，则程序输出 0。

{{ select(21) }}

• 正确
• 错误

22. 程序读取的输入字符必须是 '0' 到 '7' 之间的数字字符，否则可能导致错误结果。

{{ select(22) }}

• 正确
• 错误

23. 程序中的 q[0] 初始值只能设置为 10。

{{ select(23) }}

• 正确
• 错误

24. 若输入的数据长度为 $n$，该程序的时间复杂度为（ ）。

{{ select(24) }}

• $\Theta(\sqrt n)$
• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n^2)$

25. 程序的主要功能是（ ）。

{{ select(25) }}

• 将八进制整数转换为十进制整数
• 将八进制小数转换为十进制整数
• 将十进制整数转换为八进制
• 计算输入数字字符的累加和

26. 在循环中，语句 r = r * 10 + q[i] 的作用是（ ）。

{{ select(26) }}

• 将数组 q 直接拼接为一个整数
• 模拟除法运算中的被除数（用于除以 $8$）
• 计算除法的余数
• 扩展数组 q 的小数部分

27. 如果输入 2 时程序输出 250，那么输入 3 时程序输出是（ ）。

{{ select(27) }}

• 375
• 3000
• 125
• 500

第三题

#include<iostream>
const int mod = 1000000007;
int exp();
int term()
{
    char dummy;
    std::cin >> dummy;
    int t = exp();
    std::cin >> dummy;
    if (t == 0) return 1;
    else return t*2 % mod;
}
int exp()
{
    int result = 0;
    while (std::cin.peek() == '(')
    {
        result += term();
        result %= mod;
    }
    return result;
}
int main()
{
    std::cout << exp();
}

28. term 函数处理单个括号项时总会消耗输入流中的两个字符。

{{ select(28) }}

• 正确
• 错误

29. 代码无法处理超过 $200000$ 字符的输入，因为存在递归深度限制。

{{ select(29) }}

• 正确
• 错误

30. exp 函数使用 std::cin.peek() 预读字符但不消耗输入流，用于判断是否继续处理并列项。

{{ select(30) }}

• 正确
• 错误

31. 若输入字符串 (()())，程序的运行结果（ ）。

{{ select(31) }}

• $2$
• $4$
• $6$
• $8$

32. 计分规则中，AB 的分数是 A 与 B 的和，对应代码中的（ ）部分实现。

{{ select(32) }}

• term() 中的 t*2
• exp() 中的 result += term()
• term() 中的 return 1
• main() 中的输出

33. exp() 函数返回 $0$ 的情况是（ ）。

{{ select(33) }}

• 输入为空
• 遇到右括号
• 遇到非法字符
• 所有情况都不返回 $0$

34. 若将 term 函数中的 t*2 % mod 改为 (t*2+1) % mod，输入 ((()))，输出（ ）。

{{ select(34) }}

• $4$
• $7$
• $10$
• $15$

35. 若输入字符串 ()()()，代码执行过程中 term() 函数被调用的次数是？

{{ select(35) }}

• $1$
• $2$
• $3$
• $6$

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

第1题

两人进行 $n$ 次石头剪刀布游戏，给定对方的出拳序列，由 R、S、P 组成（分别表示石头、剪刀、布）。你的出拳需满足：从未输过（每次非赢即平）；相邻两次出拳不同。求可能赢的最大对局数（即赢的次数，平局不计入）。

#include<iostream>
int score(int a,int b){
    if(____(1)____) return 0;
    else if(a=='R' and b=='S')return 1;
    else if(____(2)____)return 1;
    else if(a=='P' and b=='R')return 1;
    else return -10000000;
}
int main(){
    ____(3)____ ;
    int n;
    std::cin>>n;
    while(n-->0){
        char c;
        std::cin>>c;
        int newR = ____(4)____ ;
        int newS = ____(5)____ ;
        int newP = ____(6)____ ;
        R=newR;
        S=newS;
        P=newP;
    }
    std::cout<<std::max(std::max(R,S),P);
}

36. (1) 处应填（ ）。

{{ select(36) }}

• a != b
• a < b
• a > b
• a == b

37. (2) 处应填（ ）。

{{ select(37) }}

• a=='S' and b=='P'
• a=='S' and b=='R'
• a=='P' and b=='S'
• a=='R' and b=='P'

38. (3) 处应填（ ）。

{{ select(38) }}

• char R,S,P
• char R = 'R',S = 'S',P = 'P'
• int R = 0,S = 0,P = 0
• int R = 'R',S = 'S',P = 'P'

39. (4)(5)(6) 处应填（ ）。

{{ select(39) }}

• score(R,c)、score(S,c)、score(P,c)
• score('R',c)、score('S',c)、score('P',c)
• R + score('R',c)、S + score('S',c)、P + score('P',c)
• std::max(S,P)+score('R',c)、std::max(R,P)+score('S',c)、std::max(R,S)+score('P',c)

第2题

给定 $n\times n$ 个方格构成的矩阵，刷满了红色和蓝色。现在要矩阵的一些格子刷上紫色，使得矩阵同时满足以下两个条件：从 $(1,1)$ 走到 $(n,n)$，保证存在一条路径使其只经过红色和紫色；从 $(1,n)$ 走到 $(n,1)$，保证存在一条路径使其只经过蓝色和紫色。注意，行动时只可以往任何一个方向前进，至少要将多少格子刷成紫色才能使以上两个条件成立呢？

#include<iostream>
#include<deque>
int n;
const int maxn = 500;
char c[maxn][maxn];
int dist[maxn][maxn];
int solve(int sx, int sy, int tx, int ty, char color) {
    bool visited[maxn][maxn] = {false};
    std::deque<std::pair<int, int>> q;
    q.push_back({sx, sy});
    visited[sx][sy] = true;
    ____(1)____ ;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();
        const int dx[4] = {1, -1, 0, 0};
        const int dy[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx and nx < n and 0 <= ny and ny < n) {
                if (not visited[nx][ny]) {
                    visited[nx][ny] = true;
                    if ( ____(2)____ ) {
                        dist[nx][ny] = dist[x][y];
                        q.push_front({nx, ny});
                    }
                    else {
                        dist[nx][ny] = ____(3)____ ;
                        q.push_back({nx, ny});
                    }
                }
            }
        }
    }
    return ____(4)____ ;
}

int main()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> c[i][j];
        }
    }
    std::cout << ____(5)____ + ____(6)____ << "\n";
}

40. (1) 处应填（ ）。

{{ select(40) }}

• c[sx][sy] = 0
• dist[sx][sy] = -1
• dist[sx][sy] = 0
• dist[sx][sy] = 1

41. (2) 处应填（ ）。

{{ select(41) }}

• dist[nx][ny] == 0
• dist[nx][ny] == 1
• c[nx][ny] == color
• c[nx][ny] == c[x][y]

42. (3) 处应填（ ）。

{{ select(42) }}

• 0
• 1
• dist[x][y]
• dist[x][y] + 1

43. (4) 处应填（ ）。

{{ select(43) }}

• dist[sx][sy]
• dist[tx][ty]
• c[sx][sy]
• c[tx][ty]

44. (5) 处应填（ ）。

{{ select(44) }}

• solve(0, 0, n-1, n-1, 'R')
• solve(0, 0, n-1, n-1, 'B')
• solve(0, n - 1, 0, n-1, 'R')
• solve(0, n - 1, 0, n-1, 'B')

45. (6) 处应填（ ）。

{{ select(45) }}

• solve(0, n-1, n-1, 0, 'R')
• solve(0, n-1, n-1, 0, 'B')
• solve(0, 0, n-1, n-1, 'R')
• solve(0, 0, n-1, n-1, 'B')