[已解决]【C++板块提升计划】成都第二届三国之战 C++场 (已结束【原创】【答题有奖】

zhangjinxuan

答题结束，当然你也可以继续答题，我也可以给你分数与奖励

成都 第2届三国之战 C++答题卡

一，选择题（50分）
1. 以下的排序算法中，最坏时间复杂度也是 O(n log n) 的是：
A. 拓扑排序   B. 快速排序  C. 归并排序   D. 选择排序

2.  若某个C++程序出现无限递归，那么程序运行大概率会（）
A. 编译错误    B. 数组越界  C. 栈溢出    D. 正常运行

3. main 函数可以返回 （）类型
A. unsigned int   B. signed   C. void   D. long

4. 埃氏筛的时间复杂度是 ( )
A. O(n*n)    B. O(n log n)   C. O(n log log n)   D. O(n)

5. abs 是 （）
A. 求绝对值函数   B. 求平方根函数   C. 将这个数转化为浮点数的函数    D. 一个常量

二，阅读程序题（100分）
（1）
已知有以下程序：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, m, t;
   
5. 
   
6. int solve(int i, int j) {
   
7.         return (j ? solve(j, i % j) : i);
   
8. }
   
9. 
   
10. int main() {
    
11.         scanf("%d", &t);
    
12.         while (t--) {
    
13.                 scanf("%d%d", &n, &m);
    
14.                 printf("%d\n", solve(n, m));
    
15.         }
    
16. }

复制代码

1. 该程序的时间复杂度是：
A. O(tn)    B. O(t)    C. O(t log nm)   D. O(t log n)

2. while(t--) 改成 for(int i=1;i<=t;i++)对程序没有任何影响
A. 正确  B.出现编译错误   C.出现运行时错误  D.仅影响输出结果

3. 这个程序可以求出（）
A. 一元二次方程的根   B. 最小公倍数   C.最大公因数   D.最小公因数

4. 若输入为 1 0 5，程序输出（）
A. 除零错误    B. 1    C. 0     D. 5

5. 若输入为 3 101 1111 93 10007 6481 4678, 输出的数字之和是（）
A. 100   B. 103   C. 203   D. 196

（2）

1. #include <cstdio>
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. int n, cnt;
   
6. bool q[13][13], col[13], lx[30], rx[30];
   
7. 
   
8. void dfs(int i) {
   
9.         if (i == n + 1) {
   
10.                 for (int j = 1; j <= n; ++j)
    
11.                         for (int k = 1; k <= n; ++k)
    
12.                                 if (q[j][k]) {
    
13.                                         cout << k << ' ';
    
14.                                         break;
    
15.                                 }
    
16.                 puts("");
    
17.                 ++cnt;
    
18.                 return;
    
19.         }
    
20.         for (int j = 1; j <= n; ++j) {
    
21.                 if (!col[j] && !lx[i + j] && !rx[i + n - j]) {
    
22.                         col[j] = lx[i + j] = rx[i + n - j] = q[i][j] = 1;
    
23.                         dfs(i + 1);
    
24.                         col[j] = lx[i + j] = rx[i + n - j] = q[i][j] = 0;
    
25.                 }
    
26.         }
    
27. }
    
28. 
    
29. int main() {
    
30.         scanf("%d", &n);
    
31.         dfs(1);
    
32.         return 0;
    
33. }

复制代码

1. 该程序只能输入 （） 及以下的数字，否则会发生数组越界
A. 13   B. 30    C. 12    D. 29

2. 这个程序只能输入（）个数字
A. 0    B. 1   C. 2    D. 3

3. n = 8 时，这个程序会输出 （）行
A. 34    B. 108    C. 342    D. 92

4. 请问哪一行去掉也不会影响结果？
A. 14行的 break     B. 18行的return   C. 24行   D. ABC不能去掉

5. 这个代码用到的主要思想（算法）是
A. Dijkstra    B. 递推    C. 深度优先搜索/回溯    D. 二分

三，完善程序题（50分）
01背包：有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
输入格式：第一行两个整数 n,m。接下来 n 行，每行两个整数 vi,wi。
输出格式：一个整数，表示答案。
请完善程序，使程序可以实现上面的功能：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, m, v[1001], w[1001], f[1001];
   
5. 
   
6. int main() {
   
7.         scanf("%d%d", &n, &m);
   
8.         for (int i = 1; i <= n; ++i)
   
9.                 scanf("%d%d", &v[i], &w[i]);
   
10.         for (int i = 1; 1._____; ++i)
    
11.                 for (int j = m; 2._____; 3._____)
    
12.                         f[j] = max(f[j], 4._____);
    
13.         printf("%d", 5._____);
    
14. }

复制代码

第一处应该填：
A.

1. i <= n

复制代码

B.

1. i * i <= n

复制代码

C.

1. i <= n + m

复制代码

D.

1. i <= m

复制代码

第二处应该填：
A.

1. j <= i

复制代码

B.

1. j >= v[i]

复制代码

C.

1. j <= w[i]

复制代码

D.

1. j >= 1

复制代码

第三处应该填：
A.

1. ++j

复制代码

B.

1. j += 2

复制代码

C.

1. --j

复制代码

D.

1. j -= 2

复制代码

第四处应该填：
A.

1. f[j] + w[i]

复制代码

B.

1. f[i - v[j]] + w[i]

复制代码

C.

1. f[i - w[v[j] + w[i]]] + f[n - i + v[j]]

复制代码

D.

1. f[j - v[i]] + w[i]

复制代码

第五处应该填：
A.

1. f[m]

复制代码

B.

1. f[n]

复制代码

C.

1. f[n + m]

复制代码

D.

1. f[1]

复制代码

                               
登录/注册后可看大图

其他说明
答题卡格式建议类似于 ：

1. AAAAA BBBBB CCCCC DDDDD

复制代码

的形式，方便批改和填写

所有题均为个人原创，转载请注明出处

                               
登录/注册后可看大图

题目更改通知
这里什么也没有

四国排行榜

国家	总分	参加人数	平均分
魏国	190	1	190
蜀国	50	1	50
吴国	0	0	0
燕国	0	0	0

总排行榜

排名	名字	得分	国家
1	ExiaGN001	190	魏国 默认分组
2	sfqxx	50	蜀国 默认分组

答案

游客，如果您要查看本帖隐藏内容请回复

选手奖励
注：发放奖励方式由评分的方式，只有报名了奖励才有效

排名	前20%	前40%	前60%	前80%
奖励	8鱼币	5鱼币	3鱼币	2鱼币

只要参加了比赛，再奖励 2荣誉

最高得分者再附上【最佳答案】，并列者则按提交时间算

最佳答案

月排行榜 / 总排行榜

ExiaGN001

2023-2-9 07:57:43

CCBCA
DACDB
CBDDC
ABCDA

跳转到最佳答案楼层

zhangjinxuan

@tommyyu @KeyError @柿子饼同学 欢迎来答题

@hveagle 请验收

sfqxx

为为啥不是PYthon

zhangjinxuan

sfqxx 发表于 2023-2-8 19:04
为为啥不是PYthon

额，python 场题目因为有争议，所以延期
实际上是 hveagle 忘了出题，C++ 场我出，Python 场是 hveagle 出……

sfqxx

zhangjinxuan 发表于 2023-2-8 19:06
额，python 场题目因为有争议，所以延期
实际上是 hveagle 忘了出题，C++ 场我出，Python 场 ...

6

sfqxx

这种太难，我还是蒙吧
您好像没设置仅作者可见

sfqxx

能修改几次？

sfqxx

选择题：1.C 2.B 3.A 4.C 5.A
二（1）：1.A 2.C 3.A 4.D 5.B
1. C 2. B 3. A  4. C 5.D
1.D 2.C 3.C4.D 5.B
先这么写着（不提交）

高山

此帖仅作者可见

ExiaGN001

选择题3有锅，紫菜罢（无慈悲
实测windows10 x64+intel i7（CPU）+GCC+Cpp98标准的情况下无论返回值类型是signed ,int 亦或是long ，main都可正常运行
而旧标准中void main也是对的
所以这道题多解了

ExiaGN001

CCBCA
DACDB
CBDDC
ABCDA

zhangjinxuan

来顶