CSP

CSP

一、单选题

1.【 单选 】2 分

在非空的双向链表中由q所指向的结点右边插入一个由p所指向的结点，其动作依次为：
p->left=q;
p->right=q->right;
q->right=p;()
A.q->left=p;
B.q->right->left=p;
C.p->right->left=p;
D.p->left->left=p;

2.【 单选 】2 分

长度为n的顺序表L，删除其中一个元素的时间复杂度为（）
A.O(1)
B.O(n)
C.O(n2)
D.O(logn)

3.【 单选 】2 分

现有八人排成一排照相，其中甲乙丙三人不能相邻的排法有（）种
A.A(6,3)*A(5,5)
B.A(8,8)-A(6,6)*A(3,3)
C.A(5,3)*A(3,3)
D.A(8,8)-A(6,4)

4.【 单选 】2 分

我们往一个数据结构内按先后顺序丢入数值5，7，9，3。等到所有数都丢进去之后，从该数据结构内按顺序取出数值，按先后顺序为3，5，7，9，请问可能是如下哪种数据结构？
A.队列
B.栈
C.小根堆
D.链表

5.【 单选 】2 分

一棵高度为10的二叉树，最多具有（）个节点。
A.512
B.511
C.255
D.1023

6.【 单选 】2 分

Internet中运输层适合可靠性要求高的通信协议是（）
A.UDP
B.IPC
C.TCP
D.FTP

7.【 单选 】2 分

设x是任意输入的数，阅读下面的递归算法：

void dfs(long long x){if(x>9) dfs(x/10);printf("%lld",x%10);
}

请问递归算法结束之后输出的是什么？（）
A.将x翻转后输出
B.将x除去个位以外的数输出
C.将x除去最高位以外的数输出
D.输出x

8.【 单选 】2 分

小于28的正整数中，与28互质的数的个数为（）
A.10
B.11
C.12
D.13

9.【 单选 】2 分

2021年7月1日是星期四，我们热烈庆贺了中国共产党成立一百周年，完成了两个一百年中的第一个。我们将在2049年10月1日欢庆建国一百年，这一天是星期几？（）
A.星期四
B.星期五
C.星期六
D.星期日

10.【 单选 】2 分

甲乙丙丁四个人被安排完成三份代码，每份代码至少需要一个人完成，且一个人只能去完成一份代码，甲乙有矛盾不能完成同一份代码，有多少种合理的安排方式？（）。
A.12
B.30
C.48
D.36

11.【 单选 】2 分

全国青少年信息学奥林匹克竞赛（NOI）创办于（）年。
A.1984
B.1986
C.1995
D.2010

12.【 单选 】2 分

10层的满二叉树有()个结点。（规定独根树层数为1）
A.512
B.1023
C.1024
D.2047

13.【 单选 】2 分

原码为11100110 的二进制数的补码为（）。
A.11100110
B.10011001
C.10011010
D.00011010

14.【 单选 】2 分

666 和996 的最大公约数是（）。
A.2
B.6
C.12
D.18

15.【 单选 】2 分

农场主和老婆每隔一年半就生一个孩子，他们一共生了15个孩子。最大的孩子的年龄是最小的孩子年龄的8倍。试求最大的孩子的年龄？
A.16
B.20
C.24
D.32

二、阅读程序

阅读程序，完成16~21题。

#include<iostream>
#include<string>
using namespace std;string s;
int n,a[110],cnt;
int main()
{cin>>s;n=s.size();for(int i=0;i<n;i++)a[i]=s[i]-'a';for(int i=0;i<n;i++)for(int j=0;j<n-1;j++)if(a[j]<a[j+1])swap(a[j],a[j+1]),++cnt;cout<<cnt;return 0;
}

16.【 判断 】1.5分

如果s包含除了小写字母以外的字符或长度过长，程序可能不能正常运行。______

17.【 判断 】1.5分

最终a数组一定是有序的。______

18.【 判断 】1.5分

输出可能是4950。______

19.【 单选 】3分

若a数组是12 5 3 6，则s是______ 。
A.mfdg
B.lecf
C.ngeh
D.kdbe

20.【 单选 】3分

当n=4，输出的最大值是______ 。
A.3
B.4
C.6
D.8

21.【 单选 】4分

若a数组是12 5 3 6 7 9 0 9 8，则输出是______ 。
A.13
B.19
C.24
D.33
阅读程序，完成22~27题。

#include<algorithm>
#include<iostream>
using namespace std;
int a[10005]={0},n,k,i;
int main(){cin>>n>>k;for(i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);for(i=1;i<=k&&i<=n;i++){if(a[i]=a[i+1])k++;}if(i>n)cout<<"NO RESULT";elsecout<<a[i-1];return 0;
}

22.【 判断 】1分

当n<k 时，输出结果一定是"NO RESULT"。 _______

23.【 判断 】1分

当输入n>1，k=1 时，输出结果不可能是"NO RESULT"。_______

24.【 判断 】1分

若输入n=k ，输出结果一定是"NO RESULT"。_______

25.【 判断 】2分

若将第12行的"i>n" 改成"i>n+1" ，程序运行结果一定不会变。_______

26.【 单选 】3分

若输入"6 3 1 1 4 5 1 4" ，输出结果为_______ 。
A. 1
B. 4
C. 5
D. NO RESULT

27.【 单选 】3分

若输入"4 3 1 2 3 4" ，输出结果为_______ 。
A. 2
B. 3
C. 4
D. NO RESULT
阅读程序，完成28~33题。

#include<iostream>
using namespace std;const int N=1e4+5;int n,A[N],B[N]C[2*N];int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>A[i];for(int i=1;i<=n;i++)cin>>B[i];for(int i=1,j=1,k=1;i<=n||j<=n;k++)if(i<=n&&A[i]<=B[j])C[k]=A[i++];elseC[k]=B[j++];for(int i=1;i<2*n;i++)cout<<C[i]<<" ";return 0;
}

假设输入的n是小于N的正整数，数列A、B中的数字均是int范围内的整数。

28.【 判断 】1.5分

将第16行的i<=n&&删去会影响输出的结果_____

29.【 判断 】1.5分

将第17行的i++改为++i，同时将第19行的j++改为++j，不会影响输出的结果_____

30.【 判断 】1.5分

若将第15行的||改为&&，一定有C[2*n]==0_____

31.【 单选 】3分

若数列A是1 5 7 8，数列B是2 3 6 9，则输出的数列C是_____
A.1 5 7 8 2 3 6 9
B.1 2 3 5 6 7 8 9
C.1 5 2 3 6 7 9 8
D.1 3 2 5 6 7 8 9

32.【 单选 】3分

若给定的数列A、B严格递增，对于最后得到的数列C，满足对任意正整数i(1<=i<2n)_____
A.C[i]<C[i+1]
B.C[i]>C[i+1]
C.C[i]<=C[i+1]
D.C[i]>=C[i+1]

33.【 单选 】4分

对于以下需求，这份代码可以满足的是_____
A.给定两个递增数列A、B，输出A、B混合后的数列从小到大排序的结果
B.给定两个递增数列A、B，输出A、B混合后的数列从大到小排序的结果
C.给定两个递减数列A、B，输出A、B混合后的数列从小到大排序的结果
D.给定两个递减数列A、B，输出A、B混合后的数列从大到小排序的结果

三、完善程序

菲披拉契数列为1,1,2,3,5,8,13,21,…，其元素产生的规则是前两个数为1，从第三个数开始每个数等于它前面两个数之和。已知任意一个正整数可以表示为若干个互不相同的非波拉契数之和。例如：36=21+13+2。
下面的程序是由键盘输入一个正整数n，输出组成n的互不相同的菲波拉契数。试补全代码。
算法说明：
(1）寻找小于等于n的最大菲波拉契数a，并以a作为组成n的一个数。
(2）若n≠a，则以n-a作为n的新值，重复步骤（1)。若a=n，则结束。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
bool first;
int find(int n)
{int a,b,c;a=1;b=1;do{c=a+b;(___①___)}while(b<n);if(___②___)return b;else(___③___);
}
void p(int n)
{int a;a=find(n);if(first){printf("%4d",a);first=false;}else(__④____);if(a<n)(___⑤__);
}
int main()
{cin>>n;first=true;printf("%5d=",n);p(n);cout<<endl;return 0;
}

34.【 单选 】3分

①处应填：
A.a=c;b=a
B.a=b;b=c
C.a== c;b== a
D.a== b;b== c

35.【 单选 】3分

②处应填：
A.b== n
B.b<n
C.a== n
D.a<n

36.【 单选 】3分

③处应填：
A. return c
B. return b
C. return a+b
D. return a

37.【 单选 】3分

④处应填：
A. printf(“%4d”,a)
B. printf(“+%4d”,a)
C. printf(“%4d”,b)
D. printf(“+%4d”,b)

38.【 单选 】3分

⑤处应填：
A. p(a)
B. p(b)
C. p(n-a)
D. p(n-b)
（排列数）输入两个正整数n，m（1<n<20,1<m<n），在1~n中任取m个数，按字典序从小到大输出所有这样的排列。试补全代码。
例如：
输入：
3 2
输出：
1 2
1 3
2 1
2 3
3 1
3 2

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE=25;
bool used[SIZE];
int data[SIZE];
int n,m,i,j,k;
bool flag;
int main() 
{cin>>n>>m;memset(used,false,sizeof(used));for(i=1; i<=m; i++) {data[i]=i;used[i]=true;}flag=true;while(flag){for(i=1; i<=m-1; i++)cout<<data[i]<<" ";cout<<data[m]<<endl;flag=[ ① ];for(i=m; i>=1; i--) {[ ② ];for(j=data[i]+1; j<=n; j++)if(!used[j]) {used[j]=true;data[i]=[ ③ ];flag=true;break;}if(flag) {for(k=i+1; k<=m; k++)for(j=1; j<=[ ④ ]; j++)if(!used[j]) {data[k]=j;used[j]=true;break;}[ ⑤ ];}}}return 0;
}

39.【 单选 】3分

①处应填：
A. false
B. true
C. 1
D. -1

40.【 单选 】3分

②处应填：
A. used[i]=true
B. data[i]=i
C. used[data[i]]=true
D. used[data[i]]=false

41.【 单选 】3分

③处应填：
A. j
B. i
C. true
D. false

42.【 单选 】3分

④处应填：
A. n
B. m
C. i
D. j

43.【 单选 】3分

⑤处应填：
A.return 0
B.exit
C.continue
D.break