【第一部分 选择题】1.以下不属于面向对象程序设计语言的是 。A. CB. PythonC. JavaD. C【解析】D。C语言是一种面向过程的结构化程序设计语言。2.以下奖项与计算机领域最相关的是 。A. 奥斯卡奖B. 图灵奖C. 诺贝尔奖D. 普利策奖【解析】B。3.目前主流的计算机储存数据最终都是转换成 数据进行储存。A. 二进制B. 十进制C. 八进制D. 十六进制【解析】A。B选项十进制 是人类习惯使用的计数方式。C和D选项八进制 和 十六进制 主要是为了方便人类阅读和书写二进制代码而引入的缩写形式例如在编程中常用来表示颜色或内存地址但它们在计算机硬件底层依然是以二进制的形式存在的。4.以比较作为基本运算在 N 个数中找出最大数最坏情况下所需要的最少的比较次数为 。A.N2N^{2}N2B. NC. N−1D. N1【解析】C。让第1个数作为默认最大数与后面的N-1个数进行N-1次比较。5.对于入栈顺序为 a,b,c,d,e 的序列下列 不是合法的出栈序列。A. a,b,c,d,eB. e,d,c,b,aC. b,a,c,d,eD. c,d,a,e,b【解析】D。d出栈后不可能是a出栈。6.对于有 n 个顶点、m 条边的无向连通图 (mn)需要删掉 条边才能使其成为一棵树。A. n−1B. m−nC. m−n−1D. m−n1【解析】D。树核心特点1没有环无回路树中的结点之间不能形成闭环。2连通树中任意两个结点之间都有且仅有一条路径相连。3边与结点的关系 n 个结点的树有且仅有 n−1 条边。4层次结构树具有明显的层级关系包含根结点、双亲结点等。所以要成为一个棵树需要保留n-1条边删掉m-(n-1)m-n1。7. 二进制数 101.11 对应的十进制数是 。A. 6.5B. 5.5C. 5.75D. 5.25【解析】C。整数部分和小数部分按位权展开求和。101.112 1*222^{2}220*212^{1}211*202^{0}201*2−12^{-1}2−11*2−22^{-2}2−24010.50.255.75。8.如果一棵二叉树只有根结点那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 种不同的形态A. 16B. 15C. 17D. 32【解析】A。第1层有1个结点第2层有2个结点第3层有4个结点第4层有8个结点第5层最多有16个结点最少保证有1个结点第5层从左右依次不间断的情况下增加结点构成不同的完全二叉树。9.表达式 a*(bc)*d 的后缀表达式为( )其中 * 和 是运算符。A. **abcdB. abc*d*C. abcd**D. *a*bcd【解析】B。按照运算优先级依次加上括号:((a*(bc))*d),然后按照运算优先级依次将对应括号中的运算符挪到对应括号后面((a(bc))*d)*去掉括号得到后缀表达式abc*d*。10.6 个人两个人组一队总共组成三队不区分队伍的编号。不同的组队情况有 种。A. 10B. 15C. 30D. 20【解析】B。区分队伍的编号即队伍的先后顺序第1支队伍C(6,2)第2支队伍C(4,2),第3支队伍就是剩余2人所以共有C(6,2)* C(4,2)*1 90。如果6个人依次是16考虑队伍编号的情况以下6种情况属于一种组队方式。[12 34 56]、[12 56 34]、[34 12 56]、[34 56 12]、[56 12 34]、[56 34 12]所以考虑队伍编号的情况下总共的组队方式是90/A(3,3) 90/6 15。11. 在数据压缩编码中的哈夫曼编码方法在本质上是一种 的策略。A. 枚举B. 贪心C. 递归D. 动态规划【解析】B。哈夫曼树构造规则每次选两个频率最小的结点合并新结点频率为两结点之和根据构造出的哈夫曼树进行哈夫曼编码是一种贪心的策略。12.由 1,1,2,2,3 这五个数字组成不同的三位数有 种。A. 18B. 15C. 12D. 24【解析】A。假设三位数为abc分情况讨论三个数位都不相同从{1,2,3}中构成有A(3,3) 6种。有两个数位相同1有两个数位是相同的1{ab,ac,bc}剩下一位可以是{2,3}共有3*2 6种。2有两个数位是相同的2{ab,ac,bc}剩下一位可以是{1,3}共有3*2 6种。共有18种。13.考虑如下递归算法则调用 solve(7) 得到的返回结果为 。A. 105B. 840C. 210D. 420【解析】C。1*2*3*5*7 210。14.以 a 为起点对下边的无向图进行深度优先遍历则 b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为 。A. 1B. 2C. 3D. 4【解析】B。起点固定为a的情况下深搜过程可能是abdce、acedb、acdbe最后一个遍历的点可能是e或b两种情况。15.有四个人要从 A 点坐一条船过河到 B 点船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8且两个人坐船的过河时间为两人独自过河时间的较大者。则最短 时间可以让四个人都过河到 B 点包括从 B 点把船开回 A 点的时间。A. 14B. 15C. 16D. 17【解析】B。1先让1和2一起过河到B然后1自己开回A点共耗时213。2再让4和8一起过河到B然后2自己开回A点共耗时8210。3最后让1和2一起过河到B耗时2。最少耗时15。核心点是第2步让大的和大的一起否则可能会出现84的情况。【第二部分 阅读程序题】阅读程序程序输入不超过数组或字符串定义的范围1输入的 n 等于 1001 时程序不会发生下标越界。A.对B.错【解析】B。数组a长度为1000最大下标999n为1001第22行会用到下标1000会发生下标越界。2输入的 a[i] 必须全为正整数否则程序将陷入死循环。A.对B.错【解析】B。可以参考3的解析f函数和g函数是对x的二进制进行的操作x是负数情况下不受影响。3当输入为 5 2 11 9 16 10 时输出为 3 4 3 17 5。A.对B.错【解析】B。n为5依次2、11、9、16、10这五个数的二进制形式进行操作输出的为3 4 3 17 4。4当输入为 1 511998 时输出为 18。A.对B.错【解析】A。将511998转换为二进制111 1100 1111 1111 1110共16个1f函数返回16g函数取最低位有效1返回2程序输出18。5将源代码中 g 函数的定义14∼17 行移到 main 函数的后面程序可以正常编译运行。A.对B.错【解析】B。g函数没有在main函数之前声明会报编译错误。6当输入为 2 -65536 2147483647 时输出为 。A. 65532 33B. 65552 32C. 65535 34D. 65554 33【解析】B。2147483647 0111 1111 1111 1111 1111 1111 1111 1111共31个1f返回31g函数返回1。选B。-65536涉及负数的补码可以理解为f函数和g函数的二进制表示都是补码形式正数的原码和补码相同所以不用可以刻意转换。在32位系统中-65536的原码是0000 0000 0000 0001 0000 0000 0000 0000取反1111 1111 1111 1110 1111 1111 1111 1111加11111 1111 1111 1111 0000 0000 0000 000所以f函数返回16g函数返回2^16 65536输出65552。【阅读程序-2】base64编码是通过算法将任意的字节数组数据对照编码表生成只有大小写英文字母、数字字符、、-的字符串形式。原理base64编码是把3个字节原数据变成4个字符编码后的数据。编码过程原数据3字节24位编码成4字节具体过程如图所示解码过程对照编码过程取出原3字节对应的二进制位还原回来。分析程序init函数初始化编码表base和映射表table假设编码后的字符‘F’通过table[‘F’]就能快速得到‘F’在base数组中的下标5所以table数组是用来提高查表速度的。table的有效下标是‘A’‘Z’、‘a’‘z’、‘0’‘9’、‘’、‘-’、‘’。decode函数每次取4字节还原为3字节可以参考下图从下往上理解。1输出的第二行一定是由小写字母、大写字母、数字和 、 /、 构成的字符串。A.对B.错【答案】B。decode函数是解码还原的过程原先的字符串可能是任意值例如第6题结果中就有空格。base64编码过程会将原先的字符串聚焦到小写字母、大写字母、数字和 、 /、构成的字符串。2可能存在输入不同但输出的第二行相同的情形。A.对B.错【解析】A。3输出的第一行为 -1。A.对B.错【解析】A。base编码数组元素没有0注意字符‘0’不是数值0table[0]就是0xffchar是有符号类型值对应-1。4设输入字符串长度为 ndecode 函数的时间复杂度为 。A. O(√n)B. O(n)C. O(nlogn)D. O(n2n^{2}n2)【解析】A。decode函数中只有一层for循环时间负责度为O(n)。5当输入为 Y3Nx 时输出的第二行为。A. cspB. csqC. CSPD. Csp【解析】B。‘Y’- 24 – 00 011000‘3’- 55 - 00 110111‘N’- 13 – 00 001101‘x’- 49 – 00 110001还原后第1个字节011000 11 – 99 – ‘c’第2个字节0111 0011 – 115 – ‘s’第3个字节01110001 – 113 – ‘p’6当输入为 Y2NmIDIwMjE 时输出的第二行为 。A. ccf2021B. ccf2022C. ccf 2021D. ccf 2022【解析】C。每4个字符为一组解码后对应3个字符。但是最后一组有一个‘’所以最后一组解码后对应2个字符所以会输出8个字符排除A和B选项C和D选项只在最有一个分组不同解码最后一个分组。第1组Y2Nm第2组IDIw第3组MjE最后一个分组参考第5题的过程需要超耐心的位运算与进制转换计算储备。【阅读程序-3】假设输入的 x 是不超过 1000 的自然数完成下面的判断题和单选题题目是在经典欧拉筛的基础上增加了一些操作。从第15和第16行可以猜出a数组标记是否是质数b数组是存储质数。筛选几次理解不同数组含义f[i]表示i的约数个数g[i]表示i的所有约数之和。1若输入不为 1把第 13 行删去不会影响输出的结果。A.对B.错【解析】A。除了第13行对f[1]和g[1]进行初始化后面没有用到f[1]和g[1]删掉不影响输出结果。2第 25 行的 f[i] / c[i * k]可能存在无法整除而向下取整的情况。A.对B.错【解析】B。第24行i*k是合数k是i*k的最小质因数每次c[i]1表示i*k的最小质因数的个数。例如9 32c[9] 2。结合约数个数定理假设i的质因数分解为(p1)a1(p1)^{a1}(p1)a1*(p2)a2(p2)^{a2}(p2)a2*…f[i] (p1 1)*p21*…所以f[i]是包含c[i]1的f[i] / c[i * k]不可能存在无法整除而向下取整的情况。3在执行完 init() 后f 数组不是单调递增的但 g 数组是单调递增的。A.对B.错【解析】B。f数组表示约数个数g数组表示约数之和都不是单调递增的。4init 函数的时间复杂度为 。A. O(n)B. O(nlogn)C. O(n√n)D. O(n2n^{2}n2)【解析】A。欧拉筛也称为线性筛应为每个合数仅会被筛掉一次。5在执行完 init() 后f[1],f[2],f[3]…f[100] 中有个等于 2。A. 23B. 24C. 25D. 26【解析】C。f数组存储约数个数只有质数的约数个数是2个1100之间的质数有25个。6当输入为 1000 时输出为。A. 15 1340B. 15 2340C. 16 2340D. 16 1340【解析】C。1000的约数有16个分别是1、2、4、5、8、10、20、25、40、50、100、125、200、250、500、1000约数之和2340。【第三部分 完善程序题】【完善程序-1】Josephus 问题有 n 个人围成一个圈依次标号 0 至 n1。从 0 号开始依次 0,1,0,1,… 交替报数报到 1 的人会离开直至圈中只剩下一个人。求最后剩下人的编号。做题顺序先2、3、4、5再11①处应填 A.i nB.c nC.i n- 1D.c n-1【解析】D。环上离开n-1个人剩余1个人就不需要循环c是记录离开的人数排除A和C选项分析B选项当c是n-1时c n成立仍进行标记可能把最后一个人也标记掉不符合题意所以此处应该c n-1。2②处应填 A.i % 2 0B.i % 2 1C.pD.!p【解析】C。p用来实现0、1、0、1、...交替报数p初始值为0当p为1时i离开圈。3③处应填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】C。F[i]1表示i编号的人离开c记录离开的人数此处c。4④处应填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】D。p用来实现0、1、0、1、...交替报数p ^ 1异或运算能够实现0、1交替例如当p为0时p ^ 1p变为1当p为1时p ^ 1p变为0。5⑤处应填 A.iB.i (i 1) % nC.cD.p ^ 1【解析】B。因为第13行会判断当前i是否被标记所以此处就是下一个环上的编号不管这个编号是否被标记因为是在环上环的大小是n此处要取余i (i 1) % n。【完善程序-2】矩形计数平面上有 n 个关键点求有多少个四条边都和 x 轴或者 y 轴平行的矩形满足四个顶点都是关键点。给出的关键点可能有重复但完全重合的矩形只计一次。试补全枚举算法。1①处应填 A. a.x ! b.x ? a.x b.x : a.id b.idB. a.x ! b.x ? a.x b.x : a.y b.yC. equals(a, b) ? a.id b.id : a.x b.xD. equals(a, b) ? a.id b.id : (a.x ! b.x ? a.x b.x : a.y b.y)【解析】B。第61行和62行是先排序再去重去重函数中unique中只要保证x和y都相同的关键点连续在一起不关心id的顺序。2②处应填 A. i 0 || cmp(A[i], A[i - 1])B. t 0 || equals(A[i], A[t - 1])C. i 0 || !cmp(A[i], A[i - 1])D. t 0 || !equals(A[i], A[t - 1])【解析】D。t用来记录去重后关键点的个数当!equals(A[i], A[t - 1])成立时记录。3③处应填 A. b - (b - a) / 2 1B. (a b 1) 1C. (a b) 1D. a (b - a 1) / 2【解析】C。取中间点。4④处应填 A. !cmp(A[mid], p)B. cmp(A[mid], p)C. cmp(p, A[mid])D. !cmp(p, A[mid])【解析】B。4和5结合结合起来理解相当于构造了两个新的点p1i点的x和j点的y构成一个新的点p利用二分查找与p相同的点2i点的y和j点的x构成一个新的点p利用二分查找与p相同的点。如果能找到就找到了如图所示的矩形。因为关键点都按照x、y从小到大排序所以mid点小于p点时往右收敛。5⑤处应填 A. A[i].x A[j].xB. A[i].id A[j].idC. A[i].x A[j].x A[i].id A[j].idD. A[i].x A[j].x A[i].y A[j].y【解析】D。枚举i和j时所有情况都包含如果不保证i和j一个在左边一个在右边会有重复枚举的情况。参考4解析的图。