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

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

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

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

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

struct Node { int data; Node* next; }

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

{{ select(3) }}

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

4. 对于入栈顺序为a，b，c，d，e的序列，下列（ ）不是合法的出栈序列。 {{ select(4) }}

• a，b，c，d，e
• e，d，c，b，a
• b，a，c，d，e
• c，d，a，e，b

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

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

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

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

7. 对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照进栈 S 、出栈 S 、进队列 Q 、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1 、 e2 、 e3 、 e4 、 e5 和 e6 进栈，队列 Q 依次有数据 e2 、 e4 、 e3 、e6 、 e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。 {{ select(7) }}

• 2
• 3
• 4
• 6

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

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

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

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

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.对于有n个顶点、m条边的无向连通图（m>n）,需要删掉（）条边才能使其成为一棵树。 {{ select(11) }}

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

12.如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？ {{ select(12) }}

• 16
• 15
• 17
• 32

13.在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。 {{ select(13) }}

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

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

• 1
• 2
• 2或3
• 3

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

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

16. 根节点高度为 1，一颗拥有 2023 个节点的三叉树高度至少为（）。

{{ select(16) }}

• 6
• 7
• 8
• 9

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

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

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

• EDBGFCA
• EDGBFCA
• DEBGFCA
• DBEGFCA

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

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

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

{{ select(20) }}

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