1. 链表不具备的特点是( )。 {{ select(1) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事物估计存储空间大小
• 所需存储空间与存储元素个数成正比

2. 下图中所使用的数据结构是（ ）。 {{ select(2) }}

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

3. 表达式 a * (b + c) * d 的后缀表达式为( )，其中 * 和 + 是运算符。 {{ select(3) }}

• * * a + b c d
• a b c + * d *
• a b c + d * *
• a * * + b c d

4. 有 $6$ 个元素，按照 $6 、 5 、 4 、 3 、 2 、 1$ 的顺序进入栈 S ，请问下列哪个出栈序列是非法的（）。 {{ select(4) }}

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

5. 链表和数组的区别包括（）。 {{ select(5) }}

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

6. 对假设栈 $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(6) }}

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

7. 对表达式 a + (b - c) * d 的前缀表达式为（ ），其中 + 、 - 、 * 是运算符。 {{ select(7) }}

• * + a - b c d
• + a * - b c d
• a b c - d * +
• a b c - + d

8. 以下哪组操作能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的效果（其中， $next$ 域为结点的直接后继， prev 域为结点的直接前驱）：（ ）。 {{ select(8) }}

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

9. 假设有一个链表的节点定义如下：

   struct Node {
       int data;
       Node* next;
   };
   

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

{{ select(9) }}

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

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

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

11. 给定一个空栈，支持入栈和出栈操作。若入栈操作的元素依次是 1 2 3 4 5 6 ，其中 $1$ 最先入栈，$6$ 最后入栈，下面哪种出栈顺序是不可能的？ （ ） {{ select(11) }}

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

12. 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。 {{ select(12) }}

• A0, A1 , A2, A3
• A0, A1, A3, A2
• A0, A2, A1, A3
• A0, A3, A1, A2

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

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

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

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

15. 考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。 {{ select(15) }}

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

16. 以下对数据结构的表述不恰当的一项为：（）。 {{ select(16) }}

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

17. 根节点高度为 $1$，一颗拥有 $2023$ 个节点的三叉树高度至少为（）。 {{ select(17) }}

• $6$
• $7$
• $8$
• $9$

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

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

19. 给定一棵二叉树，其前序遍历结果为: ABDECFG，中序遍历结果为: DEBACFG。请问这棵树的正确后序遍历结果是什么？（） {{ select(19) }}

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

20. 考虑一个有向无环图，该图包含四条有向边：$1\to 2$, $1\to 3$, $2\to 4$ 和 $3\to 4$。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（）

{{ select(20) }}

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

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

• 图的边数
• 图的边数的 $2$ 倍
• 图的点数
• 图的点数的 $2$ 倍

22. 已知二叉树的前序遍历为 [A, B, D, E, C, F, G] ，中序遍历为 [D, B, E, A, F, C, G]，求二叉树的后序遍历。

{{ select(22) }}

• [𝐷, 𝐸, 𝐵, 𝐹, 𝐺, 𝐶, 𝐴]
• [𝐷, 𝐸, 𝐵, 𝐹, 𝐺, 𝐴, 𝐶]
• [𝐷, 𝐵, 𝐸, 𝐹, 𝐺, 𝐶, 𝐴]
• [𝐷, 𝐸, 𝐵, 𝐹, 𝐺, 𝐴, 𝐶]