第 1 题 程序和数据在内存中都是用( ) 表示的。

第 2 题 被誉为“计算机界的诺贝尔奖”的是( ) 。

第 3 题 记(x)y表示x是y进制数，下列数中最大的是( ) .

第 4 题 以下哪个不是操作系统( ) 。

第 5 题 设栈的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序非法的是( )。

第 6 题 将数组{1,2,3,4,5,6,7,8}中的元素用冒泡排序的方法从大到小排序，需要比较( )次。

第 7 题 以下哪个是合法的电子邮件地址( ) 。

第 8 题 有n个叶子的哈夫曼树的结点总数为( ) 。

第 9 题 以下不是存储设备的是( ) 。

第 10 题 用P表示命题“派小王参加下周的会议”，用Q表示命题“派小李参加下周的会议”，则命题“小王和小李两个人中必须派一人且只能派一人参加下周的会议”可以表示为( ).

第 11 题 如果在某个进制下等式13*13=171成立，那么在该进制下 12*12=( ) 。

第 12 题 以下哪个后缀表达式与中缀表达式a*(b+c)-d等价( ) 。

第 13 题 以下哪个排序不是稳定的排序( ) 。

第 14 题 在无向图中，所有项点的度数之和是边数的( ) 倍。

第 15 题 若某算法的计算时间表示为递推关系式: $T(n)=2T(\frac{n}{2})+O(n^2)$,则该算法的时间复杂度为( )。

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

第 16 题

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=1;
	cin>>n;
	for (int i=2; i*i<=n; i++)
	if (n%i==0)
	{
		ans*=i;
		while (n%i==0) n/=i;
	}
	cout<<ans<<endl;
	return 0;
}

假设输入的n是不超过$2^{10}$的正整数，完成下面的判断题和单选题:

第 16 题 该算法的时间复杂度为$O(\sqrt{n})$ 。( )

第 17 题 将第11行的代码删去，输出结果不会改变。( )

第 18 题 若输入为4，则输出为( ) 。

第 19 题 若输入为60，则输出为( ) 。

第 21 题

#include<bits/stdc++.h>
using namespace std;
int a[105],n,x,ans=0;
int main ()
{
	cin>>n;
	for (int i=1; i<=n; i++)
	{
		cin>>x;
		a[x]++;
	}
	for (int i=0; i<=100; i++)
	{
		ans+=a[i]%2;
		a[i+1]+=a[i]/2;
	}
	cout<<ans<<endl ;
	return 0;
}

假设输入的n是不超过20的正整数，x是不超过100非负整数，完成下面的判断题和单选题:

第 21 题 该算法的输出可能大于n。( )

第 22 题 当n=59时，存在一种输入，使得输出的ans为1。 ( )

第 23 题 当n=60时，存在一种输入，使得输出的ans为1。 ( )

第 24 题 若输入为5 1 1 2 3 3,则输出为()。

第 25 题 若输入的n 等于35，接下来的输入全为0，则输出为( )。

第 26 题 若输入的n等于15，接下来的输入全为98，则输出为( )。

第 28 题

#include<bits/stdc++.h>
using namespace std;
int n,p[10], ans=20220504;
bool check ()
{
	for (int i=0; i<n-1; i++) if (p[i]>p[i+1]) return 0;
	return 1;
}
void dfs(int now)
{
	if (check())
	{
		ans=min(ans,now);
		return ;
	}
	for (int i=0; i<n; i++)
	for (int j=i; j<n; j++)
	if(p[i]>p[j])
	{
		swap(p[i],p[j]);
		dfs(now+1);
		swap(p[i],p[j]);
	}
}
int main()
{
	cin>>n;
	for (int i=0; i<n; i++) cin>>p[i];
	dfs(0);
	cout<<ans<<endl;
	return 0;
}

假设输入的n是不超过$2^{20}$的正整数，p[0...n-1]是一个 0到n-1的排列，完成下面的判断题和单选题: ●判断题

第 28 题 该算法的输出不可能等于大于n。( )

第 29 题 该算法可能在某种合法是输入下进入死循环( )

第 30 题 若将第17行的j=i改为j=0，输出的结果不会改变( )

第 31 题 1)若输入为3 2 1 0,则输出为( )

第 32 题 若输入为10 7 1 4 3 2 5 9 8 0 6，则输出为( )

第 33 题 目前学术界已证明该算法所求解的问题的时间复杂度最优可以做到( ) 。

第 34 题 若将第13行的min改为max,将第三行的ans=20220504改为ans=0,当输入为5 4 2 3 0 1时，输出为( )。

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

第 36 题 (列队)有n个人排成一排，第i个人的体力为ai,你只能挑选出一段连续的人让他们出列去跑操。因为你不敢选一些体力太差的人去跑，担心他们太累，所以你选的人的体力值不能小于X。可是你希望每次能多选一些人去跑操，你需要求出至少能够选y个人去跑操时x的最大值。 如果始终都不能选出y个人，输出-1。 输入的第一行是两个 正整数n和y ($ 1 \leq n \leq 10^5 ,1 \leq y \leq 10^5$)。 输入的第二行是n个正整数$a_i (1\leq a_i\leq 2 \times 10^9)$。 提示:使用二分答案解决这个问题，二分答案为x，判断是否至少能够选出y个人。 试补全程序。

#include<bits/stdc++.h>
using namespace std;
int n,y,a[100005];
int chk(int x)
{
    int ans=0;
    int tot=0;
    for (int i=1; i<=___(1)___; i++)
	{
        if (a[i]>=x) tot++;
        else
		{
            ___(2)___;
        }
        ans=max(ans,tot);
    }
    return ans>=y;
}
int main()
{	
	cin>>n>y;
	for (int i=1; i<=n; i++) cin>>a[i];
	int ans=___(3)___;
	int l=1, r=200000000;
	while (___(4)___)
	{
	    int mid=___(5)___;
	    if (chk(mid))
	    {
	    	ans=mid;
	    	l=mid+1;
		}else
	    	r=mid-1;
	}
	cout<<ans<<endl;
}

第 36 题 ⑴处应填( )。

第 37 题 ⑵处应填( )。

第 38 题 ⑶处应填( )。

第 39 题 ⑷处应填( )。

第 40 题 ⑸处应填( )。

第 42 题 最大子段和 给定一个整数序列a[0],a[1],...,a[n-1],你可以选择k个位置加x，使得最大子段和最大。你需要对于每个0≤k≤n,求出最大子段和的最大值。 最大子段和定义为选择0≤1≤r≤n, a[l]+a[l+1]+...+a[r-1] (选择l=r时即为0)的最大值。 1≤n≤5000, 0≤x≤10^5,|a[il|≤10^5。 输入格式: 第一行两个整数n,x。 第二行n个整数a[0],a[1],...,a[n-1]. 输出格式: n+1行，第i行一个整数，表示k=i-1时的答案。 输入样例: 3 5 -2 -7 -1 输出样例 0 4 4 5 提示:假设固定k，对于一对l,r,最大的和为a[l]+a[l+1]+...+a[r-1]+min(k,r-1)*x. 枚举k,对于r-1<=k和r-1>=k的分别计算最大值即可。 程序:

#include <bits/stdc++.h>
using namespace std;
int n,x,a[5000], sum[5001], ans [5001];
int main(){
	cin>> n>> x;
	for (int i=0; i<n; ++i) cin>>a[i];
	for (int i=0; i<n; ++i) sum[i+1]=__(1)__;
	for (int l=0; l<=n; ++l)
		for(int r=1; r<=n; ++r)
			ans[r-1] = max(ans[r-1], __(2)__);
	for (int i=1; i<=n; ++i)
		ans[i] = max (ans[i], __(3)__);
	for (int k=0; k<=n; ++k){
		int pre_min =0;
		for (int i=k; i<=n; ++i){
				pre_min = min(pre_min, __(4)__);
				ans[k] = max(ans[k],__(5)__);
		}
	}
	for (int i=0; i<=n; ++i) cout << ans[i]<<"\n";
}

第 42 题 ⑴处应填( )。

第 43 题 ⑵处应填( )。

第 44 题 ⑶处应填( )。

第 45 题 ⑷处应填( )。

第 46 题 ⑸处应填( )。