小测试-03月28号

朝外信奥1队 3月28号课堂测试

答案版
一、单项选择题
1. 在标准 ASCII 码表中，已知英文字母 Z 的 ASCII 码十进制表示是 90，那么英文字母 B 的 ASCII 码二进制表示是（ ）。
A. 01000001
B. 01000010
C. 01000011
D. 01000000
答案：B。B 的 ASCII 十进制是 66，二进制是 01000010。
2. 以下不能用作 C++ 程序中的标识符的是（ ）。
A. private
B. friends
C. news
D. pascal
答案：A。private 是关键字。
3. NOI 复赛测评机所用的 Linux 系统属于（ ）。
A. UML
B. IDE
C. OS
D. Database
答案：C。Linux 属于操作系统。
4. 下列排序算法中，稳定排序算法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 选择排序
答案：C。归并排序是稳定排序。
5. 搜索算法中的 BFS 算法经常用到的数据结构是（ ）。
A. 堆
B. 栈
C. 链表
D. 队列
答案：D。BFS 按层扩展，常用队列。
6. 在已经从小到大排好序的 n 元素单向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ ）。
A. O(logn)
B. O(n)
C. O(n²)
D. O(nlogn)
答案：B。单向链表不能随机访问，只能顺扫。
7. 在下列各种排序算法中，不是以“比较”作为主要操作的算法是（ ）。
A. 归并排序
B. 快速排序
C. 冒泡排序
D. 桶排序
答案：D。桶排序属于非比较排序。
8. 关于计算机网络，下面的说法中正确的是（ ）。
A. 现在的计算机必须连接到互联网才能正常运行
B. 192.168.0.1 是 A 类 IP 地址
C. 互联网的诞生用到了现代计算机技术和现代通信技术
D. 接入互联网的计算机的 IP 地址已经全部升级到了 IPv6 地址
答案：C。
9. 将 (2,6,10,17) 分别存储在某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x)=（ ），将不会产生冲突。
A. x%11
B. x²%11
C. 2x%11
D. floor(sqrt(x))%11
答案：D。对应值分别为 1、2、3、4，没有重复。
10. 现在有一个十六进制数 27，它等于二进制数的（ ）。
A. 100011
B. 100101
C. 100111
D. 100011
答案：C。十六进制 27 转二进制是 0010 0111。
11. 某二叉树有 16 个结点都同时有左孩子结点和右孩子结点，则该二叉树中的叶子结点数是（ ）个。
A. 19
B. 17
C. 18
D. 16
答案：B。满二叉树性质：叶子数 = 度为 2 的结点数 + 1。
12. 现有 16 张不同的卡片，其中红、黄、蓝、绿色卡片各 4 张。从中任取 3 张，要求红色最多有 1 张并且 3 张卡片不能是同一种颜色，不同的取法组合共有（ ）种。
A. 232
B. 472
C. 256
D. 484
答案：B。
13. 有 8 个结点的非连通无向图最多有（ ）条边。
A. 8
B. 7
C. 21
D. 49
答案：C。把 8 个点分成 7 个点和 1 个点时边数最多，为 C(7,2)=21。
14. 在 C++ 程序中用到的一个常量 a = 5e-6 在内存中占（ ）空间。
A. 2 字节
B. 1 字节
C. 4 字节
D. 8 字节
答案：D。浮点字面量默认是 double。
15. 某单位安装一条电信宽带进行上网，运营商说下行速度是 500 Mbps。要下载大小为 10 GB 的软件，最快大约需要（ ）秒。
A. 2
B. 20
C. 200
D. 2000
答案：C。10GB 约等于 80Gb，80 / 0.5 ≈ 160 秒，最接近 200 秒。
16. 大写字母 M 的 ASCII 码整数值和空格的 ASCII 码整数值之和，是字母 m 的 ASCII 码整数值。空格的 ASCII 码整数值是（ ）。
A. 32
B. 31
C. 30
D. 29
答案：A。小写字母比对应大写字母大 32。
17. 对于长度为 n 的数组，使用顺序查找查找某个元素，在最坏情况下时间复杂度是（ ）。
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)
答案：C。最坏要把数组扫完。
18. 搜索算法中的 DFS 算法经常用到的数据结构是（ ）。
A. 堆
B. 栈
C. 链表
D. 队列
答案：B。DFS 常用栈或递归实现。
19. 在下列排序算法中，STL 中的 sort() 函数采用的主要算法是（ ）。
A. 选择排序
B. 快速排序
C. 冒泡排序
D. 拓扑排序
答案：B。竞赛语境下一般记作快速排序，工程实现通常是内省排序。
20. 以下不能对二维数组 a 进行正确初始化的语句是（ ）。
A. int a[2][3]={{1,2},{3,4},{5,6}};
B. int a[][3]={{1,2},{0}};
C. int a[2][3]={0};
D. int a[][3]={1,2,3,4,5,6};
答案：A。声明了 2 行，却给了 3 组初始化列表。
21. 设 A=true，B=false，C=false，D=true，以下逻辑运算表达式的值为假的是（ ）。
A. ((A∧B)∨C)∧D
B. (A∨B)∧(C∨D)
C. A∧((B∨C)∨D)
D. (A∧(B∨C))∨D
答案：A。代入后分别为 false, true, true, true。
22. 二叉树的中序序列为 ABCEFGHD，后序序列为 ABFHGEDC，则其前序序列为（ ）。
A. CBADEGHF
B. CBADEGFH
C. CBDAEGFH
D. CBADGEFH
答案：B。
23. 从班级中体育比较好的 12 人中选 5 人去参加运动会，其中甲、乙、丙最多同时选两人，不同的选法共有（ ）种。
A. 792
B. 756
C. 720
D. 676
答案：B。总数 C(12,5)=792，减去甲乙丙全选时的 C(9,2)=36，得到 756。
24. 以下哪个结构可以用来存储图？（ ）
A. 栈
B. 二叉树
C. 邻接表
D. 队列
答案：C。图的常见存储方式有邻接矩阵和邻接表。
二、阅读程序题
01 #include <iostream> 02 using namespace std; 03 int gcd(int a, int b){ 04 int tmp; 05 if(b) tmp = a%b; 06 else return a; 07 while(tmp){ 08 a = b; 09 b = tmp; 10 tmp = a%b; 11 } 12 return b; 13 } 14 int lcm(int a, int b){ 15 return a/gcd(a,b)*b; 16 } 17 int main(){ 18 int a,b; 19 cin >> a >> b; 20 cout << gcd(a, b) << endl; 21 return 0; 22 }
25. 若输入 0 2024，则输出结果为 0。
答案：错。输出为 2024。
26. 将第 5 行中的 if(b) 改为 if(0 != b)，程序的运行结果不会改变。
答案：对。两种写法等价。
27. 若输入 2.4 4.8，则输出错误。
答案：对。程序按 int 读入，这组输入会导致读入失败，结果不符合正常题意。
28. 将第 15 行 return a/gcd(a,b)*b 替换成 return a*b/gcd(a,b)，程序的运行结果不会改变。
答案：错。先乘再除更容易发生整型溢出。
29. 若输入数据为 20244204 12348，则输出为（ ）
答案：C。最大公约数是 36。
30. 若将第 20 行替换成 cout << lcm(a, b) << endl，输入数据为 20244204 12348，则输出为（ ）
答案：D。数学上的最小公倍数是 6943761972，但函数返回类型是 int，会溢出，常见环境下会输出负数。
Previous Topic
Back to Lesson
Next Topic