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

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

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

  • A.ASCII码
  • B.二进制码
  • C.机内码
  • D.十六进制码

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

  • A.图灵奖
  • B.奥斯卡金像奖
  • C.王选奖
  • D.格莱美奖

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

  • A.(10110101010)2
  • B.(2653)8
  • C.(1450)10
  • D.(5A9)16

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

  • A.HarmonyOS
  • B.iOS
  • C.UmaMusume Pretty Derby
  • D.Windows

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

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

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

  • A.64
  • B.27
  • C.28
  • D.7

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

  • A.1004535809@qq.com
  • B.114.514.1919.810
  • C.CodeForces@$$,edu,cn
  • D.wang@hotmail@rf.edu.jp

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

  • A.2^n
  • B.2n+1
  • C.2n-1
  • D.2n

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

  • A.光盘
  • B.鼠标
  • C.磁盘
  • D.固态硬盘

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

  • A.P∧¬Q
  • B.(¬P∧Q)∨(P∧¬Q)
  • C.P∨¬Q
  • D.(P∨¬Q)V(Q∨¬P)

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

  • A.140
  • B.144
  • C.AE
  • D.148

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

  • A.abc+*d-
  • B.-+*abcd
  • C.abcd*+-
  • D.abc*+d-

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

  • A.冒泡排序
  • B.归并排序
  • C.快速排序
  • D.基数排序

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

  • A.4
  • B.2
  • C.1
  • D.0.5

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

  • A.$O(n^2 logn)$
  • B.$O(n^2log^2n)$
  • C.$O(nlogn)$
  • D.$O(n^2)$

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

1.

#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}$的正整数,完成下面的判断题和单选题:

判断题

1) 该算法的时间复杂度为$O(\sqrt{n})$ 。( )
2) 将第11行的代码删去,输出结果不会改变。( )

选择题

3) 若输入为4,则输出为( ) 。
4) 若输入为60,则输出为( ) 。

2.

#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非负整数,完成下面的判断题和单选题:

判断题

1) 该算法的输出可能大于n。( )
2) 当n=59时,存在一种输入,使得输出的ans为1。 ( )
3) 当n=60时,存在一种输入,使得输出的ans为1。 ( )

选择题

4) 若输入为5 1 1 2 3 3,则输出为()。
5) 若输入的n 等于35,接下来的输入全为0,则输出为( )。
6) 若输入的n等于15,接下来的输入全为98,则输出为( )。

3.

#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的排列,完成下面的判断题和单选题:
●判断题

判断题

1) 该算法的输出不可能等于大于n。( )
2) 该算法可能在某种合法是输入下进入死循环( )
3) 若将第17行的j=i改为j=0,输出的结果不会改变( )


选择题

4) 1)若输入为3 2 1 0,则输出为( )
5) 若输入为10 7 1 4 3 2 5 9 8 0 6,则输出为( )
6) 目前学术界已证明该算法所求解的问题的时间复杂度最优可以做到( ) 。
7) 若将第13行的min改为max,将第三行的ans=20220504改为ans=0,当输入为5 4 2 3 0 1时,输出为( )。

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

1. (列队)有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;
}

选择题

1) ⑴处应填( )。
2) ⑵处应填( )。
3) ⑶处应填( )。
4) ⑷处应填( )。
5) ⑸处应填( )。

2. 最大子段和
给定一个整数序列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";
}

选择题

1) ⑴处应填( )。
2) ⑵处应填( )。
3) ⑶处应填( )。
4) ⑷处应填( )。
5) ⑸处应填( )。