#5136. 2022 CCF 非专业级别软件能力认证第一轮 CSP -S1

2022 CCF 非专业级别软件能力认证第一轮 CSP -S1

一、单项选择题(共 15 题,每题 2 分,共计 30 分;每题有且仅有一个正确选项)

  1. 在Linux系统终端中,用于切换工作目录的命令为( )。 {{ select(1) }}
  • ls
  • cd
  • cp
  • all
  1. 你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如 下:
    real 0m30.721s
    user 0m24.579s
    sys 0m6.123s
    以下最接近秒表计时的时长为( )。 {{ select(2) }}
  • 30s
  • 24s
  • 18s
  • 6s
  1. 若元素 a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次 退栈操作,则不可能得到的出栈序列是( )。 {{ select(3) }}
  • dcebfa
  • cbdaef
  • bcaefd
  • afedcb
  1. 考虑对n个数进行排序,以下最坏时间复杂度低于O(n2)的排序方法是( )。 {{ select(4) }}
  • 插入排序
  • 冒泡排序
  • 归并排序
  • 快速排序
  1. 假设在基数排序过程中,受宇宙射线的影响,某项数据异变为一个完全不同的值。请问排 序算法结束后,可能出现的最坏情况是( )。 {{ select(5) }}
  • 移除受影响的数据后,最终序列是有序序列
  • 移除受影响的数据后,最终序列是前后两个有序的子序列
  • 移除受影响的数据后,最终序列是一个有序的子序列和一个基本无序的子序列
  • 移除受影响的数据后,最终序列基本无序
  1. 计算机系统用小端(Little Endian)和大端(Big Endian)来描述多字节数据的存储地 址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数 据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代 码段表示的程序,将分别输出什么结果?( )
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);

{{ select(6) }}

  • EF、EF
  • EF、DE
  • DE、EF
  • DE、DE
  1. 一个深度为 5(根结点深度为 1)的完全 3 叉树,按前序遍历的顺序给结点从 1 开始编号,则第100号结点的父结点是第( )号。 {{ select(7) }}
  • 95
  • 96
  • 97
  • 98
  1. 强连通图的性质不包括( ): {{ select(8) }}
  • 每个顶点的度数至少为 1
  • 任意两个顶点之间都有边相连
  • 任意两个顶点之间都有路径相连
  • 每个顶点至少都连有一条边
  1. 每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正 规图,其中包含欧拉回路的不同2正规图的数量为( )。 {{ select(9) }}
  • n!
  • (n-1)!
  • n!/2
  • (n-1)!/2
  1. 共有8人选修了程序设计课程,期末大作业要求由2人组成的团队完成。假设不区分每个 团队内2人的角色和作用,请问共有多少种可能的组队方案。( ) {{ select(10) }}
  • 28
  • 32
  • 56
  • 64
  1. 小明希望选到形如“省 A·LL𝒟𝒟𝒟𝒟𝒟𝒟”的车牌号。车牌号在“·”之前的内容固定不变;后面 的 5 位号码中,前 2 位必须是大写英文字母,后 3 位必须是阿拉伯数字(L代表 A 至 Z,𝒟𝒟 表示 0 至 9,两个L和三个𝒟𝒟之间可能相同也可能不同)。请问总共有多少个可供选择的车牌号。( ) {{ select(11) }}
  • 20280
  • 52000
  • 676000
  • 1757600
  1. 给定地址区间为0~9的哈希表,哈希函数为h(x) = x % 10,采用线性探查的冲突解决 策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0 重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请 问89存储在哈希表哪个地址中。( ) {{ select(12) }}
  • 9
  • 0
  • 1
  • 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; 
        }
    }

{{ select(13) }}

  • O(n)O(n)
  • O(nlogn)O(n log n)
  • O(nn)O(n\sqrt{n})
  • O(n2)O(n^2)

14.以比较为基本运算,在n个数的数组中找最大的数,在最坏情况下至少要做( )次运算。 {{ select(14) }}

  • n/2
  • n-1
  • n
  • n+1
  1. 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));
}

{{ select(15) }}

  • 5
  • 7
  • 9
  • 13

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

(1)

假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:

判断题

  1. (1 分)当输入为“abcde fg”时,输出为-1。( ) {{ select(16) }}
  • 正确
  • 错误
  1. 当输入为“abbababbbab abab”时,输出为 4。( ) {{ select(17) }}
  • 正确
  • 错误
  1. 当输入为“GoodLuckCsp2022 22”时,第 20 行的“j++”语句执行次数为 2。 () {{ select(18) }}
  • 正确
  • 错误

单选题

  1. 该算法最坏情况下的时间复杂度为( )。 {{ select(19) }}
  • 𝑂(𝑛+𝑚)
  • 𝑂(𝑛log𝑚)
  • 𝑂(𝑚log𝑛)
  • 𝑂(𝑛𝑚)
  1. f(a, b)与下列( )语句的功能最类似。 {{ select(20) }}
  • a.find(b)
  • a.rfind(b)
  • a.substr(b)
  • a.compare(b)
  1. 当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为 ( )。 {{ select(21) }}
  • 9
  • 10
  • 11
  • 12

(2)

假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在 int 表示范围内,完成下面的判断题和单选题:

判断题

22.这是一个不稳定的排序算法。( ) {{ select(22) }}

  • 正确
  • 错误

23.该算法的空间复杂度仅与n有关。( ) {{ select(23) }}

  • 正确
  • 错误

24.该算法的时间复杂度为𝑂(𝑚(𝑛+𝑘))𝑂(𝑚(𝑛+𝑘))。( ) {{ select(24) }}

  • 正确
  • 错误

单选题

25.当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的 内容依次为( )。 {{ select(25) }}

  • 91 26 46 37 98
  • 91 46 37 26 98
  • 98 26 46 91 37
  • 91 37 46 98 26

26.若val[i]的最大值为100,k取( )时算法运算次数最少。 {{ select(26) }}

  • 2
  • 3
  • 10
  • 不确定

27.当输入的k比val[i]的最大值还大时,该算法退化为( )算法。 {{ select(27) }}

  • 选择排序
  • 冒泡排序
  • 计数排序
  • 桶排序

(3)

假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和 单选题:

判断题

  1. 该算法的时间复杂度为𝑂(log𝑘𝑛)𝑂(log_𝑘 𝑛)。( ) {{ select(28) }}
  • 正确
  • 错误
  1. 删除第23行的强制类型转换,程序的行为不变。( ) {{ select(29) }}
  • 正确
  • 错误
  1. 除非输入的n为0,否则程序输出的字符数为O(log𝑘𝑛+1)O(⌊log_𝑘|𝑛|⌋ + 1)。( ) {{ select(30) }}
  • 正确
  • 错误

单选题 31.当输入为“100 7”时,输出为( )。 {{ select(31) }}

  • 202
  • 1515
  • 244
  • 1754

32.当输入为“-255 8”时,输出为“( )”。 {{ select(32) }}

  • 1400
  • 1401
  • 417
  • 400

33.当输入为“1000000 19”时,输出为“( )”。 {{ select(33) }}

  • BG939
  • 87GIB
  • 1CD428
  • 7CF1B

三、 完善程序(单选题,每小题3分,共计30分)

(1) (归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严 格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。 试补全程序。

  1. 1处应填( ) {{ select(34) }}
  • (m1+m2)*2
  • (m1-1)+(m2-1)
  • m1+m2
  • (m1+1)+(m2+1)
  1. 2处应填( ) {{ select(35) }}
  • a1[m1]==a2[m2]
  • a1[m1]<=a2[m2]
  • a1[m1]>=a2[m2]
  • a1[m1]!=a2[m2]
  1. 3处应填( ) {{ select(36) }}
  • left1==right1
  • left1<right1
  • left1>right1
  • left1!=right1
  1. 4处应填( ) {{ select(37) }}
  • y=a1[k-left2-1]
  • y=a1[k-left2]
  • y=a2[k-left1-1]
  • y=a2[k-left1]
  1. 5处应填( ) {{ select(38) }}
  • y=a1[k-left2-1]
  • y=a1[k-left2]
  • y=a2[k-left1-1]
  • y=a2[k-left1]

(2)(容器分水)有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允 许下列的三种操作,分别为: 1)FILL(i):用水龙头将容器 i(i∈{1,2})灌满水;
2)DROP(i):将容器 i 的水倒进下水道;
3)POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要 么容器 i 被清空)。
求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和操作序列。上 述 a、b、c 均为不超过 100 的正整数,且 c≤max{a,b}。
试补全程序。

39.1处应填( ) {{ select(39) }}

  • dfs(x+t,y-t)+1
  • dfs(x+t,y-t)-1
  • dfs(x-t,y+t)+1
  • dfs(x-t,y+t)-1

40.2处应填( ) {{ select(40) }}

  • dfs(x+t,y-t)+1
  • dfs(x+t,y-t)-1
  • dfs(x-t,y+t)+1
  • dfs(x-t,y+t)-1

41.3处应填( ) {{ select(41) }}

  • x==c||y==c
  • x==c&&y==c
  • x>=c||y>=c
  • x>=c&&y>=c

42.4处应填( ) {{ select(42) }}

  • dfs(x+t,y-t)+1
  • dfs(x+t,y-t)-1
  • dfs(x-t,y+t)+1
  • dfs(x-t,y+t)-1

43.5处应填( ) {{ select(43) }}

  • dfs(x+t,y-t)+1
  • dfs(x+t,y-t)-1
  • dfs(x-t,y+t)+1
  • dfs(x-t,y+t)-1