1. （2019年第6题）链表不具有的特点是（）

{{ select(1) }}

• 插入删除不需要移动元素
• 不必事先估计存储空间
• 所需空间与线性表长度成正比
• 可随机访问任一元素

2. （2019年第8题）一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 $1$，若某结点的下标为 $i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（）。

{{ select(2) }}

• 6
• 10
• 15
• 12

3. （2019年第14题）假设一棵二叉树的后序遍历序列为 $\texttt{DGJHEBIFCA}$，中序遍历序列为 $\texttt{DBGEHJACIF}$，则其前序遍历序列为（）。

{{ select(3) }}

• $\texttt{ABCDEFGHIJ}$
• $\texttt{ABDEGHJCFI}$
• $\texttt{ABDEGJHCFI}$
• $\texttt{ABDEGHJFIC}$

4. （2020年第7题）链表不具有的特点是（）。

{{ select(4) }}

• 可随机访问任一元素
• 不必事先估计存储空间
• 插入删除不需要移动元素
• 所需空间与线性表长度成正比

5. （2020年第8题）有 $10$ 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

{{ select(5) }}

• 9
• 10
• 11
• 12

6. （2020年第11题）下图中所使用的数据结构是（ )。

{{ select(6) }}

• 栈
• 队列
• 二叉树
• 哈希表

7. （2020年第12题）独根树的高度为 $1$。具有 $61$ 个结点的完全二叉树的高度为（ ）。

{{ select(7) }}

• 7
• 8
• 5
• 6

8. （2021年第5题）对于入栈顺序为 $a, b, c, d, e$ 的序列，下列（ ）不是合法的出栈序列。

{{ select(8) }}

• $a, b, c, d, e$
• $e, d, c, b, a$
• $b, a, c, d, e$
• $c, d, a, e, b$

9. （2021年第6题）对于有 $n$ 个顶点、$m$ 条边的无向连通图 $(m>n)$，需要删掉（ ）条边才能使其成为一棵树。

{{ select(9) }}

• $n-1$
• $m-n$
• $m-n-1$
• $m-n+1$

10. （2021年第8题）如果一棵二叉树只有根结点，那么这棵二叉树高度为 $1$。请问高度为 $5$ 的完全二叉树有 （ ）种不同的形态？

{{ select(10) }}

• 16
• 15
• 17
• 32

11. （2021年第9题）表达式 $\texttt{a*(b+c)*d}$ 的后缀表达式为( )，其中 $\texttt{*}$ 和 $\texttt{ + }$ 是运算符。

{{ select(11) }}

• $\texttt{a+bcd}$
• $\texttt{abc+*d*}$
• $\texttt{abc+d}$
• $\texttt{*a*+bcd}$

12. （2021年第11题）在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

{{ select(12) }}

• 枚举
• 贪心
• 递归
• 动态规划

13. （2021年第14题）以 $a$ 为起点，对下边的无向图进行深度优先遍历，则 $b,c,d,e$ 四个点中有可能作为最后一个遍历到的点的个数为（ ）。

{{ select(13) }}

• 1
• 2
• 3
• 4

14. （2022年第2题）有 $6$ 个元素，按照 $6,5,4,3,2,1$ 的顺序进入栈 $S$，请问下列哪个出栈序列是非法的（ ）。

{{ select(14) }}

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

15. （2022年第4题）链表和数组的区别包括（ ）。

{{ select(15) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确

16. （2022年第5题）对假设栈 $S$ 和队列 $Q$ 的初始状态为空。存在 $e_1\sim e_6$ 六个互不相同的数据，每个数据按照进栈 $S$、出栈 $S$、进队列 $Q$、出队列 $Q$ 的顺序操作，不同数据间的操作可能会交错。已知栈 $S$ 中依次有数据 $e_1$、$e_2$、$e_3$、$e_4$、$e_5$ 和 $e_6$ 进栈，队列 $Q$ 依次有数据 $e_2$、$e_4$、$e_3$、$e_6$、$e_5$ 和 $e_1$ 出队列。则栈 $S$ 的容量至少是（ ）个数据。

{{ select(16) }}

• $2$
• $3$
• $4$
• $6$

17. （2022年第6题）对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。

{{ select(17) }}

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d

18. （2022年第7题）假设字母表 $\{a,b,c,d,e\}$ 在字符串出现的频率分别为 $10\%$，$15\%$，$30\%$，$16\%$，$29\%$。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 $d$ 的编码长度（ ）位。

{{ select(18) }}

• $1$
• $2$
• $2$ 或 $3$
• $3$

19. （2022年第8题）一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

{{ select(19) }}

• $8$、$18$
• $10$、$18$
• $8$、$19$
• $10$、$19$

20. （2022年第9题）考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

{{ select(20) }}

• $N-1$
• $N$
• $N+1$
• $N^2$

21. （2022年第10题）以下对数据结构的表述不恰当的一项为：（ ）。

{{ select(21) }}

• 图的深度优先遍历算法常使用的数据结构为栈。
• 栈的访问原则后进先出，队列的访问原则是先进先出。
• 队列常常被用于广度优先搜索算法。
• 栈与队列存在本质不同，无法用栈实现队列。

22. （2022年第11题）以下哪组操作能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

{{ select(22) }}

• p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

23. （2023年第4题）假设有一个链表的节点定义如下：

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 $42$，并使新节点成为链表的第一个节点，下面哪个操作是正确的？

{{ select(23) }}

• Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; newNode->data = 42; head->next = newNode;
• Node* newNode = new Node; newNode->data = 42; newNode->next = head;

24. （2023年第5题）根节点的高度为 $1$，一棵拥有 $2023$个节点的三叉树高度至少为（）。

{{ select(24) }}

• 6
• 7
• 8
• 9

25. （2023年第8题）后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是

{{ select(25) }}

• ((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

26. （2023年第10题）假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 $5\%,9\%,12\%,13\%,16\%,45\%$。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码?

{{ select(26) }}

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

27. （2023年第11题）给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?

{{ select(27) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

28. （2023年第12题）考虑一个有向无环图，该图包含 $4$ 条有向边：$(1,2),(1,3),(2,4)$ 和 $(3,4)$。以下哪个选项是这个有向无环图的一个有效的拓扑排序?

{{ select(28) }}

• 4,2,3,1
• 1,2,3,4
• 1,2,4,3
• 2,1,3,4

29. （2024年第11题）在无向图中，所有顶点的度数之和等于（ ）。

{{ select(29) }}

• 图的边数
• 图的边数的两倍
• 图的顶点数
• 图的顶点数的两倍

30. （2024年第12题）已知二叉树的前序遍历为 $[A, B, D, E, C, F, G]$，中序遍历为 $[D, B, E, A, F, C, G]$，请问该二叉树的后序遍历结果是？（ ）

{{ select(30) }}

• $[D, E, B, F, G, C, A]$
• $[D, E, B, F, G, A, C]$
• $[D, B, E, F, G, C, A]$
• $[D, B, E, F, G, A, C]$

31. （2024年第13题）给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 $1\ 2\ 3\ 4\ 5\ 6$，其中 $1$ 最先入栈，$6$ 最后入栈，下面哪种出栈顺序是不可能的？（ ）

{{ select(31) }}

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

32. （2025年第4题）用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？

{{ select(32) }}

• $176$
• $186$
• $196$
• $206$

33. （2025年第5题）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？

{{ select(33) }}

• 顶点数
• 边数
• 顶点数 + 边数
• 顶点数 $\times 2$

34. （2025年第14题）一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？

{{ select(34) }}

• $499$
• $512$
• $500$
• $501$

35. （2025年第15题）给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$。我们按顺序处理输入的整数队列 $A: 7, 5, 8, 3, 1, 4, 2$。对于队列 $A$ 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 $S$；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素，并加入到队列 $P$ 的末尾；如果该数是偶数，且栈 $S$ 为空，则不进行任何操作。当队列 $A$ 中的所有数都处理完毕后，队列 $P$ 的内容是什么？

{{ select(35) }}

• $5,1,3$
• $7,5,3$
• $3,1,5$
• $5,1,3,7$