Description
**一，单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）**
1. ()是C++的关键字。
* key
* repeat
* void
* var
2. 在8位二进制补码中，10110110表示的是十进制下的()。
* 202
* 74
* -202
* -74
3. 2019 年 10 月 14 日 是星期一，1978 年 10 月 14 日 是()。
* 星期日
* 星期五
* 星期一
* 星期六
4. 图G是一棵n节点的树，G上有()条边。
* n
* 2n
* n-1
* n+1
5. 具有5个记录的序列，采用直接选择排序的方式进行排序，需要比较的次数是()次。
* 8
* 9
* 10
* 11
6. 有一个长为5的A序列:{3, 20, 4, 6, 1}，现通过进行交换其中相邻两个数字的操作进行排序，要将A序列排成从小到大的递增序列最少要进行()次交换操作。
* 5
* 6
* 7
* 15
7. 7^4和7&4的结果分别为()。
* 3 4
* 4 4
* 3 3
* 4 3
8. 在C++中，使用()定义一个数组。
* int a[];
* int a{10};
* int a[10];
* int a(10);
9. 一张有9个节点的简单无向图最多有()条边。
* 40
* 81
* 72
* 36
10. 下图中所使用的数据结构是()。
* 哈希表
* 栈
* 队列
* 二叉树
11. G是一张有n个点m条边的连通图，必须删去()条边才可能将其变成一棵n节点的树。
* 1
* m - n - 1
* m + n - 1
* m - n + 1
12. 字符串“abcab”本质不同的连续子串(不包含空串)个数为()
* 15
* 14
* 13
* 12
13. 十进制小数13.375对应的二进制数是()(
* 1101.011
* 1011.011
* 1101.101
* 1010.01
14. 在一个班级里，有10个男生和8个女生，如果要从中选出一支由3个人组成的代表团，其中至少有1个女生，那么有()种不同的选择方案。
* 520
* 696
* 816
* 752
15. 一家三口人，恰有两人生日在同一天的概率是()。(假设每年都有365天。)
* 1 / 365
* 365 / (364 x 365)
* (3 x 364) / (365 x 365)
* 1 / 12
**二，阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确在答题卡上涂“A”，错误涂“B”;除第16题1分外，判断题每题1.5分，选择题每题3分，共计40分)**
(一)
■判断题
16. 若输入 3 9 1，则输出 9 3 3。()
* 正确
* 错误
17. 若输入 12300400000 3 7，将一定能输出 3 12300400000 3。()
* 正确
* 错误
18. 该程序中，头文件#include可以改成#include。()
* 正确
* 错误
■选择题
19. 若输入 3 6 9，输出()
* 6 3 6
* 9 3 3
* 6 9 3
* 6 3 3
20. 若将“c = a”改成“c = t”,则若输入 3 6 9，输出()
* 6 3 6
* 9 3 3
* 6 9 3
* 6 3 3
21. 若将“c = a”改成“c = b”,则若输人 3 6 9，输出()。
* 6 3 6
* 9 3 3
* 6 9 3
* 6 3 3
(二)
■判断题
22. 上述代码中，双重循环里循环变量 j 的枚举顺序改为 从 w[i] 到 m, 输出结果一定不变。()
* 正确
* 错误
23. 上述代码中，双重循环中变量 i 的枚举顺序改为从 n 到 1,输出结果一定不变。()
* 正确
* 错误
24. 若输入数据中,1 <= n, m, w[i], d[i] <= 30000,则所求答案一定没有溢出。()
* 正确
* 错误
■选择题
25. 当m等于所有 w[i] 的和时，输出结果为()。
* 所有 d[i] 的和
* 最大的 d[i] 值的n倍
* 最大的 d[i] 值的m倍
* nm
26. 当输入为:
输出为()。
* 17
* 28
* 29
* 23
27. 上述代码的时间复杂度为(）。
* O(n)
* O(n * n * m)
* 0(n * m)
* O(n * m * m)
(三)
■判断题
28. 上述代码实现了对一个长度为n的序列进行排序。()
* 正确
* 错误
29. 去掉头文件 “#include” 后程序仍能正常编译运行。()
* 正确
* 错误
30. 去掉 “using namespace std;” 后程序仍能正常编译运行。()(
* 正确
* 错误
■选择题
31. 我们将上述算法称为()。
* 插入排序
* 冒泡排序
* 选择排序
* 归并排序
32. 上述代码的时间复杂度为()。
* O(n)
* O(nlogn)
* O(n$^2$)
* O(n$^3$)
33. 若输入数据为:
则 if(a[j] < a[tmp]) 这句话中的条件会成立()次(即后面的 tmp = j 会执行多少次)。
* 5
* 7
* 3
* 4
**三、完善程序（单选题，每小题3分，共计30分）**
(一) (下一个全排列)输人一个正整数 n(2 ≤ n ≤ 10$^6$)，以及一个长度为n的排列，规定(1, 2, 3, 4, ···, n)是第1个排列，(n, n-1, ···, 1)是最后一个排列。
根据这n个数组成的排列，输出下一个排列，每一个数后输出一个空格; 若这n个数已经是最后一个排列，输出“ No Next Permutation ”。
输入：
输出：
34. (1)处应填()。
* a[i] < a[i - 1]
* a[i+1] a[i - 1]
* a[i + 1] > a[i]
35. (2)处应填()。
* b[num] = a[i -2]
* b[num + 1]=a[i - 1]
* b[num + 1]=a[i]
* b[num]=a[i-1]
36. (3)处应填()。
* num++
* mid = 0
* mid--
* cout< b[mid]
* b[i] < b[mid]
* b[i] b[num]
38. (5)处应填()。
* cout<<b[i + 1]<<“ ”
* cout<<b[num - i]<<“ ”
* cout<<b[i - 1]<<“ ”
* cout<<b[i]<<“ ”
(二) (拓扑排序)给出一张n个节点m条边的有向图，求出该图的一个拓扑排序，若无拓扑排序输出 -1。
输入:
第一行两个正整数 n, m 表示点数与边数。
接下来 m 行，每行两个正整数 x, y 表示节点 x 到节点 y 之间有一条有向边。
输出:
一个拓扑序，按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可。若无拓扑序，输出 -1。
关于拓扑序的例子，如学校里有 A, B, C, D 四门课程，要求课程 B, C 必须在学习课程 A 之后才能学习,课程 D 必须在学习课程 B, C 之后学习。则序列 A B C D 与序列 A C B D 均是合理的拓扑序，而序列 A B D C 与序列 B A C D 等均不是拓扑序。即在安排某课程时，其前置课程必须全部学习完毕。
试补全程序。
39. (1)处应填()。
* du[i]
* q[i]
* hd <= t1
* !du[i]
40. (2)处应填()。
* i <= n
* i < n
* i < G[u].size()
* i <= G[u].size()
41. (3)处应填()。
* q[++t1] = v
* q[t1++] = v
* q[++hd] = v
* q[hd++] = v
42. (4)处应填
* G[y].push_back(x)
* G[x].push_back(y)
* G[x].push(y)
* G[y].push(x)
43. (5)处应填(
* G[y].push_back(x)
* G[y].push(x)
* du[y]++
* du[x]++
