Description
**一，单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）**
1. ()是C++存储单个字符的数据类型。
* int
* float
* char
* string
2. ()是稳定的排序方式。
* 快速排序
* 堆排序
* 选择排序
* 归并排序
3. ()是8比特无符号整数能表示的最大数字。
* 127
* 128
* 255
* 256
4. 每个点都和所有别的点相连的图叫作()。
* 有向图
* 完全图
* 稠密图
* 二分图
5. 在一个有 10 个元素的序列中进行二分查找，每个元素被查找的概率相同，平均查询次数为()。
* 29 / 10
* 1og$_2$( 10 )
* 19 / 10
* 3
6. 若( 120 )$_3$表示 3 进制下的数字 120, 那么( 1026 )$_1$$ _0$+( 1AB )$_1$$_6$ = ()。
* (1001010010)$_2$
* (2654)$_8$
* (59D)$_1$$_6$
* (1222211)$_3$
7. 13 <> 2 的结果分别为()。
* 15 0
* 52 3
* 3 52
* 0 15
8. 在C++中, cout << () 不能输出数组 a 的地址。
* a
* &a
* &a[0]
* *a
9. 一棵有 9 个节点的树最多有()条边。
* 9
* 8
* 81
* 36
10. 下图中所使用的数据结构是()。
* 哈希表
* 栈
* 队列
* 链表
11. 节点数为 3 的本质不同的二叉树有 () 种。
* 5
* 3
* 1
* 9
12. 某班有 30 名同学，有 20 名同学语文得到满分，有 25 名同学数学得到满分，最少有 () 名同学语、数得到满分。
* 20
* 10
* 15
* 5
13. 二进制小数110.011对应的十进制数是()。
* 6.75
* 6.375
* 3.75
* 5.1
14. a, b, c 为三个正整数，若a + b + c = 10, ( a, b, c )有()种不同的情况。
* 1331
* 1000
* 84
* 120
15. ()命令行可以生成一个源代码为 a.cpp 的可执行文件。
* cpp -o b a.cpp
* cpp -g b a.cpp
* g++ -o b a.cpp
* g++ -g b a.ppp
**二，阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确在答题卡上涂“A”，错误涂“B”;除第16题1分外，判断题每题1.5分，选择题每题3分，共计40分)**
(一)
■判断题
16. 若输人 65 10 A，则输出 65 10 A。()
* 正确
* 错误
17. 若输入 114 51.4 0，将输出0 51 r。()
* 正确
* 错误
18. 该程序中，头文件 #include可以改成 #include。()
* 正确
* 错误
■选择题
19. 若输出97 5 a，输入可能为()。
* 65 5.7 a
* 97 5.7 a
* 97 4.9 a
* 65 4.9 a
20. 若将“d = c”改成“d = c - '0’”，则可能()。
* 若输入的字符为数字，输出的第一个数字与其相同
* 若输入的字符为小写字母，输出的第一个数字与其在字母表中的次序相同
* 若输人的字符为大写字母，输出的第一个数字与其在字母表中的次序相同
* 以上情况均不会出现
21. 若将“d = c”改成“d = c - 48”,则可能()。
* 若输人的字符为数字，输出的第一个数字与其相同
* 若输人的字符为小写字母，输出的第一个数字与其在字母表中的次序相同
* 若输人的字符为大写字母，输出的第一个数字与其在字母表中的次序相同
* 以上情况均不会出现
(二)
■判断题
22. 上述代码中，第 13 行、第 14 行双重循环的次序先 i 后 j 改为先 j 后 i，输出结果不变。()
* 正确
* 错误
23. 上述代码中，第 13 行、第 14 行双重循环中第 10 行的 i = 0 改为 i = 1, 输出结果一定不变。()
* 正确
* 错误
24. 若输人数据中,1 ≤ n ≤ 1000,1 ≤ a[i] ≤ 1000000, 则所求答案一定没有溢出。()
* 正确
* 错误
■选择题
25. 当输入的 a[i][j] 全部都是 1 时，输出结果为()。
* 0
* 1
* (y2 - y1) * (x2 - x1)
* (y2 - y1 + 1)*(x2 - x1 + 1)
26. 当输人为：
输出为()。
* 4
* 22
* 25
* 33
27. 上述代码的时间复杂度为()。
* O(n * n)
* O(n * n * q)
* O(q)
* O(max( n * n, q))
(三)
■判断题
28. 上述代码实现了求任意两点之间的最短路。()
* 正确
* 错误
29. 上述代码中，输人的a[i][j]的最小上界为1,000,000,007。()
* 正确
* 错误
30. 去掉“(a[i][j] == MAXL? - 1 : a[i][j])” 中的括号 “()” 后程序仍能正常编译运行。()
* 正确
* 错误
■选择题
31. 上述代码的作用的算法名为()。
* Bellman-Ford
* Floyd
* SPFA
* Dijkstra
32. 上述代码的时间复杂度为()。
* O(n)
* O(nlogn)
* O($n^2$)
* O($n^3$)
33. 若输入数据为:
输出数据中有()个 -1。
* 0
* 8
* 12
* 13
**三、完善程序（单选题，每小题3分，共计30分）**
(一) (区间极值)输人一个正整数 n，以及 n 个正整数组成的序列，输入一个正整数 q，以及 q 组询问，每组询问求区间最大值。
34. (1)处应填()。
* ST[0][i] = a[i]
* ST[0][i] = 0
* ST[i][0] = a[i]
* ST[i][0] = 0
35. (2)处应填()。
* (1 << i) - 1
* 1 << (i - 1)
* (1 << i) + 1
* 1 << (i + 1)
36. (3)处应填()。
* max(a[j], ST[i - 1][j + D])
* max(a[j], ST[i - 1][j - D])
* max(ST[i - 1][j], ST[i - 1][j + D])
* max(ST[i - 1][j], ST[i - 1][j - D])
37. (4)处应填()。
* floor(log2(D))
* floor(ln(D))
* round(log2(D))
* round(ln(D))
38. (5)处应填()。
* min(ST[q][1], ST[q][r - (1 << q)])
* min(ST[q][1], ST[q][r -(1 << q) + 1])
* max(ST[q][1], ST[q][r - (1 << q)])
* max(ST[q][1], ST[q][r - (1 << q) + 1])
(二) (强连通分量)给出一张 n 个节点 m 条边的有向图，求这张图的强连通分量
输入:
第一行两个正整数 n, m 表示点数与边数。
接下来 m 行，每行两个正整数 x, y; 表示节点 x 到节点 y 之间有一条有向边。
接下来输入一个整数 q 表示询问数。
接下来 q 行，每行两个正整数 x, y，询问这两个点是否互相可达，即节点 x 可以通过有向边到达 y 点,反之亦然。
输出:
输出询问的答案
试补全程序。
39. (1)处应填()。
* min(low[u], low[v])
* min(low[u], dfn[v])
* max(low[u], low[v])
* max(low[u], dfn[v])
40. (2)处应填()。
* stack[top] == u
* dfn[u] == low[u]
* stack[top] != u
* dfn[u] != low[u]
41. (3)处应填()。
* top != 0
* instack[stack[top]]==1
* stack[top] != cnt
* stack[top] != u
42. (4)处应填()。
* E[y].push_back(x)
* E[x].push_back(y)
* E[x].push(y)
* E[y].push(x)
43. (5)处应填()。
* dfn[x] == dfn[y]
* low[x] == dfn[y]
* scc[x] == scc[y]
* instack[x] == instack[y]
