一，单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）

1. 如下关于C++编程语言中基础数据类型说法不正确的是()。{{ select(1) }}

• double 类型的变量占用内存的大小是浮动的。
• bool 类型的变量占用 1 字节内存。
• int 类型变量的取值范围不是无限的。
• char 类型的变量有 256 种取值。

2. ()是一种解释型编程语言。{{ select(2) }}

• C 语言
• C++
• Golang
• python

3. 以下程序执行完毕时变量x的值为()。

   {{ select(3) }}

• 54321
• 543210
• 531
• 5309

4. 如下语句中等价于“ cout << a[5];”的语句为()。

   {{ select(4) }}

• cout << a + 5;
• cout << *(a + 5);
• printf( “%d” ,a+5);
• printf( “%d” ,a+6);

5. 整数数字 100,000,000 的因数共有()个。{{ select(5) }}

• 64
• 81
• 100
• A、B、C都不对

6. 在C++中，容器 vector 向量类型包含函数()。{{ select(6) }}

• push()
• top()
• length()
• push_back()

7. 已知开放集合(open_set)S={x}规定，如整数 x 属于集合，则 2x 与 3x 同样属于集合。若集合包含1，则集合一定包含()。{{ select(7) }}

• 2023
• 2024
• 3072
• 6066

8. 以下数据结构中满足先进先出特性的为()。{{ select(8) }}

• stack
• queue
• set
• vector

9. 已知^为位运算符异或，则在C++的表达式计算中,(-5)^(-6)的结果为()。{{ select(9) }}

• 1
• -1
• 3
• -3

10. 数组与指针的说法正确的是()。{{ select(10) }}

• 数组名是一个指向数组首元素的指针，可以重新申请内存空间改变数组大小
• 数组名是一个指向数组尾元素的指针
• 数组定义时会立即分配固定的内存空间，而指针定义会占用大量的零散空间预备储存数据
• 无法在程序中定义指针类型的数组

11. 将二进制小数 11.011 转化为 10 进制表示法为()。{{ select(11) }}

• 3.75
• 2.75
• 2.625
• 3.375

12. 已知由 n 个点的组成的森林中为 m 棵树，则这个森林中边的总数量为()。{{ select(12) }}

• m
• n - 1
• n - m
• n - m - 1

13. 若一棵二叉树的中序遍历与后序遍历完全一致，则(()。({{ select(13) }}

• 任意节点没有右孩子
• 任意节点没有左孩子
• 该二叉树只存在根节点
• 任意节点只有一个孩子，可能是左孩子，也可能是右孩子

14. 一条直线最多可以将平面分为两份，两条直线最多可以将平面分为四份，三条直线最多可以将平面分为七份，十条直线最多可以将平面分为()份。{{ select(14) }}

• 49
• 55
• 56
• 104

15. 一根 27 厘米的细木杆，在第 3 厘米、7 厘米、11 厘米、17 厘米、23 厘米这五个位置上各有一只蚂蚁木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米( speed = 1 )。走到第 0 厘米或第 27 厘米会离开木杆。若蚂蚁们均头朝右( 27 厘米处 )，则全部离开木杆的时间为 24。所有蚂蚁都离开木杆的最小时间和最大时间分别为()。{{ select(15) }}

• 11 23
• 11 24
• 17 24
• 16 17

二，阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确在答题卡上涂“A”，错误涂“B”;除第16题1分外，判断题每题1.5分，选择题每题3分，共计40分)

(一)

■判断题

16. 当输入 x.d 的值为 0 时，第 22 行 if 结构输出值为 0。(){{ select(16) }}

• 正确
• 错误

17. 第 22 行 if 结构输出值恒为输入到 x.d 的值的两倍。(){{ select(17) }}

• 正确
• 错误

18. 程序执行结束时 x.b[1] 的值一定为字符 '1’。(){{ select(18) }}

• 正确
• 错误

■选择题

19. 程序第 18 行的输出恒为()。{{ select(19) }}

• 16 7
• 23 7
• 16 8
• 23 8

20. 若程序输入为 14 7，则第 22 行 if 结构输出值为()。{{ select(20) }}

• 14
• 21
• 7
• 0

21. 若程序输入为 1000000 1000000000000，则第 22 行 if 结构输出值为()。{{ select(21) }}

• 1000000000000
• 1000001000000
• 2000000000000
• 以上都不对

(二)

■判断题

22. 合法输入的程序输出结果可能等于 a[1] 的值。(){{ select(22) }}

• 正确
• 错误

23. 将第 7 行语句“int j = i + 1”修改为“int j = 1”，任意程序执行结果保持不变。(){{ select(23) }}

• 正确
• 错误

24. 第 13 行语句与第 14 行语句交换位置，任意程序执行结果保持不变。(){{ select(24) }}

• 正确
• 错误

■选择题

25. 若数组 a 是一个长度为 n 的排列，当输入排列 a 的顺序为()时，输出的答案最小。{{ select(25) }}

• 升序
• 降序
• a[1]必须为 1
• 与输人的顺序无关

26. 如上程序的时间复杂度最接近()。{{ select(26) }}

• O(n)
• O(n! )
• O(n$^n$)
• O(n!$^2$/ 2$^n$)

27. 若程序输入 n 的值为 6，输人数组值为 1 2 3 4 5 6，则程序输出为()。{{ select(27) }}

• 21
• 55
• 51
• 11

(三)

■判断题

28. 若输人 p.size() > s.size()，则程序输出一定为负整数 -1。(){{ select(28) }}

• 正确
• 错误

29. 若字符串 p 中字符均不重复，则执行中 pmt 数组的值恒为 0。(){{ select(29) }}

• 正确
• 错误

30. 对于任意合法输人，程序输出为大于等于 -1 且小于 s.size() 的整数数字。(){{ select(30) }}

• 正确
• 错误

■选择题

31. 若程序输人 s 为 “abcdabceabcf” , p 为 “aaa” , 则程序输出为()。{{ select(31) }}

• -1
• 0
• 4
• 8

32. 若程序输入 s 为 “abcdabceabcf” , p 为 “bcd” , 则程序输出为()。{{ select(32) }}

• -1
• 0
• 1
• 9

33. 若输入 s 由 500 个字符 a 与 1 个字符 b 任意排列组成，输入 p 为连续的 200 个字符 a，则程序输出最大可能为()。{{ select(33) }}

• -1
• 0
• 200
• 301

三、完善程序（单选题，每小题3分，共计30分）

(一) (求后序遍历)在二叉树的先序 ( 根左右 ) 、中序 ( 左根右 ) 、后序 ( 左右根 ) 遍历中，已知先序与中序就能唯一地确定二叉树的形态。

现对二叉树的每个节点给定一个唯一的字母字符编号，并已知其先序与中序遍历，计算并输出其对应后序遍历。 例如前序为ABDC，中序为DBAC时，程序输出后序应为DBCA。

34. (1)处应填()。{{ select(34) }}

• p1 > ir
• pr < i1
• p1 < pr
• i1 > ir

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

• p1
• pr
• i1
• i

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

• js = i
• js = i - 1
• js = pr - i
• js += 1

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

• js
• root - i1 + 1
• root
• root - 1

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

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

(二) (石子合并)桌面上从左到右放着 n( 1 ≤ n ≤ 20 ) 堆石子，其中 i 堆石子包含的石子数量为b$_i$ ( 1 ≤ b$_i$ ≤ 20 )。现在要将石子有序地合并成一堆。

规定每次能取任意的两堆石子合并成新的一堆，并将新的一堆的石子数，记为该次合并的花费。那么，n - 1 次合并后，石子将合并成一堆。

你需要寻找一种合并方案，使得花费总和最小。输出最小的花费总和。

例如有 4 堆石子，每堆依次为 3、5、6、7。则首先合并第一堆和第二堆，花费为 3 + 5 = 8，剩余 3 堆石子依次为 8、6、7; 再合并当前第二堆和第三堆，花费为 6 + 7 = 13; 剩余两堆石子依次为 8 和 13; 最后合并两堆花费为 8 + 13 = 21。

总花费最小为 8 + 13 + 21 = 42，其他合并方案的花费均大于等于 42。

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

• i
• 1 << i
• i + 1
• i * ( i + 1 ) / 2

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

• a[0]
• i / 2
• n - i
• 1

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

• i + j
• i - j
• j
• i

42. (4)处应填()。{{ select(42) }}

• dp[i]
• dp[i]
• dp[i - j]
• dp[i] + dp[i-j]

43. (5)处应填()。{{ select(43) }}

• i == 1
• i <= 3
• i % 2 == 0
• dp[i] == 1e9