第 1 题 计算机中央处理器简称为（ ）。

第 2 题 下列IP地址格式正确的是（ ）。

第 3 题 要将数组{7,1,5,3,8,2,6,4}中的元素从小到大排列，每次操作可以选择一个元素取出，然后将该元素插入到另一个位置，最少需要操作（ ）次。

第 4 题 以下Linux命令中，（ ）可以用于显示访问一个主机需要经过的路由器。

第 5 题 将crosssea这8个字母按顺序推入栈中，则有（ ）种出栈顺序可以使出栈序列仍然是crosssea。

第 6 题 如果使用左儿子右兄弟表示法将一棵有根树T转换为二叉树T’，那么T’的后序遍历序 列一定与T的（ ）序列相同。

第 7 题 将(123456789ABCDEF) 16转换成二进制后，一共有（ ）位为1。

第 8 题 在RSA中，（ ）可以用于解密一条密文。

第 9 题 下列三个表达式中，和 a^b 等价的表达式有（ ）个。 (1).(a|b)&~(a&b) (2).(a&~b)|(~a&b) (3).(a|~b)&(~a|b)

第 10 题 2n个白色的位置排成一排，等概率随机将n个不同的位置染黑。若两个相邻的格子颜色相同，则认为这两个格子在一个同色连通块内。在这种条件下，同色连通块期望有（ ）个。

第 11 题 在C++语言中，表达式(5/2)+(-5/4)的值是（ ）。

第 12 题 字符串queue有（ ）个本质不同的非空子序列。

第 13 题 （ ）不是NP-Complete问题。

第 14 题 由n个无序元素创建二叉堆的最优时间复杂度是（ ）。

第 15 题 3114514 mod 7 = （ ）。

第 16 题 一张简单图的邻接矩阵为{{0,0,1},{0,0,0},{1,0,0}}}，以下说法正确的是（ ）。

第 17 题 一棵树的某个DFS序为{1,2,3,4,5}，某个BFS序为{1,2,4,3,5}，则以下说法错误的是（ ）。

第 18 题 已知T(n)=T(√n)+ Θ(1)(n>=2), T(1)= Θ(1)，那么有（ ）。

第 19 题 有（ ）种方式选择凸六边形的三条互不相交的对角线。

第 20 题 设f(x)为x在十进制下各位数之和，且f0(x)=x,fi(x)=f(f i-1(x))(i>=1)，那么f2023(2^2023)=（ ）

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

第 21 题

#include <iostream>
using namespace std;

const int N = 1001;

int n, a[N], s[N][N];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i += 1)
		cin >> a[i];
	for(int i = 2; i <= n; i += 1)
		for(int j = 1; j + i - 1 <= n; j += 1) {
			int L = j, R = j + i - 1;
			s[L][R] = s[L + 1][R] + s[L][R - 1] - s[L + 1][R - 1] + (a[L] > a[R]);
		}
	for(int i = 1; i <= n; i += 1)
		for(int j = i; j <= n; j += 1)
			cout << s[i][j] << endl;
}

第 21 题 如果输入n的值为1000，并且1 <= a[i] <= n，程序不会发生运行错误。（ ）

第 22 题 该程序时间复杂度为Θ(n^2)。（ ）

第 23 题 第12行将循环初始条件修改为i = 1, 程序对于n = 1000的数据能够正确输出。（ ）

第 24 题 当n = 10时，第14行会被执行（ ）次。

第 25 题 当n = 5，a数组对应输入数据为：{1,3,5,3,4}，则下列选项说法正确的是（ ）。

第 27 题

#include <iostream>
using namespace std;

const int N = 1001;

int n, a[N];

int ans = 0;

void dfs(int L, int R) {
	if(L > R)
		return;
	int p = L;
	for(int i = L + 1; i <= R; i += 1)
		if(a[i] < a[p])
			p = i;
	ans += (p - L + 1) * (R - p + 1) * a[p];
	dfs(L, p - 1);
	dfs(p + 1, R);
}

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

第 27 题 如果输入n = 1000, 所有的a[i] = 100000，程序不会产生整形溢出。（ ）

第 28 题 将第11行改为if(L >= R) 程序仍然可以计算出相同的结果。（ ）

第 29 题 当n = 4, a = {1, 2, 4, 3}时，输出为20。（ ）

第 30 题 该程序的最劣复杂度为（ ）。

第 31 题 该程序在a为1,2,…,n的随机排列时，时间复杂度的期望为（ ）。

第 33 题

#include <iostream>
using namespace std;

const int N = 100001;

int n, a[N];

int check(int a, int b, int c) {
	return (a <= c && c <= b) || (b <= c && c <= a);
}

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i += 1) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	int q;
	cin >> q;
	while(q--) {
		int L, R;
		cin >> L >> R;
		int target = (a[L] + a[R]) / 2;
		int pos = -1;
		while(L != R) {
			int mid = (L + R) / 2;
			if(a[mid] == target) {
				pos = mid;
				break;
			}
			if(check(a[L], a[mid - 1], target))
				R = mid - 1;
			else
				L = mid + 1;
		}
		if(pos == -1)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
}

第 33 题 该算法的时间复杂度为Θ((n+q)*log(n))。（ ）

第 34 题 程序输出NO时，代表不存在l<=x<=r，使得a[x]=target。（ ）。

第 35 题 当输入的n = 3，输入的a[i]分别为2,3,1, q=2, 两组询问分别为L=2,R=3和L=1,R=3时，输出的是（ ）。

第 36 题 当输入的n = 100，输入的a[i]当i为奇数时为-1，偶数时为1, q=2, 两组询问分别为L=1,R=100和L=30,R=40时，输出的是（ ）。

第 37 题 当a满足以下哪种条件时，程序总是输出YES（ ）。

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

第 39 题 （水仙花数问题）给定一个n <= 15，令所有十进制下长度为n的数，其各数位的n次方之和等于这个数本身，我们称这个数为水仙花数，例如当n = 3, 153 = 1^3 + 5^3 + 3^3。当n = 4, 1634 = 1^4 + 6^4 + 3^4 + 4^4。 你需要求出所有n位的水仙花数的和。

#include <cstdio>
using namespace std;

long long cost[10], ans;

int cnt[10], t[10], n;

void dfs(int rest, int now, long long current) {
	if (rest == 0) {
		long long temp = current;
		for (int i = 0; i < 10; i++)
			t[i] = 0;
		while (temp > 0) {
			++t[temp % 10];
			temp /= 10;
		}
		bool flag = 1;
		for (int i = 0; i < 10; i++)
			if (cnt[i] != t[i]) {
				flag = 0;
				break;
			}
		if (flag) {
			__(1)__;
		}
		return;
	}
	if ( __(2)__ ) {
		return;
	}
	for (cnt[now] = 0; cnt[now] <= rest; cnt[now]++)
		dfs(rest - cnt[now], now + 1, __(3)__ );
	cnt[now] = 0;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 10; i++) {
		cost[i] = 1;
		for (int j = 0; j < n; j++)
			__(4)__ ;
	}
	dfs( __(5)__ );
	printf("%lld\n",ans);
	return 0;
}

第 39 题 ⑴处应填( )。

第 40 题 ⑵处应填( )。

第 41 题 ⑶处应填( )。

第 42 题 ⑷处应填( )。

第 43 题 ⑸处应填( )。

第 45 题 （修改序列问题） 给定长度为n的序列a，定义b[i]=a[1]^a[2]^…^a[i]，其中^为异或运算。每次操作你可以将序列a中任意一个元素修改为任意数，求最少几次操作可以使得b序列单调不降。 数据范围：n <= 10^6,0 <= a[i] <= 10^9。 提示：贪心，维护每一位可能的取值。

#include <iostream>
using namespace std;

const int N = 1000001;

int n, a[N], sta[30];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i += 1)
		cin >> a[i];
	for(int i = 0; i < 30; i += 1)
		__(1)__ ;
	int ans = 0;
	for(int i = 1; i <= n; i += 1)
	{
		int msb = __(2)__ ;
		for(int j = 29; j >= 0; j -= 1) {
			if( __(3)__ ) {
				msb = j;
				break;
			}
		}
		if(msb == -1)
			continue;
		if(sta[msb] == 1) {
			ans += 1;
			fill(sta, sta + 30, __(4)__ );
		} else {
			for(int j = 0; j < 30; j += 1)
				if(sta[j] != -1)
					sta[j] ^= (a[i] >> j & 1);
			__(5)__;
		}
	}
	cout << ans << endl;
}

第 45 题 ⑴处应填( )。

第 46 题 ⑵处应填( )。

第 47 题 ⑶处应填( )。

第 48 题 ⑷处应填( )。

第 49 题 ⑸处应填( )。