#4770. 2021年CSP-J 初赛试题

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

  1. 以下不属于面向对象程序设计语言的是( )。
  1. 以下奖项与计算机领域最相关的是( )。
  1. 目前主流的计算机储存数据最终都是转换成( )数据进行储存。
  1. 以比较作为基本运算,在 NN 个数中找出最大数,最坏情况下所需要的最少的比较次数为 ( )。
  1. 对于入栈顺序为 a,b,c,d,ea, b, c, d, e 的序列,下列( )不是合法的出栈序列。
  1. 对于有 nn 个顶点、mm 条边的无向连通图 (m>n)(m>n),需要删掉( )条边才能使其成为一棵树。
  1. 二进制数 101.11101.11 对应的十进制数是( )。
  1. 如果一棵二叉树只有根结点,那么这棵二叉树高度为 11。请问高度为 55 的完全二叉树有 ( )种不同的形态?
  1. 表达式 a*(b+c)*d\texttt{a*(b+c)*d} 的后缀表达式为( ),其中 *\texttt{*} + \texttt{ + } 是运算符。
  1. 66 个人,两个人组一队,总共组成三队,不区分队伍的编号。不同的组队情况有( )种。
  1. 在数据压缩编码中的哈夫曼编码方法,在本质上是一种( )的策略。
  1. 由 1,1,2,2,3 这五个数字组成不同的三位数有( )种。
  1. 考虑如下递归算法
solve(n)  
     if n<=1 return 1  
      else if n>=5 return n*solve(n-2)  
      else return n*solve(n-1) 

则调用 solve(7) 得到的返回结果为( )。

  1. aa 为起点,对下边的无向图进行深度优先遍历,则 b,c,d,eb,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为( )。
  1. 有四个人要从 A 点坐一条船过河到 B 点,船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,81,2,4,8,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短( )时间可以让四个人都过河到 B 点(包括从 B 点把船开回 A 点的时间)。

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

·判断题

输入的 nn 等于 10011001 时,程序不会发生下标越界。( )

输入的 a[i]a[i] 必须全为正整数,否则程序将陷入死循环。( )

当输入为 5 2 11 9 16 10 时,输出为 3 4 3 17 5。( )

当输入为 1 511998 时,输出为 18。( )

将源代码中 g 函数的定义(141714\sim 17 行)移到 main 函数的后面,程序可以正常编译运行。( )

·单选题

当输入为 2 -65536 2147483647 时,输出为( )。

判断题 输出的第二行一定是由小写字母、大写字母、数字和 +/=\texttt +、 \texttt /、\texttt = 构成的字符串。( )

可能存在输入不同,但输出的第二行相同的情形。( )

输出的第一行为 -1\texttt -1。( )

单选题 设输入字符串长度为 nn,decode 函数的时间复杂度为( )

当输入为 Y3Nx\texttt{Y3Nx} 时,输出的第二行为()。

(3.5 分)当输入为 Y2NmIDIwMjE=\texttt{Y2NmIDIwMjE=} 时,输出的第二行为( )。

假设输入的 xx 是不超过 10001000 的自然数,完成下面的判断题和单选题:

判断题

若输入不为 1\texttt 1,把第 13 行删去不会影响输出的结果。( )

(2 分) 第 25 行的 f[i]/c[ik]f[i] / c[i * k] 可能存在无法整除而向下取整的情况。 ( )

(2 分) 在执行完 init() 后,f 数组不是单调递增的,但 g 数组是单调递增的。 ( )

单选题

init 函数的时间复杂度为( )。

在执行完 init() 后,f[1],f[2],f[3]f[1], f[2], f[3] \dots 中有()个等于 22

(4 分) 当输入为 1000\texttt{1000} 时,输出为()。

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

(Josephus 问题) 有 nn 个人围成一个圈,依次标号 00n1n - 1。从 00 号开始,依次 0,1,0,1,0 , 1 , 0 , 1 , \dots 交替报数,报到 11 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

①处应填( )

②处应填( )

③处应填( )

④处应填( )

⑤处应填( )

①处应填 ( )

②处应填 ( )

③处应填 ( )

④处应填 ( )

⑤处应填 ( )

参考答案(请提交完答案后再看)