入门级CSP-J第12套初赛模拟试题

ID: 4713

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

椰子

标签>

初赛模拟试题

CSP-J

一、单项选择题（共15题，每题2分，共计30分）

（）提出计算机的体系结构主要包括运算器、（）、存储器、输入和输出设备。 {{ select(1) }}

图灵控制器
冯诺依曼控制器
图灵 CPU
冯诺依曼 CPU

A、B、C、D、E五个人并排站成一列，若A、B必相邻，则有（）种不同排法。 {{ select(2) }}

设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为假的是（）。 {{ select(3) }}

(A∧B)∨(C∧D∨A)
((A∧B)∨C)∧D
(B∨C∨D)∧C∧A
A∧(D∨C)∨B

二进制数1011.01转换成十进制数是（）。 {{ select(4) }}

10.25
11.25
11.5
12.5

以下数据中，C++编程时用整型(int)表示最恰当的是（）。 {{ select(5) }}

宇宙中的原子数目
一头蓝鲸的体重（用吨表示）
小明的身高（用厘米表示）
一个学校的教师人数

设有一顺序栈S，元素a₁、a₂、a₃、a₄依次进栈，如果4个元素出栈的顺序是a₂、a₃、a₄、a₁，则栈的容量至少应该是（）。 {{ select(6) }}

下列设备中，既是输入设备又是输出设备的是（）。 {{ select(7) }}

鼠标器
键盘
扫描仪
磁盘驱动器

假设用双核CPU运行我们平常编写的信息学竞赛程序，相对于同等规格的单核CPU而言，运行时间（）。 {{ select(8) }}

会缩短为原来的1/4
会缩短为原来的1/2
基本没有差别
会缩短为原来的1/3

以下程序段的时间复杂度为（）。

for(i=0;i<n;i++){
    for(j=0;j<n;j++){
        x=x+1;
    }
}

O(2n)
O(n)
O(n²)
O(log₂n)

有6个顶点的无向图至少应该有（）条边才能确保是一个连通图。 {{ select(10) }}

对一组数据(82,47,25,12,21)排序，数据的排列次序在排序过程中的变化为： (1) 82 47 25 12 21 (2) 12 47 25 82 21 (3) 12 21 25 82 47 (4) 12 21 25 47 82 则采用的排序是（）排序。 {{ select(11) }}

选择
冒泡
快速
插入

折半查找对元素的排列要求及适用的表的存储方式为（）。 {{ select(12) }}

元素无序，链接方式存储
元素有序，链接方式存储
元素无序，顺序方式存储
元素有序，顺序方式存储

一个具有1025个结点的二叉树的高度h为（）。 {{ select(13) }}

11
10
11~1025之间
10~1025之间

计算机病毒的传染需要计算机运行和（）这两个条件，否则病毒是不会传染的。 {{ select(14) }}

编写程序
读写磁盘
编辑文档
扫描打印

从5个人中选择2个人参加文艺活动，其中1人唱歌，1人朗诵，则有（）种不同排法。 {{ select(15) }}

二、阅读程序（共计40分；判断题每题1.5分，选择题每题3分，特殊标注除外）

（一）斐波那契数列的递归与递推

#include<iostream>
using namespace std;
long long fun_one (int n){
    if(n==1){
        return 1;
    }else if(n==2){
        return 2;
    }else{
        return fun_one(n-1) + fun_one(n-2);
    }
}
long long fun_two(int n){
    long long a[2005];
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=n;i++){
        a[i]=a[i-1]+a[i-2];
    }
    return a[n];
}
int main(){
    int k;
    cin>>k;
    cout<<fun_two(k)<<endl;
    cout<<fun_one(k)<<endl;
    return 0;
}

假设输入的k是不超过2000的数，试完成下面的判断题和选择题。

判断题 16. 输入的k必须大于0。（） {{ select(16) }}

正确
错误

输入的k值只要小于2000，则第24和25行会得到大于0的数。（） {{ select(17) }}

正确
错误

输入的k值不能太大，否则会发生运行错误。（） {{ select(18) }}

正确
错误

函数fun_one(k)调用靠栈来实现，当次数足够大时，会导致函数栈溢出而死机。（） {{ select(19) }}

正确
错误

选择题 20. 若输入k值为10，则输出的值是（） {{ select(20) }}

89 88
89 89
88 88
88 89

（4分）以下说法正确的是（） {{ select(21) }}

随着k值的变大，函数fun_two(k)和fun_one(k)的输出结果几乎同时得到
随着k值的变大，函数fun_two(k)的输出结果快于fun_one(k)且时间差越来越大
随着k值的变大，函数fun_two(k)的输出结果慢于fun_one(k)且时间差越来越大
无法确定函数fun_two(k)和fun_one(k)输出结果的得到时间

（二）归并排序求逆序对

#include<cstdio>
using namespace std;
int k,n,ans;
int a[50010],r[50010];
void merge_sort(int s,int t) {
    if(s==t)
        return;
    int m=(s+t)>>1;
    merge_sort(s,m);
    merge_sort(m+1,t);
    int i=s,j=m+1,k=s;
    while(i<=m&&j<=t){
        if(a[i]<=a[j])
            r[k++]=a[i++];
        else{
            r[k++]=a[j++];
            ans+=m-i+1;
        }
    }
    while(i<=m)
        r[k++]=a[i++];
    while(j<=t)
        r[k++]=a[j++];
    for(int p=s;p<=t;++p)
        a[p]=r[p];
}
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    merge_sort(1,n);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        printf("%d",a[i]);
    return 0;
}

假设输入的n是不超过50000的正整数，试完成下面的判断题和选择题。

判断题 22. 若将第31行的merge_sort(1,n)改成merge_sort(0,n)，输出结果不变。（） {{ select(22) }}

正确
错误

若将第31行的merge_sort(1,n)改成merge_sort(1,n+1)，输出结果不变。（） {{ select(23) }}

正确
错误

输出结果中ans的值一定大于0。（） {{ select(24) }}

正确
错误

该程序最坏情况下的时间复杂度是O(nlogn)，平均时间复杂度是O(nlogn)。（） {{ select(25) }}

正确
错误

选择题 26. 若输入的n值是5，数组a的值是4,5,3,2,1，则输出结果是（） {{ select(26) }}

6 12345
9 12345
9 45321
6 45321

（4分）若输入的n值是5，数组a的值是4,5,3,2,1，但将第31行改成merge_sort(3, n)，则输出结果是（） {{ select(27) }}

3 45123
3 12345
6 12345
6 45123

（三）进制转换

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
char a[10001];
int b[10001];
int n,m;
char w[6]={'A','B','C','D','E','F'};
int main(){
    cin>>n;
    scanf("%s",&a);
    cin>>m;
    int len=strlen(a);
    if(a[0]=='0'&&len==1){
        cout<<"0";
        return 0;
    }
    for(int i=0;i<len;i++){
        if(a[i]>=97&&a[i]<=122){
            a[i]=a[i]-32;
        }
        if(a[i]>=49&&a[i]<=57)
            b[i]=a[i]-48;
        else if(a[i]>=65&&a[i]<=90)
            b[i]=a[i]-55;
    }
    int ans=0,cnt=0;
    for(int i=len-1;i>=0;i--){
        ans = ans + b[i]*(pow(n, cnt));
        cnt++;
    }
    int cnt1=1;
    while(ans!=0){
        int r=ans%m;
        b[cnt1++]=r;
        ans=ans/m;
    }
    for(int i=cnt1-1;i>=1;i--){
        if(b[i]<10)
            cout<<b[i];
        else{
            int k=b[i]-10;
            cout<<w[k];
        }
    }
    return 0;
}

假设输入的n、m在[2,16]范围内，数组a中存放非负整数的字符形式，试完成下面的判断题和选择题。

判断题 28. 第21行的作用是将小写字母转换成大写字母。（） {{ select(28) }}

正确
错误

第24行的作用是将数字字符转换成数字并保存。（） {{ select(29) }}

正确
错误

第26行的作用是将大写字母转换成数字10到35。（） {{ select(30) }}

正确
错误

如果将第34行中cnt1的值改成0，则程序输出结果不变。（） {{ select(31) }}

正确
错误

选择题 32. （4分）若输入8 735 10，则输出结果是（） {{ select(32) }}

（4分）若输入10 735 8，则输出结果是（） {{ select(33) }}

136
137
1337
1336

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

（一）平方和取模

计算 f(n) = 1² + 2² + 3² + ... + n² 对1007取余的值。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    long long n,a,b,mod=1007;
    while (cin>>n){
        if(n%3==1){
            ①
            b=((2*n+1)/3)%mod;
        }else{
            a=(n*(n+1)/6)%mod;
            ②
        }
        long long ans=0;
        while(b){
            if(b&1)
                ③
            ④
            ⑤
        }
        printf("%lld\n",ans);
    }
    return 0;
}

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

a=(n*(n+1)/2)
a=(n*(n+1)/2)%mod
a=n*(n+1)%mod
a=(n+1)/6

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

b=(2*n+1)%mod
b=(3*n+1)%mod
b=(2*n+1)
b=(3*n+1)

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

ans=(ans * a)%mod
ans=(ans+a)%mod
ans=(ans+a)
ans=(ans*a)

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

b=b-1
b=b+1
b=b>>1
b=b<<1

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

a=a<<1 % mod
a=a>>1 % mod
a=a<<1
a=a>>1

（二）Dijkstra最短路径

有V个点，给出点之间的双向距离，求从第V个点到第1个点的最短距离。

#include<cstdio>
using namespace std;
const int MAXN=1005;
const int INF=0x3fffffff;
int mp[MAXN][MAXN];
int V,E, vis[MAXN], d[MAXN];
int dijkstra (int s){
    for(int i=1;i<=V;i++){
        vis[i]=0;
        d[i]=mp[s][i];
    }
    vis[s]=1;
    for(int i=1;i<=V;i++){
        int mincost,k;
        ① ;
        for(int j=1;j<=V;j++){
            if(②){
                k=j;
                mincost=d[j];
            }
        }
        ③
        for(int j=1;j<=V;j++)
            if(!vis[j]&&d[j]>d[k]+mp[k][j])
                ④
    }
    return ⑤;
}
int main(){
    while (scanf("%d %d", &E, &V)!=EOF){
        for(int i=1;i<=V;i++)
            for(int j=1;j<=V;j++)
                if(i==j) mp[i][j]=0;
                else
                    mp[i][j]=INF;
        for(int i=0;i<E;i++){
            int u,v,cost;
            scanf("%d%d%d", &u,&v, &cost);
            if (cost<mp[u][v])
                mp[u][v]=mp[v][u]=cost;
        }
        int ans=dijkstra(V);
        printf("%d\n",ans);
    }
    return 0;
}

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

mincost=0
mincost= -INF
mincost= INF
mincost=-1

②处应填入（） {{ select(40) }}

!vis[j]||d[j]<mincost
!vis[j]&&d[j]<mincost
!vis[j]&&d[j]>mincost
!vis[j]||d[j]>mincost

③处应填入（） {{ select(41) }}

vis[s]=1
vis[k]=1
vis[i]=1
vis[j]=1

④处应填入（） {{ select(42) }}

d[j]=d[k]+mp[k][i]
d[j]=d[k]-mp[k][j]
d[j]=d[i]+mp[i][j]
d[j]=d[k]+mp[k][j]

⑤处应填入（） {{ select(43) }}

d[1]
d[V]
d[0]
d[V-1]

#CSP012. 入门级CSP-J第12套初赛模拟试题