30 个选择题，总共 60 分。

一、选择题

1. 以下哪个编码不能表示数字（）

{{ select(1) }}

• $[00000000]$反
• $[11111111]$反
• $[10000000]$补
• $[10000000]$原

2. 人工智能之父是（） {{ select(2) }}

• 图灵
• 姚期智
• 周志华
• 冯·诺伊曼

3. $0,1,2,3,4,5$ 可以组成 ( ) 个没有重复数字和前导零的五位奇数。

{{ select(3) }}

• $288$
• $320$
• $144$
• $224$

4. 以下对于算法的描述中，完全正确的是： {{ select(4) }}

• 二分法是指将问题一分为二，二分为四，四分为八，再逐一解决分解出的小问题，最终解决整个问题。
• 枚举算法是将可能的答案一一尝试，枚举算法可能会借助 for 循环或递归实现。
• 一个算法可能没有输出，但不能没有输入。
• 选择，冒泡，插入排序都是稳定的排序算法。

5. $10$ 个三好学生名额分配到 $7$ 个班级，每个班级至少有一个名额，一共有( )种不同的分配方案 {{ select(5) }}

• $84$
• $72$
• $56$
• $504$

6. 三个男生和三个女生站成一排，要求恰好有两个女生相邻，问有多少种方案（）

   {{ select(6) }}

• $432$
• $576$
• $192$
• $72$

7. 一个链表中，每一个结点有一个 next 指针指向下一个结点，现在想要删除链表中结点 $p$ 的下一个结点，正确的操作是（） {{ select(7) }}

• free(p->next);
• temp = p->next; p->next = temp->next; free(temp);
• temp = p->next; temp->next = p->next; free(temp);
• temp = p->next; free(temp);

8. 入栈顺序为 $1,2,3,4,5$，则不可能的出栈顺序为（） {{ select(8) }}

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

9. 下列关于线性表的叙述中，错误的是？ {{ select(9) }}

• 顺序表在内存中的存储单元地址必须连续
• 链表在内存中的存储单元地址连续不连续均可
• 顺序表插入元素不需要移动任何元素的位置
• 双向链表插入元素不需要移动任何元素的位置

10. 往一个初始为空的顺序表中依次插入 3,5,2,4,1，且满足任意时刻顺序表中的元素从左至右都是升序的，则插入过程中总共移动了（ ）次元素。 {{ select(10) }}

• $4$
• $7$
• $8$
• $10$

11. FIFO,LILO 形容的是哪一个数据结构？ {{ select(11) }}

• 顺序表
• 双向链表
• 栈
• 队列

12. 已知包含 $7$ 个节点的二叉树的前序遍历序列为 1,2,4,3,5,6,7，中序遍历序列为 4,2,1,5,3,7,6，则其后序遍历序列为（ ） {{ select(12) }}

• 2,3,4,5,6,7,1
• 2,4,3,5,6,7,1
• 3,5,6,7,4,1,2
• 4,2,5,7,6,3,1

13. 完全二叉树的顺序存储方案，是指将完全二叉树的节点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根节点存放在数组的 $1$ 号位置，则第 $k$ 号节点的右儿子节点如果存在的话，应当存放在数组的（ ）号位置。 {{ select(13) }}

• $k+1$
• $k+2$
• $2k+1$
• $2k+2$

14. 有 $10$ 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图 {{ select(14) }}

• $9$
• $10$
• $11$
• $12$

15. 关于拓扑排序，下面说法正确的是？ {{ select(15) }}

• 所有连通的有向无环图都可以实现拓扑排序
• 对同一个图而言，拓扑排序的结果是唯一的
• 拓扑排序中入度为 $0$ 的节点总会排在入度大于 $0$ 的节点的前面
• 拓扑排序结果序列中的第二个节点一定是入度为 $1$ 的点

16. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 $G$ 有 $10$ 个顶点，则它共有（ ）条边。

{{ select(16) }}

• $9$
• $45$
• $55$
• $90$

17. 将 $6$ 个一模一样的苹果放到 $3$ 个一样的盘子中，允许有的盘子空着不放，一共有（ ）种放法。 {{ select(17) }}

• $5$
• $6$
• $7$
• $8$

18. 甲、乙、丙、丁、戊五人站在一排，要求甲、乙均不与丙相邻，不同排法有（ ）种。

{{ select(18) }}

• $12$
• $24$
• $36$
• $54$

19. $8$ 次射击,命中 $3$ 次,其中恰有 $2$ 次连续命中的情形有（ ）种

{{ select(19) }}

• $15$
• $30$
• $45$
• $60$

20. 一棵层数为 $n$ 的满二叉树有（ ）个结点？

{{ select(20) }}

• $n$
• $2^n$
• $2^{n-1}$
• $2^n-1$

21. 在 C++ 程序中，表达式 130 | 10 的值为

{{ select(21) }}

• $13$
• $1$
• $120$
• $138$

22. 八进制数$(12345670)$₈和$(07654321)$₈的和为（）。 {{ select(22) }}

• $(22222221)$₈
• $(21111111)$₈
• $(22111111)$₈
• $(22222211)$₈

23. 后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是（） {{ select(23) }}

• ( ( 6 - ( 2 + 3 ) ) * ( 3 + 8 / 2 ) ) ^ 2 + 3
• 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
• ( 6 - ( 2 + 3 ) ) * ( ( 3 + 8 / 2 ) ^ 2 ) + 3
• 6 - ( ( 2 + 3 ) * ( 3 + 8 / 2 ) ) ^ 2 + 3

24. 假设有一组字符 {$a,b,c,d,e,f$}，对应的频率分别为 $5\%$，$9\%$，$12\%$，$13\%$，$16\%$，$45\%$，请问以下哪个选项是字符 $a,b,c,d,e,f$ 分别对应的一组哈夫曼编码？（） {{ select(24) }}

• 1111, 1110, 101, 100, 110, 0
• 1010, 1001, 1000, 011, 010, 00
• 000, 001, 010, 011, 10, 11
• 1010, 1011, 110, 111, 00, 01

25. 在计算机中，以下哪个选项描述的数据存储容量最小？（） {{ select(25) }}

• 字节（byte）
• 比特（bit）
• 字（word）
• 千字节（kilobyte）

26. 以下哪个不是操作系统？（） {{ select(26) }}

• Linux
• Windows
• Android
• HTML

27. 前缀表达式 $+3*2+5\ 12$ 的值是（）。

    {{ select(27) }}

• $23$
• $25$
• $37$
• $65$

28. 一棵完全二叉树上有 $1001$ 个节点，其中叶子节点的个数是？

    {{ select(28) }}

• $500$
• $501$
• $499$
• $502$

29. 对下图从 $1$ 出发进行 DFS，哪个是可能的 DFS 序列？

{{ select(29) }}

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

30. 对下图从 $1$ 出发进行 BFS，哪个是可能的 BFS 序列？

{{ select(30) }}

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