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

1. 下列关于顺序表与链表的对比，说法正确的是（ ）。 {{ select(1) }}

• 链表支持随机访问，访问任意元素的时间复杂度为O(1)
• 顺序表插入、删除元素的平均时间复杂度为O(n)，链表为O(1)
• 顺序表的存储不要求连续的内存空间，链表要求连续内存
• 顺序表比链表更适合频繁插入、删除元素的场景

2. 在长度为n的单向链表中，访问第i个位置元素的时间复杂度为（ ）。 {{ select(2) }}

• O(1)
• O(log n)
• O(n)
• O(n²)

3. 在单向链表中，若要在指针p所指结点的后方插入一个新结点，需要修改的指针数量为（ ）。 {{ select(3) }}

• 1个
• 2个
• 3个
• 4个

4. 下列场景中，最适合使用链表而非数组的是（ ）。 {{ select(4) }}

• 需要频繁随机访问元素的场景
• 元素数量固定，极少修改的场景
• 需要频繁在表头、表中插入删除元素的场景
• 需要连续存储大量数据的场景

5. 循环链表的核心特性是（ ）。 {{ select(5) }}

• 链表中存在多个头结点
• 尾结点的指针域指向头结点，整个链表形成一个环
• 每个结点包含两个指针域，分别指向前后结点
• 只能从表头开始遍历，无法反向遍历

6. 栈结构的核心操作特性是（ ）。 {{ select(6) }}

• 先进先出（FIFO）
• 先进后出（LIFO）
• 支持随机访问
• 两端均可插入删除

7. 若元素入栈序列为1、2、3、4、5，下列不可能出现的出栈序列是（ ）。 {{ select(7) }}

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

8. 递归函数调用与执行时，用于存储函数参数、返回地址和局部变量的数据结构是（ ）。 {{ select(8) }}

• 栈
• 队列
• 链表
• 数组

9. 队列结构的核心操作特性是（ ）。 {{ select(9) }}

• 先进后出
• 先进先出
• 只允许在一端进行插入删除
• 支持随机访问

10. 下列算法场景中，通常使用队列实现的是（ ）。 {{ select(10) }}

• 表达式求值
• 括号匹配校验
• 二叉树的层序遍历
• 二叉树的前序遍历

11. 若元素入栈序列为a、b、c、d，经过合法的入栈出栈操作后，第一个出栈的元素不可能是（ ）。 {{ select(11) }}

• a
• b
• c
• d

12. 下列场景中，不属于栈的典型应用的是（ ）。 {{ select(12) }}

• 操作系统的进程调度
• 函数调用的现场保护与恢复
• 逆波兰表达式求值
• 浏览器的前进后退功能

13. 一棵树中所有结点的总度数为24，则这棵树的结点总数为（ ）。 {{ select(13) }}

• 23
• 24
• 25
• 26

14. 一棵二叉树中，度为2的结点有15个，则该二叉树的叶子结点数量为（ ）。 {{ select(14) }}

• 14
• 15
• 16
• 17

15. 深度为5的满二叉树，总的结点数量为（ ）。 {{ select(15) }}

• 16
• 31
• 32
• 63

16. 一棵包含100个结点的完全二叉树，其中叶子结点的数量为（ ）。 {{ select(16) }}

• 49
• 50
• 51
• 52

17. 已知一棵二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，则该二叉树的后序遍历序列为（ ）。 {{ select(17) }}

• DEBFCA
• DBFACE
• DEFBCA
• DBEAFC

18. 哈夫曼树（最优二叉树）中，不存在度为多少的结点？（ ） {{ select(18) }}

• 0
• 1
• 2
• 3

19. 某森林包含3棵树，3棵树的结点数分别为4、5、6，将该森林转换为二叉树后，根结点的右子树的结点总数为（ ）。 {{ select(19) }}

• 3
• 4
• 10
• 11

20. 一棵非空二叉树的后序遍历序列与中序遍历序列完全相同，则该二叉树一定满足（ ）。 {{ select(20) }}

• 所有结点无左孩子
• 所有结点无右孩子
• 是一棵满二叉树
• 是一棵完全二叉树

21. 一个有10个顶点的完全无向图，其边的总数为（ ）。 {{ select(21) }}

• 10
• 45
• 90
• 100

22. 一个无向图有n个顶点、e条边，则所有顶点的度数之和为（ ）。 {{ select(22) }}

• n
• e
• 2n
• 2e

23. 某有向图中，所有顶点的入度之和为20，则该有向图的边总数与所有顶点的出度之和分别为（ ）。 {{ select(23) }}

• 10、20
• 20、20
• 20、10
• 40、20

24. 图的邻接矩阵存储方式，最适合应用于下列哪种场景？（ ） {{ select(24) }}

• 顶点数量多、边数极少的稀疏图
• 顶点数量少、边数多的稠密图
• 只需要存储边的信息，无需存储顶点信息
• 需要频繁遍历某个顶点的所有邻接顶点

25. 图的深度优先搜索（DFS）算法的实现，通常使用的数据结构是（ ）。 {{ select(25) }}

• 栈
• 队列
• 链表
• 数组

26. 下列关于无向图欧拉回路的说法，正确的是（ ）。 {{ select(26) }}

• 所有顶点的度数均为奇数，存在欧拉回路
• 所有顶点的度数均为偶数，存在欧拉回路
• 只有2个顶点的度数为奇数，其余为偶数，存在欧拉回路
• 顶点数量为偶数，一定存在欧拉回路

27. 一个包含n个顶点的连通无向图，其最小生成树的边数为（ ）。 {{ select(27) }}

• n
• n-1
• n+1
• 2n

28. 下列关于强连通图的说法，正确的是（ ）。 {{ select(28) }}

• 强连通图是针对无向图的概念
• 强连通图中任意两个顶点之间都存在双向的路径
• 无向连通图一定是强连通图
• 有向图中只要任意两个顶点之间有路径，就是强连通图

29. 下列关于图的存储的说法，错误的是（ ）。 {{ select(29) }}

• 邻接矩阵中，判断两个顶点之间是否有边的时间复杂度为O(1)
• 邻接表中，存储的空间复杂度与边数相关
• 无向图的邻接矩阵是对称矩阵
• 有向图的邻接矩阵中，第i行的非零元素个数等于第i个顶点的入度

30. 图的广度优先搜索（BFS）算法，核心遵循的遍历规则是（ ）。 {{ select(30) }}

• 按层次依次遍历顶点，先访问完当前层所有顶点，再访问下一层
• 沿着一条路径一直深入，直到无法继续再回溯
• 优先访问度数最大的顶点
• 优先访问权值最小的边对应的顶点

二、判断题（共 20 题，每题 2 分，共计 40 分；判断下列说法的正误，每题有且仅有一个正确选项）

31. 链表支持随机访问，访问任意位置元素的时间复杂度为O(1)。（ ） {{ select(31) }}

• 正确
• 错误

32. 在双向链表中，删除一个中间结点需要修改2个指针域。（ ） {{ select(32) }}

• 正确
• 错误

33. 顺序表的插入、删除操作平均需要移动约一半的元素，在频繁修改的场景下效率低于链表。（ ） {{ select(33) }}

• 正确
• 错误

34. 栈和队列都是限制存取位置的线性表，栈是先进后出，队列是先进先出。（ ） {{ select(34) }}

• 正确
• 错误

35. 入栈序列为1、2、3，经过合法操作后，出栈序列可以是3、1、2。（ ） {{ select(35) }}

• 正确
• 错误

36. 循环队列可以有效解决普通顺序队列的"假溢出"问题。（ ） {{ select(36) }}

• 正确
• 错误

37. 括号匹配、表达式求值问题，通常使用队列来解决。（ ） {{ select(37) }}

• 正确
• 错误

38. 树中的结点总数，等于所有结点的度数之和。（ ） {{ select(38) }}

• 正确
• 错误

39. 任意一棵非空二叉树中，叶子结点的数量总是比度为2的结点数多1。（ ） {{ select(39) }}

• 正确
• 错误

40. 满二叉树一定是完全二叉树，完全二叉树也一定是满二叉树。（ ） {{ select(40) }}

• 正确
• 错误

41. 二叉树的前序遍历序列中，根结点一定出现在序列的最开头。（ ） {{ select(41) }}

• 正确
• 错误

42. 哈夫曼树中，权值越大的叶子结点，离根结点的距离越远。（ ） {{ select(42) }}

• 正确
• 错误

43. 深度为h的二叉树，最多包含2^h个结点。（ ） {{ select(43) }}

• 正确
• 错误

44. 森林转换为二叉树后，原森林中第一棵树的根结点，就是转换后二叉树的根结点。（ ） {{ select(44) }}

• 正确
• 错误

45. 无向图中，边的总数等于所有顶点的度数之和。（ ） {{ select(45) }}

• 正确
• 错误

46. 包含n个顶点的有向完全图，边的总数为n*(n-1)。（ ） {{ select(46) }}

• 正确
• 错误

47. 邻接表存储方式，更适合用于存储稀疏图，空间利用率更高。（ ） {{ select(47) }}

• 正确
• 错误

48. 无向连通图存在欧拉回路的充要条件是：所有顶点的度数均为偶数。（ ） {{ select(48) }}

• 正确
• 错误

49. 图的最小生成树可能不唯一，但最小生成树的总权值一定是唯一的。（ ） {{ select(49) }}

• 正确
• 错误

50. 图的广度优先搜索（BFS）会沿着一条路径深入遍历，直到无法继续再回溯，因此需要栈来实现。（ ） {{ select(50) }}

• 正确
• 错误