CSP-S 2021 初赛解析

解析

1.选A，ls列出目录，cd是定位目录，cp是复制问卷,all只有作为命令的参数使用

2.选B，

3.选A，递归函数的参数和局部变量存储在系统栈，如果层数过多，栈就会溢出。

解析

4.选C，排序稳不稳定看相等值得元素排序后得相对位置有没有变化，因此元素之间得比较只要是相邻的，排序就是稳定的，而堆排序元素的比较跨度很大。

5.选C

• a1与a2比，消耗比较次数1次，不妨令a1>=a2
• 剩下的2n-2个数，两两比较，消耗次数n-1次，产生n-1个更大的数，n-1个更小的数
• a1与剩下的n-1个更大的数依次比较，消耗次数n-1次
• a2与剩下的n-1个更小的数依次比较，消耗次数n-1次
• 总的消耗次数\(S=1+(n-1)+(n-1)+(n-1)=3n-2\)

6.选C

初始哈希表如下：

\(h[0]=0,h[1]=1,h[2]=4,h[3]=9,h[4]=5,h[5]=3\)，哈希表如下：

\(h[6]==3——>h[6]=4-->h[6]=5-->h[6]==6\)，哈希表如下：

\(h[7]=5-->h[7]=6-->h[7]=7\)

7.选C

解析

8.选B

令二叉树的高度位h,题意求最少的高度，要满足趋于满二叉树的状态；满二叉树的情况下其结点个数\(n=2^h-1\), 选项A，\(2^{10}-1=1023\)，排除，选项B，\(2^{11}-1=2047\),只需最后一层减掉26个节点就可以满足.

9.选D

如果树上某个结点A存在左子树B和右子树C，那么在前序遍历的顺序是A-B-C,中序遍历则是B-A-C，显然，把B去掉两个序列相同。

10.选A

解析

11.选A

\(solve(23,23)\) <-- \(5*solve(22,23)\bmod n\) <-- \(5^{2}*solve(21,23)\bmod n\) <-- ... \(5^{22}*solve(1,23) \bmod n\)
根据费马小定理：
\(a^p \bmod p=a \bmod p\) (p为质数)
\(a^{p-1} \bmod p=1 \bmod p=1\) (p为质数)
\(5^{22} \bmod 23=1 \bmod 23=1\)

12.选C

\(T(n)=T(n−1)+T(n−2)\) ，所以复杂度是 \(O(Fn)\) 。
或者说是 \(2^n\) ，因为每一项都是 \(Fn=Fn−1+Fn−2\) 。

13.选C

• 挑1个：\(C_8^1=8\)
• 挑2个：\(C_7^2=21\)(插空法，拿掉两个苹果剩余7个空位)
• 挑3个：\(C_6^3=20\)(插空法)
• 挑4个：\(C_5^4=5\)（插空法）
• 挑5个：不满足条件
  \(ans=8+21+20+5=54\)

14.选C

满足三角形的条件是任意两边之和大于第三条边。
根据上面的定理，依次枚举a=b的情况c可能的个数：

• a b c的个数
• 1 1 1个
• 2 2 3个
• 3 3 5个
• 4 4 7个
• 5 5 9个
• 6 6 9个（a,b,c均为1~9的整数，故最多9个）
• 7 7 9个
• 8 8 9个
• 9 9 9个
  \(N=1+3+5+7+9*6=61\)
  考虑等腰三角形有以下三种状态，\(aab,aba,baa\),则\(N=61*3=183\)
  再考虑等边三角形重复计算的情况，\(N=183-9*2=165\)

15.选B