一、单选题（共 15 题，每题 2 分，共计 30 分）

1. 十进制小数 15.625 对应的二进制数是（ ）

{{ select(1) }}

• 1011. 101
• 1011. 011
• 1101. 101
• 1111. 101

2. 二进制数-1111001 的补码是（ ）。

{{ select(2) }}

• $00110101$
• $10010110$
• $10000111$
• $01101010$

3. 字符串”acacb”本质不同的子串个数为（ ）

{{ select(3) }}

• 12
• 13
• 14
• 15

4.由 4个节点构成的形态不同的二叉树有（ ）种。

{{ select(4) }}

• 16
• 14
• 20
• 10

5.一棵6节点二叉树的中序遍历为ABDGECF,先序遍历为DBACEGF,后序遍历（ ）。 {{ select(5) }}

• DGBEFAC
• ABGEFCD
• GBEACFD
• ABCDEFG

6.一棵高度为8的完全二叉树至少有（　　）叶子节点 {{ select(6) }}

• 65
• 66
• 63
• 64

7.在24*24 点阵的字库中，汉字“一 ”与“编”的字模占用字节数分别是( )。

{{ select(7) }}

• 32，32
• 32，72
• 72，36
• 72，72

8.在下列关于图灵奖的说法中，不正确的是( )。 {{ select(8) }}

• 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人
• 图灵奖有“计算机界诺贝尔奖”之称
• 迄今为止，还没有华裔计算机科学家获此殊荣
• 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵

9.无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有( )条边。 {{ select(9) }}

• $32$
• $42$
• $21$
• $31$

10.在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是（ ）。

{{ select(10) }}

• $O(1)$
• $O(log(n))$
• $O(n)$
• $O(n^2)$

11.8 颗子弹,编号为1,2,3,4,5,6,7,8,从编号 1开始按序嵌入弹夹,以下不是正常的打出子弹的次序的是（ ）

{{ select(11) }}

• 12345678
• 87654321
• 32154876
• 32164587

12.二分图是指能将定点划分成两个部分,每一部分内的顶点间没有边相连的简单无向图。那么,12个顶点的二分图至多有（ ）条边

{{ select(12) }}

• 18
• 24
• 36
• 66

13.深度优先搜索需要借助的数据结构是（）

{{ select(13) }}

• 栈
• 队列
• 链表
• 优先队列

14.有 A,B,C,D,E,F六人聪明绝顶且势均力敌的盗墓贼,他们都排着队,他们每个人都想独吞财宝,最前面的 A 如果拿了财宝,那么体力下降,则其后面的 B 会杀掉A,拿了财宝,当然 B拿了财宝,体力也会下降,一样会被C 杀掉,如果 B 不拿财宝,则 C 无法杀 B,请问 A、C、E的最终想法是（ ）

{{ select(14) }}

• A 不拿 C 不拿 E拿
• A 拿 C 拿 E 不拿
• A 不拿 C不拿 E 不拿
• A 不拿 C 拿 E 拿

15.非常经典的汉诺塔问题，目标是将A柱上的盘子移到C柱上，但是大的盘子不能放到小的盘子的上面。现在规定：A柱上的盘子只能移动到B柱，B只能移动C，C只能移到A。现在A柱上有3个盘子，要把这些盘子安照上述规则都挪到C柱上，每次移动一个盘子，至少要移动（ ）次。

{{ select(15) }}

• 7
• 17
• 21
• 31

二.阅读程序(程序输入不超过数组或字符串定义的范围；除特殊说明外，判断题1.5分选择题3分,共计 40 分)

判断题

1).输出的结果为三位数。（）

{{ select(16) }}

• √
• ×

2).将5行的$\le$改为$＜$则输出结果不变。（）

{{ select(17) }}

• √
• ×

3).将第13行true改为1，程序运行结果不会改变。（）

{{ select(18) }}

• √
• ×

4).将第15行删除，程序运行结果不会改变。（）

{{ select(19) }}

• √
• ×

单选题

5).如果输入2和12，则输出结果为多少（）

{{ select(20) }}

• 4
• 96
• 096
• 4096

6).这个算法的时间复杂度为（）

{{ select(21) }}

• $O(m*n)$
• $O(n)$
• $O(m)$
• $O(m^n)$

判断题

1).若输入为：0 0 0时，程序运行会出错。（） {{ select(22) }}

• √
• ×

2).若输入为：1 2 3时，则输出为3：1。（） {{ select(23) }}

• √
• ×

3).若把11行的“index!=k”改为1，不会影响程序运行结果。（） {{ select(24) }}

• √
• ×

4).若去掉37和38行，不会影响程序运行结果。（） {{ select(25) }}

• √
• ×

单选题

5).程序运行时，输入5 4 3，输出（） {{ select(26) }}

• 3:5
• 2:3
• 1:2
• 4:1

6). (4分)程序运行时，输入7 5 2，输出（） {{ select(27) }}

• 1:5
• 6:1
• 2:3
• 2:4

判断题

1).若输入为：32时，程序运行后没有输出（）。 {{ select(28) }}

• √
• ×

2).times(string a,int num)函数实现了将一个字符串a复制num次后返回。（） {{ select(29) }}

• √
• ×

3).(2分)如果程序输入3ac[[b]] 和3ac[b]输出结果相同（） {{ select(30) }}

• √
• ×

单选题

4).程序运行时，输入3f[2a]，输出（）。 {{ select(31) }}

• $faafaafaa$
• $ffaaffaaffaa$
• $3faa3faa3faa$
• $fffaafffaa$

5).程序运行时，输入3a[2a3b]，输出包含（）个B

{{ select(32) }}

• 18
• 12
• 6
• 24

6).(4分)程序运行时，输入3[[]]],输出结果是（）

{{ select(33) }}

• 程序错误
• [[]]][[]]][[]]]
• ]]]
• []][]][]]

三、完善程序

（1）

1.扫雷游戏是一款十分经典的单机小游戏。在 n 行 m 列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出 n 行 m 列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。第一行是用一个空格隔开的两个整数 n 和 m，分别表示雷区的行数和列数。 接下来 n 行，每行 m 个字符，描述了雷区中的地雷分布情况。字符 ** 表示相应格子是地雷格，字符 ?? 表示相应格子是非地雷格。相邻字符之间无分隔符。试补全程序。

1).①处应填（ ）。

{{ select(34) }}

• 1，1
• -1,-1
• 1，0
• -1,0

2).②处应填（ ）。 {{ select(35) }}

• dir[i][1]
• dirs[0][i]
• dirs[i][0]
• dirs[i][1]

3).③处应填（ ）。 {{ select(36) }}

• check();
• return sum;
• return check();
• ans;

4).④处应填（ ）。 {{ select(37) }}

• !=’?’
• ==‘*’
• ==’?’
• !=’*’

5).⑤处应填（ ）。 {{ select(38) }}

• check(i,j);
• cout<<(check(i,j);
• check(x,y)
• cout<<check(x,y);

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4。 现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。试补全程序。 输入格式 只一个正整数 n，（3≤n≤10000）。 输出格式 第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。第二行是最大的乘积。

1).①处应填（ ）。 {{ select(39) }}

• ans[a.size()+i] += num
• ans[a.size()+b.size()-1] += num
• ans[i+b.size()-1] += num
• ans[i+b.size()] += num`

2).②处应填（ ）。 {{ select(40) }}

• ans.size()>1
• ans.size()>=1
• ans.size()>=0
• ans.size()!=1

3).③处应填（ ）。 {{ select(41) }}

• cout<<n-1<<endl<<n-1<<endl;
• cout<<n-1<<endl<<n<<endl;
• cout<<n<<endl<<n-1<<endl;
• cout<<n<<endl<<n<<endl;

4).④处应填（ ）。

{{ select(42) }}

• a[idx-1]+=1
• a[1]+=1
• a[idx]+=1
• a[idx]-=1

5).⑤处应填（ ）。

{{ select(43) }}

• idx
• b.size()
• ans.size()
• a.size()+b.size()