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

1. 在计算机组成部分中，用于运行时存储数据，且断电后数据会丢失的是（）{{ select(1) }}

• CPU
• 硬盘
• 内存
• 主板

2. 下列科学家中，主要成就位于计算机领域的是（）{{ select(2) }}

• 菲尔兹
• 朗道
• 哈密顿
• 沃森

3. 十进制数 2024 转换为二进制数的结果是（）{{ select(3) }}

• 111 1110 1000
• 111 1101 1000
• 110 1110 1000
• 111 1100 0000

4. 在 C++ 中定义数组 int a[1024][512]，则数组 a 占用的内存空间至少为（）{{ select(4) }}

• $1\,\mathrm{MB}$
• $2\,\mathrm{MB}$
• $4\,\mathrm{MB}$
• $8\,\mathrm{MB}$

5. 现有如下程序段，其中 s, a, b 均已定义为整型变量，且 a, b 均已赋值，b 大于 a。

   s = 0;
   for (int i = a; i <= b; i++) s += i;
   

   若计算过程中不会发生溢出，则与上述程序段功能等价的赋值语句是（）{{ select(5) }}

• s = a * b / 2;
• s = (a + b - 1) * (b - a) / 2;
• s = (a + b) * (b - a) / 2;
• s = (a + b) * (b - a + 1) / 2;

6. 对于有 $n$ 个顶点的连通的基环树，图中应当有（）条边{{ select(6) }}

• $n$
• $n-1$
• $n+1$
• $2\cdot n$

7. 下列关于 stl 标准库的描述中，不正确的一项是（）{{ select(7) }}

• map 使用红黑树来维护有序性。
• unordered_map 使用散列表保证线性访问。
• vector 使用块状链表保证能动态申请内存。
• stable_sort 使用归并排序保证排序稳定性。

8. 前 $1000$ 个正整数中，既不是 $7$ 的倍数，也不是 $11$ 的倍数的数有（）个{{ select(8) }}

• $782$
• $780$
• $765$
• $797$

9. 一棵二叉树的前序遍历为 A B C D E F G，中序遍历为 C B D A E F G，则它的后序遍历可能为（）{{ select(9) }}

• A F D C B G E
• C A F B D G E
• B C G F E D A
• C D B G F E A

10. 考虑如下递归算法：

    solve(a, b):
      1. if a < b then return solve(b, a)
      2. if b = 0 then return a
      3. if a mod 2 = 0 and b mod 2 = 0 then return 2 * solve(a / 2, b / 2)
      4. if a mod 2 = 0 then return solve(a / 2, b)
      5. if b mod 2 = 0 then return solve(a, b / 2)
      6. return solve(a - b, b)
    

    则调用 solve(12, 20) 得到的返回结果为（）{{ select(10) }}

• 0
• 1
• 2
• 4

11. 线段树主要体现了（）的思想{{ select(11) }}

• 分治
• 贪心
• 枚举
• 多态

12. 下列单词中，不属于常见 linux 命令的是（）{{ select(12) }}

• ls
• echo
• whois
• aloha

13. $(216)_8$ 和下列哪个值一样（）{{ select(13) }}

• $(140)_{10}$
• $(8E)_{16}$
• $(1000\ 1010)_2$
• $(1001\ 1010)_2$

14. 《三国杀》中的武将神吕蒙能够翻开牌堆顶上的五张牌，并挑选其中花色各不同的牌各一张。花色总共有四种，并等概率均匀随机分布在无穷大的牌堆中。他期望能获得（）张牌{{ select(14) }}

• $\frac{781}{1024}$
• $\frac{781}{256}$
• $3$
• $\frac{15}{64}$

15. 大语言模型（LLM）指使用大量文本数据训练的深度学习模型，它们可以生成自然语言文本或理解语言文本的含义。下列人工智能技术中，不属于 LLMs 的是（）{{ select(15) }}

• Kimi
• ChatGPT
• CLIP
• llava

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

(1)

#include <iostream>
using namespace std;

int n, m;
int a[100];

int foo(int x) {
    int cnt1 = 0;
    for (; x > 0; x -= x & -x) cnt1++;
    return cnt1;
}

int bar(int x) {
    int cnt2 = 0;
    for (; x <= m; x += x & -x) cnt2++;
    return cnt2;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cout << foo(a[i]) + bar(a[i]) << ' ';
    return 0;
}

16. 为保证程序不发生下标越界，输入的 $n$ 最大只能为 $100$。（）{{ select(16) }}

• 对
• 错

17. 若 $m\ge0$ 且输入的 a[i] 中包含 $0$，程序在执行 bar 函数时将陷入死循环。（）{{ select(17) }}

• 对
• 错

18. 当输入为 3 4 1 2 3 时，输出为 3 2 3。（）{{ select(18) }}

• 对
• 错

19. 若将 bar 函数中的 cnt2 全部替换为 cnt1，则程序不能正常编译运行。（）{{ select(19) }}

• 对
• 错

20. 当输入为 2 8 4 7 时，输出为（）{{ select(20) }}

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

21. 当输入为 2 0 65530 1048579 时，输出为（）{{ select(21) }}

• 13 3
• 14 3
• 13 2
• 14 2

(2)

#include <iostream>
#include <string>
using namespace std;

const char base[17] = "0123456789abcdef";
int table[256];

string str, res;

void init() {
    for (int i = 0; i < 256; i++) table[i] = -1;
    for (int i = 0; i < 16; i++) table[base[i]] = i;
}

bool decode() {
    int n = str.length();
    if (n % 2 != 0) return false;
    for (int i = 0; i < n; i += 2) {
        int high = table[str[i]];
        int low = table[str[i + 1]];
        if (high == -1 || low == -1) return false;
        res += char(low | high << 4);
    }
    return true;
}

int main() {
    init();
    cout << table['b'] << endl;

    cin >> str;
    if (decode())
        cout << res << endl;
    else
        cout << "error" << endl;
    return 0;
}

22. 输出的第一行为 11。（）{{ select(22) }}

• 对
• 错

23. 可能存在输入不同，但输出的第二行相同且不为 error 的情形。（）{{ select(23) }}

• 对
• 错

24. 若执行 decode() 返回 true，则 res 的长度恰好是 str 的两倍。（）{{ select(24) }}

• 对
• 错

25. 当输入为 4e61436c 时，输出的第二行为（）{{ select(25) }}

• nacl
• NaCl
• NACL
• nACl

26. 若输出的第二行为 Noip，则输入可能是（）{{ select(26) }}

• 6e4f4950
• 4e4f4950
• 4e6f6970
• 6e6f6970

27. 若输出的第二行为 error，则输入不可能是（）{{ select(27) }}

• 4A4B4C4D
• 374g5d60
• 6572726f72
• 6e6f6970

(3)

#include <iostream>
using namespace std;

int n;
long long k;
int a[100000];

bool check(long long x) {
    int r = 0;
    long long cnt = 0;
    long long sum = 0;
    for (int l = 0; l < n; l++) {
        while (r < n && sum + a[r] < x) {
            sum += a[r];
            r++;
        }
        cnt += r - l;
        if (cnt >= k) return false;
        sum -= a[l];
    }
    return true;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    long long l = 0, r = 0;
    for (int i = 0; i < n; i++) r += a[i];

    while (l < r) {
        long long mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << l;
    return 0;
}

假设输入的 $n$ 是不超过 $10^5$ 的正整数，a[i] 均为不超过 $10^9$ 的非负整数。对 a[i] 的一段子区间（即 a[i] 中连续且非空的一段），定义它的权值为区间中所有数之和。

28. 程序输出 l 时，主函数中变量 l 和 r 的值一定相等。（）{{ select(28) }}

• 对
• 错

29. 将第 32 行的 (l + r + 1) >> 1 改为 (l + r + 1) / 2，程序运行结果不变。（）{{ select(29) }}

• 对
• 错

30. 若 a[i] 的所有 $\frac{n(n+1)}2$ 个子区间中至少有 $k$ 个子区间的权值小于 $x$，则调用 check(x) 将返回 true，否则返回 false。（）{{ select(30) }}

• 对
• 错

31. 单次执行 check 函数的时间复杂度为（）{{ select(31) }}

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

32. 若输入为 4 5 1 2 4 3，则输出为（）{{ select(32) }}

• $3$
• $4$
• $5$
• $6$

33. （4 分）若输入的前两个数为 $30$ 和 $233$，接下来输入的数依次为 $2^0,2^1,2^2,\dots,2^{29}$，则输出的数等于（）{{ select(33) }}

• $2^{21}-2^{19}$
• $2^{21}-2^{18}$
• $2^{22}-2^{20}$
• $2^{22}-2^{19}$

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

(1)（橡皮泥斑马）

给定一个 01 字符串 s ，记它的长度是 |s| ， 你可以对它进行若干次操作。每次操作可以任选一个正整数 $1 \le k \le |s|$ ，使得 $[1, k]$ 和 $(k, |s|]$ 处的字符分别翻转。求经过任意次操作后能得到的最长的 01 交替出现的子串的长度。

输入包含一个 01 串 $s$，保证 $1\le |s|\le 10^5$。

提示：问题等价于求原串首尾相接成环以后的最长交错字符串。

试补全程序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

char ch[__(1)__];
int f[__(1)__];

void init(){
    scanf("%s",ch+1);
    int len = strlen(ch+1); 
    for(int i = 1; i <= len; ++i){
        __(2)__
    }
    len = len * 2;
    f[1] = 1;
    for(int i = 2; i <= len; ++i){
        if(__(3)__){
            f[i] = f[i - 1] + 1;
        }else{
            __(4)__
        }
    }
    int ans = 0;
    for(int i = 1;i <= len; ++i){
        ans = max(ans, f[i]);
    }
    printf("%d", __(5)__);
}
int main(){
    init();
    return 0;
}

34. (1) 处应填（）{{ select(34) }}

• 200005
• 200000
• 100000
• 100005

35. (2) 处应填（）{{ select(35) }}

• ch[len + i] = ch[i];
• ch[++len] = ch[i]
• ch[i] ^= 1
• ch[i * 2] = ch[i];

36. (3) 处应填（）{{ select(36) }}

• ch[i] == ch[i - 1]
• ch[i] != ch[i - 1]
• ch[i] != ch[i / 2]
• ch[i] == ch[i / 2]

37. (4) 处应填（）{{ select(37) }}

• f[i] = 0;
• f[i] = i;
• f[i] = len;
• f[i] = 1;

38. (5) 处应填（）{{ select(38) }}

• len / 2
• max(ans, 1)
• ans
• min(ans, len / 2)

(2)（挑战不可能）

给定一个森林，判断它的补图的哈密顿通路是否存在，如果存在，输出其中一条。

森林指的是一张无环的简单图。

哈密顿通路指的是，不重不漏地恰好访问每个顶点各一次的路径。

一张简单图的补图，指的是，将原图中连边的点对不连边、原图中不连边的点对连边以后形成的图。

输入第一行两个正整数 $n, m$。

接下来一行 $m$ 个整数 $u, v$，分别表示这 $m$ 条边。

提示：当且仅当给定的森林是一棵菊花（也就是说，所有其他点都和其中某个特定点连边）时，其补图的哈密顿回路不存在；其他情况下，将森林分层，同层间一定可以连边；编号奇偶性相同的层之间也一定可以连边。惟一需要特判一下的就是只有三层的情况：这时候将最后一层的点直接连边到倒二层的某个点有可能出现问题。因此我们需要特判一下。显然这个时候交换这个点和这一组的前一个点是不影响答案的。

试补全程序。

#include<bits/stdc++.h>

using namespace std;
const int N = 500005;
vector<int> e[N];
int level, vis[N];
vector<int> layer[N];

struct Order{
	int deg; int id;
}order[N];

void dfs(int X, int FA, int dep) {
	layer[dep].push_back(X);
	vis[X] = 1;
	level = std::max(level, dep);
	for(auto v: e[X]) {
		if(__(1)__) {
			dfs(v, X, dep + 1);
		}
	}
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		e[i].clear(); layer[i].clear(); vis[i] = 0;
	}
	level = 0;
	for(int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v); e[v].push_back(u);
	}
	for(int i = 1; i <= n; ++i) {
		if((int)__(2)__) {
			puts("-1"); return;
		}
	}
	for(int i = 1; i <= n; ++i) {
		order[i] = (Order){(int)e[i].size(), i};
	}
	std::sort(order + 1, order + 1 + n, __(3)__ {
		return A.deg < B.deg;
	});
	for(int i = 1; i <= n; ++i) {
		int X = order[i].id;
		if(vis[X]) {
			continue;
		}
		++level;
		__(4)__;
	}
	vector<int> ans;
	for(int i = 2; i <= level; i += 2) {
		if(!ans.empty()) {
			for(auto j: e[ans.back()]) {
				if(j == layer[i][0]) {
					swap(layer[i][0], layer[i][1]);
					break;
				}
			}
		}
		for(auto u: layer[i]) {
			ans.push_back(u);
		}
	}
	for(int i = 1; i <= level; i += 2) {
		if(!ans.empty()) {
			for(auto j: e[ans.back()]) {
				if(j == layer[i][0]) {
					swap(layer[i][0], layer[i][1]);
					break;
				}
			}
		}
		for(auto u: layer[i]) {
			__(5)__;
		}
	}
	for(auto u: ans) {
		printf("%d ", u);
	}
	puts("");
    return 0;
}

39. (1) 处应填（）{{ select(39) }}

• v > 0
• v != FA
• v == FA
• !vis[v]

40. (2) 处应填（）{{ select(40) }}

• e[i].size() == n - 1
• e[i].size() == 1
• e[i].size() == 0
• e[i].size() == n

41. (3) 处应填（）{{ select(41) }}

• [](const int A, const int B) -> bool
• [](const Order A, const Order B) -> bool
• func(const Order A, const Order B) => bool
• lambda(const int A, const int B) => bool

42. (4) 处应填（）{{ select(42) }}

• dfs(X, 1, layer[X])
• dfs(e[X], 0, layer[X])
• dfs(X, 1, level)
• dfs(X, 0, level)

43. (5) 处应填（）{{ select(43) }}

• ans.insert(u)
• ans.push_back(u)
• ans.add(u)
• ans.push(u)