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

ID: 4715

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

椰子

标签>

初赛模拟试题

CSP-J

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

下列数中最大的数为（） {{ select(1) }}

(10010101)₂
(236)₈
(66)₁₆
(142)₇

微型计算机的以下选项中，（）的存取速度最快。 {{ select(2) }}

内存储器
外存储器
高速缓存
寄存器

表达式(3+5)*25-34/(7-5)的后缀形式是（） {{ select(3) }}

3 5 + 25 * 34 7 5 - /
3 5 25 34 7 5 + * - /
3 5 25 + * 34 7 5 - /
3 5 25 + * - 34 / 7 5

定义一颗有根树的深度：根结点的深度为0，其余结点的深度等于该结点的父亲结点的深度加1。一颗深度为9的完全二叉树至少包含（）个结点。 {{ select(4) }}

511
512
1023
1024

下列程序的时间复杂度是（）

int m,n,s=0;
cin>>m>>n;
for(int i=0;i<m;i++)
    for(int j=1;j<=n;j*=2)
        s++;

O(m²)
O(n²)
O(m*n)
O(m*log₂n)

下列各排序法中，最坏情况下的时间复杂度最低的是（） {{ select(6) }}

选择排序
快速排序
堆排序
冒泡排序

已知二叉树的中序遍历为DECHFCABI，后序遍历为HCFEDCIBA，则该二叉树的前序遍历为（） {{ select(7) }}

ABCDEFCHI
ACDEFHCBI
ADCEFGHBI
ACDEFGHBI

设栈S的初始状态为空，若干个元素{a,b,c,d,e,f}依次入栈S，出栈序列为{b,d,f,e,c,a}，根据出栈的序列求栈S的最小容量为（） {{ select(8) }}

小明想开个造纸飞机的公司，于是雇了5个人。接着他要去购买原材料了，已知一包A1纸中有4张纸，一张A1纸能折7架飞机，每位员工要制造100架飞机。因为制造飞机需要一个相对安静的环境，所以员工之间不能互相借纸，也不能提前裁纸。但是老板小明可以把一包纸拆开分给员工，以确保分给每个员工的纸张数量是一样的，又尽可能的少用原材料。求小明至少要买（）包A1纸。 {{ select(9) }}

田忌与齐王各派出10匹马赛马，每场比赛赢方得10两黄金，平局双方不拿钱，输方出10两。每匹马的速度固定，齐王出马顺序固定。田忌马的速度为100、85、75、55……，齐王马的速度为97、88、85、40……。田忌最优安排下最多能赢取（）两黄金。 {{ select(10) }}

设W=true，X=Y=false，Z=true，以下逻辑运算表达式值为真的是（） {{ select(11) }}

W∨(Z∨Y)∧X
W∧(X∨Y∨!Z)∨!Z
(W∧X)∨(Y∧Z∨!W)
(W∧X∨Y)∧Z

汉诺塔问题，规定盘子只能按A→B→C→A的方向移动，大盘不能放在小盘上。A柱上有3个盘子，要全部挪到C柱上，每次移动一个盘子，至少要移动（）次。 {{ select(12) }}

有5本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有（）种摆法。 {{ select(13) }}

字符串"zhangnahz"，本质不同的子串个数为（） {{ select(14) }}

一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度，则T有（）个4度结点。 {{ select(15) }}

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

（一）快速幂

#include<iostream>
using namespace std;
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    int anx=1;
    while(b){
        if(b&1) anx=anx*a;
        a=a*a;
        b>>=1;
    }
    printf("%d\n",anx);
}

判断题 16. 输入a=10，b=10，能够正确输出答案。（） {{ select(16) }}

正确
错误

第06行的anx=1，改成anx=0不会影响最终结果。（） {{ select(17) }}

正确
错误

将第08行与第09行交换位置，不会影响最终结果。（） {{ select(18) }}

正确
错误

将第10行改成b /= 2，不会影响最终结果。（） {{ select(19) }}

正确
错误

选择题 20. 如果输入a=2，下列哪个数字最可能为该程序输出的结果（） {{ select(20) }}

输入a=9，b=9，输出结果为（） {{ select(21) }}

387420489
387420191
388420489
3774204890

（二）约瑟夫环与排序

#include<bits/stdc++.h>
using namespace std;
struct num{int a,b;};
void fun (struct num s[],int n) {
    int index,j,k;
    struct num temp;
    for(k=0;k<n-1;k++){
        index=k;
        for(j=k+1;j<n;j++)
            if(s[j].b<s[index].b) index=j;
        if(index!=k){
            temp=s[index];
            s[index]=s[k];
            s[k]=temp;
        }
    }
}
int main(){
    int count,i,k,m,n,no;
    struct num s[100];
    cin>>n>>m>>k;
    for(i=0;i<n;i++){
        s[i].a=i+1;
        s[i].b=0;
    }
    i=0;
    count=no=0;
    while (no<n){
        if(s[i].b==0)
            count++;
        if(count==m){
            no++;
            s[i].b=no;
            count=0;
        }
        i++;
        if(i==n)
            i=0;
    }
    fun (s,n);
    printf("%d:%d\n",s[k-1].b,s[k-1].a);
    return 0;
}

判断题 22. 若输入为0 0 0时，程序运行会出错。（） {{ select(22) }}

正确
错误

若输入为1 2 3时，则输出为3:1。（） {{ select(23) }}

正确
错误

若把11行的"index!=k"改为1，不会影响程序运行结果。（） {{ select(24) }}

正确
错误

若去掉37和38行，不会影响程序运行结果。（） {{ select(25) }}

正确
错误

选择题 26. 程序运行时，输入5 4 3，输出（） {{ select(26) }}

程序运行时，输入7 5 2，输出（） {{ select(27) }}

（三）归并排序变种

#include<iostream>
using namespace std;
long long a[100010],b[100010],ans;
void mmm(int L,int R)
{
    if(L==R) return;
    int mid=(L+R)>>1;
    mmm(L,mid);
    mmm(mid+1,R);
    int i=L,j=mid+1,k=L;
    while(i<=mid && j<=R)
    {
        if(a[i]>a[j])
        {
            ans+=j-k;
            b[k++]=a[j++];
        }
        else b[k++]=a[i++];
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=R) b[k++]=a[j++];
    for(i=L;i<=R;i++) a[i]=b[i];
}
int main()
{
    int i,n;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    mmm(1,n);
    cout<<ans;
}

判断题 28. 去掉第06行，程序运行结果相同。（） {{ select(28) }}

正确
错误

第21行与第22行交换一下，程序运行结果相同。（） {{ select(29) }}

正确
错误

第07行改为int mid=(L+R)/2，程序运行结果相同。（） {{ select(30) }}

正确
错误

该算法的原理是归并排序。（） {{ select(31) }}

正确
错误

选择题 32. 该程序的时间复杂度为（） {{ select(32) }}

O(n)
O(n log n)
O(n²)
O(n√n)

程序输入4 3 2 3 2，则输出为（） {{ select(33) }}

（4分）程序输入4 6 5 2 4，则执行到第32行时，数组a[]的数据为（） {{ select(34) }}

6 5 2 4
6 5 4 2
2 4 6 5
2 4 5 6

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

（一）判断等比数列

第一行输入一个正整数n，第二行输入n个整数，判断这些数是否构成等比数列。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int cur,q,i,n,pre;
    cin>>n;
    ①
    ②
    pre=cur;
    for(i=3;i<=n;i++){
        cin>>cur;
        if(③)
            break;
        q=cur/pre;
        ④
    }
    if(⑤) printf("Yes\n");
    else
        printf("No\n");
}

①处应填（） {{ select(35) }}

cin>>pre>>cur;
cin>>pre;
cin>>cur;
cin>>cur>>pre;

②处应填（） {{ select(36) }}

q=1;
q=0;
q=cur/pre;
q=pre/cur;

③处应填（） {{ select(37) }}

cur>pre
cur==pre*q
cur<pre
cur!=pre*q

④处应填（） {{ select(38) }}

cur=pre;
cur =q;
pre= cur;
pre =q;

⑤处应填（） {{ select(39) }}

i>n
i>=n
i<n
i<=n

（二）次大值之和

给定一个1到n的数字各出现一次的排列，定义f(l,r)表示区间[l,r]中的次大值，求所有区间次大值的总和。采用双向链表实现。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=100005;
struct T{
    int v,id;
}x[MAXN];
int pre[MAXN],nxt[MAXN];
int cmp (T t1,T t2){ return t1.v<t2.v;}
void del(int p){
    int L=pre[p],r=nxt[p];
    nxt[L]=r;pre[r]=L;
}
int main(){
    int m,n,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&x[i].v);
        x[i].id= ① ;
        pre[i]=i-1;
        nxt[i]=i+1;
    }
    nxt[0]=1; pre[n+1]=n;
    ②
    LL ans=0;
    LL L1,L2,r1,r2;
    for(i=1;i<=n;i++){
        L1=pre[x[i].id];
        if(L1) L2=pre[L1]; else L2=-1;
        r1=nxt[x[i].id];
        if(r1!=n+1) r2=nxt[r1]; else r2=-1;
        if(L2!=-1) ans+= ③ *i;
        if(r2!=-1) ans+= ④ *i;
        del(⑤);
    }
    printf("%lld",ans);
}

①处应填（） {{ select(40) }}

-1
0
i
n

②处应填（） {{ select(41) }}

sort(x, x+n)
sort(x, x+n, cmp)
sort(x, x+n+1, cmp)
sort(x+1, x+n+1, cmp)

③处应填（） {{ select(42) }}

(L2-L1)*(L2-x[i].id)
(L1-L2)*(r1-x[i].id)
(L1-L2)*(x[i].id-r1)
(L2-L1)*(x[i].id-L1)

④处应填（） {{ select(43) }}

(r2-r1)*(L1-x[i].id)
(r1-r2)*(r1-x[i].id)
(r1-r2)*(x[i].id-r2)
(r2-r1)*(x[i].id-L1)

⑤处应填（） {{ select(44) }}

i
L1
x[i].id
r1

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