CSP-S提高级第2套初赛模拟试题

ID: 4733

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

椰子

标签>

初赛模拟试题

CSP-S

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

今有一空栈S，对下列待进栈的数据元素序列1,2,3,4,5,6,7,8,9…进行以进栈、进栈、出栈、进栈、进栈、进栈、出栈为一次操作的规律一直进行操作，那么在2019次操作后，S栈的栈顶元素为()。 {{ select(1) }}

A.10090
B.10094
C.10100
D.10086

对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率的情况下查找成功的平均查找长度(平均比较次数)是()。 {{ select(2) }}

A. $\frac{35}{11}$
B. $\frac{34}{11}$
C. $\frac{33}{11}$
D. $\frac{34}{10}$

下面有四个数据组，每个组各有三个数据，第一个八进制，第二个十进制，第三个十六进制，三个数值全部相等的是()。 {{ select(3) }}

A.120 82 50
B.144 100 68
C.300 200 C8
D.1762 1010 3F2

将(2,6,10,17)存入0~10地址区间哈希表，哈希函数()不会产生冲突。 {{ select(4) }}

A. $x \bmod 11$
B. $x^2 \bmod 11$
C. $2x \bmod 11$
D. $\lfloor\sqrt{x}\rfloor \bmod 11$

二分图可将顶点划分为两部分，同部分无边；12个顶点二分图最多有()条边。 {{ select(5) }}

A.18
B.24
C.36
D.66

单峰数组二分查找峰顶，代码填空顺序正确的是()。 {{ select(6) }}

A.a,c,b,d,e
B.a,d,b,c,e
C.b,e,a,d,c
D.b,e,a,c,d

快速排序不随机化，最坏后果是()。 {{ select(7) }}

A.数组访问越界
B.陷入死循环
C.排序结果错误
D.时间复杂度退化为 $O(n^2)$

二进制数-1101010的8位补码是()。 {{ select(8) }}

A.0010101
B.10010110
C.10010101
D.01101010

$x=11001101$ ， $x\&y$ 保留低4位、清零高4位，y是()。 {{ select(9) }}

A.11110000
B.00001100
C.00001111
D.00000010

循环链表主要优点()。 {{ select(10) }}

A.不需要头指针
B.任意结点快速找到前驱
C.删除后链表不断开
D.任意结点可遍历整张表

递推 $T(N)=N+T(N/2)$ ，时间复杂度()。 {{ select(11) }}

A. $O(N^2)$
B. $O(N\log N)$
C. $O(N)$
D. $O(1)$

$T(n)=3T(n/4)+n\log_2 n$ ，复杂度()。 {{ select(12) }}

A. $O(n)$
B. $O(n\log_2 n)$
C. $O(n\log_2^2 n)$
D. $O(n\log_2^3 n)$

5个不同节点无根树共有()种。 {{ select(13) }}

A.3125
B.125
C.32
D.1024

2019.10.14周一，1978.10.14是()。 {{ select(14) }}

A.星期日
B.星期五
C.星期一
D.星期六

9个节点简单无向图最多()条边。 {{ select(15) }}

A.40
B.81
C.72
D.36

二、阅读程序（判断√/×，判断1.5分，选择4/5分，共40分）

阅读程序1 拓扑排序+最长路径

#include<iostream>
using namespace std;
int graph[100][100];
int n,m,i,j,a,b,head,tail,ans;
int degree[100];
int len[100];
int queue[100];
int main(){
    cin>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            graph[i][j]=0;
    for(i=0;i<n;i++)
        degree[i]=0;
    for(i=0;i<m;i++){
        cin>>a>>b;
        graph[a][b]=1;
        degree[b]++;
    }
    tail=0;
    for(i=0;i<n;i++)
        if (!degree[i]){
            queue[tail]=i;
            tail++;
        }
    head=0;
    while (tail<n){
        for(i=0;i<n;i++)
            if (graph[queue[head]][i]==1){
                degree[i]--;
                if (degree[i]==0){
                    queue[tail]=i;
                    tail++;
                }
            }
        head++;
    }
    ans=0;
    for(i=0;i<n;i++){
        a =queue[i];
        len[a]=1;
        for(j=0;j<n;j++)
            if (graph[j][a]==1 && len[j]+1>len[a])
                len[a]=len[j]+1;
        if (len[a]>ans)
            ans=len[a];
    }
    cout<<ans<<endl;
    return 0;
}

将degree[b]++改为degree[a]++运行结果不变。 {{ select(16) }}

A.√
B.×

程序时间复杂度 $O(n)$ 。 {{ select(17) }}

A.√
B.×

删除11~15行代码运行结果不变。 {{ select(18) }}

A.√
B.×

输入：

输出结果为3。 {{ select(19) }}

A.√
B.×

graph[100][100]作用是()。 {{ select(20) }}

A.邻接矩阵存图
B.记录入度
C.存拓扑序列
D.存终点最长路径

程序核心算法是()。 {{ select(21) }}

A.基数排序
B.归并排序
C.拓扑排序
D.堆排序

阅读程序2 数位DP

#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
LL l,r;
LL f[12][10][10][2][2][2],a[20];
LL Dfs (LL now, LL p,LL pp,LL _4,LL _8,LL top, LL hw) {
    if(_4&&_8)
        return 0;
    if(!now)
        return hw;
    if (!top && f[now][p][pp][_4][_8][hw]!=-1)
        return f[now][p][pp][_4][_8][hw];
    LL Up=top ? a[now]: 9;
    LL ret=0;
    for (LL i=0;i<=Up;i++)
        ret+=Dfs (now-1,i,p,_4|(i==4), _8|(i==8), top&&(i==p),hw|(i==p &&i==pp));
    if(!top)
        f[now][p][pp][_4][_8][hw]=ret;
    return ret;
}
inline LL Solve (LL x) {
    LL tot=0;
    while (x){
        a[++tot]=x%10;
        x/=10;
    }
    if(tot!=11)
        return 0;
    LL ret=0;
    for (LL i=1;i<=a[tot];++i)
        ret+=Dfs (tot-1,i,0,(i==4),(i==8),i==a[tot],0);
    return ret;
}
int main(){
    cin>>l>>r;
    memset (f, -1, sizeof(f));
    cout<<Solve (r)-Solve (l-1);
    return 0;
}

同时包含4和8的数字不会被统计。 {{ select(22) }}

A.√
B.×

存在3个连续相同数字的数字不会被统计。 {{ select(23) }}

A.√
B.×

以下合法可统计数字()。 {{ select(24) }}

A.2323234823
B.1015400080
C.23333333333
D.10010012022

输入l=1212128400 r=1212128550输出()。 {{ select(25) }}

A.5
B.457
C.455
D.6

阅读程序3 奇数阶幻方填充

#include<iostream>
using namespace std;
int main(){
    int n,i,j,x,y,nx,ny;
    int a[40][40];
    for(i=0;i<40;i++)
        for (j=0;j<40;j++) a[i][j]=0;
    cin>>n;
    y=0;
    x=n-1;
    n=2*n-1;
    for(i=1;i<=n*n;i++){
        a[y][x]=i;
        ny=(y-1+n)%n;
        nx=(x+1)%n;
        if ((y==0 &&x==n-1)||a[ny][nx]!=0)
            y=y+1;
        else{
            y=ny;
            x=nx;
        }
    }
    for (j=0;j<n;j++) cout<<a[0][j]<<" ";
    cout<<endl;
    return 0;
}

输出数字总个数为 $2n$ 。 {{ select(26) }}

A.√
B.×

输入1，输出为1。 {{ select(27) }}

A.√
B.×

输入3，第一行输出()。 {{ select(28) }}

A.17 24 1 8 15
B.1 8 24 17 15
C.15 24 17 8 1
D.24 17 8 1 15

输入5，输出一行数字个数()。 {{ select(29) }}

输入4，输出行所有数字和()。 {{ select(30) }}

A.175
B.200
C.150
D.120

输入2，输出行数字顺序()。 {{ select(31) }}

A.8 6 1
B.8 1 6
C.6 1 8
D.1 8 6

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

完善程序1 循环比赛日程表（ $N=2^M$ ）

#include<cstdio>
using namespace std;
const int MAXN=1025;
int a[MAXN][MAXN];
int m;
int main(){
    scanf("%d",&m);
    int n=1<<m,k=1,half=1;
    ①;
    while(k<=m){
        for(int i=0;i<half;i++){
            for (int j=0;j<half;j++)
                a[i][②]=③;
        }
        for (int i=0;i<half;i++){
            for(int j=0;j<half;j++){
                a[i+half][j]=④;
                a[i+half][j+half]=a[i][j];
            }
        }
        ⑤;
        k++;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",a[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

①处填()。 {{ select(32) }}

A.a[0][1]=1
B.a[0][0]=1
C.a[1][0]=1
D.a[1][1]=1

②处填()。 {{ select(33) }}

A.i
B.i+half
C.j
D.j+half

③处填()。 {{ select(34) }}

A.a[i][j]-half
B.a[i][j+1]-half
C.a[i][j]+half
D.a[i][j+1]+half

④处填()。 {{ select(35) }}

A.a[i][j+half]
B.a[i+half][j+half]
C.a[i+half][j]
D.a[i][j]

⑤处填()。 {{ select(36) }}

A.half/=2
B.half*=2
C.half+=2
D.half-=2

完善程序2 银河英雄传说（带权并查集）

#include<bits/stdc++.h>
using namespace std;
int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans;
char ins;
int find(int n){
    if (fa[n]==n)
        return fa[n];
    int fn=find(fa[n]);
    ①;
    return fa[n]=fn;
}
int main(){
    cin>>T;
    for(i=1;i<=30000;++i){
        fa[i]=i;
        ②;
        num[i]=1;
    }
    while(T--){
        cin>>ins>>x>>y;
        int fx=find(x); int fy=find(y);
        if(ins=='M'){
            front[fx]+=num[fy];
            fa[fx]=fy;
            ③;
            num[fx]=0;
        }
        if(ins=='C'){
            if(④)
                cout<<"-1"<<endl;
            else
                cout<<⑤ <<endl;
        }
    }
    return 0;
}

①处填()。 {{ select(37) }}

A.front[n]+=front[fa[n]]
B.front[n]+=front[n]
C.front[fa[n]]+=front[n]
D.front[fa[n]]+=front[fa[n]]

②处填()。 {{ select(38) }}

A.front[i]=1
B.front[i]=0
C.front[i]=i
D.front[fa[i]]=0

③处填()。 {{ select(39) }}

A.num[fx]+=num[fy]
B.num[fy]+=num[fy]
C.num[fx]+=num[fx]
D.num[fy]+=num[fx]

④处填()。 {{ select(40) }}

A.fx>fy
B.fx==fy
C.fx<fy
D.fx!=fy

⑤处填()。 {{ select(41) }}

A.abs( front[x]-front[y])-1
B.abs( front[x]-front[y])+1
C.abs( front[ num[x]]-front[num[y]])-1
D.abs( front[ num[x]]-front[ num[y]])+1

#CSPS002. CSP-S提高级第2套初赛模拟试题

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

二、阅读程序（判断√/×，判断1.5分，选择4/5分，共40分）

阅读程序1 拓扑排序+最长路径

阅读程序2 数位DP

阅读程序3 奇数阶幻方填充

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

完善程序1 循环比赛日程表（N=2MN=2^MN=2M）

完善程序2 银河英雄传说（带权并查集）

登录

完善程序1 循环比赛日程表（ $N=2^M$ ）