CSP-J模拟卷16

ID: 2515

客观题

尝试: 21

已通过: 1

难度: 10

上传者:

yhxx

标签>

CSP-J

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

以下可以用作C++程序变量名的是（）{{ select(1) }}

hello
bool
001
static

一个unsigned long long类型的变量占用的字节数是（）{{ select(2) }}

给定一个字符串，计算把它修改为回文字符串的最小修改次数，下列位置正确的是（）

int f(string &s) {
    int n = s.size(), cnt = 0;
    for(int i = 0; i < n / 2; ++i) {
        if(__________) // 1处
            __________; // 2处
    }
    return cnt;
}

1处填入s[i] == s[n- i- 1]，2处填入cnt += 1
1处填入s[i] == s[n- i- 1]，2处填入cnt += 2
1处填入s[i] != s[n- i- 1]，2处填入cnt += 1
1处填入s[i] != s[n- i- 1]，2处填入cnt += 2

下列选项中，不是线性数据结构的一项是（）{{ select(4) }}

链表
二叉树
栈
队列

计算机的中央处理器CPU的组成部件是（）{{ select(5) }}

控制器和存储器
运算器和存储器
控制器、存储器和运算器
运算器和控制器

已知小写字母a的ASCII码是97，则小写字母x的ASCII码是（）{{ select(6) }}

现在有10枚除了颜色外完全相同小球被放进盒子里。其中5枚小球被涂成蓝色，3枚小球被涂成绿色，2枚小球被涂成紫色，从中任意拿取两次小球，小球颜色不同的概率是（）{{ select(7) }}

$\frac{29}{90}$
$\frac{17}{30}$
$\frac{31}{45}$
$\frac{11}{15}$

关于二分算法，下列说法中错误的是（）{{ select(8) }}

二分算法可以用于二分查找、二分答案等应用
$n$ 个数的随机序列，先排序，再进行二分查找，总时间复杂度为 $O(\log(n))$
二分算法的左右区间可以左闭右闭，也可以左闭右开
二分算法是典型的使用分治思想的算法

已知一个序列的前缀和数组为[10, 15, 14, 18, 20]，下列说法正确的是（）{{ select(9) }}

原序列中的元素均为正整数
原序列是一个升序的序列
原序列中没有数字小于5
原序列中的所有数字都不相同

已知int a[5] = {1, 2, 3, 4, 5};，下列访问数组元素错误的是（）{{ select(10) }}

a[0]
a[5]
*(a+2)
*(a+4)

在下面各个世界顶级奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）{{ select(11) }}

沃尔夫奖
诺贝尔奖
菲尔茨奖
图灵奖

对于一个有10个节点的有向连通图，若每个点的入度不小于1且不大于2，该图中节点连通，且没有重边和自环，则每个点的出度最多为（）{{ select(12) }}

已知递归函数定义为：{{ select(13) }}

int f(int x) {
    if(x <= 1) return 1;
    else return 2 * f(x-1) + f(x-2);
}

则f(6)的返回值为（）

已知一个8位二进制数的原码为 1111 1001，则这个数字对应的补码是（）{{ select(14) }}

1000 0111
1000 0001
1111 0110
0000 0110

在互联网中，每台连网的设备都必须由唯一的IP地址，下列格式正确的IP地址是（）{{ select(15) }}

8.8.8.8
2001.258.4
232,100,2,88
223.112.8:88

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题2分，选择题每题3分，共40分）

（一）阅读下列程序，回答问题。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int func(int x, int y) {
    if(!x || !y) return 0;
    if(x > y) {
        return func(x- 1, y) + 1;
    } else {
        return func(x, y- 2) + 1;
    }
}

int main() {
    int a, b; cin >> a >> b;
    cout << func(a, b);
    return 0;
}

其中保证输入的两个数都是int范围内的整数。

判断题 16. 当输入a = 5，b = 6时，程序输出的结果为5。（）{{ select(16) }}

正确
错误

当输入a，b中存在负数时，存在可能的情形，使得程序可以正常运行（）{{ select(17) }}

正确
错误

当a和b至少有一者为零时，存在可能的情形，使得程序输出不为零。（）{{ select(18) }}

正确
错误

选择题 19. （4分）当y = 1时，x取何值可以使得程序打印100。（）{{ select(19) }}

（二）阅读下列程序，回答问题。

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

vector<int> f(int n) {
    if (n < 2) return {};
    vector<bool> ok(n + 1, true);  // 注释1
    vector<int> ask;  
    vector<int> test(n + 1, 0);               
    ok[0] = ok[1] = false;    
    for (int i = 2; i <= n; ++i) {
        if (ok[i]) {
            ask.push_back(i);
        }
        for (int p : ask) {
            if (i * p > n) break;       
            ok[i * p] = false; 
            test[i * p]++;
            if (i % p == 0) break;      
        }
    }
    for(int p : test) if(p > 1) cout << "wow\n"; 
    return ask;
}

int main() {
    int n; cin >> n;
    vector<int> a = f(n);
    for (int p : a) cout << p << " ";
    return 0;
}

该代码接收一个不大于 $10^6$ 的正整数。据此回答问题。

判断题 20. （3分）这份代码的复杂度为 $O(n\log(n))$ 。{{ select(20) }}

正确
错误

（3分）不存在任何合法的输入，使得该代码首先输出wow。{{ select(21) }}

正确
错误

注释1所在语句若改为vector<bool> ok(n + 1);，其效果并无实际区别。{{ select(22) }}

正确
错误

该代码输出的数字部分至多只有1个数字是偶数。{{ select(23) }}

正确
错误

选择题 24. （4分）对于输入100，最后一个输出的整数是（）{{ select(24) }}

（三）阅读下列程序，回答问题。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int n, num[N], temp[N];

ll f(int x, int y) {
    if(x >= y) return 0; 
    int mid = (x + y) / 2;
    ll result = 0;
    result += f(x, mid); 
    result += f(mid + 1, y);
    int cnt = 0;
    int l = x, r = mid + 1;
    while(l <= mid || r <= y) { 
        if(r > y || (l <= mid && num[l] <= num[r])) { 
            temp[++cnt] = num[l]; 
            l++;
            result += (r- (mid + 1));
        } else { 
            temp[++cnt] = num[r]; 
            r++;
        }
    }
    for(int i = 1;i <= cnt; ++i) 
        num[x + i- 1] = temp[i];
    return result;
}

int main() {
    cin >> n;
    for(int i = 1;i <= n; ++i)
        cin >> num[i];
    cout << f(1, n);
    return 0;
}

程序接收第一行一个正整数 $n$ ，接下来一行 $n$ 个正整数 $1 \leq num_i \leq 10^5$ 。

判断题 25. 若给出下列输入，程序运行的结果为1。（）

2
2 1

正确
错误

（3分）在给定数据范围内，程序不可能输出0。（）{{ select(26) }}

正确
错误

（3分）程序的复杂度是 $O(n\log^2(n))$ 。（）{{ select(27) }}

正确
错误

选择题 28. （4分）对于 $n = 2$ 时，一共可以构造（）种不同的合法输入，使得程序运行的结果为1。{{ select(28) }}

4999950000
4999999999
5000000000
5000050000

（4分）下列输入的正确结果是（）

8
2 2 3 3 1 1 4 4

三、完善程序（单选题，每小题3分，共计30分）

（一）完善程序第一题

给定一个长度为 $n$ 的序列 $a_1 \sim a_n$ ，要求找到一个区间 $[x,y]$ ，使得 $y- x + 1 \geq m$ ，并使得 $ans = \frac{\sum_{i=x}^{y} a_i}{y- x + 1}$ 尽量大。四舍五入保留2位小数给出 $ans$ ，其中 $1 \leq n,m \leq 10^5$ ， $0 \leq |a_i| \leq 10^3$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
double a[N], b[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    double left =-1e9, right = 1e9;
    while(____1____ >= 0.001) { 
        double ret = 1e9;
        bool ok = 0;
        double mid = ____2____; 
        for(int i = 1;i <= n; ++i) {
            ____3____; 
            ____4____; 
            if(b[i] > ret) ok = 1;
        }
        if(ok) ____5____; 
        else right = mid;
    }
    cout << fixed << setprecision(2) << right << endl;
    return 0;
}

1处应填入（）{{ select(30) }}

right- left
left- right
left + right
(left + right) / 2

2处应填入（）{{ select(31) }}

left + right / 2
(left + right) * 0.5
left * 0.5 + right
right- (right- left) / 3

3处应填入（）{{ select(32) }}

b[i] = b[i] + a[i]- mid
b[i] = b[i-1] + (a[i] / mid)
b[i] = a[i]- mid[i]
b[i] = b[i-1] + a[i]- mid

4处应填入（）{{ select(33) }}

if(i >= m) ret = min(ret, b[i-m])
if(i >= m) ret = max(ret, b[i])
if(i >= m) ret = min(ret, b[i])
if(i >= m) ret = max(ret, b[i-m])

5处应填入（）{{ select(34) }}

right = mid
left = mid + 0.001
left = mid
right = mid- 0.001

（二）完善程序第二题

现在有两个字符串A和B，你可以对这两个串做下列三种操作之一：

删除一个字符；
插入一个字符；
将一个字符改为另一个字符。

A,B均只包含小写字母。现在要求你让A和B变得相同，求最少的操作次数。两个字符串长度均小于1000。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int dp[N][N], n, m;
string A, B;

int main() {
    cin >> A >> B;
    n = A.size(), m = B.size();
    A = '#' + A; B = '#' + B;

    for(int i = 1;i <= m; ++i)
        dp[0][i] = i;
    for(int i = 1;i <= n; ++i)
        ____1____; // 填空1

    for(int i = 1;i <= n; ++i) {
        for(int j = 1;j <= m; ++j) {
            if(A[i] == B[j]) 
                dp[i][j] = ____2____; // 填空2
            else {
                int p;
                p = ____3____; // 填空3
                p = min(p, dp[i- 1][j- 1]); 
                ____4____; // 填空4
            }
        }
    }
    cout << ____5____; // 填空5
    return 0;
}

1处应填入（）{{ select(35) }}

dp[0][i] = i
dp[i][0] = dp[i-1][0]
dp[i][0] = 0
dp[i][0] = i

2处应填入（）{{ select(36) }}

dp[i-1][j-1]
dp[i-1][j] + 1
dp[i][j- 1] + 1
min(dp[i-1][j], dp[i][j-1])

3处应填入（）{{ select(37) }}

dp[i-1][j] + dp[i][j-1]
min(dp[i][j-1], dp[i-1][j])
max(dp[i][j-1], dp[i-1][j])
dp[i-1][j]

4处应填入（）{{ select(38) }}

dp[i][j] = p + 1
dp[i][j] = p
dp[i][j] = min(p, dp[i-1][j- 1])
dp[i][j] = p + 2

5处应填入（）{{ select(39) }}

dp[0][0]
dp[n][m]
dp[m][n]
min(dp[n][m], dp[m][n])

在下列比赛中:

cspj初赛模拟赛6

#YHCSPJ0016. CSP-J模拟卷16

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题2分，选择题每题3分，共40分）

（一）阅读下列程序，回答问题。

（二）阅读下列程序，回答问题。

（三）阅读下列程序，回答问题。

三、完善程序（单选题，每小题3分，共计30分）

（一）完善程序第一题

（二）完善程序第二题

相关

状态

开发

支持

关于

#YHCSPJ0016. CSP-J模拟卷16

CSP-J模拟卷16

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

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题选正误；除特殊说明外，判断题每题2分，选择题每题3分，共40分）

（一）阅读下列程序，回答问题。

（二）阅读下列程序，回答问题。

（三）阅读下列程序，回答问题。

三、完善程序（单选题，每小题3分，共计30分）

（一）完善程序第一题

（二）完善程序第二题

相关

状态

开发

支持

关于

还没有账户？

登录