第 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个节点的简单无向图最多有( )条边。

二、判断题（每题 2 分，共 20 分）

第 16 题

#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;
}

第 16 题 若将19行 “(decree[b]++);”"改为“(degree[a]++);”则运行结果不变。()

第 17 题 该程y序的时间复杂度是O(n)。( )

第 18 题 将代码书删除11至15行，值不变。( )

第 19 题 若输人数据为:4 5 0 2 1 3 0 1 0 3 2 3 则输出3。()

第 20 题 (4分)第5行定义的意义是( )

第 21 题 这个程序是用了( )。

第 23 题

#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;
}

第 23 题 同时包含4和8的数字都不可能被统计。(

第 24 题 相邻数位中，位中。超过3个数位相同的数字都不可能被统计。( )

第 25 题 (4分)下列哪个是合法(可能会被优计)的数字?( )

第 26 题 (5分)当输入12121000 12121350时1序输出结果为( )

第 28 题

#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;
}

第 28 题 结果的数字个数为2n。( )

第 29 题 输入1时，结果为1。( )

第 30 题 若输入3，则输出是( )。

第 31 题 若输入5，则输出的个数有。( )

第 32 题 若输入4时，则输出结果的和是( )。

第 33 题 若输入2，则输出( )。

三、编程题（每题 25 分，共 50 分）

第 35 题 (循环比赛日程表)设有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;
}

第 35 题 ①处应填( )

第 36 题 ②处应填( )

第 37 题 ③处应填( )

第 38 题 ④处应填( )

第 39 题 ⑤处应填( )

第 41 题 (并查集)舰队司令莱因哈特率领十万余艘战规出征。名将杨威利组织麾下三万晚战舰迎敌。在这次决战中，他将巴米利恩星域战场划分成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;
}

第 41 题 ①处应填( )

第 42 题 ②处应填( )

第 43 题 ③处应填( )

第 44 题 ④处应填( )

第 45 题 ⑤处应填( )