2021CSP-S(提高级)认证第一轮试题及详细解析
选择题
1.在Linux系统终端中，用于列出当前目录下所含的文件和子目录的命令为（）。
A.ls
B.cd
C.cp
D.all
【解析】Linux系统中：ls命令用于显示指定工作目录下之内容（列出目前工作目录所含之文件及子目录)；cd命令用于切换当前工作目录；cp命令主要用于复制文件或目录；all只是用来凑数的，没什么实际意义
故选A。
2.二进制数001010102和000101102的和为（）。
A.001111002
B.010000002
C.001111002
D.010000102
【解析】这是一个最基本的二进制加法，出现了连续的进位算出来是010000002
故选B。
3.在程序运行过程中，如果递归调用的层数过多，可能会由于（）引发错误。
A.系统分配的栈空间溢出
B.系统分配的队列空间溢出
C.系统分配的链表空间溢出
D.系统分配的堆空间溢出
【解析】递归需要使用到系统堆栈空间，如果递归层数过多，导致系统堆栈空间不足。
故选A。
4.以下排序方法中，（）是不稳定的。
A.插入排序
B.冒泡排序
C.堆排序
D.归并排序
【解析】待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj（即i<j）.若在排序后的序列中Ri仍然领先于Rj，则称所用的方法是稳定的。比如int数组[1,1,1,6,4]中a[0],a[1],a[2]的值相等，在排序时不改变其序列，则称所用的方法是稳定的
故选C。
5.以比较为基本运算，对于2n个数，同时到最大值和最小值，最坏情况下需要的最小的比较次数为（）。
A.4n−24n−2
B.3n+13n+1
C.3n−23n−2
D.2n+12n+1
【解析】比较可以分解成3步来进行：1.将2n个两两比较n次将数字分为两组：含有最大值的较大值一组与含有最小值的较小值一组；2.在较大值组中进行n-1次比较得出最大值
3.在较小值组中进行n-1次比较得出最小值，总共n+n-1+n-1=3n-2次故选C。
6.现有一个地址区间为00到1010的哈希表，对于出现冲突情况，会往后第一个空的地址存储（到1010冲突了就从00开始往后），现在要依次存储(0,1,2,3,4,5,6,7)，哈希函数为h(x)=x2mod11。请问7存储在哈希表哪个地址中（）。
A.5
B.6
C.7
D.8
【解析】每个都算一下。分别为0,1,4,9,5,3,3,5。重复的调整一下0,1,4,9,5,3,6,7。故选C。
7.G是一个非连通简单无向图（没有自环和重边），共有36条边，则该图至少有（）个点。
A.8
B.9
C.10
D.11
【解析】设有n个点，除了一个孤立点外剩下点为完全图。(n−1)(n−2)/2=36解得n=10故选C。
8.令根结点的高度为1，则一棵含有2021个结点的二叉树的高度至少为（）。
A.10
B.11
C.12
D.2021
【解析】当树为完全二叉树时的高度为最小，所以210≤2021<211
故选B。
9.前序遍历和中序遍历相同的二叉树为且仅为（）。
A.只有1个点的二叉树
B.根结点没有左子树的二叉树
C.非叶子结点只有左子树的二叉树
D.非叶子结点只有右子树的二叉树
【解析】前序遍历：先根再左子树后右子树，中序遍历：先左子树再根后右子树。所以去掉左子树时两个相同，选择D。
10.定义一种字符串操作为交换相邻两个字符。将DACFEB变为ABCDEF最少需要（）次上述操作。
A.7
B.8
C.9
D.6
【解析】AD CFEB->ACDFEB->ACDEFB->ACDEBF->ACDBEF->
ACBDEF->ABCDEF，共7次，故选A。
11.有如下递归代码
solve(t,n):
if t=1return1
else return5*solve(t-1,n)mod n
则solve(23,23)的结果为（）。
A.1
B.7
C.12
D.22
【解析】程序的运行结果为522mod23，根据用费马小定理，在p为素数的情况下，a p-1≡1（mod p），所以522≡1(mod23)，故选A。
12.斐波那契数列的定义为：F1=1,F2=1,F n=F n−1+F n−2(n≥3)。现在用如下程序来计算斐波那契数列的第n项，其时间复杂度为（）。
F(n):
if n<=2return1
else return F(n-1)+F(n-2)
A.O(n)cp复制文件到指定目录下
B.O(n2)
C.O(2n)
D.O(nlogn)
【解析】时间复杂度
f(n)=f(n-1)+f(n-2)每一层都包含一个加法操作
例如n=8时，T(n)=2^0+2^1+2^2+2^3+2^4+2^5+2^6=2^7-1 O(n)=2^7-1=2^n
故选C。

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