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

1. $(2025)_8 + (2025)_{16}$ 和以下哪个选项相等（ ）。

{{ select(1) }}

• $(9244)_{10}$
• $(2100222)_4$
• $(10010000111010)_2$
• $(234A)_{16}$

2. 以下（ ）函数声明是合法的。

{{ select(2) }}

• int Bubblesort(char a[][],int n)
• int Bubblesort(char a[10][],int n)
• int Bubblesort(char a[][20],int n)
• int Bubblesort(char [,] a,int n)

3. 设循环队列中数组的下标范围是 $0 \sim n-1$，其头尾指针分别为 $f$ 和 $r$，则其元素个数为（ ）。

{{ select(3) }}

• $r-f$
• $r-f+1$
• $(r-f) \bmod n + 1$
• $(r-f+n) \bmod n$

4. 后缀表达式 1 2 + 3 * 14 7 / - 对应的前缀表达式为（ ）。

{{ select(4) }}

• 1 + 2 * 3 - 14 / 7
• - * 1 + 2 3 / 14 7
• - * + 1 2 3 / 14 7
• - 1 + 2 * 3 14 / 7

5. 给定一棵二叉树，其前序遍历结果为 $abdecfg$，中序遍历结果为 $debacfg$，则这棵树的后序遍历结果为（ ）。

{{ select(5) }}

• $edbgfca$
• $edgbfca$
• $debgfca$
• $dbegfca$

6. 下列是关于数据结构的说法不正确的是（ ）。

{{ select(6) }}

• 数据结构是带有结构的数据元素的集合
• 线性表的线性存储结构优于链式存储结构
• 队列是一个先进先出的线性表
• 队列是只能在一端插入，另一端删除的线性表

7. 已知无向图 $G$ 含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。$G$ 所含的顶点个数至少是（ ）。

{{ select(7) }}

• $10$
• $11$
• $13$
• $15$

8. 下面关于指针的说法正确的是（ ）。

{{ select(8) }}

• 在64位计算机中一个指针变量占4字节
• 指针运算实际上是地址操作，只能取地址和间接访问，不能进行加减运算
• 数组名不是指向数组元素的指针变量
• 指针只可以静态申请内存空间

9. 方程 $a \times b = (a \operatorname{or} b) \times (a \operatorname{and} b)$，在 $a,b$ 都取 $[0,31]$ 中的整数时，共有（ ）组解。（$\times$ 表示乘法；or 表示按位或运算；and 表示按位与运算）

{{ select(9) }}

• $32$
• $256$
• $454$
• $512$

10. 双向链表中有两个指针域，$llink$ 和 $rlink$，分别指向前驱及后继，设 $p$ 指向链表中的一个结点，$q$ 指向一待插入结点，现要求在 $p$ 前插入 $q$，则正确的插入为（ ）。

{{ select(10) }}

• p->llink = q; q->rlink = p; p->llink->rlink = q;q->llink = p->llink;
• q->llink = p->llink; p->llink->rlink = q; q->rlink = p;p->llink = q->rlink;
• p->llink->rlink = q; q->rlink = p;q->llink = p->llink; p->llink = q;
• q->rlink = p; p->rlink = q;p->llink->rlink = q; q->rlink = p;

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

{{ select(11) }}

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

12. 输入由 $n$ 个不等的数构成的数组 $a$，输出 $a$ 中第二小的数。在最坏的情况下，该算法需要做（ ）次比较。

if (a[1] < a[2])
{
    min1 = a[1];
    min2 = a[2];
}
else
{
    min1 = a[2];
    min2 = a[1];
}
for(int i = 3; i <= n; i++)
    if (a[i] < min2)
        if (a[i] < min1)
        {
            min2 = min1;
            min1 = a[i];
        }
        else
        {
            min2 = a[i];
        }

{{ select(12) }}

• $2n-1$
• $2n-2$
• $2n-3$
• $2n$

13. 整型数组 a 中有 n 个元素，能计算 a 中有多少个数字大于 lower 且小于 upper 的函数，应该将下划线依次替换为（ ）。

int solve(int a[], int n, int lower, int upper)
{
    std::sort(a, a + n);
    auto begin = std::________(a, a + n, lower);
    auto end = std::________(a, a + n, upper);
    return end - begin;
}

{{ select(13) }}

• lower_bound、lower_bound
• lower_bound、upper_bound
• upper_bound、lower_bound
• upper_bound、upper_bound

14. 若 $f_0=0,\;f_1=1,\;f_{n+1}=\dfrac{f_n+f_{n-1}}{2}$，则随着 $i$ 的增大，$f_i$ 将接近于（ ）。

{{ select(14) }}

• $\dfrac{1}{2}$
• $\dfrac{2}{3}$
• $\dfrac{\sqrt{5}-1}{2}$
• $1$

15. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。

{{ select(15) }}

• $6$
• $7$
• $8$
• $9$

二、阅读程序（判断题正确填 T，错误填 F；判断题1分，选择题3分，共计40分）

第1题

using i64 = long long;
i64 f(i64 n)
{
    i64 s = 1;
    i64 i = 2;
    while (i * i < n)
    {
        if (n % i == 0) {
            s += i;
            s += n / i;
        }
        ++i;
    }
    if (i * i == n) s += i;
    return s;
}

判断题

16. 当 n = 1 时，函数返回 1（ ）。

{{ select(16) }}

• 正确
• 错误

17. 当 $n$ 是质数时，函数返回 $n$（ ）。

{{ select(17) }}

• 正确
• 错误

18. 存在两个数 $n \ne m$ 且 $f(n)=f(m)$（ ）。

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• 正确
• 错误

选择题

20. f(100) 会进入 while 循环次数是（ ）。

{{ select(20) }}

• $7$
• $8$
• $9$
• $10$

21. 运行 f(1024) 时，返回值是（ ）。

{{ select(21) }}

• $512$
• $1023$
• $1024$
• $2047$

第2题

int solve(int n, int a[])
{
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int sum = 0;
            for (int k = j; k <= i; ++k)
            {
                sum += a[k];
            }
            ret += sum;
        }
    }
    return ret;
}

判断题

22. 若在进入 solve 函数执行其他操作之前，先对 a[] 排序，返回值不变（ ）。

{{ select(22) }}

• 正确
• 错误

23. 当 n = 1 时，函数返回值为 a[0]（ ）。

{{ select(23) }}

• 正确
• 错误

24. 若数组 a[] 中所有元素均为0，则当 $n$ 取1到100之间的整数时，函数一定返回0（ ）。

{{ select(24) }}

• 正确
• 错误

选择题

25. 若 n = 10 且 $a=\{1,1,\ldots,1,1\}$，程序的返回值是（ ）。

{{ select(25) }}

• $10$
• $100$
• $165$
• $210$

26. 若 n = 5，且 $a=\{3,1,4,1,5\}$，则程序返回（ ）。

{{ select(26) }}

• $14$
• $75$
• $78$
• $80$

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

{{ select(27) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(n^2 \cdot \log n)$
• $\Theta(n^3)$

28. 如果打算用更好的算法实现 solve 函数，那么最好的算法可以达到的时间复杂度为（ ）。

{{ select(28) }}

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

第3题

using i64 = long long;

i64 solve1(i64 n)
{
    std::vector<i64> c(n);
    c[0] = 0;
    i64 sum = 0;
    for (i64 i = 1; i < n; ++i)
    {
        c[i] = c[i / 2] + (i % 2);
        sum += c[i];
    }
    return sum;
}

std::pair<i64,i64> solve2(i64 n)
{
    if (n == 0)
        return {0, 0};
    auto r = n % 2;
    auto q = n / 2;
    auto [s, c] = solve2(q);
    if (r == 1)
        return {s*2 + q + c, c + 1};
    else
        return {s*2 + q, c};
}

判断题

29. solve1(5) 返回 5（ ）。

{{ select(29) }}

• 正确
• 错误

30. solve2(8) 返回 {10, 1}（ ）。

{{ select(30) }}

• 正确
• 错误

31. 若输入参数 $n$ 在0到1024之间，则 solve1(n) 的返回值与 solve2(n) 的第一项返回值必定相等（ ）。

{{ select(31) }}

• 正确
• 错误

选择题

32. solve1(n) 计算的是（ ）。

{{ select(32) }}

• 0到 $n-1$ 之间，全体二进制数的零出现的数量
• 0到 $n-1$ 之间，全体二进制数的一出现的数量
• 0到 $n$ 之间，全体二进制数的零出现的数量
• 0到 $n$ 之间，全体二进制数的一出现的数量

33. solve2(n) 的第二个返回值，计算的是（ ）。

{{ select(33) }}

• 参数 $n$ 的二进制长度
• 参数 $n$ 的十进制长度
• 参数 $n$ 在二进制表示下，0的数量
• 参数 $n$ 在二进制表示下，1的数量

34. solve1 及 solve2 的时间复杂度是（ ）。

{{ select(34) }}

• $\Theta(n)$、$\Theta(n)$
• $\Theta(n)$、$\Theta(\log n)$
• $\Theta(\log n)$、$\Theta(n)$
• $\Theta(\log n)$、$\Theta(\log n)$

35. solve1(4096) 的返回值等于（ ）。

{{ select(35) }}

• $4096 \times 5$
• $4096 \times 6$
• $2048 \times 5$
• $2048 \times 6$

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

第1题

两人进行 $N$ 次石头剪刀布游戏，给定对方的出拳序列，由 $R$、$P$、$S$ 组成（分别表示石头、剪刀、布）。你的出拳需满足：

• 从未输过（每次非赢即平）。
• 相邻两次出拳不同。

求可能赢的最大对局数（即赢的次数，平局不计入）。

#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<< ____(7)____;
}

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)

40. （7）处应填（ ）。

{{ select(40) }}

• std::min(std::min(R,S),P)
• std::max(std::max(R,S),P)
• n - std::min(std::min(R,S),P)
• n - std::max(std::max(R,S),P)

第2题

给定 $n$ 根火柴的长度 $a_1,a_2,\ldots,a_n$，请用这些火柴围成一个面积最大的三角形。注意所有的火柴都必须用上，不得丢弃。输出最大三角形的面积。假设最大面积为 $s$，则输出 $16s^2$。$1 \le a_i \le 40$，数据保证至少有一种方案可以围成三角形。

#include<iostream>
using i64 = long long;
int n;
int a[40];
bool mem[40][40*40][40*40];
i64 value[40][40*40][40*40];

i64 solve(int i, int x, int y, int z) {
    if (i < n) {
        if (mem ____(1)____ > 0) return value ____(2)____;
        auto s1 = solve(i+1, x + a[i], y, z);
        auto s2 = solve(i+1, x, y + a[i], z);
        auto s3 = solve(i+1, x, y, z + a[i]);
        mem ____(3)____ = true;
        return value ____(4)____ = ____(5)____;
    }
    else {
        if ( ____(6)____ ) return 0;
        i64 p = ____(7)____ ;
        return ____(8)____ ;
    }
}

int main()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::cout << solve(0, 0, 0, 0);
}

41. （1）、（2）、（3）、（4）处应填（ ）。

{{ select(41) }}

• [i][x][y]、[i][x][y]、[i][x][y]、[i][x][y]
• [i][x][y]、[x][y][z]、[i][x][y]、[x][y][z]
• [x][y][z]、[i][x][y]、[x][y][z]、[i][x][y]
• [x][y][z]、[x][y][z]、[x][y][z]、[x][y][z]

42. （5）处应填（ ）。

{{ select(42) }}

• s1 + s2 + s3
• *std::max_element({s1, s2, s3}.begin(), {s1, s2, s3}.end())
• std::max(std::max(s1, s2), std::max(s3, z))
• std::max(std::max(s1, s2), s3)

43. （6）处应填（ ）。

{{ select(43) }}

• x + y <= z && x + z <= y && y + z <= x
• x + y <= z || x + z <= y || y + z <= x
• x + y > z || x + z > y || y + z > x
• x + y >= z && x + z >= y && y + z >= x

44. （7）处应填（ ）。

{{ select(44) }}

• x * y * z
• x + y + z
• (x * y) / 2
• (x + y + z) / 2

45. （8）处应填（ ）。

{{ select(45) }}

• p * (p - 2 * x) * (p - 2 * y)
• (p / 2) * (p / 2 - x) * (p / 2 - y) * (p / 2 - z)
• p * (p - 2 * x) * (p - 2 * y) * (p - 2 * z)
• p + (p - 2 * x) + (p - 2 * y) + (p - 2 * z)