客观题

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

CSP-J/S: CCF非专业级软件能力认证(Certified Software Professional Junior/Senior, 简称CSP-J/S)创办于( )年。{{ select(1) }}

2018
2019
2020
2021

十进制数2023等值于二进制数( )。{{ select(2) }}

11100000111
11000001111
10100010111
11111100111

中缀表达式 F-(B+C/D)*E 的后缀形式是( )。{{ select(3) }}

FB-C+D/E*
FBC+D/-E*
FBCD/E*+-
FBCD/+E*-

对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列。{{ select(4) }}

前序
中序
后序
按层次

递归过程或函数调用时，处理参数和返回地址，通常使用一种称为( )的数据结构。{{ select(5) }}

栈
队列
树
链表

某有序数列有1000个各不相同的元素，由小到大排列，现要对该数列进行二分查找，在最坏的情况下，需要查找( )个元素。{{ select(6) }}

1000
500
10
8

将两个各有100个元素的有序表合并成一个有序表，最坏情况下的比较次数是( ){{ select(7) }}

线性链表不具有的特点是( )。{{ select(8) }}

随机访问
不必事先估计所需存储空间大小
插入与删除时不必移动元素
所需空间与线性表长度成正比

二叉树的先序遍历和中序遍历如下：先序遍历: EFHIGJK 中序遍历: HFIEJKG. 该二叉树根的左子树的根是( )。{{ select(9) }}

下面关于算法的描述不正确的是( )。{{ select(10) }}

算法必须有输出
算法必须在计算机上用某种语言实现
算法不一定有输入
算法必须在有限步执行后能结束

下列代码执行后, s的值是( )。{{ select(11) }}

int s=0;
for(int i=1; i<=100; i++)
    for(int j=1; j<=i; j++) s++;
cout<<s<<endl;

100
10000
200
5050

若已知一个栈的入栈顺序是1, 2, 3, …, 100, 其输出序列为P₁, P₂, P₃, …, P₁₀₀,若 P₁是100, 则 Pᵢ是( )。{{ select(12) }}

I
100-I
101-I
不确定

对于给定的数字11223344，如果每次取连续的一段(长度至少为1)构成一个新的数字，问能构成多少个不同的数字 ( )。{{ select(13) }}

以下函数的时间复杂度为( )。{{ select(14) }}

int f(int n){
    if(n==0||n==1) return 1;
    return f(n/2)+f(n/2)+f(n/2)+f(n/2);
}

O(nlogn)
O(n²)
O(n²logn)
O(2ⁿ)

从6个白球和3个黑球中选出4个球，至少有一个黑球的方案数是( )。{{ select(15) }}

111
2664
60
360

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

(1)

1  #include <bits/stdc++.h>
2  using namespace std;
3  int n, ans;
4  
5  int main(){
6      cin>>n;
7      for(int i=1; i<=n; i++){
8          for(int j=(i<<1); j<=n; j+=i){
9              ans+=(j^i)==j-i;
10         }
11     }
12     cout<<ans;
13     return 0;
14 }

保证输入的n不超过10⁶，完成下面的判断题和单选题。

判断题

(1分) 删除第2行, 程序能正常运行。( ) {{ select(16) }}

正确
错误

将第8行j=(i<<1)改成j=2*i, 程序输出结果不会发生改变。( ) {{ select(17) }}

正确
错误

当输入为“3”时, 输出为“1“。( ) {{ select(18) }}

正确
错误

当输入为“6”时, 输出为“4”。( ) {{ select(19) }}

正确
错误

单选题

20.输入“10”时, 程序的输出为 ( )。{{ select(20) }}

21.程序的时间复杂度为 ( )。{{ select(21) }}

O(n)
O(nlogn)
O(n²)
不确定

(2)

1  #include <iostream>
2  using namespace std;
3  int n, top;
4  int a[1000], stack[1000], ans[1000];
5  
6  int main(){
7      cin>>n;
8      for(int i=1; i<=n; i++){
9          cin>>a[i];
10     }
11     for(int i=1; i<=n; i++){
12         while(top && a[i]>a[stack[top]]){
13             ans[stack[top]] = i;
14             top--;
15         }
16         stack[++top]=i;
17     }
18     for(int i=1; i<=n; i++){
19         cout<<ans[i]<<" ";
20     }
21     return 0;
22 }

判断题

(1分) 第1行把头文件#include<iostream>改成万能头文件#include<bits/stdc++.h>程序能正常运行。( ) {{ select(22) }}

正确
错误

将第12行>改成>=，程序输出结果可能发生改变。( ) {{ select(23) }}

正确
错误

如果第一行输入2000，第二行输入2000个以空格隔开的整数1，程序输出结果全为0。( ) {{ select(24) }}

正确
错误

如果输入的数组 $a$ 单调递减，则程序输出结果全为0。( ) {{ select(25) }}

正确
错误

单选题

针对下列输入数据，程序的输出为 ( )。

6
3 3 4 1 5 2

2 3 5 5 0 0
2 3 5 5 0 5
3 3 5 5 0 0
3 3 5 5 0 5

程序的时间复杂度为 ( )。{{ select(27) }}

O(n)
O(nlogn)
O(n²)
不确定

(3)

1  #include<bits/stdc++.h>
2  using namespace std;
3  const int N=1e6+5;
4  
5  int n,k;
6  int nums[N];
7  int partition(int left, int right){
8      int pivot = nums[right];
9      int i = left - 1;
10     for(int j = left; j < right; j++){
11         if(nums[j] <= pivot){
12             i++;
13             swap(nums[i], nums[j]);
14         }
15     }
16     swap(nums[i+1], nums[right]);
17     return i+1;
18 }
19 
20 int quickSelect(int left, int right, int k) {
21     if(left == right){
22         return nums[left];
23     }
24     int pivotIndex = partition(left, right);
25     if(k == pivotIndex){
26         return nums[k];
27     } else if(k < pivotIndex){
28         return quickSelect(left, pivotIndex - 1, k);
29     } else {
30         return quickSelect(pivotIndex + 1, right, k);
31     }
32 }
33 
34 int main() {
35     cin >> n >> k;
36     for(int i = 1; i <= n; i++) cin >> nums[i];
37     int ans = quickSelect(1, n, k);
38     cout << ans << endl;
39     return 0;
40 }

保证输入的n不超过10⁶，k不超过n，且 1≤aᵢ≤10⁹。完成下面的判断题和单选题。

判断题

(1分) 上述代码正确运行后，可以将nums数组按从小到大的顺序排序。( ) {{ select(28) }}

正确
错误

如果将程序第10行<=改成<，程序运行结果不变。( ) {{ select(29) }}

正确
错误

该程序实现的功能是求n个数中第k大的数。( ) {{ select(30) }}

正确
错误

单选题

对于以下输入数据，输出结果为 ( )。

10 6
8 3 4 100 2 1 23 45 8 1 50

对于以下输入数据：

10 4
1 2 6 4 3 10 9 7 8 5

程序运行结束时，nums数组内的值为 ( )。{{ select(32) }}

[1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,10,9,8,7,6]
[1,2,3,4,5,10,9,7,8,6]
[3,2,1,4,5,10,9,8,7,6]

该程序时间复杂度为 ( )。{{ select(33) }}

O(logn)
O(n)
O(nlogn)
O(n²)

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

(1) 高精度减法

输入两个高精度数a和b，输出a-b的值。

程序中使用了运算符重载：运算符重载，就是对已有的运算符重新进行定义，赋予其另一种功能，以适应不同的数据类型的运算。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=10100;
struct big{
    int d[N];
    int len;
};
big a,b;
char s[N];

big read(){ // 读入大整数
    big c;
    memset(c.d, 0, sizeof(c.d));
    scanf("%s", s+1);
    int n = strlen(s+1);
    for(int i=1; i<=n; i++) c.d[i] = ___①___ ;
    c.len = n;
    return c;
}

bool operator >=(big a, big b){ // 重载>=
    int n = a.len, m = b.len;
    if(n > m) return 1;
    if(n < m) return 0;
    for(int i=n; i>0; i--){
        if(a.d[i] > b.d[i]) return 1;
        if(a.d[i] < b.d[i]) return 0;
    }
    return 1;
}

big operator -(big a, big b){ // 重载-
    int n = a.len;
    for(int i=1; i<=n; i++){
        if(___②___){
            a.d[i+1]--;
            ___③___ ;
        }
        a.d[i] -= b.d[i];
    }
    while(___④___) n--;
    a.len = n;
    return a;
}

void write(big a){ // 输出大整数
    for(int i=a.len; i>0; i--) printf("%d", a.d[i]);
    printf("\n");
}

int main(){
    a = read();
    b = read();
    if(a >= b){
        write(a-b);
    } else {
        printf("-");
        ___⑤___;
    }
    return 0;
}

单项选择

①处应填 ( ){{ select(34) }}

s[n-i]
s[n-i]-'0'
s[n+1-i]
s[n+1-i]-'0

②处应填 ( ){{ select(35) }}

a.d[i] > b.d[i]
a.d[i] < b.d[i]
a.d[i] = b.d[i]
a.d[i] == b.d[i]

③处应填 ( ){{ select(36) }}

a.d[i] = 10
a.d[i] =+ 10
a.d[i] -= 10
a.d[i] += 10

④处应填 ( ){{ select(37) }}

a.d[n] == 0
n > 1
a.d[n] == 0 && n > 1
a.d[n] == 0 || n > 1

⑤处应填 ( ){{ select(38) }}

write(b-a)
b-a
write(a-b)
-write(a-b)

(2) 求区间最值

给定序列 $a_n$ ，你需要回答 $q$ 次询问，每次询问一个区间 $[1, r]$ 内的最大值与最小值之差。数据范围满足 $ n, q \leq 100000 , 1 \leq l \leq r \leq n , a_i \leq 1000000 $。提示：每次询问暴力去求区间最值很显然超时，因此我们采用分块算法，分块算法如下：

分块：将序列分成等长的 $\sqrt{n}$ 块，其中每块长度也为 $\sqrt{n}$ ，预处理并记录每个元素所属的块以及每块的左右端点下标、最大值和最小值。
查询：如果查询区间在同一块内，则暴力扫描统计区间最大最小值；否则，如果查询区间包含多个块，统计除去头尾两个块的中间每个块的已经维护好的最大最小值，然后再暴力统计左端点所在块以及右端点所在块的最大最小值。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n, q, block, num;
int a[N], L[N], R[N], belong[N], block_max[N], block_min[N];

void build(){
    block = sqrt(n * 1.0);
    num = n / block;
    if (n % num) num++;
    for (int i = 1; i <= num; i++) { //每块左右端点下标
        ___①___;
    }
    R[num] = n;
    for (int i = 1; i <= n; i++) { //每个元素所属块号
        belong[i] = ___②___;
    }
    for (int i = 1; i <= num; i++) {
        int minn = 1e9, maxx = -1e9;
        for (int j = L[i]; j <= R[i]; j++) {
            maxx = max(maxx, a[j]);
            minn = min(minn, a[j]);
        }
        block_max[i] = maxx;
        block_min[i] = minn;
    }
}

int query(int l, int r){
    int minn = 1e9, maxx = -1e9;
    if (___③___) {
        for (int i = l; i <= r; i++) {
            maxx = max(maxx, a[i]);
            minn = min(minn, a[i]);
        }
        return maxx - minn;
    } else {
        for (int i = l; i <= R[belong[l]]; i++) {
            maxx = max(maxx, a[i]);
            minn = min(minn, a[i]);
        }
        for (___④___) {
            maxx = max(maxx, block_max[i]);
            minn = min(minn, block_min[i]);
        }
        for (int i = L[belong[r]]; i <= r; i++) {
            maxx = max(maxx, a[i]);
            minn = min(minn, a[i]);
        }
        return maxx - minn;
    }
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build();
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ___⑤___ << endl;
    }
    return 0;
}

单项选择

①处应填 ( ){{ select(39) }}

L[i]=(i-1)*block, R[i]=i*block
L[i]=(i-1)*block+1, R[i]=i*block
L[i]=i*block+1, R[i]=(i+1)*block
L[i]=i*block, R[i]=(i+1)*block

②处应填 ( ){{ select(40) }}

(i-1)/block+1
(i-1)/block
i/block+1
i/block

③处应填 ( ){{ select(41) }}

r-l+1<block
belong[l]==belong[r]
l/block==r/block
l/block+1==r/block

④处应填 ( ){{ select(42) }}

int i=belong[l]; i<=belong[r]; i++
int i=R[belong[l]]; i<L[belong[r]]; i++
int i=l/block+1; i<=r/block+1; i++
int i=belong[l]+1; i<=belong[r]-1; i++

⑤处应填 ( ){{ select(43) }}

query(l-1,r)
query(l,r)
query(l+1,r)
query(1+1,r-1)

历年CSP初赛真题

未认领

状态: 已结束
题目: 2
开始时间: 2024-8-19 15:00
截止时间: 2024-10-26 23:59
可延期: 24 小时

#A. 2023 年 CSP-X 第一轮试题

2023 年 CSP-X 第一轮试题

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

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

(1)

判断题

单选题

(2)

判断题

单选题

(3)

判断题

单选题

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

(1) 高精度减法

单项选择

(2) 求区间最值

单项选择

历年CSP初赛真题

状态

开发

支持

#A. 2023 年 CSP-X 第一轮试题

2023 年 CSP-X 第一轮试题

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

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

(1)

判断题

单选题

(2)

判断题

单选题

(3)

判断题

单选题

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

(1) 高精度减法

单项选择

(2) 求区间最值

单项选择

历年CSP初赛真题

状态

开发

支持

还没有账户？

登录