1222: csp初赛模拟5
题目描述
一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)
1.以下关于CSP-J/S的描述错误的是（）
A.参加CSP-S/J两组两轮认证均须在网上注册报名。未注册者，无认证成绩
B.CSP-J/S是中国计算机学会举办的程序设计竞赛
C.CSP-JS第二轮实行网上注册、报名，未通过网上报名的认证者可向所在省份特派员申请获得第二轮参加认证的资格
D.CSP-J/S认证成绩优异者，可参加NOI省级选拔，省级选拔成绩优异者可参加NOI
2.在8位二进制补码中，10110110表示的是十进制下的()
A.202 B.74 C.-202 D.-74
3.2019年10月14日是星期一，1978年10月14日是()
A.星期日 B.星期五 C.星期一 D.星期六
4.图G是一棵n节点的树，G上有（）条边
A.n B.2*n C.n-1 D.n+1
5.由五个不同的节点构成的树有（）种
A. 3125 B. 125 C.32 D.1024
6.有一个长为6的A序列：{3,20,4,6,1}，现通过进行交换其中相邻两个数字的操作进行排序，要将A序列排成从小到大的递增序列最少要进行多少次交换操作（）
A.5 B.6 C.7 D.15
7.某算法计算时间表示为递推关系式： T(N)=N+T(N/2) ,则该算法时间复杂度为( )。
A.O(N*N) B.O(NlogN) C.O(N) D.O(1)
8.一棵6节点二叉树的中序遍历为DBAGECF,先序遍历为ABDCEGF，后序遍历为（）
A. DGBEFAC B. GBEACFD C. DBGEFCA D. ABCDEFG
9.一张有9个节点的无向图最多有()条边
A.40 B.81 C.72 D.36
10.下列不属于面向对象程序设计语言的是( )
A.C++ B. C C.JAVA D.C#
11.G是一张有n个点m条边的连通图，必须删去（）条边才能将其变成一棵n节点的树
A.1 B.m-n-1 C.m+n-1 D.m-n+1
12.字符串”abcab”本质不同的子串个数（）,不考虑空串
A.15 B.14 C.13 D.12
13.十进制小数13.375对应的二进制数是()：
A.1101.011 B.1011.011 C.1101.101 D.1010.01
14.若某算法的计算时间表示为递推关系：
T(n) = 3T(n/4) + nlog2(n)
则该算法的复杂度为()
A．O(n) B.O(n*log2(n)) C.O(2n*log2(n)) D.O(3n*log2(n))
15. 一家三口人，恰好仅有两个人生日在同一天的概率是（） 【假设每年都是365天】
A．1/365 B.365/（364*365） C.（3*364）/（365*365） D.1/12
二、阅读程序写结果(共8小题，每小题5分，共计40分)
第一题
#include <bits/stdc++.h>using namespace std;
int a,b,c;
int main()
{
cin >> a >> b >> c;
int t = b;
b = a, a = t;
c = a;
cout << a << " " << b << " " << c ;
return 0;
}
16. 若输入3 9 1，则输出9 3 3
A.正确
B.错误
17. 若输入12300400000 3 7，将一定能输出3 12300400000 3
A.正确
B.错误
18.该程序中，头文件#include <bits/stdc++.h>可以改成#include<camth>
A.正确
B.错误
19.若输入3 6 9，输出()
A. 6 3 6
B. 9 3 3
C. 6 9 3
D. 6 3 3
20.若将c=a改成c=t,则若输入3 6 9，输出()
A. 6 3 6
B. 9 3 3
C. 6 9 3
D. 6 3 3
21.若将c=a改成c=b,则若输入3 6 9，输出()
A. 6 3 6
B. 6 3 9
C. 6 3 3
D. 3 6 3
第二题
#include <bits/stdc++.h>using namespace std;
int w[35000],d[35000],dp[35000];
int main()
{
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
cin >> w[i] >> d[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
}
}
cout << dp[m] << endl;
return 0;
}
22. 上述代码中，双重循环里循环变量j的枚举顺序改为从w[i]到m，输出结果一定不变
A.正确
B.错误
23. 上述代码中，双重循环中变量i的枚举顺序改为从n到1，输出结果一定不变
A.正确
B.错误
24. 当输入为：
4 6
1 4
2 6
3 12
2 7
输出为()
A.17
B.28
C.29
D.23
25.若输入数据中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=30000,则所求答案一定没有溢出()
A.正确
B.错误
26.若输入数据中，1<=n<=30000,1<=m<=30000,1<=w[i]<=30000,1<=d[i]<=1000000000,则所求答案一定没有溢出()
A.正确
B.错误
27.上述代码的时间复杂度为()
A.O(n)
B.O(n*n*m)
C.O(n*m)
D.O(n*m*m)
第三题
#include <bits/stdc++.h>
#include <iostream>
#define N 500+10
using namespace std;
int a[N], n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<n;i++)
{
int tmp=i;
for(int j = i+1;j <= n;j++)
if(a[j] < a[tmp])
tmp = j;
swap(a[i], a[tmp]);
}
for(int i=1;i<=n;i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
28. 上述代码实现了对一个长度为n的序列进行排序（）
A.正确
B.错误
29. 我们将上述算法称为（）
A. KMP
B. 冒泡排序
C. 选择排序
D. 归并排序
30.上述代码的时间复杂度为()
A. O(n) B. O(nlogn) C. O(n*n) D. O(n*n*n)
31.若输入数据为：
5
3 2 1 5 4
则if(a[j]<a[tmp])这句话中的条件会成立多少次（即后面的tmp=j会被执行多少次) </a[tmp])这句话中的条件会成立多少次（即后面的tmp=j会被执行多少次)()
A. 5 B. 7 C.3 D.4
32.去掉头文件#include<iostream>后程序仍能正常编译运行()
A.正确
B.错误
33.去掉using namespace std;后程序仍能正常编译运行()
A.正确
B.错误
34.上述程序___(1)___中应该填写（）
A.int u;
B.int st;
C.int &st;
D.int st
35.上述程序___(2)___中应该填写（）
A.hd<tl< span=""></tl<>
B.hd>tl
C.hd<=tl< span="">
D.hd>=tl
36.上述程序___(3)___中应该填写（）
A.vis[v]==true
B.dis[v]<=dis< span="">
C.dis[v]!=-1
D.dis[v]>dis
37. 上述程序___(4)___中应该填写（）
A.G[y].push_back(x)
B.G[y].insert(x)
C.G[y][x]=1
D.G[y].push(x)
38. 上述程序___5___中应该填写（）
A. int j=1;j<=n;j++< span="">
B. int i=1;i<=n;i++< span="">
C. int i=0;i<n;i++< span=""></n;i++<>
D. int i=1,i<=n,i++< span="">
2.(拓扑排序)给出一张n节点m条边的有向图，求出该图的一个拓扑排序，若无拓扑排序输出-1
输入：
第一行两个正整数 n,m 表示点数和边数。
接下来 m 行，每行三个正整数 x,y表示节点 x->y之间有一条边。
输出：
一个拓扑序：按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可。若无拓扑序，输出 -1.
#include <bits/stdc++.h>#define N 200020
using namespace std;
int n,m;
vectorG[N];
int q[N],hd,tl;
int du[N];
int ans[N],tot;
void topo()
{
hd=1,tl=0;
for(int i=1;i<=n;i++)if(___(1)____)q[++tl]=i;< span="">
while(hd<=tl)< span="">
{
int u=q[hd++];
ans[++tot]=u;
for(int i=0;____(2)____;i++)
{
int v=G[i];
du[v]--;
if(!du[v])____(3)____;
}
}
if(tot!=n)puts("-1");
else
{
for(int i=1;i<=n;i++)< span="">
printf("%d ",ans[i]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)< span="">
{
int x,y;
scanf("%d%d",&x,&y);
_____(4)___________;
_____(5)___________;
}
topo();
}
39. 上述程序___1___中应该填写（）
A. du[i]
B. q[i]
C. hd<=tl
D. !du[i]
40. 上述程序___2___中应该填写（）
A. i<=n
B. i<n
C. i<g.size()
D. i<=g.size()
41. 上述程序___3___中应该填写（）
A. q[++tl]=v
B. q[tl++]=v
C. q[++hd]=v
D. q[hd++]=v
42. 上述程序___4___中应该填写（）
A.G[y].push_back(x)
B.G[x].push_back(y)
C.G[x].push(y)
D.G[y].push(x)
43. 上述程序___5___中应该填写（）
A.G[y].push_back(x)
B.G[y].push(x)
C.du[y]++
D.du[x]++