不是VIP会员,不能显示答案,请在后台“我的信息” 在线升级 VIP

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

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

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

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

  • A.35/11
  • B.34/11
  • C.33/11
  • D.34/10

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

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

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

  • A.x mod ll
  • B.x^2 mod ll
  • C.2x mod 11
  • D.([sort(x)] mod 11,其中[x]表示向下取整

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

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

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 _____________;
正确的填空顺序是( )。

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

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

  • A.数组访问越界
  • B.排序结果错误
  • C.陷入死循环
  • D.排序时间退化为平方级

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

  • A.0010101
  • B.100101l0
  • C.10010101
  • D.01101010

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

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

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

  • A.不再需要头指针了
  • B.已知某个结点的位置后,能很容易地找到它的直接前驱结点
  • C.在进行删除操作后,能保证链表不断开
  • D.从表中任一结点出发都能遍历整个链表

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

  • A.O(N*N)
  • B.O(NlogN)
  • C.O(N)
  • D.O(1)

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

  • A.O(n)
  • B.O(nlog2(n))
  • C.O(nlog2^2(n)))
  • D.O(nlog2^3(n))

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

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

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

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

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

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

二、阅读程序(程序输入不超过数组或字符串定义的范围;除特殊说明外,判断题1.5分,选择题3分,共计40分)

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


判断题

1) 若将19行 “(decree[b]++);”"改为“(degree[a]++);”则运行结果不变。()
2) 该程y序的时间复杂度是O(n)。( )
3) 将代码书删除11至15行,值不变。( )
4) 若输人数据为:4 5 0 2 1 3 0 1 0 3 2 3 则输出3。()


选择题

5) (4分)第5行定义的意义是( )
6) 这个程序是用了( )。

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

判断题

1) 同时包含4和8的数字都不可能被统计。(
2) 相邻数位中,位中。超过3个数位相同的数字都不可能被统计。( )


选择题

3) (4分)下列哪个是合法(可能会被优计)的数字?( )
4) (5分)当输入12121000 12121350时1序输出结果为( )

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) 结果的数字个数为2n。( )
2) 输入1时,结果为1。( )


选择题

3) 若输入3,则输出是( )。
4) 若输入5,则输出的个数有。( )
5) 若输入4时,则输出结果的和是( )。
6) 若输入2,则输出( )。

三、完善程序(单选题,每题3分,共计30分)

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


选择题

1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )

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


选择题

1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )