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

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

1. 下列选项中最大的数是( )。

  • A.(504)10
  • B.(11111000)2
  • C.(770)8
  • D.(1FA)16

2. 主机IP地址为194.32.6.22,掩码为255.255.255.192,子网地址是( )。

  • A.194.32.6.22
  • B.194.32.0.0
  • C.0.0.0.22
  • D.194.32.6.0

3. 现代普通计算机的网关不能设置为( )。

  • A.10.16.13.100
  • B.127.0.0.1
  • C.234.123.6.5
  • D.168.10.7.100

4. 2021个点的二叉树的叶子个数最大是( )

  • A.1010
  • B.1
  • C.2020
  • D.1011

5. 深度优先搜索时,一定需要用到的数据结构是( )。

  • A.栈
  • B.二叉树
  • C.链式前向星
  • D.队列

6. 2023的2023次方对5取模的结果为( ).

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

7. 众所周知,希尔排序的复杂度与增量序列有着很密切的联系,下列增量序列中,( )在确保正确的前提下会使希尔排序的最坏时间复杂度最好。

  • A.{1,2,4,8,...}
  • B.{5,19,41,109,...}
  • C.{1,3,7,...,2^k-1}
  • D.{1,2,3,4,5,...}

8. NP问题的讨论是计算机科学中一个重要的话题。以下问题中,( )在一般情况下仍有着关于输入规模n的多项式复杂度的确定性正确算法。

  • A.0-1背包问题,n为物品个数
  • B.数字的质因数分解,n为数字位数
  • C.旅行商问题,n为点的个数
  • D.求矩阵行列式,n为矩阵的行数

9. 表达式3*(1-2)+4的后缀形式为( )。

  • A.3 1 2 - * 4 +
  • B.3 1 - 2 * 4 +
  • C.+ * 3 - 1 2 4
  • D.3 1 * 2 - 4 +

10. 只采用路径压缩的并查集最坏平均复杂度为( )。

  • A.O(n)
  • B.O(na(n))
  • C.O(n log n)
  • D.O(n^2)

11. 有以下程序段: const int N=1000, M = 10000; int h[N], tot, n, m;struct edge(double c; int nxt, v;} e[M << 1]; double d[N];其占用的静态空间大小约为( )。

  • A.30000Bytes
  • B.324KB
  • C.3200KB
  • D.3MB

12. 下列表达式中,不论变量p,q如何取值,恒为真的只有( )。 (1) ((!p)&&q)||(p&&q) (2) ((!p)&&q)&&(p||q) (3) (!p)||q)&&(p||q))||p||(!q) (4) (p&&(!q)&.&)||(((!p)||q)&&(p||q))

  • A.(3)(4)
  • B.(1)(3)
  • C.(2)(4)
  • D.(3)

13. 定义一个数是“好的”:当且仅当这个数是个六位数(允许有前导零),并且里面含有数字9。“好的”数的个数是( )。

  • A.1000000
  • B.531441
  • C.468559
  • D.99999

14. 现在有20个人约定一起玩一局游戏。但是因为可能要补作业,所以每个人有50%的概率最终参加。他们认为一局游戏的有趣程度为参加人数的平方,则游戏有趣程度的期望为( )。

  • A.425/4
  • B.105
  • C.110
  • D.100

15. 以下( )是 C++之父?

  • A.本贾尼.斯特劳斯特卢普(Bjarne Stroustrup)
  • B.图灵(Alan Turing)
  • C.吉多.范罗苏姆(Guido van Rosum)
  • D.姚期智

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

1.

# include<algorithm>
# include<iostream>
using namespace std ;
const int MAXN = 1000;
int a[MAXN], c[MAXN];

int main() {
int n, x, y;
cin>> n>> x>> y;
int sum=(x^y)+((x&y)<<1);
n=n<<3^5&3|2;
for(int i=1; i<=n; ++i)
cin >> a[i];
int answer;
answer = c[1] = max(a[1], 0);
for (int i= 2; i<= n; ++i) {
c[i] = max(c[i-1] + a[i],a[i]);
if (c[i]<= 0)
c[i] = 0;
answer = max(answer, c[i]);
}
if (answer <= sum)
puts("Good.");
else
puts("It's too sad.");
return 0 ;
}

判断题

1) sum=x+y ( )
2) 将程序18,19行删去后输出结果不变。( )
3) 14行answer没赋初值可能会导致答案错误。( )
4) 输入的n应小于等于125,否则会运行时错误。( )


选择题

5) 若输入的n = 15,则程序12行以后的n的值为( )
6) 若12行时n=11,且输入 a 数组元索依次是:5,12,-7,-11,-9,4,9,5,-6,11,-1,则程序运行到22行时answer是( )。

2.

# include <cmath>
# include <cstring>
# include <iostream>

const int MAXN =1000000;
int n;
int f1[MAXN], f2[MAXN],f3[MAXN];

int calc_f1(int x) {
int ans=1;
int maxNum = sqrt(x);
for (int i= 2; i<= maxNum; ++i)
if(x%i==0) {
ans=-ans;
x/=i;
if (x%i== 0)
return 0;
}
if(x!=1)
ans =-ans;
return ans;
}

int calc_f2(int x) {
return x;
}

void convolute( ) {
memset(f3, 0, sizeof(f3));
for (int i = 1; i<= n; ++i)
for (int j= 1; j<= n/i; ++j)
if(i*j<=n)
f3[i*j]= f3[i* i]+ f1[i]*f2[j];
}
int main() {
scanf("%d", &n);
for (int i= 1; i<= n; ++i)
f1[i] = calc_f1(i);
for (int i= 1; i<= n; ++i)
f2[i] - calc_f2(i);
convolute();
printf("% d\backslashn", f3[n]);
return 0;
}

判断题

1) 若将程序第31行的 n/i 改为n后运行,且已知程序可以安全地运行至第36行而不发生任何未定义行为,则程序依旧可以正常输出正确的答案。( )
2) 去掉程序第3行,程序依然可以正常编译。()


选择题

3) 该程序中,第30~33行运行的时间复杂度为( )。
4) 若输入3,程序的输出为( )。
5) 若输入1003,程序的输出为( )。
6) 若输入1000000,程序输出为( )。


注:本题中你只需要考虑数组越界这一种未定义行为。

3.

#include <iostream>
using namespace std;

const int maxn =10000000;
int n,size ;
int prime[maxn+5];
bool vis[maxn+5];

int main() {
cin >>n;
size = 0;
for (int i= 2; i<=n; ++i) {
if (!vis[i]) {
size = size + 1;
prime[size]= i;
}
for (int j=1; i*prime[j]<=n; ++j) {
vis[i * prime[j]]= 1;
if (i % prime[j]==0)
break ;
}
}
int sum = 0;
for (int i=1; i<=size; ++i)
sum=sum + prime[i];
cout<<sum<<endl;
return 0;
}

判断题

1) n必须小于等于10000004,否则程序可能会运行时错误。
2) 输出可能为1。( )
3) 若输入为1000000,那么程序会输出小于等于1000000的质数之和。( )
4) 该程序的输出含又是小于等于n的所有质数之和。()


选择题

5) 若输入n为40,那么输出为( )。
6) (2.5分)若输出的答案在500000~500000之间,那么n的量级约为( )。
7) (2.5分)该程序的复杂度为( )

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

1. 1.(背包问题1)有一个质量上限为m的背包和n个物品。物品分三类,第一类物品有取的数量限制,第二类物品只能取一个,第三类物品可以无限取。
第i个物品的类别为tp[i](tp[i]∈[1,2,3])质量为w[i],价值为c[i],如果tp[i]=1 ,还会有一个a[0]表示这种物品最多只能取a[i]个。求这个背包可以装下的最大价值。
M≤1000,n ≤100,w[i],c[i]≤1000,a[i]<10,1≤tp[i]≤3。

试补全程序。

# include <iostream>
using namespace std;
int n, m, ans;
int f[100],a[101],tp[101],w[101],c[101];

int main() {
cin>>m>>n;
for(int i= 1; i<=n; ++i) {
cin>> tp[i]>> w[i]>> c[i];
if(tp[i] == 1) cin>> a[i];
}
f[0]= 0;
for (int i= 1; i<= m; ++i)
f[i]=___(1)___;
for(int i= 1; i<=n; ++i) {
if(tp[i]==1) {
for (int j= 1; j<= a[i]; ++j)
for(int v= m; v>=w[i]; --v)
f[v] = max(f[v], ___(5)___ );
}
else if(tp[i]== ___(2)___) {
for(int v=m; v>= ___(3)___ ; --v)
f[v]=max(f[v], ___(5)___ );
}
else {
for( ___(4)___ )
f[v]=max(f[v], ___(5)___ ) ;
}
}
printf("%d", f[m]);
return 0;
}


选择题

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

2. (背包问题2)有N(O<N≤50)个物品,第i个物品体积为v[i](0≤v[i]≤10^18),价值为w[i](0≤w[i]≤10^17)。现有一个容量为V(0≤V≤10^18)的背包。你需要选择一些物品使
得体积之和不超过V且价值最大。求出最大价值及方案。如有多种方案,尽可能选择编号较大的方案(即尽量选第n个,仍有多组解选第n-1个,以此类推)。
提示:将物品按标号是否大于n/2分成两组,每组内枚举如何选择。再在两组间确定方案。
试补全程序。

#include <iostream>
using namespace std;

const long long inf=___(1)___;
long long v[41];
long long w[41];
struct Item {
long long value, weight, choose;
} itm[2][1<<20];

bool cmp1(Item a, Item b) {
return a.value < b.value||(a.value == b.value && a.choose < b.choose);
}
bool cmp2(Item a, Item b) {
return a.value < b.value||(a. value == b.value && a.choose==b.choose);
}
int get_id(int n) {
for(int i=0; ; ++i)
if(!(n>>i)) return i-1;
}

void sort(Item item[], int L, int R) {
if(L>= R) return;
int x=rand()%(R-L+1)+L;
swap(item[L], item[x]);
int a=L+1,b= R;
while (a<b) {
while (a<b&& cmp1(item[a], item[L]))
++a;
while(a< b&& ___(2)___)
--b;
swap(item[a],item[b]);
}
while (b<= R&& item[b].value == item[L].value)
++b;
if (item[a].value < item[L].value)
swap(item[a],item[L]);
sort(item, L, a-1);
sort(item, b, R);
}

int solve(int L, int R, Item item[]) {

item[0].value=0;
item[0].choose = 0;
int len = ___(3)___;
for (int i=1; i <= len; ++i) {
int tmp= ___(4)___;
item[i].value = item[i - tmp].value + v[L + get_id(tmp)];
item[i].weight = item[i - tmp].weight + w[L + get_id(tmp)];
if (item[i].value > inf) item[i].value = inf;
item[i].choose = i;
}
sort(item, 0, len);
return len;
}

int main() {
int N;
long long V, ans = 0;
cin>>N>>V;
for (int i = 1; i<= N; ++i)
cin>> v[i] >> w[i];
int len1 = solve(1,N/2, itm[0]);
int len2 = solve(N/2 + 1, N, itm[1]);
for (int i= 1; i<= len2; ++i)
itm[1][i].value=max(itm[1][i].value, itm[1][i-1].value);
long long choose = 0;
for (int i= 0; i<= len1; ++i) {
while (len2 >= 0 && itm[0][i].value + itm[1][len2].value>V)
--len2;
if(len2>=0) {
long long new_value = itm[0][i].weight + itm[1][len2].weight;
long long new_choose = ___(5)___ ;
if (ans == new_value)
choose = max( choose, new_choose);
if (ans < new_value) {
ans = new_value ;
choose = new_choose ;
}
}
}
cout<<ans<<endl;
for (int i= 0; i< N; i++)
if (choose & (1LL<<i))
cout<<i+1<<' ';
cout << endl;
}


选择题

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