CSP 2020 入门级第一轮1~17题解析

第 1 题

在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。

A. 地址
B. 序号
C. 下标
D. 编号

常识题
答案：A

第 2 题

编译器的主要功能是（ ）。

A. 将源程序翻译成机器指令代码
B. 将源程序重新组合
C. 将低级语言翻译成高级语言
D. 将一种高级语言翻译成另一种高级语言

直接排除D，B，C
答案：A

第 3 题

设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是（ ）。

A. (y∨z)∧x∧z
B. x∧(z∨y) ∧z
C. (x∧y) ∧z
D. (x∧y)∨(z∨x)

只需要记住一件事，∧左右两边必须为真，否则判断为假；∨左右两边左右两边只要有一边为真，判断为真（和&&，||意思相近）
答案：D

第 4 题

现有一张分辨率为 $2048\times 1024$ 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。

A. 16MB
B. 4MB
C. 8MB
D. 2MB

遇到这种题目，直接把其分辨率相乘再除以1024^2（也可以分别除以1024再相乘）。然后再乘图像的位数，最后除以8即可。（注意上方公式的单位最后是MB，其它的单位需转换一下单位）
答案：C

第 5 题

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
   1. FLAG ← n //标记被交换的最后元素位置
   2. while FLAG > 1 do
   3.     k ← FLAG -1
   4.     FLAG ← 1
   5.     for j=1 to k do
   6.         if L(j) > L(j+1) then do
   7.              L(j)  ↔ L(j+1)
   8.              FLAG ← j
1
2
3
4
5
6
7
8
9
10

对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。
A. $n^2$
B. $n-2$
C. $n-1$
D. $n$

遇到这种题，绝对不要慌！先给它翻译一下：

   1. 将n的值赋给FLAG
   2. 只要FLAG的值>1：
   3.     将k的值变为FLAG-1
   4.     将1的值赋给FLAG
   5.     j的初值为1，循环至j==k
   6.         如果第j位比第j+1位大
   7.              将它们的位置交换
   8.              将j的值赋给FLAG
1
2
3
4
5
6
7
8

有没有感觉简单一点了呢？接下来把n的值带进去算就行了！（建议不要小于5）
答案：C

第 6 题

设 A 是 n 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
1.  if n=1 then return A[1]
2.  else temp ← XYZ (A[1..n-1])
3.  if temp < A[n]
4.  then return temp
5.  else return A[n]
1
2
3
4
5
6

请问算法 XYZ 的输出是什么？（）。

A. A 数组的平均
B. A 数组的最小值
C. A 数组的中值
D. A 数组的最大值

和上一道题一样，翻译加模拟即可
答案：B

第 7 题

链表不具有的特点是（）。

A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比

关于链表的特点，必须记住：链表不可随机访问任一元素！（好像大部分链表的题目都考这个）
答案：A

第 8 题

有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

A. 9
B. 10
C. 11
D. 12

常识题，背就完了！
答案：10-1=9，A

第 9 题

二进制数 1011 转换成十进制数是（ ）。

A. 11
B. 10
C. 13
D. 12

转进制都会吧，从最右边开始。$(1011{)}_2$=$1\ast 2^0$+$1\ast 2^1$+$1\ast 2^3$=$1+2+8$=$11$
答案：A

第 10 题

5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?

A. 48
B. 36
C. 24
D. 72

我们可以用捆绑法，将双胞胎看做一个人，最后在答案上乘2。$A_4^1\ast A_3^1\ast A_2^1\ast A_1^1\ast 2=48$
答案：A

第 11 题

下图中所使用的数据结构是（ )。

A. 栈
B. 队列
C. 二叉树
D. 哈希表

很明显，是栈
答案：A

第 12 题

独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）。

A. 7
B. 8
C. 5
D. 6

在草稿纸上凑一下就能算出来了。
答案：D

第 13 题

干支纪年法是中国传统的纪年方法，由 10 个天干和 12 个地支组合成 60 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

• 天干 =（公历年份）除以 10 所得余数
• 地支 =（公历年份）除以 12 所得余数

例如，今年是 2020 年，2020 除以 10 余数为 0，查表为"庚”；2020 除以 12，余数为 4，查表为“子” 所以今年是庚子年。

请问 1949 年的天干地支是（ ）

A. 己酉
B. 己亥
C. 己丑
D. 己卯

简单算一下即可。
答案：C

第 14 题

10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。

A. 84
B. 72
C. 56
D. 504

排列组合一下即可。
答案：A

第 15 题

有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。

A. 120
B. 180
C. 150
D. 30

也是排列组合，求出所有的情况，再减去不满足条件的情况。
答案：A

第 16 题

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分)

#include 
#include 
using namespace std;

char encoder[26] = {'C','S','P',0};
char decoder[26];

string st;

int main()  {
  int k = 0;
  for (int i = 0; i < 26; ++i)
    if (encoder[i] != 0) ++k;
  for (char x ='A'; x <= 'Z'; ++x) {
    bool flag = true;
    for (int i = 0; i < 26; ++i)
      if (encoder[i] ==x) {
        flag = false;
        break;
      }
      if (flag) {
        encoder[k]= x;
        ++k;
      }
  }
  for (int i = 0; i < 26; ++i)
     decoder[encoder[i]- 'A'] = i + 'A';
  cin >> st;
  for (int i = 0; i < st.length( ); ++i)
    st[i] = decoder[st[i] -'A'];
  cout << st;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

•判断题

输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。（ ）
若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（）
将第 12 行的 i < 26 改为 i < 16，程序运行结果不会改变。（ ）
将第 26 行的 i < 26 改为 i < 16，程序运行结果不会改变。（ ）

•单选题

5） 若输出的字符串为 $\text{ABCABCABCA}$，则下列说法正确的是（ ）。

6）若输出的字符串为 $\text{CSPCSPCSPCSP}$，则下列说法正确的是（ ）。

1. A. 正确 B. 错误
2. A. 正确 B. 错误
3. A. 正确 B. 错误
4. A. 正确 B. 错误
5. A. 输入的字符串中既有 S 又有 P
   B. 输入的字符串中既有 S 又有 B
   C. 输入的字符串中既有 A 又有 P
   D. 输入的字符串中既有 A 又有 B
6. A. 输入的字符串中既有 P 又有 K
   B. 输入的字符串中既有 J 又有 R
   C. 输入的字符串中既有 J 又有 K
   D. 输入的字符串中既有 P 又有 R

很简单，就是到模拟题。
答案：ABABAD

第 17 题

#include 
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
  cin >> n >> k;
  d[0] = 0;
  len= 1;
  ans = 0;
  for (long long i = 0; i <n; ++i) {
    ++d[0];
    for (int j = 0; j + 1<len; ++j) {
      if (d[j] == k) {
        d[j] = 0;
        d[j + 1] += 1;
        ++ans;
      }
    }
    if (d[len- 1] == k) {
      d[len - 1] = 0;
      d[len] =1;
      ++len;
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

假设输入的 n 是不超过 $2^{62}$的正整数，k 都是不超过10000 的正整数，完成下面的判断题和单选题：

• 判断题
  若 k=1，则输出 $\mathrm{ans}$ 时，$\mathrm{len}=n$。（ ）
  若 k>1，则输出 $\mathrm{ans}$ 时，$\mathrm{len}$ —定小于 n。（ ）
  若 k>1，则输出 $\mathrm{ans}$时，$k^{len}$ —定大于 n。（ ）
• 单选题
  若输入的 n 等于：$10^{15}$ ，输入的 k 为 1，则输出等于（ ）。
  若输入的 n 等于 205,891,132,094,649（即 $3^{30}$ ），输入的 k 为 3，则输出等于（ ）。

若输入的 n 等于 100,010,002,000,090，输入的 k 为 10，则输出等于（ ）。

1. A. 正确 B. 错误
2. A. 正确 B. 错误
3. A. 正确 B. 错误
4. A. 1
   B. $(10^{30}-10^{15})/2(10^{30}-10^{15})/2$
   C. $(10^{30}-10^{15})/2(10^{30}+10^{15})/2$
   D. $10^{15}$
5. A. $3^{30}$
   B. $(3^{30}-1)/2$
   C. $3^{30}-1$
   D. $(3^{30}+1)/2$
6. A. 11,112,222,444,543
   B. 11,122,222,444,453
   C. 11,122,222,444,543
   D. 11,112,222,444,453

答案：BBADBD

总结

相对来说还比较简单。（保证1~17题全对，后面几道题乱蒙就能过了）
祝大家在今年的CSP初赛取得好成绩！