第一套

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

1. 在 IEEE 754 标准中，一个规格化的 $32$ 位浮点数 $x$ 的真值表示为

$$x = -1^s * (1.M) * 2^{E-127}$$

$S,E,M$ 各位占比如下所示：

S	E	M
1位	8位	23位

若一浮点数 $x$ 的 754 标准储存格式为 $(41360000)_{16}$，则其十进制数值为 {{ select(1) }}

• $314.625$
• $63.125$
• $11.375$
• $303.125$

2. 在计算机系统中，采用总线结构便于实现系统的积木化构造，同时可以 {{ select(2) }}

• 提高数据传输速度
• 提高、数据传输量
• 减少信息传输线的数量
• 减少指令系统的复杂性

3. 如果某系统 $15*4=112$ 成立，则该系统采用的是几进制？{{ select(3) }}

• 六
• 七
• 八
• 九

4. 将多项式 $2^7+2^5+2^2+2^0$ 表示为十六进制数，其值为{{ select(4) }}

• $55$
• $95$
• $A5$
• $EF$

5. 一张分辨率为 4K 的 $32$ 位真彩色照片，在不压缩的情况下，其存储容量为{{ select(5) }}

• $16$KB
• $128$KB
• $33.75$MB
• $270$MB

6. 下列问题中不可用贪心算法求得最优解的是{{ select(6) }}

• 哈夫曼编码
• 活动安排问题
• 0-1 背包问题
• 单源最短路径

7. 线性表采用链式存储时，节点的存储地址{{ select(7) }}

• 必须是不连续的
• 连续与否均可
• 必须是连续的
• 和头结点的存储地址相连续

8. 树是一种非线性数据结构，其最适合用来表示{{ select(8) }}

• 有序数据元素
• 无序数据元素
• 元素之间具有分支层次关系的数据
• 元素之间无联系的数据

9. 二叉树是一种特殊的树，一颗二叉树的第 $k$ 层的节点数最多为{{ select(9) }}

• $2k-1$
• $2k+1$
• $2^{k-1}$
• $2^{k+1}$

10. 设连通图 $G$ 中的边集 $E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}$，则从顶点 $a$ 出发可以得到的一种深度优先遍历的顶点序列为{{ select(10) }}

• abedfc
• acfebd
• abcedf
• abcdef

11. 随着世界各国互联网应用的发展，越来越多的 IP 地址被不断分配给最终用户，这样一来，IP 地址近乎枯竭，在这样的情况下，IPv6 应运而生，IPv6 采用 {{ select(11) }} 位二进制表示网络地址。

• $48$
• $64$
• $96$
• $128$

12. 有 $7$ 个一模一样的苹果，放到 $3$ 个不同的盘子中，每个盘子中至少有 $1$ 个苹果的放法一共有 {{ select(12) }} 种。

• $10$
• $15$
• $21$
• $30$

13. 在博士学位的授予仪式上，执行主席看到一脸稚气的维纳，颇为惊讶，于是就当面询问他的年龄，维纳不愧为数学申通，他的回答十分巧妙：“我今年岁数的立方是一个四位数，岁数的四次方是一个六位数，这两个数，刚好把十个数字 $0,1,2,3,4,5,6,7,8,9$ 全都用上了，不重不漏。这意味着全体数字都向我俯首称臣，预祝我将来在数学领域里一定能干出一番惊天动地的大事业”维纳此言一出，四座皆惊，大家都被他的这道妙题深深地吸引住了，整个会场上的人，都在议论他的问题。请问当年维纳的年龄是 {{ select(13) }} 。

• $16$
• $18$
• $19$
• $21$

14. 新上任的宿舍管理员拿到 $10$ 把钥匙去开 $10$ 个房间的们，他知道没把钥匙只能开其中的一个门，但不知道每把钥匙是开那一个门的钥匙，现在要打开所有关闭着的 $10$ 个房间，他最多要试开{{ select(14) }}次。

• $10$
• $25$
• $30$
• $55$

15. 通过下面的哪项技术，人类实现了世界范围的信息资源共享，世界变成了“地球村”？{{ select(15) }}

• 现代交通
• 现代通信
• 计算机网络
• 现代基因工程

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×，除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）

1	#include<iostream>
2	using namespace std;
3	#define maxn 50
4	const int y=2021;
5	int n,c[maxn][maxn],i,j,s=0;
6	int main()
7	{
8		cin>>n;
9		c[0][0]=1;
10		for(i=1;i<=n;i++)
11		{
12			c[i][0]=1;
13			for(j=1;j<i;j++)
14				c[i][j]=c[i-1][j-1]+c[i-1][j];
15			c[i][i]=1;
16		}
17		for(i=0;i<=n;i++)
18			s=(s+c[n][i])%y;
19		cout<<s<<endl;
20		return 0;
21	}

判断题

16. 第 $3$ 行和 $4$ 行的功能相似，都是定义变量，交换定义，即

const int maxn=50;
#define y 2021

程序运行结果不变{{ select(16) }}

• √
• ×

17. 将第 $15$ 行移动到第 $12$ 行行末，程序运行结果不变{{ select(17) }}

• √
• ×

18. 输入的 $n$ 的范围为 $[1,50]$,若超过这个范围，则程序无法正常运行{{ select(18) }}

• √
• ×

19. 根据第 $14$ 行程序可知，对于 $1\le i,j\le n$，$c_{i,j}$ 的值肯定比 $c_{i-1,j-1}$ 的值大 {{ select(19) }}

• √
• ×

选择题

20. 当输入 $n=7$ 时，输出结果为 {{ select(20) }}

• $64$
• $128$
• $256$
• $512$

21. 当输入 $n=17$ 时，输出结果为{{ select(21) }}

• $1728$
• $1435$
• $65536$
• $131072$

1	#include<iostream>
2	#include<cstdlib>
3	using namespace std;
4	int a[1000001],n,ans=-1;
5
6	void swap(int &a,int &b)
7	{
8		int t;
9		t=a;a=b;b=t;
10	}
11	int kth(int left,int right,int n)
12	{
13		int tmp,value,i,j;
14		if(left==right)return left;
15		tmp=rand()%(right-left)+left;
16		swap(a[tmp],a[left]);
17		value=a[left];
18		i=left;
19		j=right;
20		while(i<j)
21		{
22			while(i<j && a[j]<value)j--;
23			if(i<j){a[i]=a[j];i++;}else break;
24			while(i<j && a[i]>value)i++;
25			if(i<j){a[j]=a[i];j--;}else break;	
26		}
27		a[i]=value;
28		if(i<n)return kth(i+1,right,n);
29		if(i>n)return kth(left,i-1,n);
30		return i;
31	}
32	int main()
33	{
34		int i,m;
35		cin>>m;
36		for(i=1;i<=m;i++)
37			cin>>a[i];
38		cin>>n;
39		ans=kth(1,m,n);
40		cout<<a[ans]<<endl;
41		return 0;
42	}

判断题

22. 将第 $15$ 行 tmp = rand()%(right - left) + left 换成 tmp=(right + left) / 2，程序运行结果不变{{ select(22) }}

• √
• ×

23. 第 $28$ 行和第 $29$ 行的递归调用，每次只能调用其中一个。{{ select(23) }}

• √
• ×

24. 第 $22$ 行和第 $24$ 行的 while 循环，程序每次运行都会至少执行 $1$ 次循环{{ select(24) }}

• √
• ×

选择题

25. 此程序的时间复杂度是 {{ select(25) }}。

• $O(\text{log} n)$
• $O(n^2)$
• $O(n\text{log} n)$
• $O(n)$

26. 若输入数据为

3 
4 7 5 
2

则程序的运行结果是 {{ select(26) }}。

• $3$
• $4$
• $7$
• $5$

27. 若输入数据为

10
80 90 40 50 20 30 10 60 70 100
4

则程序的运行结果是 {{ select(27) }}。

• $44$
• $40$
• $60$
• $70$

1	#include<iostream>
2	#include<cstring>
3	using namespace std;
4	const int SIZE=1000;
5	const int LENGTH=10;
6	int n,m,a[SIZE][LENGTH];
7	int h(int u,int v)
8	{
9		int ans,i;
10		ans=0;
11		for(i=1;i<=n;i++) 
12			if(a[u][i]!=a[v][i])
13				ans++;
14		return ans;
15	} 
16	int main()
17	{
18		int sum,i,j;
19		cin>>n;
20		memset(a,0,sizeof(a));
21		m=1;
22		while(1)
23		{
24			i=1;
25			while((i<=n) && (a[m][i]==1))
26				i++;
27			if(i>n)break;
28			m++;
29			a[m][i]=1;
30			for(j=i+1;j<=n;j++)
31				a[m][j]=a[m-1][j];
32		}
33		sum=0;
34		for(i=1;i<=m;i++)
35			for(j=1;j<=m;j++)
36				sum+=h(i,j);
37		cout<<sum<<endl;
38		return 0;
39	}

判断题

28. 程序的输出结果有可能是 $0$。{{ select(28) }}

• √
• ×

29. 数组 $a$ 中的值要么是 $0$，要么是 $1$，没有其他值。{{ select(29) }}

• √
• ×

30. 第 $25$ 行的 while 循环每次执行至少执行 $1$ 次。{{ select(30) }}

• √
• ×

选择题

31. 当 $n<10$ 时且代码运行到第 $33$ 行，用 $n$ 计算 $m$ 最接近的表达式是 {{ select(31) }}

• $n^2$
• $nlog n$
• $2^n$
• $n^3$

32. 若 $n=3$，则输出结果为{{ select(32) }}

• $8$
• $64$
• $96$
• $108$

33. （$4$ 分）若输入 $n=7$，则输出结果为{{ select(33) }}

• $16384$
• $57344$
• $65536$
• $131072$

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

（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一做独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 $n(2\le n<100)$ 和这 $n$ 个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有三个人甲、乙、丙，他们单独过桥的时间分别为 $1$、$2$、$4$，则总共最少需要的时间为 $7$，具体方法是：甲、乙一起过桥到达河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为 $2+1+4=7$。

#include<iostream>
using namespace std;
const int SIZE=100;
const int INFINITY=10000;
const bool LEFT=true;
const bool RIGHT=false;
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
	if(a>b)
		return a;
	else 
		return b;
}
int go(bool stage)
{
	int i,j,num,tmp,ans;
	if(stage == RIGHT_TO_LEFT){
		num = 0;
		ans = 0;
		for(i=1;i<=n;i++)
			if(pos[i]==RIGHT){
				num++;
				if(hour[i]>ans)
					ans=hour[i];
			}
		if(①)
			return ans;
		ans = INFINITY;
		for(i=1;i<=n-1;i++){
			if(pos[i]==RIGHT)
				for(j=i+1;j<=n;j++)
					if(pos[j]==RIGHT){
						pos[i]=LEFT;
						pos[j]=LEFT;
						tmp=max(hour[i],hour[j])+②;
						if(tmp<ans)
							ans=tmp;
						pos[i]=RIGHT;
						pos[j]=RIGHT; 
					}
			return ans;
		} 
	}
	if(stage==LEFT_TO_RIGHT){
		ans = INFINITY;
		for(i=1;i<=n;i++)
			if(③){
				pos[i]=RIGHT;
				tmp=④;
				if(tmp<ans)
					ans=tmp;
				⑤; 
			}
		return ans;
	}
	return 0;
}
int main()
{
	int i;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>hour[i];
		pos[i]=RIGHT;
	}
	cout<<go(RIGHT_TO_LEFT)<<endl;
	return 0;
}

34. ① 处应填{{ select(34) }}。

• num <= 0
• num <= 1
• num <= 2
• num <= 3

35. ② 处应填{{ select(35) }}。

• go(LEFT_TO_RIGHT)
• go(RIGHT_TO_LEFT)
• go(LEFT)
• go(RIGHT)

36. ③ 处应填{{ select(36) }}。

• pos[i] == LEFT && pos[i + 1] == LEFT
• pos[i] == LEFT || pos[i + 1] == LEFT
• pos[i] == LEFT
• pos[i] != LEFT

37. ④ 处应填{{ select(37) }}。

• go(RIGHT_TO_LEFT) + hour[i]
• go(LEFT_TO_RIGHT) + hour[i]
• min(hour[i], hou[i + 1]) + hour[i]
• hour[i]

38. ⑤ 处应填{{ select(38) }}。

• pos[i] = LEFT_TO_RIGHT
• pos[i] = RIGHT_TO_LEFT
• pos[i] = LEFT
• pos[i] = RIGHT

（黑白棋）在一个 $4\times 4$ 的棋盘上摆放了 $14$ 颗棋子，其中由 $7$ 颗白色棋子，$7$ 颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，称为棋子的一步，黑白双方交替走棋，任意一方可以先走，如果在某个时刻使得任意一种颜色的棋子形成四个一条线（包括斜线），则这样的状态称为目标棋局，棋盘的初始状态如下。

BWBO
WBWB
BWBW
WBWO

程序读入一个 $4*4$ 的初始棋局，黑棋用 B 表示，白棋用 W 表示，空白地带用 O 表示。输出移动到目标棋局所需要的最少步数

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};
int map[5][5],minn=1000;
char s;
void Dfs(int x,int y,int num,int b)
{
	int m=10000,i,j,k;
	if(①)
		return;
	for(i=1;i<=4;i++)
	{
		if(map[i][1]==map[i][2] && map[i][2]==map[i][3] && map[i][3]==map[i][4] && (map[i][4]==1 || map[i][4]==2))
			m=num;
		if(map[1][i]==map[2][i] && map[2][i]==map[3][i] && map[3][i]==map[4][i] && (map[4][i]==1 || map[4][i]==2))
			m=num;
	}
	if(map[1][1]==map[2][2] && map[2][2]==map[3][3] && map[3][3]==map[4][4] && (map[4][4]==1 || map[4][4]==2))
			m=num;
	if(map[4][1]==map[3][2] && map[3][2]==map[2][3] && map[2][3]==map[1][4] && (map[1][4]==1 || map[1][4]==2))
			m=num;
	if(②)
	{
		minn = m;
		return;
	}
	for(i=1;i<=4;i++)
	{
		int tx=x+xx[i];
		int ty=y+yy[i];
		if(tx>0 && tx<=4 && ty>0 && ty<=4 && ③)
		{
			map[x][y]=map[tx][ty];
			map[tx][ty]=0;
			if(b==1)
				b = 2;
			else b=1;
			for(j=1;j<=4;j++)
				for(k=1;k<=4;k++)
					if(!map[j][k])
						④;
			map[tx][ty]=map[x][y];
			⑤
			if(b==1)
				b=2;
			else b=1; 
		}	
	}
}
int main()
{
	int i,j;
	for(i=1;i<=4;i++){
		for(j=1;j<=4;j++){
			cin>>s;
			if(s=='W')map[i][j]=1;
			if(s=='B')map[i][j]=2;
		}
	}
	for(i=1;i<=4;i++)
		for(j=1;j<=4;j++)
		{
			Dfs(i,j,0,1);
			Dfs(i,j,0,2);
		}
	cout<<minn<<endl;
	return 0;
}

39. ① 处应填{{ select(39) }}。

• num <= 0
• num <= 1
• num >= minn
• b==0

40. ② 处应填{{ select(40) }}。

• m <= minn
• m < minn
• m > minn
• m >= minn

41. ③ 处应填{{ select(41) }}。

• !map[tx][ty]
• map[tx][ty] == b
• b == 1
• b == 2

42. ④ 处应填{{ select(42) }}。

• Dfs(tx, ty, num, b)
• Dfs(tx, ty, num + 1, b)
• Dfs(j, k, num, b)
• Dfs(j, k, num + 1, b)

43. ⑤ 处应填{{ select(43) }}。

• map[x][y] = 0
• map[x][y] = 1
• map[tx][ty] = 0
• map[tx][ty] = 1