朝外信奥 1 队 2026-06-14 笔试训练题目

答案版
题型：单项选择题、阅读程序题、完善程序题
题量：32 题，满分 100 分
考试时间：6月14日
一、选择题（共15题，每题2分，共30分）
每题只有一个正确选项，绿色为正确答案，并附简要解析。
1. 完整的计算机系统应该包括（ ）
A. 运算器、存储器、控制器
B. 外部设备和主机
C. 主机和应用程序
D. 配套的硬件和软件系统
答案：D。完整的计算机系统由硬件系统和软件系统两大部分组成。
2. 文件传输使用的协议是（ ）
A. SMTP
B. FTP
C. UDP
D. TELNET
答案：B。FTP 是 File Transfer Protocol，即文件传输协议。
  • A. SMTP 是 Simple Mail Transfer Protocol，主要用于发送电子邮件，不是文件传输协议。
  • B. FTP 是专门用于文件上传、下载和传输的协议，符合题意。
  • C. UDP 是传输层协议，提供无连接的数据报传输，本身不是专门的文件传输协议。
  • D. TELNET 主要用于远程登录和远程命令行操作，不是文件传输协议。
3. 根据 IP 地址分类，下列地址中（ ）属于 C 类地址。
A. 10.1.56.23
B. 172.15.34.128
C. 192.168.32.17
D. 172.128.45.34
答案：C。判断传统 IP 地址分类时主要看第一段：A 类为 1~126，B 类为 128~191，C 类为 192~223。
  • A. 10.1.56.23 第一段是 10，落在 1~126，所以是 A 类地址。
  • B. 172.15.34.128 第一段是 172，落在 128~191，所以是 B 类地址。
  • C. 192.168.32.17 第一段是 192，落在 192~223，所以是 C 类地址，符合题意。
  • D. 172.128.45.34 第一段也是 172，所以同样是 B 类地址，不是 C 类地址。
4. 在 Linux 系统中，cp 命令的作用是（ ）
A. 更改文档或目录的日期时间
B. 创建一个新的目录
C. 复制一个文件到另一个位置
D. 查看指定文件的内容
答案：C。cp 是 copy 的缩写，用于复制文件或目录。
  • A. 更改文件或目录的日期时间通常使用 touch 命令，例如 touch a.txt 可更新文件时间。
  • B. 创建一个新的目录使用 mkdir 命令，例如 mkdir test。
  • C. 复制文件或目录使用 cp 命令，例如 cp a.txt b.txt。
  • D. 查看指定文件内容常用 cat、less 或 more，例如 cat a.txt。
5. 现有一个文件夹，其中包含 1000 张图片，图片的分辨率以 1240*720、1920*1080、1600*900 三个分辨率交替存储，每张图片均为 32 位图像，则这个文件夹最少要用（ ）GB 的 U 盘存储。
A. 2
B. 4
C. 6
D. 8
答案：C。若按题目给出的顺序交替存储，1000=333*3+1，所以第一种分辨率有 334 张，第二种和第三种各 333 张。32 位图像每像素 4 字节，总容量为 334*1240*720*4 + 333*1920*1080*4 + 333*1600*900*4 = 5872896000 字节，约为 5.87GB，因此至少要选 6GB。
6. 总共有 6 个不同的元素进栈，能得到（ ）种不同的出栈序列。
A. 123
B. 121
C. 132
D. 130
答案：C。n 个不同元素按固定顺序进栈时，合法出栈序列数为第 n 个卡特兰（Catalan）数：C_n = (2n)!(n+1)! * n!。本题 n=6，所以 C_6 = 12!7! * 6! = 132。
7. 已知一个根节点在第一层的完全二叉树的第 6 层有 8 个叶子节点，则该完全二叉树至少有（ ）个节点。
A. 39
B. 23
C. 111
D. 119
答案：A。至少有 6 层，前 5 层共有 2^5-1=31 个结点，第 6 层有 8 个叶子结点，总数最少为 31+8=39。
8. 一个有 n 个顶点和 n 条边组成的无向图一定是（ ）
A. 连通的
B. 无环的
C. 有环的
D. 不连通的
答案：C。无环无向图最多只有 n-1 条边；题目中已有 n 条边，超过了无环无向图的最大边数，所以一定存在环。
9. 已知一个二叉树的中序遍历为 HBDIAEFCG，先序遍历为 ABHDICEFG，则该二叉树的后序遍历为（ ）
A. IHDBEFGCA
B. IHDBFEGCA
C. HIDBFGECA
D. HIDBFEGCA
答案：D。先序根为 A；中序中 A 左边是左子树 HBDI，右边是右子树 EFCG。还原出的二叉树如下：
ABCHDEGIF
按后序遍历“左子树、右子树、根”：左子树为 HIDB，右子树为 FEGC，最后加根 A，得到 HIDBFEGCA。
10. 23|15+9^16&69 的结果是（ ）
A. 31
B. 5
C. 28
D. 3
答案：A。按 C++ 运算符优先级，先算 15+9=24、16&69=16，再算 24^16=8，最后 23|8=31。
11. 若序列的原始状态为 {73,94,46,20,77,61,51,28,81,58}，使用快速排序进行排序，以第一个记录为基准值，第一次划分结果为（ ）
A. {20,73,58,46,77,28,51,61,81,94}
B. {58,20,51,61,28,73,77,81,94,46}
C. {46,20,61,51,28,58,73,94,77,81}
D. {58,28,46,20,51,61,73,77,81,94}
答案：D。以 73 为基准，使用常见的左右指针划分，最终小于 73 的元素在左侧，大于 73 的元素在右侧，基准回到中间位置。
12. 求出下列算法的时间复杂度（ ）
  1. int y=0;
  2. while((y+1)*(y-1)<=n){
  3. y++;
  4. }
A. O(logn)
B. O(n)
C. O(n^{1/2})
D. O(n^2)
答案：C。循环条件等价于大约 y^2<=n，所以循环次数与 sqrt(n) 同阶。
13. 已知图 G 如下图所示，若将图中的边按无向边处理，使用 Kruskal 算法求图 G 的最小生成树，加到最小生成树中的边依次是（ ）
第13题图
A. (b,c),(e,d),(c,d),(d,a)
B. (b,c),(e,d),(e,b),(c,d)
C. (b,c),(e,d),(e,b),(a,b)
D. (b,c),(e,d),(e,b),(d,a)
答案：D。按边权从小到大考虑：先加入 (b,c)、(e,d)、(e,b)；接着 (c,d) 会使 c-b-e-d-c 成环，不能加入；最后加入 (d,a)。因此真正加入最小生成树的是 (b,c),(e,d),(e,b),(d,a)。
14. 设一批产品共 10 件，其中 4 件是次品，现进行放回抽样，即每次取一个检查完放回后继续抽取，总共抽取三次，恰好其中两件为次品的概率为（ ）
A. 310
B. 36125
C. 12
D. 1325
答案：B。每次抽到次品概率为 410=25，正品概率为 35。三次中恰好两次次品：C(3,2)×(25)2×35=36125。
15. 假定编译器规定 int 和 short 长度范围分别为 32 位和 16 位，执行以下代码：
  1. unsigned short x=65530;
  2. unsigned int y=x;
得到的 y 的机器码为（ ）
A. 0000 7FFAH
B. 0000 FFFAH
C. FFFF 7FFAH
D. FFFF FFFAH
答案：B。65530 的 16 位无符号表示是 FFFAH，转换为 32 位无符号整数时高位补 0，得到 0000 FFFAH。
二、阅读程序题（共12题，每题3分，共36分）
阅读下面程序，回答第 16~21 题。
阅读程序
  1. #include <bits/stdc++.h>
  2. long long n, m, t, a[1000005];
  3. using namespace std;
  4. int main() {
  5. cin >> n >> m;
  6. while (m > 0) {
  7. t++;
  8. m--;
  9. if (m <= 0)
  10. break;
  11. a[t] = a[t - 1] + 1;
  12. while (m > (1 << n - a[t]) && a[t] <= n) {
  13. m -= 1 << n - a[t];
  14. a[t]++;
  15. }
  16. }
  17. if (t != 1)
  18. for (int i = 1; i < t; i++)
  19. cout << a[i] << " ";
  20. else
  21. puts("0");
  22. return 0;
  23. }

代码功能：这段程序把输入的 m 按照一段一段的块大小进行拆分，逐步确定数组 a 中的若干值，最后输出 a[1] 到 a[t-1]。如果循环只执行了一轮，则输出 0。

  • n 控制块大小中的指数，程序多次使用 1 << (n-a[t])，也就是 2^(n-a[t])。
  • m 是不断被消耗的值。每进入一轮外层循环，先令 t++，再令 m--。
  • a[t] = a[t-1] + 1 表示当前选出的值至少比前一个值大 1，所以 a 数组整体呈递增趋势。
  • 内层 while 会比较 m 和当前块大小 2^(n-a[t])。如果 m 还大，就减去这一块，并把 a[t] 继续增大。
  • 最后当 t != 1 时，程序输出已经确定好的 a[1..t-1]；否则说明没有形成有效序列，输出 0。
16. 第 21 行的 "0" 改成 '0'，程序运行会报错。（ ）
A. TRUE
B. FALSE
答案：A。puts 需要的是字符串地址，"0" 是字符串常量；'0' 是字符常量，类型不匹配，会导致编译错误。
17. 若输入的 n 为负整数，并且程序执行到第 12 行的 1 << (n - a[t])，则可能出现负数移位，程序行为不能保证。（ ）
A. TRUE
B. FALSE
答案：A。移位表达式按运算优先级等价于 1 << (n-a[t])。当 n-a[t] 为负数时，会出现负数移位，属于未定义行为，因此不能保证程序正常输出。
18. 第 11 行的功能是对 a 数组求前缀和。（ ）
A. TRUE
B. FALSE
答案：B。第 11 行只是令当前项等于前一项加 1，表示在前一项基础上递增，不是对数组元素求前缀和。
19. 输入的 n 最大可以到 1000000。（ ）
A. TRUE
B. FALSE
答案：B。虽然数组开到了 1000005，但程序还使用 1 << (n-a[t])。当 n 很大时，移位位数远超整型范围，不能支持 n=1000000。
20. 输入 4 12，输出（ ）
A. 0
B. 2 3
C. 2 3 4
D. 1 2 3
答案：C。按程序模拟：第一次得到 a[1]=2，第二次得到 a[2]=3，第三次得到 a[3]=4，最后输出 2 3 4。
21. 当输入 n 为 3，m 为 1~8 之间的整数时，平均输出整数的个数（保留一位小数）是（ ）。
A. 1.0
B. 1.6
C. 1.8
D. 2.0
答案：B。分别令 m=1..8 模拟，输出整数个数依次为 1,1,2,3,2,1,2,1，总数为 13，平均为 13/8=1.625，保留一位小数为 1.6。
阅读下面程序，回答第 22~27 题。
阅读程序
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. string a,b;
  5. int f[2010][2010];
  6. int Dfs(int i, int j){
  7. if(f[i][j]!=-1)
  8. return f[i][j];
  9. if(i==0)
  10. return f[i][j]=j;
  11. if(j==0)
  12. return f[i][j]=i;
  13. int c=1;
  14. if(a[i-1]==b[j-1])
  15. c=0;
  16. return f[i][j]=min(min(Dfs(i-1,j)+1,Dfs(i,j-1)+1),Dfs(i-1,j-1)+c);
  17. }
  18. int main(){
  19. cin>>a>>b;
  20. memset(f,-1,sizeof(f));
  21. int len1=a.length(),len2=b.length();
  22. Dfs(len1,len2);
  23. cout<<f[len1][len2];
  24. return 0;
  25. }

代码功能：这段程序计算两个字符串的编辑距离，也就是把字符串 a 变成字符串 b 所需的最少操作次数。

  • f[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符之间的最小编辑距离。
  • memset(f,-1,sizeof(f)) 把所有状态标记为“还没有计算过”，配合第 7 行实现记忆化搜索。
  • 如果 i==0，说明第一个串为空，只能插入 j 个字符；如果 j==0，说明第二个串为空，只能删除 i 个字符。
  • c 表示最后一个字符是否需要替换：相同则 c=0，不同则 c=1。
  • 递推式比较三种操作：删除一个字符、插入一个字符、替换或匹配最后一个字符，取其中最小值。
  • 主函数读入两个字符串后，调用 Dfs(len1,len2)，最终输出完整两个字符串的编辑距离。
22. 第 7 行和第 20 行的 -1 如果改成 -2，程序运行结果可能不一样。（ ）
A. TRUE
B. FALSE
答案：A。第 20 行使用 memset 按字节填充。若改为 memset(f,-2,sizeof(f))，整数数组元素并不会被可靠地设置为数值 -2，与第 7 行的判断配合后可能直接返回错误值。
23. n 是输入两个字符串长度的最大值，程序的时间复杂度为 log(n)。（ ）
A. TRUE
B. FALSE
答案：B。这是带记忆化搜索的编辑距离程序，状态为 i,j，状态数量约为 len1×len2，若最大长度为 n，时间复杂度约为 O(n^2)。
24. 输出的最小值为 -1。（ ）
A. TRUE
B. FALSE
答案：B。程序求的是两个字符串的编辑距离，最小值是 0，例如两个字符串完全相同；-1 只是未计算状态的标记。
25. 设 len1 和 len2 为执行完第 21 行后的值，则程序输出的最大值为 len1+len2。（ ）
A. TRUE
B. FALSE
答案：B。由于程序允许替换操作，编辑距离最大不会简单达到 len1+len2；通常可以用替换配合插入或删除完成，结果不超过 max(len1,len2)。
26. 输入为 sfdqxbw gfdgw，输出（ ）。
A. 2
B. 3
C. 4
D. 5
答案：C。程序求编辑距离，sfdqxbw 到 gfdgw 的最少编辑次数为 4。
27. 保证输入的两个字符串长度均为 100，且只包含小写字母 a~z，第一个字符串为 acegikmoqsuwyace...uwy...ace...moq，第二个字符串为 abcdefghijklmnopqrstuvwxy...abc...wxyabcd（... 表示省略了中间的字符），输出为（ ）
A. 4
B. 13
C. 50
D. 96
答案：D。按题面省略号表示的规律补齐两个长度为 100 的字符串后，运行编辑距离程序得到 96。
三、完善程序题（共5题，共34分）
补全程序，统计数列中的奇数区间数量。
（奇数区间）给定一个长度为 n 的数列：a1, a2, ..., an，如果其中一段连续的子序列 ai, ai+1, ..., aj (i <= j) 中，奇数比偶数多，我们就称这个区间 [i,j] 是奇数区间。求给定的 n 个数中有多少个奇数区间。
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int off = 1e6 + 1;
  4. const int maxn = 1e6 + 5;
  5. int a[maxn], s[maxn], c[2 * maxn];
  6. int n;
  7. long long ans;
  9. int lowbit(int x){
  10. return x & -x;
  11. }
  12. long long getSum(int x){
  13. long long res = 0;
  14. while(x > 0){
  15. res += c[x];
  16. ① ;
  17. }
  18. return res;
  19. }
  21. void add(int x, int k){
  22. while( ② ){
  23. c[x] += k;
  24. ③ ;
  25. }
  26. }
  28. int main(){
  29. cin >> n;
  30. add(off, 1);
  31. for(int i = 1; i <= n; i++){
  32. cin >> a[i];
  33. s[i] = ④ ;
  34. ans += getSum( ⑤ );
  35. add(s[i] + off,1);
  36. }
  37. cout << ans << endl;
  38. return 0;
  39. }

代码功能：这段程序统计数列中有多少个“奇数比偶数多”的连续区间。

  • 核心转换是把奇数看成 +1，偶数看成 -1。这样一个区间的和大于 0，就表示这个区间里奇数比偶数多。
  • s[i] 是前缀和。区间 [l,r] 的和为 s[r]-s[l-1]，它大于 0 等价于 s[r] > s[l-1]。
  • 因此处理到位置 i 时，只要统计之前出现过多少个前缀和严格小于当前 s[i]，就能得到以 i 结尾的奇数区间数量。
  • c 是树状数组，用来维护已经出现过的前缀和次数；off 用来把可能为负的前缀和整体平移成正下标。
  • getSum(x) 查询小于等于某个下标的前缀和数量；add(x,k) 把某个前缀和出现次数加上 k。
  • 空前缀 s[0]=0 需要先加入，所以程序开始时执行 add(off,1)。
28. ①处应该填（ ）
A. x -= lowbit(x)
B. x = lowbit(x)
C. x += lowbit(x)
D. x--
答案：A。树状数组查询前缀和时，每次向前跳到父节点，写作 x -= lowbit(x)。
29. ②处应该填（ ）
A. x < off
B. x <= n
C. x != 0
D. x <= 2 * off
答案：D。树状数组更新时要在数组有效范围内不断向后更新。这里下标经过 off 平移，范围上界使用 2*off。
30. ③处应该填（ ）
A. x -= lowbit(x)
B. x = lowbit(x)
C. x += lowbit(x)
D. x++
答案：C。树状数组单点更新时，下标要向后跳到下一个负责区间，写作 x += lowbit(x)。
31. ④处应该填（ ）
A. s[i - 1] + (a[i] % 2 == 0 ? 1 : -1)
B. s[i - 1] + (a[i] % 2 == 1 ? -1 : 1)
C. s[i - 1] + (a[i] % 2 != 0 ? 1 : -1)
D. s[i - 1] + (a[i] % 2 != 0 ? 1 : 0)
答案：C。把奇数看作 +1，偶数看作 -1，所以当前前缀和应写成 s[i-1] + (a[i]%2!=0 ? 1 : -1)。括号是必要的，否则三目运算符可能被解析到整个表达式外层。
32. ⑤处应该填（ ）
A. 0
B. s[i] + off - 1
C. s[i - 1]
D. s[i] + off
答案：B。区间奇数比偶数多等价于当前前缀和 s[i] 大于某个之前的前缀和，因此需要统计严格小于 s[i] 的前缀和数量，即查询到 s[i]+off-1。