2021-CSP-S(提高组)认证第一轮试题详细解析.docxVIP

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