初赛做题方法学习3
一、单项选择题（每题2分，共计30分；每题有且仅有一个正确选项）
- (1047)₈ =（ ）。 {{ select(1) }}
- (1011011101)₂
- (11010)₅
- (20213)₄
- (308)₁₆
- 若逻辑变量A、C为真，B、D为假，以下逻辑表达式的值为假的是（ ）。 {{ select(2) }}
- (B∨C∨D)∨D∧A
- ((﹁A∧B)∨C)∧﹁B
- (A∧B)∨﹁(C∧D∨﹁A)
- A∧(D∨﹁C)∧B
- 小恺编写了如下函数，希望计算斐波那契数列f(n)第n项对10000取余数的值：
在运行空间限制128MB、栈空间不超过空间限制、运行时限1秒的情况下，在主函数中运行函数f(12345)，则最有可能首先发生什么问题？ {{ select(3) }}
- 运行时间超时
- 栈溢出
- 访问无效内存
- 返回错误的答案
- 表达式a+b*(c-d)/e-f的后缀表达式为（ ）。 {{ select(4) }}
- -+a/*b-c-cdef
- abcd-*e/+f-
- +ab*-cd/e-f
- f-e/d-d*b+a
- 某个MV是一段时长4分整的视频文件。它每秒播放10帧图像，每帧图像是一幅分辨率为2048×1152像素（长宽比16:9）的32位真彩色图像，其画面没有被压缩。这个视频没有音频。这个视频文件大约需要占用多大的存储空间？（ ）。 {{ select(5) }}
- 21 GiB
- 27 GiB
- 168 GiB
- 2 GiB
- 下图是一棵二叉树，它的后序遍历是（ ）。
{{ select(6) }}
- ABDEFC
- DBEFAC
- DFEBCA
- ABCDEF
- 五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是（ ）？ {{ select(7) }}
- 10
- 1024
- 15
- 120
- 设元素a,b,c,d,e,f依次入栈，则下列不合法的出栈序列为（ ）？ {{ select(8) }}
- d,c,b,e,f,a
- f,e,d,c,b,a
- c,d,f,e,b,a
- e,d,b,a,f,c
- 同时扔出3枚完全相同的六面骰子，每个骰子上有1到6的数字。将得到的点数排序后，有（ ）种不同的结果？ {{ select(9) }}
- 208
- 56
- 216
- 120
- 在编程时（使用任一种高级语言，不一定是C++），如果需要从磁盘文件中输入一个很大的二维数组（例如1000×1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（ ）。 {{ select(10) }}
- 没有区别
- 按行读的方式更高
- 按列读的方式更高
- 取决于数组的存储方式
- 不考虑稳定性，下列排序方法中平均时间复杂度最大的是（ ）。 {{ select(11) }}
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 将数组12,23,-1,19,117,-103,79,602中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。 {{ select(12) }}
- 4
- 5
- 6
- 7
- 3名男生和3名女生围成一个圈，男生和男生不相邻，女生和女生不相邻。如果两个围成的圈经过旋转可以重合，则视为同一种方案。请问一共有几种方案？ {{ select(13) }}
- 18
- 15
- 12
- 9
- 以下关于C++字符串的说法，错误的是（ ）。 {{ select(14) }}
- 定义string类型的字符串时，不需要预先确定它的最大长度。
- 字符数组和string类型的字符串是可以相互转化的。
- 定义字符数组char a[100]时并从键盘读入字符串，则读入的字符串长度不能超过99。
- 定义一个字符串string s后，获得它长度的方式就是strlen(s)。
- 中国计算机学会成立于（ ）年。 {{ select(15) }}
- 1961
- 1962
- 1971
- 1972
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题2分，选择题3分，共计40分）
题目1
已知，0 ≤ n ≤ 10006, 0 ≤ ai ≤ 10006。完成下面的判断题和单选题：
判断题
- solve2函数实现了选择排序。（ ） {{ select(16) }}
- 正确
- 错误
- solve1函数的时间复杂度为O(m² + V)，其中V指的是ai的最大值。（ ） {{ select(17) }}
- 正确
- 错误
- 当输入数据为：7 2 3 5 7 1 4 6时，solve2函数中的变量cnt最终值为9。（ ） {{ select(18) }}
- 正确
- 错误
- 若将solve2函数中的双斜杠全部移除，不会影响输出结果。（ ） {{ select(19) }}
- 正确
- 错误
单选题
- 下列哪组数据，会使得solve1函数与solve2函数的输出结果不同？（ ）（假设已经输入了n = 8） {{ select(20) }}
-
1 10 100 1000 10000 888 8888 88888
-
6321 158987 16305 68486 50556 847 156505 15610
-
777 888 999 888 777 888 999 666
-
999993 999994 999995 999996 999997 999998 999999 1000000
- 若要使得solve1和solve2函数的输出结果相同，则应当修改程序中的哪一处？（ ） {{ select(21) }}
- ①
- ②
- ③
- ④
题目2
输入保证t的长度不大于s的长度，且两字符串均只含有大小写字母，不是空串，type = 1,2,3，完成下面的判断题和单选题：
判断题
- 将程序中所有的比较运算符小于号(<)改为不等于号(!=)，则程序对所有符合要求的输入的输出结果不变。（ ） {{ select(22) }}
- 正确
- 错误
- 当输入为1 xyz abcd时，程序的输出为xyzd。（ ） {{ select(23) }}
- 正确
- 错误
- 程序在输入为1 xyz abcd时的输出与输入为2 xyz abcd的输出相同。（ ） {{ select(24) }}
- 正确
- 错误
- 将程序第25~28行的while循环替换为do-while循环（判断条件和循环体不变），则程序对同一合法输入的输出结果一定不变。（ ） {{ select(25) }}
- 正确
- 错误
单选题
- （2分）若将程序第13行改为
for (int i = 0; i < strlen(t); ++i) s[i] = t[i];，且已知输入的type一定为1的情况下，用n表示s的长度，m表示t的长度，则程序的时间复杂度为（ ）。 {{ select(26) }}
- Θ(n + m)
- Θ(n + m²)
- Θ(n² + m)
- Θ(n² + m²)
- 给程序分别输入选项( )的两组输入数据，得到的输出不同。 {{ select(27) }}
- 1 ab abc 和 3 ab abc
- 1 AB ABC 和 3 AB ABC
- 1 de fgh 和 3 de fgh
- 1 DE FGH 和 3 DE FGH
题目3
以下程序的输入数据的绝对值均不超过1003。完成下面的判断题和单选题：
判断题
- 存在一种合法的输入数据，使得运行程序时，某次find_down函数的返回值是-1。（ ） {{ select(28) }}
- 正确
- 错误
- 该程序的时间复杂度为Θ(n²m²)。（ ） {{ select(29) }}
- 正确
- 错误
- 对于任意s ∈ [0,6)，「先执行front_rotate(u)，再执行right_rotate(u)」，与「先执行right_rotate(u)，再执行front_rotate(u)」，最终s的值相同。（ ） {{ select(30) }}
- 正确
- 错误
单选题
- 将anchorX、anchorY、anchorZ依次更换为（ ）时，对于全部合法数据，与改变之前的输出结果无异。 {{ select(31) }}
- Left、Front、Down
- Left、Up、Front
- Left、Down、Back
- Down、Right、Front
- （2分）对于以下的输入数据，输出结果为（ ）。
5 5 2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 12 5 3 14 13 1 1 1 1 1 1
{{ select(32) }}
- 95
- 97
- 94
- 103
-
（2分）对于以下的输入数据，输出结果为（ ）。
2 5 2 8 15 3 10 5 19 19 3 5
{{ select(33) }}
- 194
- 157
- 193
- 201
三、完善程序（单选题，每小题3分，共计30分）
题目1（支付问题）
有n种纸币，其中第i种纸币的面值为ai元。每种纸币只有一张。求能支付多少种金额（不包括0元）。数据范围满足n≤200，ai的总和不超过5000。
试补全程序。
- ①处应填（ ） {{ select(34) }}
- n += a[i]
- m += a[i]
- n = a[i]
- m = a[i]
- ②处应填（ ） {{ select(35) }}
- f[0] = 1
- f[1] = 1
- a[0] = 1
- a[1] = 1
- ③处应填（ ） {{ select(36) }}
- for (int j = a[i]; j <= n; j++)
- for (int j = n; j >= a[i]; j--)
- for (int j = a[i]; j <= m; j++)
- for (int j = m; j >= a[i]; j--)
- ④处应填（ ） {{ select(37) }}
- f[j - 1] + 1
- f[j - a[i]] + 1
- f[j] || f[j - a[i]]
- f[j] && f[j - a[i]]
- ⑤处应填（ ） {{ select(38) }}
- f[i]
- f[i - 1]
- f[i] == f[i + 1]
- f[i] == f[i - 1]
题目2（凑出17）
给定n(1 ≤ n ≤ 20)个互不相同的正整数a1, a2, …, an(1 ≤ ai ≤ 10⁹)，将之排成一行。你需要在每个ai前加上一个加号(+)或减号(-)，使这n个数字组成一个算式。请问是否存在一种添加符号的方案，使该算式的值为17？如果存在，请输出Yes，否则输出No。
例如，给定n = 5, a1 = 1, a2 = 4, a3 = 5, a4 = 9, a5 = 8，则−a1 − a2 + a3 + a4 + a5 = 17。
提示：使用穷举法解决这个问题。
试补全程序。
- ①处应填（ ）
{{ select(39) }}
- (s >> p) & 1
- (s << p) & 1
- s & (1 << p) & 1
- s & (1 >> p) & 1
- ②处应填（ ）
{{ select(40) }}
- int i = 0; i <= n; ++i
- int i = 1; i <= n; ++i
- int i = 0; i < n; ++i
- int i = 1; i < n; ++i
- ③处应填（ ）
{{ select(41) }}
- 1 << n
- (1 << n) | 1
- (1 << n) + 1
- (1 << n) - 1
- ④处应填（ ）
{{ select(42) }}
- int sum = 0
- unsigned long long sum = 0
- unsigned short sum = 0
- unsigned int sum = 0
- ⑤处应填（ ）
{{ select(43) }}
- sum = a[j] + sum
- sum = a[j] - sum
- sum = -a[j] + sum
- sum = -a[j] - sum