全国提高组 CSP-S 初赛模拟试题 (2) [2021年]

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

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

3. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数﹐第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是( )。

4. 将(2,6,10,17) 分别储存到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x)=( )将不会产生冲突，其中 a mod b表示a除以b的余数。

5. 二分图是指能将定点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12 个顶点的二分图至多有( )条边。

6. 有一个含有k个不同的数的数组S=。在S中有这样一个数 xi (1 < i< n)使得x1 xi+1>...>xn-1>xn，则称这个数xi为数组S的“峰顶”，S就为单峰的。 下面有几行代码，请将a~e五处代码补全到算法之中，使得算法正确找到S的峰顶。

a.S[mid] < S[mid+1] b.S[mid] > S[mid+1] c.Search(1,mid-1) d.Search(mid+1,k) e.return S[mid]
Search(1,k)
{
	mid=k/2;
	if (S[mid]>S[mid-1]&&_______)
	{
		_____________;
	}
	else if( S[mid]>S[mid-1]&&_________)
	{
		_____________;
	}
	else _____________;

7. 如果不在快速排序中引入随机化，有可能导致的后果是( )。

8. 二进制数 -1101010 的补码是( )。

9. 设二进制数x的值是11001101，若想通过 x&y 运算 x 中的低度4位不变，高4位清零，则y的二进制数是( )。

10. 循环链表的主要优点是( )。

11. 某算法计算时间表示为递推美系式: T(N)=N+T(N/2)，则该算法时间复杂度为( )。

12. 若某算法的计算时间表示为递推关系: T(n)=3T(n/4)+nlog2(n) 则该算法的复杂度为( )。

13. 由五个不同的节点构成的无根树有( )种。

14. 2019年10月14日是星期一，1978年10月l4日是( )。

15. 一张有9个节点的简单无向图最多有( )条边。

1.

#include <iostream>

using namespace std;



int n,m,i,j,a,b,head,tail,ans;

int graph[100][100];

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 (int 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;

}

判断题

选择题

2.

#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; r<= Up; ++i)

        ret += Dfs(now-1,i,p,_4|(i==4),_8|(i==8),

                   top&&(i==Up), hw|(i==pp&&i==p));

    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;

}

判断题

选择题

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;

}

判断题

选择题

1. (循环比赛日程表)设有N个选手进行循环比赛，其中N=2^M，要求每名选手要与其他 N-1 名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1 天，要求每天没有选手轮空。
输入一个正整数M。输出表格形式的比赛安排表。一行中各数据问用一个空格隔开。
例如输入: 3
样例输出:
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

#include <cstdio>

using namespace std;

const int MAXN = 1025,MAXM=11;

int a[MAXN][MAXN];

int m;

int main() {

    scanf("%d", &m);

    int n=1<<m,k=1, half=1;

    ___(1)___;

    while(k <= m) {

        for (int i= 0; i<=half; i++) {

            for (int j = 0; j< half; j++) {

                a[i][___(2)___]=___(3)___;

            }

        }

        for (int i= 0; i< half; i++) {

            for (int j = 0; j< half; j++) {

                a[i+half][j] =___(4)___;

                a[i+half][j+half] = a[i][j];

            }

        }

        ___(4)___;

        k++;

    }

    for (int i= 0; i< n; i++) {

        for (int j= 0; j<n; j++) {

            printf(" %d ",a[i][j]);

        }

        poutchar('\n');

    }

    return 0;

}

选择题

2. (并查集)舰队司令莱因哈特率领十万余艘战规出征。名将杨威利组织麾下三万晚战舰迎敌。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1,2,...,30000之后，他把自己的战舰也依次编号为1,2,...,30000，让第i号战舰处于第i列(i=1,2,...,3000)。这是初始阵形。杨威利会多次发布合并指令，将大部分战战舰集中在某几列上，实施密集攻击。合并指令为Mi,j，含义为第i号战舰所在的整个战舰队列，作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。在杨威利发布指令调动舰队的同时，莱因哈特也会发出一些询问指令:Ci,j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中， 如果在同一列中，那么它们之间布置有多少战舰。你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

#include <bits/stdc++.h>

using namespace std;

int f[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]);

    ___(1)___;

    return fa[n] = fn;

}

int main() {

    cin>> T;

    for(i=1; i<=30000; ++i) {

        fa[i]= i;

        ___(1)___;

        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]=ty;

            ___(3)___;

            num[fx]=0;

        }

        if(ins =='C') {

            if(___(4)___)

                cout <<"-1" << endl;

            else

                cout <<___(5)___<< endl;

        }

    }

    return 0;

}

选择题