2022CCF非专业级别软件能力认证第一轮
（CSP-S1）提高级C++语言试题
认证时间：2022年9月18日14:30~16:30
考生注意事项：
●试题纸共有13页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的
一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.在Linux系统终端中，用于切换工作目录的命令为（）。
A.ls
B.cd
C.cp
D.all
2.你同时用time命令和秒表为某个程序在单核CPU的运行计时。假如time命令的输出如下：
real0m30.721s
user0m24.579s
sys0m6.123s
以下最接近秒表计时的时长为（）。
A.30s
B.24s
C.18s
D.6s
3.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次
退栈操作，则不可能得到的出栈序列是（）。
A.dcebfa
B.cbdaef
C.bcaefd
D.afedcb
4.考虑对n个数进行排序，以下最坏时间复杂度低于O(n2)的排序方法是（）。
A.插入排序
B.冒泡排序
C.归并排序
D.快速排序
5.假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排
序算法结束后，可能出现的最坏情况是（）。
A.移除受影响的数据后，最终序列是有序序列
B.移除受影响的数据后，最终序列是前后两个有序的子序列
C.移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
D.移除受影响的数据后，最终序列基本无序
6.计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储
地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下C++代码段表示的程序，将分别输出什么结果？（）
unsigned x=0xDEADBEEF;
unsigned char*p=(unsigned char*)&x;
printf("%X",*p);
A.EF、EF
B.EF、DE
C.DE、EF
D.DE、DE
7.一个深度为5（根结点深度为1）的完全3叉树，按前序遍历的顺序给结点从1开始编号，
则第100号结点的父结点是第（）号。
A.95
B.96
C.97
D.98
8.强连通图的性质不包括（）：
A.每个顶点的度数至少为1
B.任意两个顶点之间都有边相连
C.任意两个顶点之间都有路径相连
D.每个顶点至少都连有一条边
9.每个顶点度数均为2的无向图称为“2正规图”。由编号为从1到n的顶点构成的所有2正
规图，其中包含欧拉回路的不同2正规图的数量为（）。
A.n!
B.(n-1)!
C.n!/2
D.(n-1)!/2
10.共有8人选修了程序设计课程，期末大作业要求由2人组成的团队完成。假设不区分每个
团队内2人的角和作用，请问共有多少种可能的组队方案。（）
A.28
B.32
C.56
D.64
11.小明希望选到形如“省A·ℒℒB”的车牌号。车牌号在“·”之前的内容固定不变；
后面的5位号码中，前2位必须是大写英文字母，后3位必须是阿拉伯数字（ℒ代表A至Z，表示0至9，两个ℒ和三个之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。（）
A.20280
B.52000
C.676000
D.1757600
12.给定地址区间为0~9的哈希表，哈希函数为h(x)=x%10，采用线性探查的冲突解决
策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址9冲突了则从地址0重新开始探查）。哈希表初始为空表，依次存储(71,23,73,99,44,79,89)后，请问89存储在哈希表哪个地址中。（）
A.9
B.0
C.1
D.2
13.对于给定的n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。
int i,j,k=0;
for(i=0;i<n;i++){
for(j=0;j<n;j*=2){
k=k+n/2;
}
}
A.O(n)
B.O(n log n)
C.O(n n)
D.O(n2)
14.以比较为基本运算，在n个数的数组中最大的数，在最坏情况下至少要做（）次运算。
A.n/2
B.n-1
C.n
D.n+1
15.ack函数在输入参数“(2,2)”时的返回值为（）。
unsigned ack(unsigned m,unsigned n){
if(m==0)return n+1;
if(n==0)return ack(m-1,1);
return ack(m-1,ack(m,n-1));
}
A.5
B.7
C.9欧拉linux系统
D.13
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分，共计40分）
(1)
01#include<iostream>
02#include<string>
03#include<vector>
04
05using namespace std;
06
07int f(const string&s,const string&t)
08{
09int n=s.length(),m=t.length();
10
11vector<int>shift(128,m+1);
12
13int i,j;
14
15for(j=0;j<m;j++)
16shift[t[j]]=m-j;
17
18for(i=0;i<=n-m;i+=shift[s[i+m]]){
19j=0;
20while(j<m&&s[i+j]==t[j])j++;
21if(j==m)return i;
22}
23
24return-1;
25}
26
27int main()
28{
29string a,b;
30cin>>a>>b;
31cout<<f(a,b)<<endl;
32return0;
33}
假设输入字符串由ASCII可见字符组成，完成下面的判断题和单选题：
●判断题
16.（1分）当输入为“abcde fg”时，输出为-1。（）
17.当输入为“abbababbbab abab”时，输出为4。（）
18.当输入为“GoodLuckCsp202222”时，第20行的“j++”语句执行次数为2。（）
●单选题
19.该算法最坏情况下的时间复杂度为（）。
A.+
B.o log)
C.log
D.B
20.f(a,b)与下列（）语句的功能最类似。
A.  a.find(b)
B.  a.rfind(b)
C.  a.substr(b)
D.  apare(b)
21.当输入为“baaabaaabaaabaaaa aaaa”，第20行的“j++”语句执行次数为（）。
A.9
B.10
C.11
D.12
(2)
01#include<iostream>
02
03using namespace std;
04
05const int MAXN=105;
06
07int n,m,k,val[MAXN];
08int temp[MAXN],cnt[MAXN];

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。