[已解决]【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）
已知有以下程序：

#include <bits/stdc++.h>
using namespace std;

int n, m, t;

int solve(int i, int j) {
        return (j ? solve(j, i % j) : i);
}

int main() {
        scanf("%d", &t);
        while (t--) {
                scanf("%d%d", &n, &m);
                printf("%d\n", solve(n, m));
        }
}

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）

#include <cstdio>
#include <iostream>
using namespace std;

int n, cnt;
bool q[13][13], col[13], lx[30], rx[30];

void dfs(int i) {
        if (i == n + 1) {
                for (int j = 1; j <= n; ++j)
                        for (int k = 1; k <= n; ++k) 
                                if (q[j][k]) {
                                        cout << k << ' ';
                                        break;
                                }
                puts("");
                ++cnt;
                return;
        }
        for (int j = 1; j <= n; ++j) {
                if (!col[j] && !lx[i + j] && !rx[i + n - j]) {
                        col[j] = lx[i + j] = rx[i + n - j] = q[i][j] = 1;
                        dfs(i + 1);
                        col[j] = lx[i + j] = rx[i + n - j] = q[i][j] = 0;
                }
        }
}

int main() {
        scanf("%d", &n);
        dfs(1);
        return 0;
}

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。
输出格式：一个整数，表示答案。
请完善程序，使程序可以实现上面的功能：

#include <bits/stdc++.h>
using namespace std;

int n, m, v[1001], w[1001], f[1001];

int main() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
                scanf("%d%d", &v[i], &w[i]);
        for (int i = 1; 1._____; ++i)
                for (int j = m; 2._____; 3._____)
                        f[j] = max(f[j], 4._____);
        printf("%d", 5._____);
}

第一处应该填：
A.

i <= n

B.

i * i <= n

C.

i <= n + m

D.

i <= m

第二处应该填：
A.

j <= i

B.

j >= v[i]

C.

j <= w[i]

D.

j >= 1

第三处应该填：
A.

++j

B.

j += 2

C.

--j

D.

j -= 2

第四处应该填：
A.

f[j] + w[i]

B.

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

C.

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

D.

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

第五处应该填：
A.

f[m]

B.

f[n]

C.

f[n + m]

D.

f[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

来顶