2020CSP-J2
一、 单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1. 设栈S的初始状态为空，现有5个元素组成的序列{1,2,3,4,5}，对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不在进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是（ ）
A. {5,4,3,2,1} B. {2,1} C. {2,3} D. {3,4}2. 设循环队列数组中的下标范围是n，其中头尾指针分别是f和r，则其元素个数是（ ）
A. r-f B. r-f+1 C. (r-f) MOD n+1 D. (r-f+n) MOD n3. 电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知：电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（ ）
A. 奇数 B. 偶数 C. 可奇可偶 D. 数据固定4. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为（ ）
A. 插入排序 B. 归并排序 C. 选择排序 D. 快速排序5. 对于一个满二叉树，m个树叶，l个分枝节点，n个节点，则（ ）
A. n=l+m B. l+m=2n C. m=l-1 D. n=2l-16. 已知元素（8,25,14,87,51,90,6,19,20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面，90在87的后面，20在14的后面，25在6的前面，19在90的后面。（ ）
A. 20,6,8,51,90,25,14,19,87
B. 51,6,19,20,14,8,87,90,25
C. 19,20,90,8,6,25,51,14,87
D. 6,25,51,8,20,19,90,87,147. 假设我们用d=(a1,a2,…,a5)，表示无向图G的5个顶点的度数，下面给出的哪组d值合理（ ）
A. {2,2,2,2,2}
B. {1,2,2,1,1}
C. {3,3,3,2,2}
D. {5,4,3,2,1}8． 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（ ）次操作，才能完成冒泡排序。
A．0 B．5 C．10 D．15
9． 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。
A．电子管 B．晶体管 C．集成电路 D．超大规模集成电路10．（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。
A．动态规划 B．贪心 C．分治 D．搜索11．地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（ ）。
A．128KB B．1MB C．1GB D．4GB12．原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（ ）个不同的非空子串。
A．3 B．12 C．36 D．4513．十六进制数9A在（ ）进制下是232。
A．四 B．八 C．十 D．十二14．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ ）。
A．ABC B．CBA C．ACB D．BAC15． 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
A．系统分配的栈空间溢出 B．系统分配的堆空间溢出
C．系统分配的队列空间溢出 D．系统分配的链表空间溢出二、 阅读程序（程序输入不超过数组或字符串定义的范围，判断题正确填T，错误填F；除特殊说明外，判断题1.5分，选择题4分，共计40分）
1)
1. #include <iostream>
2. #include <cmath>
3. using namespace std;
4.
5. bool IsPrime(int num)
6. {
7. for (int i=2;i<=sqrt(num);i++)
8. {
9. if (num%i==0)
10. {
11. return false;
12. }
13. }
14. return true;
15. }
16. int main()
17. {
18. int num=0;
19. cin>>num;
20. if (IsPrime(num))
21. {
22. cout<<"YES"<<endl;
23. }
24. else
25. {
26. cout<<"NO"<<endl;
27. }
28. return 0;
29. }16.（1分）输入97时，输出为“YES”（不含引号）
17.（1分）输入119时，输出为“NO”（不含引号）
18. 若将第7行的“<=” 改成“<”，程序输出的结果一定不会改变。
19. 当程序执行第14行时，i的值为sqrt(num) 选择题
20.（3分）最坏情况下，此程序的时间复杂度是（ ）
A. $O(num)$ B. $O(num^2)$ C. $O(\sqrt{num})$ D. $O(\log num)$
21. 若输入的num为20以内的正整数，则输出为“YES”的概率是（ ）
A. 0.45 B. 0.4 C. 0.5 D. 0.352)
1. #include<bits/stdc++.h>
2. using namespace std;
3. const int mod=2048;
4. long long c,n;
5. long long kasumi(long long x,long long mi){
6. long long res=1;
7. while(mi){
8. if (mi&1){
9. res=(res*x)%mod;
10. }
11. x=(x*x)%mod;
12. mi>>=1;
13. }
14. return res;
15. }
16. int main(){
17. cin>>n>>c;
18. if(n==3){
19. printf("%lld",c*(c-1));
20. return 0;
21. }
22. long long ans=((kasumi(c-1,n)+(c-1)*kasumi(-1,n))%mod+mod)%mod;
23. cout<<ans;
24. return 0;
25. }判断题
22.（1分）将第9行和第11行的括号去掉，程序输出结果一定不变。
23.（1分）将第12行的“mi>>=1”改为“mi*=0.5”，程序的输出结果一定不变。
24. 若输入为“4 4”,则输出为“78”。
25. 此程序的时间复杂度为 $O(\log n)$。 选择题：
26. 如输入为“3 4”，则输出为（ ）
A. 24 B. 12 C. 18 D. 19
27. kasumi(2046,13)的返回值为（ ）
A. 0 B. 2022 C. 2 D. 20243）
1. #include<cstdio>
2. int n,r,num[10000];
3. bool mark[10000];
4. void print()
5. {
6. for(int i=1;i<=r;i++)
7. printf("%d ",num[i]);
8. printf("\n");
9. }
10. void search(int x)
11. {
12. for(int i=1;i<=n;i++)
13. if(!mark[i])
14. {
15. num[x]=i;
16. mark[i]=true;
17. if(x==r) print();
18. search(x+1);
19. mark[i]=false;
20. }
21. }
22. int main()
23. {
24. scanf("%d%d",&n,&r);
25. search(1);
26. } 判断题
28.（1分）程序结束时，对于任意1<=i<=n，mark[i]=0.
29.（2分）若n<r，则程序无输出。
30.（2分）若输入为”4 3”，则输出中数字1和2的个数不同
31.（2分）此程序的时间复杂度为O(n) 选择题
32. 若输入为“6 3”，则函数print的执行次数为（ ）
A. 60 B. 120 C. 6 D. 720
33. 若输入为“7 4”，则输出的最后一行为（ ）
A. 4 5 6 7 B. 7 6 5 4 C. 4 3 2 1 D. 1 2 3 4三、 完善程序（单选题，每小题3分，共计30分）
1). 克鲁斯卡尔求最小生成树思想：首先将n个点看做n个独立的集合，将所有边快排（从小到大）。然后，按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于一个集合。若是，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若否，则跳过。直到找到n-1条边为止。
1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. struct point{
5. int x;
6. int y;
7. int v;
8. };
9. point a[10000];
10.
11. int cmp(const point &a,const point &b){
12. if ( ① ) return 1;
13. else return 0;
14. }
15.
16. int fat[101];
17. int father(int x){
18. if (fat[x]!=x) return fat[x]=( ② );
19. else return fat[x];
20. }
21.
22. void unionn(int x,int y){
23. int fa=father(x);
24. int fb=father(y);
25. if (fa!=fb) fat[fa]=fb;
26. }
27.
28. int main(){
29. int i,j,n,m,k=0,ans=0,cnt=0;
30. cin>>n;
31. for(i=1;i<=n;i++)
32. for(j=1;j<=n;j++)
33. {
34. cin>>m;
35. if (m!=0){
36. k++;
37. a[k].x=i;
38. a[k].y=j;
39. a[k].v=m;
40. }
41. }
42. sort(a+1,a+1+k,③);
43.
44. for (i=1;i<=n;i++){
45. fat[i]=i;
46. }
47.
48. for(i=1;i<=k;i++){
49. if (father(a[i].x)!= ④ ){
50. ans+=a[i].v;
51. unionn(a[i].x,a[i].y);
52. cnt++;
53. }
54. if ( ⑤ ) break;
55. }
56.
57. cout<<ans;
58. return 0;
59.
60. }
34. ①处应填（ ）
A. a.v < b.v
B. a.v > b.v
C. a.v >= b.v
D. a.v <= b.v
35. ②处应填（ ）
A. father(x)
B. father(fat[x])
C. fat[father(x)]
D. x
36. ③处应填（ ）
A. algorithm
B. point
C. cmp
D. sizeof(a)
37. ④处应填（ ）
A. a[i].y
B. father(a[i].y)
C. fat[a[i].y]
D. a[i].x
38. ⑤处应填（ ）
A. cnt > 0
B. i == 1
C. ans == n-1
D. cnt == n-11). 欧拉回路问题由七桥问题而来，其基本问题是是否能够一次性不重复地走遍这七座桥，转换为数学问题中的图论就是指的是从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边，算法代码如下:
1. #include<iostream>
2. #include<ctime>
3. using namespace std;
4. int G[5][5];
5. int visted[5][5];
6. int n=5;
7. void euler(int u){
8. for (int v=0;v<n;v++){
9. int (G[u][v] && ① ){
10. cout<<u<<"->"<<v<<endl;
11. visited[u][v]=visted[v][u]= ② ;
12. ③
13. }
14. }
15. }
16. int main(){
17. G[1][2]=G[2][1]=G[1][3]= ④ =1;
18. G[2][4]=G[4][2]=G[3][4]= ⑤ =1;
19. euler(1);
20. return 0;
21. }39. ①处应填（ ）
A. G[v][u]
B. !visited[u][v]
C. visited[u][v]
D. Visited[v][u]
40. ②处应填（ ）
A. 1
B. 0
C. u
D. v
41. ③处应填（ ）
A. euler(v);
B. euler(u);
C. G[u][v]=0;
D. G[v][u]=0;
42. ④处应填（ ）
A. G[0][1]
B. G[1][0]
C. G[3][1]
D. G[0][3]
43. ⑤处应填（ ）
A. G[0][2]
B. G[2][0]
C. G[2][1]
D. G[4][3]
要答案的私聊我^_^