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

1. ()是C++的关键字。 {{ select(1) }}

• key
• repeat
• void
• var

2. 在8位二进制补码中，10110110表示的是十进制下的()。 {{ select(2) }}

• 202
• 74
• -202
• -74

3. 2019 年 10 月 14 日 是星期一，1978 年 10 月 14 日 是()。{{ select(3) }}

• 星期日
• 星期五
• 星期一
• 星期六

4. 图G是一棵n节点的树，G上有()条边。 {{ select(4) }}

• n
• 2n
• n-1
• n+1

5. 具有5个记录的序列，采用直接选择排序的方式进行排序，需要比较的次数是()次。{{ select(5) }}

• 8
• 9
• 10
• 11

6. 有一个长为5的A序列:{3, 20, 4, 6, 1}，现通过进行交换其中相邻两个数字的操作进行排序，要将A序列排成从小到大的递增序列最少要进行()次交换操作。{{ select(6) }}

• 5
• 6
• 7
• 15

7. 7^4和7&4的结果分别为()。{{ select(7) }}

• 3 4
• 4 4
• 3 3
• 4 3

8. 在C++中，使用()定义一个数组。{{ select(8) }}

• int a[];
• int a{10};
• int a[10];
• int a(10);

9. 一张有9个节点的简单无向图最多有()条边。{{ select(9) }}

• 40
• 81
• 72
• 36

10. 下图中所使用的数据结构是()。

{{ select(10) }}

• 哈希表
• 栈
• 队列
• 二叉树

11. G是一张有n个点m条边的连通图，必须删去()条边才可能将其变成一棵n节点的树。{{ select(11) }}

• 1
• m - n - 1
• m + n - 1
• m - n + 1

12. 字符串“abcab”本质不同的连续子串(不包含空串)个数为(){{ select(12) }}

• 15
• 14
• 13
• 12

13. 十进制小数13.375对应的二进制数是()({{ select(13) }}

• 1101.011
• 1011.011
• 1101.101
• 1010.01

14. 在一个班级里，有10个男生和8个女生，如果要从中选出一支由3个人组成的代表团，其中至少有1个女生，那么有()种不同的选择方案。{{ select(14) }}

• 520
• 696
• 816
• 752

15. 一家三口人，恰有两人生日在同一天的概率是()。(假设每年都有365天。){{ select(15) }}

• 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。(){{ select(16) }}

• 正确
• 错误

17. 若输入 12300400000 3 7，将一定能输出 3 12300400000 3。(){{ select(17) }}

• 正确
• 错误

18. 该程序中，头文件#include可以改成#include。(){{ select(18) }}

• 正确
• 错误

■选择题

19. 若输入 3 6 9，输出(){{ select(19) }}

• 6 3 6
• 9 3 3
• 6 9 3
• 6 3 3

20. 若将“c = a”改成“c = t”,则若输入 3 6 9，输出(){{ select(20) }}

• 6 3 6
• 9 3 3
• 6 9 3
• 6 3 3

21. 若将“c = a”改成“c = b”,则若输人 3 6 9，输出()。{{ select(21) }}

• 6 3 6
• 9 3 3
• 6 9 3
• 6 3 3

(二)

■判断题

22. 上述代码中，双重循环里循环变量 j 的枚举顺序改为 从 w[i] 到 m, 输出结果一定不变。(){{ select(22) }}

• 正确
• 错误

23. 上述代码中，双重循环中变量 i 的枚举顺序改为从 n 到 1,输出结果一定不变。(){{ select(23) }}

• 正确
• 错误

24. 若输入数据中,1 <= n, m, w[i], d[i] <= 30000,则所求答案一定没有溢出。(){{ select(24) }}

• 正确
• 错误

■选择题

25. 当m等于所有 w[i] 的和时，输出结果为()。{{ select(25) }}

• 所有 d[i] 的和
• 最大的 d[i] 值的n倍
• 最大的 d[i] 值的m倍
• nm

26. 当输入为:

输出为()。{{ select(26) }}

• 17
• 28
• 29
• 23

27. 上述代码的时间复杂度为(）。{{ select(27) }}

• O(n)
• O(n * n * m)
• 0(n * m)
• O(n * m * m)

(三)

■判断题

28. 上述代码实现了对一个长度为n的序列进行排序。(){{ select(28) }}

• 正确
• 错误

29. 去掉头文件 “#include” 后程序仍能正常编译运行。(){{ select(29) }}

• 正确
• 错误

30. 去掉 “using namespace std;” 后程序仍能正常编译运行。()({{ select(30) }}

• 正确
• 错误

■选择题

31. 我们将上述算法称为()。{{ select(31) }}

• 插入排序
• 冒泡排序
• 选择排序
• 归并排序

32. 上述代码的时间复杂度为()。{{ select(32) }}

• O(n)
• O(nlogn)
• O(n$^2$)
• O(n$^3$)

33. 若输入数据为:

则 if(a[j] < a[tmp]) 这句话中的条件会成立()次(即后面的 tmp = j 会执行多少次)。{{ select(33) }}

• 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)处应填()。{{ select(34) }}

• a[i] < a[i - 1]
• a[i+1] < a[i]
• a[i] > a[i - 1]
• a[i + 1] > a[i]

35. (2)处应填()。{{ select(35) }}

• b[num] = a[i -2]
• b[num + 1]=a[i - 1]
• b[num + 1]=a[i]
• b[num]=a[i-1]

36. (3)处应填()。{{ select(36) }}

• num++
• mid = 0
• mid--
• cout<<“No Next Permuation”

37. (4)处应填()。{{ select(37) }}

• b[i] > b[mid]
• b[i] < b[mid]
• b[i] < b[num]
• b[i] > b[num]

38. (5)处应填()。{{ select(38) }}

• 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)处应填()。{{ select(39) }}

• du[i]
• q[i]
• hd <= t1
• !du[i]

40. (2)处应填()。{{ select(40) }}

• i <= n
• i < n
• i < G[u].size()
• i <= G[u].size()

41. (3)处应填()。{{ select(41) }}

• q[++t1] = v
• q[t1++] = v
• q[++hd] = v
• q[hd++] = v

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

• G[y].push_back(x)
• G[x].push_back(y)
• G[x].push(y)
• G[y].push(x)

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

• G[y].push_back(x)
• G[y].push(x)
• du[y]++
• du[x]++