本题代码与代码选项均使用原卷截图；截图中的拼写和排版按原样保留。

一、单项选择题

共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项。

1. 信息论之父是（　）。

{{ select(1) }}

• 图灵
• 冯诺依曼
• 克劳德·香农
• 肖克利

2. 计算机网络最主要的优点是（　）。

{{ select(2) }}

• 运算速度快
• 共享资源
• 精度高
• 存储容量大

3. 为了区分汉字与 ASCII 码，计算机中汉字编码的最高位为（　）。

{{ select(3) }}

• 1
• 0
• -1
• 2

4. 插入排序的更新数据次数为多少次（　）。

{{ select(4) }}

• 1
• $N-1$
• $N$
• $N+1$

5. 字符串“abcdefghij”的非空子串数量为（　）。

{{ select(5) }}

• 55
• 56
• 57
• 58

6. 小明用十六进制、八进制和十进制写了一个等式：$52-33=19$。式子中的三个数的进制可以不同，52、33、19 有可能分别为（　）。

{{ select(6) }}

• 十进制、十进制、八进制
• 八进制、十六进制、十进制
• 十进制、十六进制、八进制
• 十进制、八进制、十六进制

7. 已知初始为空的队列 $Q$ 的一端既能进行入队操作又能进行出队操作，另一端能进行入队操作。若 $Q$ 的入队序列是 1，2，3，4，5，则不可能得到的出队序列是（　）。

{{ select(7) }}

• 5，4，3，1，2
• 5，3，1，2，4
• 4，2，1，3，5
• 4，1，3，2，5

8. 有一个二维数组 int A[100][100]，将 $A$ 数组按行优先的顺序存入从 $SA$ 开始的连续存储单元中，则元素 A[35][84] 存储的结束地址为（　）。

{{ select(8) }}

• $SA+13936$
• $SA+13937$
• $SA+14340$
• $SA+14341$

9. 已知指针指向一个带头结点的非空单循环链表，结点结构包含 data、next，其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针，h 指向链表的首部。free(q) 表示释放 q 指向的内存。现要删除该链表的第一个元素，正确的语句序列是（　）。

{{ select(9) }}

• A
• B
• C
• D

10. 若有变量 int a, float x, y，且 a=7, x=2.5, y=4.7，则表达式 x+a%3*(int)(x+y)%2/4 的值为（　）。

{{ select(10) }}

• 2.500000
• 2.750000
• 3.500000
• 0.000000

11. 后缀表达式为 abc+*d*，假设 a、b、c、d 的值分别为 5、6、7、8，则表达式的结果为（　）。

{{ select(11) }}

• 616
• 520
• 450
• 445

12. 五种不同颜色的珠子串成一圈项链，问有多少种不同的方法（　）。

{{ select(12) }}

• 23
• 24
• 60
• 120

13. 有男女各 5 人，其中 3 对是夫妻。他们坐成一排，若每对夫妻必须相邻而坐，问有多少种方法？

{{ select(13) }}

• 5040
• 20160
• 40320
• 80640

14. 考虑如下算法：

试求 dight(12345, 2) 的返回值（　）。

{{ select(14) }}

• 1
• 2
• 3
• 4

15. 下列不满足分治思想的是（　）。

{{ select(15) }}

• 二分搜索
• 归并排序
• 快速排序
• 霍夫曼编码

二、阅读程序

判断题选择“正确”或“错误”。除特殊情况外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分。

程序（1）

判断题

16. 第 12 行可以替换为 people *p[100005]。（　）

{{ select(16) }}

• 正确
• 错误

17. 第 41 行的 % n 可以去掉。（　）

{{ select(17) }}

• 正确
• 错误

18. 此程序的时间复杂度是 $O(\max(n,m))$。（　）

{{ select(18) }}

• 正确
• 错误

19. 局部变量采用动态存储。（　）

{{ select(19) }}

• 正确
• 错误

选择题

20. 当输入为以下数据时，输出为（　）。

7 3
0 singer
0 reader
0 mengbier
1 thinker
1 archer
0 writer
1 mogician
0 3
1 1
0 2

{{ select(20) }}

• singer
• mengbier
• writer
• mogician

21. 定义一个结构体变量 people a，a 所占内存为多少？（4 分）

{{ select(21) }}

• 6
• 8
• 12
• 16

程序（2）

判断题

22. 输出可能为 -1。（　）

{{ select(22) }}

• 正确
• 错误

23. 0x7fffffff 可以用 INT_MAX 替换。（　）

{{ select(23) }}

• 正确
• 错误

24. 第 31 行等价于 minn = min(cnt, minn)。（　）

{{ select(24) }}

• 正确
• 错误

选择题

25. 当 $N=7$ 时，程序输出为（　）。

{{ select(25) }}

• 0
• 1
• 3
• 7

26. 当 $N=6$ 时，第 11 行 for 循环的循环次数为（　）。

{{ select(26) }}

• 0
• 1
• 3
• 6

27. 当 $N=163$ 时，程序输出为（　）。

{{ select(27) }}

• 0
• 3
• 157
• 16

程序（3）

判断题

28. 5 | 6 的结果为 6。（　）

{{ select(28) }}

• 正确
• 错误

29. sizeof(f) 的返回值为 4。（　）

{{ select(29) }}

• 正确
• 错误

30. 1 << 18 表示 $2^{17}$。（　）

{{ select(30) }}

• 正确
• 错误

选择题

31. 此程序的时间复杂度为（　）。

{{ select(31) }}

• $O(n)$
• $O(2^n)$
• $O(\log_2 n^2)$
• $O(n\cdot 2^n)$

32. 若输入为：

4 10
5 6 3 7

则输出为（　）。

{{ select(32) }}

• 1
• 3
• 5
• 6

33. 若输入为：

5 12
11 12 36 56 8

则输出为（　）。

{{ select(33) }}

• 4
• 5
• 6
• 7

三、完善程序

共 10 题，每题 3 分，共计 30 分。

程序（1）：翻译软件

假设内存中有 $M$ 个单元，每个单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 $M-1$，软件会将新单词存入一个未使用的内存单元；若内存中已存入 $M$ 个单词，软件会清空最早进入内存的那个单词，腾出单元来存放新单词。

假设一篇英语文章的长度为 $N$ 个单词。给定这篇待译文章，输出翻译软件需要去外存查找多少次词典。

34. (1) 处应填（　）。

{{ select(34) }}

• x
• !x
• inq[x]
• !inq[x]

35. (2) 处应填（　）。

{{ select(35) }}

• continue
• break
• ans++
• q.pop(x)

36. (3) 处应填（　）。

{{ select(36) }}

• q.front() - 1
• q.size()
• q.front()
• int[q]

37. (4) 处应填（　）。

{{ select(37) }}

• q.pop(x)
• q.front()++;
• ans++
• q.pop()

38. (5) 处应填（　）。

{{ select(38) }}

• x
• 0
• 1
• q.front()

程序（2）：手指排列

如果把五根手指——拇指、食指、中指、无名指和小指分别编号为 1、2、3、4 和 5，当它们按正常顺序排列时，形成了 5 位数 12345；当你交换无名指和小指的位置时，会形成 5 位数 12354；当你把五根手指的顺序完全颠倒时，会形成 54321。

在所有能够形成的 120 个 5 位数中，12345 最小，它表示 1；12354 第二小，它表示 2；54321 最大，它表示 120。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和它们代表的数字：

3 位数	代表的数字
123	1
132	2
213	3
231	4
312	5
321	6

科学家会告诉你一个要加上的很小的数。把用手指表示的数与这个数相加，并根据相加的结果改变手指的排列顺序。程序中，$N$ 表示手指数，$M$ 表示要加上的数。

39. (1) 处应填（　）。

{{ select(39) }}

• 0
• 1
• 2
• 3

40. (2) 处应填（　）。

{{ select(40) }}

• 0
• 1
• N
• M

41. (3) 处应填（　）。

{{ select(41) }}

• 0
• finger[i]
• used[i]
• finger[p]

42. (4) 处应填（　）。

{{ select(42) }}

• 0
• 1
• i
• N

43. (5) 处应填（　）。

{{ select(43) }}

• used[i]
• fs[i]
• used[i+1]
• fs[i+1]