You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

1. 下列不属于操作系统的是：( ) {{ select(1) }}

• $Android$
• $BSD$
• $Sublime$
• $Linux$

2. 计算机直接识别和执行的语言是：( ) {{ select(2) }}

• 汇编语言
• 机器语言
• 高级语言
• 自然语言

3. 质数是有且仅有两个因子的数。以下哪个进制数是质数：( ) {{ select(3) }}

• $(93)10$
• $(73)16$
• $(1011011)2$
• $(141)8$

4. 在 $TCP/IP$ 协议分层模型中，$5G$ 即第五代移动通信技术属于：( ) {{ select(4) }}

• 链路层
• 网络层
• 传输层
• 应用层

5. $5G$ 最大下载速度可以达到 $800MB/s$，以该速度1s内能下载最多( )张完整的分辨率为$1600×1600、256$ 位色的位图。 {{ select(5) }}

• $9$
• $10$
• $39$
• $40$

6. 某算法的计算时间满足递推关系式 $T(n) = T(n/2) + \sqrt(n), T(1) = 1$。则该算法的时间复杂度为：( ) {{ select(6) }}

• $O(\sqrt {n})$
• $O(\sqrt {nlogn})$
• $O(\sqrt{n} logn)$
• $O(n)$

7. 盒子中有 6 种颜色的球各一个，每次等概率取出一个球并放回，期望( )次后取遍所有的颜色。 {{ select(7) }}

• $12$
• $12.3$
• $14.7$
• $15$

8. 一列列车由若干车厢连接组成。平时我们听到的“列车入库”其实就是列车经过入口驶入所在站点库存的过程。下一次使用时，该列车会从出口驶出，原先作为车头的车厢成为了车尾。“列车入库”的结构与( )相仿。 {{ select(8) }}

• 队列
• 栈
• 链表
• 堆

9. 一棵二叉树如下图所示 若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。 {{ select(9) }}

• $6$
• $12$
• $7$
• $14$

10. 一棵完全二叉树有 n 个结点，哪个代码表达式可以计算出其叶子结点数：( )。{{ select(10) }}

• $n / 2$
• $(n + 1) / 2 - 1$
• $(int)(n / 2.0)$
• $(int)(n / 2.0 + 0.5)$

11. 图中 $9×9$ 网格部分格为雷，其余格为数字，表示周围一圈八个格子雷的总数。浅色部分已显示，深色部分尚未知是雷或数字。多少问号处必定为雷？( ) {{ select(11) }}

• $1$
• $2$
• $3$
• $4$

12. 如图所示，从 $A$ 点出发，每次沿网格线向上或向右行走一格，不允许穿过红线或走出网格外，到达 $B$ 点。有多少种不同的走法？（图中已画出一种走法）( ) {{ select(12) }}

• $715$
• $495$
• $455$
• $429$

13. 下列哪个算法不是用来求最小生成树的：( ) {{ select(13) }}

• $Kruscal$算法
• $Boruvka$ 算法
• $Prim$ 算法
• $Tarjan$ 算法

14. 以下关于最小生成树的性质，错误的是：( ) {{ select(14) }}

• 最小生成树的边权和是所有生成树中最小的
• 最小生成树的边权最大值是所有生成树中最小的
• 任取两点，其最小生成树上唯一路径边权和是所有生成树中最小的
• 任取两点，其最小生成树上唯一路径边权最大值是所有生成树中最小的

15. 在有 $n$ 个子叶节点的哈夫曼树中，其节点总数为（ ） {{ select(15) }}

• $2^n-1$
• $2n+1$
• $2n-1$
• $2n$

二、阅读程序（程序输入不超过数组定义的范围；选择题单选；共计 40 分）

判断题

1. 阅读程序回答下列问题

#include <iostream>

using namespace std;

int a, b, x, y;

int main()
{
	cin >> a >> b;	//0 <= a, b <= 10^9
	while(1)
	{
		x = a ^ b;	//7行
		y = a & b;
		if(y == 0)
		{
			break;
		}
		a = x;		//10行
		b = y << 1;	//11行
	}
	cout << x << endl; //13行
	return 0;
}

1. （1 分）第 $11$ 行的 << 意义与第 $13$ 行的 << 相同。( ) {{ select(16) }}

• $true$
• $false$

2. （1.5 分）第 $7$ 行计算得到的 $x$ 每次比上一次计算得到的大。( ) {{ select(17) }}

• $true$
• $false$

3. （1.5 分）存在一组注释所示范围内的 $a, b$ 使程序会陷入死循环。( ) {{ select(18) }}

• $true$
• $false$

4. （2 分）若输入 $a = 155, b = 229$，程序各执行第 $10,11$ 行八次。( ) {{ select(19) }}

• $true$
• $false$

5. （3 分）设 $n$ 为 $max (a, b)$，最优情况下，此程序的时间复杂度是( )。 {{ select(20) }}

• $O(1)$
• $O(logn)$
• $O(n)$
• $O(nlogn)$

6. （4 分）设 $n$ 为 $max (a, b)$，最坏情况下，此程序的时间复杂度是( )。 {{ select(21) }}

• $O(1)$
• $O(logn)$
• $O(n)$
• $O(nlogn)$

2. 阅读程序回答下列问题

#include <iostream>

using namespace std;

const int inf = 1e9;	//4行 1e9 = 1 * 10 ^ 9; 

int n, m, a[1000][1000], f[1000], g[1000];

void solve(int s, int res[])
{
	queue<int> que;
	for(int u=0; u<n; u++)
	{
		res[u] = inf;
	}
	res[s] = 0;
	que.push(s);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		for(int v=0; v<n; v++)
		{
			if(res[v] > res[u] + a[u][v])
			{
				res[v] = res[u] + a[u][v];
				que.push(v);
			}
		}
	}
}

int main()
{
	cin >> n >> m;	//n > 1
	for(int u=0; j<n; u++)
	{
		for(int v=0; v<n; v++)
		{
			a[u][v] = inf;
		}
	}
	for(int i=0; i<m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		if(a[u][v] > w) a[u][v] = w;
		if(a[v][u] > w) a[v][u] = w;
	}
	solve(0, f);
	solve(1, g);
	int ans = 0;
	for(int u=0; u<n; u++)
	{
		if(ans < f[u] + g[u])
		{
			ans = f[u] + g[u];
		}
	}
	cout << ans << endl;
	return 0;
}

1. （1 分）a 数组为邻接表，是一种存储无向图的结构。( ) {{ select(22) }}

• $true$
• $false$

2. （1 分）将第 4 行 $inf$ 的取值改成 $2e9$ 不影响程序运行结果。( ) {{ select(23) }}

• $true$
• $false$

3. （1.5 分）函数 $solve(int s, int res[])$ 中的 $res$ 是指针形参，在函数内对 $res$ 数组的修 改会同时作用于作为实参的数组。( ) {{ select(24) }}

• $true$
• $false$

4. （1.5 分）若输出大于等于 $inf$，则 $0$ 号结点不与 $1$ 号结点连通。( ) {{ select(25) }}

• $true$
• $false$

5. （4 分）若图连通且边权全为 $1$，此时程序输出 $6$，$n$ 最小为( )。{{ select(26) }}

• $4$
• $5$
• $6$
• $7$

6. （4 分）忽略 m，最坏情况下，此程序的时间复杂度是( )。{{ select(27) }}

• $O(n^2)$
• $O(n^2logn)$
• $O(n^3)$
• $O(n^n)$

3. 阅读程序回答下列问题

#include <iostream>

using namespace std;

const int maxn = 1000002;

int n, a[maxn], first[maxn], last[maxn], pre[maxn], suf[maxn];

int main()
{
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
		first[i] = n+1;
		last[i] = 0;
	}
	for(int i=1; i<=n; i++)
	{
		if(first[a[i]] == n+1)
		{
			first[a[i]] = i;
		}
	}
	for(int i=n; i>=1; i--)
	{
		if(last[a[i]] == 0)
		{
			last[a[i]] = i;
		}
	}
	pre[0] = 0;
	for(int i=1; i<=n; i++)
	{
		pre[i] = pre[i-1];
		if(pre[i] > first[i])
		{
			pre[i] = n+1;
		}
		if(pre[i] < last[i])
		{
			pre[i] = last[i];
		}
	}
	suf[n+1] = n+1;
	for(int i=n; i>=1; i--)
	{
		suf[i] = suf[i+1];
		if(suf[i] < last[i])
		{
			suf[i] = 0;
		}
		if(suf[i] > first[i])
		{
			suf[i] = first[i];
		}
	}
	long long ans = 0;
	for(int i=1, j=1; i<=n; i++)
	{
		while(j<=n && suf[j+1] <= pre[i-1])
		{
			j++;
		}
		if(j < i)
		{
			j = i;
		}
		ans += n + 1 - j;
	}
	cout << ans << endl;
	return 0;
}

1. （1 分）对于 $1 ≤ x ≤ n$，若不存在 $a[i] = x$，则程序执行到第 $18$ 行时 $last[x]$ 为 0。 ( ) {{ select(28) }}

• $true$
• $false$

2. （1.5 分）若对 $1 < i ≤ n$ 满足 $a[i-1] <= a[i]$，则输出为 $C_{n+1}^2$ {{ select(29) }}

• $true$
• $false$

3. （1.5 分）存在一组输入使得输出为 $2$。( ) {{ select(30) }}

• $true$
• $false$

4. （2 分）程序输出时，对 $1 ≤ i ≤ n$ 一定满足 $pre[i] >= suf[i]$。( ) {{ select(31) }}

• $true$
• $false$

5. （4 分）若 $n = 10$ 且程序输出 $18$，输入的 $a$ 数组从 $1$ 到 $n$ 可能是：( )。 {{ select(32) }}

• 1 6 2 5 3 4 8 10 9 7
• 1 6 2 5 3 4 8 9 10 7
• 1 6 2 5 8 3 4 10 9 7
• 1 6 2 5 8 3 4 9 10 7

6. （4 分）以下哪项操作不会影响程序运行结果：( ) {{ select(33) }}

• 交换第 $21$ 行和第 $22$ 行的代码
• 将第 $27$ 行的 < 修改为 <=
• 将第 $32$ 行的 <= 修改为 <
• 移除第 $34$ 行的代码

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

1. 最速洗牌

一套牌由 $n$ 张数字牌（从 $1$ 到 $n$）和 $n$ 张空牌（用 $0$ 标注）组成，其中 $n$ 张牌在你手中，其余形成牌堆。一次操作可以将手中的任意一张牌置入牌堆底，并从牌堆顶摸入新的手牌。求最少多少次操作能让最终手牌均为空牌，且牌堆 从上到下 第 $i$ 张牌恰好数值为 $i$。

输入第一行给定数字牌个数 $n(1 \le n \le 10^5)$ 第二行有 $n$ 个数，分别表示初始你的每张手牌，空牌以 $0$ 标注。 第三行有 $n$ 个数，第 $i$ 个数表示初始从 从上到下 第 $i$ 张牌的数值，空牌以 $0$ 标注。 输出达到目标最少的操作数。

可以采用贪心解决这个问题，最优策略一定是下面两种之一：

• 存在 $x$，依次从手牌中取出 $x$ 张空牌，再依次取出数值牌 $1, 2, \cdots, n$
• 存在 $x$，依次从手牌中取出数值牌 $x, x+1, \cdots, n$

试补全下面的程序

#include <iostream>

using namespace std;

int n, ans, a[100001], b[100001], p[100001];

int main()
{
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	for(int i=1; i<=n; i++)
	{
		cin >> b[i];
		_____1_____;
	}
	for(int i=1; i<=n; i++)
	{
		int t = _____2_____;
		if(ans < t)
		{
			ans = t;
		}
	}
	if(p[1] != 0)
	{
		int i = 2;
		while(i <= n && _____3_____)
		{
			i++;
		}
		if(p[i-1] == n)
		{
			int j =i;
			while(j <= n && _____4_____)
			{
				j++;
			}
			if(j > n)
			{
				int t = n - i + 1;
				if(_____5_____)
				{
					ans = t;
				}
			}
		}	
	}
	cout << ans << endl;
	return 0;
}

1. 1 处应填( ) {{ select(34) }}

• p[i] = b[i]
• p[n + 1 – i] = b[i]
• p[b[i]] = i
• p[b[i]] = n + 1 – i

2. 2 处应填( ) {{ select(35) }}

• p[i] + i - 1 + n
• i – p[i] – 1 + n
• i - p[i] + 1 + n
• p[i] - i + 1 + n

3. 3 处应填( ) {{ select(36) }}

• p[i] == p[1] + i - 1
• p[i] == p[1] - i + 1
• p[i] >= p[1] + i - 1
• p[i] >= p[1] - i + 1

4. 4 处应填( ) {{ select(37) }}

• p[j] == j – i
• p[j] <= j – i
• p[j] == p[1] - j + 1
• p[j] >= p[1] + j - 1

5. 5 处应填( ) {{ select(38) }}

• ans < t
• ans > t
• i <= n
• i <= t

2. 幸运数字

云云有 $n$ 个幸运数字 $a_0, a_1, \cdots, a_{n-1}$。此外，他定义正整数 $x$ 是厄运的，当且仅当它不是任何一个幸运数字的倍数。他想知道有多少个小于等于 $k$ 的正整数是厄运的。

输入第一行给定幸运数字的个数 $n (1 \le n \le 20)$ 和上界 $k (0 \le k \le 10^9)$。 第二行有 $n$ 个数，即幸运数字 $a_0, a_1, \cdots, a_{n-1} (1 \le a_i \le k)$。

输出合法正整数的个数。

试补全下面的程序

#include <iostream>

using namespace std;

int n, k, a[20];
long long ans;

int get(int x, int y)
{
	return !x ? y : _____1_____;
}

void dfs(int i, int s, int prod)
{
	if(i == n)
	{
		ans += _____2_____;
		return;
	}
	dfs(i+1, s, prod);
	if(k / prod >= a[i] / get(prod, a[i]))
	{
		dfs(i+1, _____3_____, _____4_____);
	}
}

int main()
{
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> a[i];
	}
	dfs(0, _____5_____, 1);
	cout << ans << endl;
	return 0;
}

1. 1 处应填( ) {{ select(39) }}

• get(x % y, y)
• get(y % x, x)
• get(y, x % y)
• get(x, y % x)

2. 2 处应填( ) {{ select(40) }}

• s * k / prod
• s * k / get(prod, k)
• k – s * k / prod
• k – s * k / get(prod, k)

3. 3 处应填( ) {{ select(41) }}

• -s
• !s
• get(prod, a[i]) != 1 ? 0 : s
• get(prod, a[i]) != 1 ? s : -s

4. 4 处应填( ) {{ select(42) }}

• prod * a[i]
• prod * a[i] / get(prod, a[i])
• prod * get(prod, a[i])
• prod / get(prod, a[i]) * a[i]

5. 5 处应填( ) {{ select(43) }}

• 0
• -1
• 1
• n % 2 ? -1 : 1