2021年408真题数据结构篇

Answer 1

第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

01. 已知头指针h指向一个带头结点的非空单循环链表，结点结构为[公式] ，其中next是指向直接后继结点的指针，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。

A. h->next = h->next->next; q = h->next; free(q);

B. q = h->next; h->next = h->next->next; free(q);

C. q = h->next; h->next = q->next; if (p != q) p = h; free(q);

D. q = h->next; h->next = q->next; if (p == q) p = h; free(q);

解答：q = h->next; h->next = q->next; if (p == q) p = h; free(q); 本题选D。

02. 已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1, 2, 3, 4, 5，则不能得到的出队序列是（ ）。

A. 5, 4, 3, 1, 2

B. 5, 3, 1, 2, 4

C. 4, 2, 1, 3, 5

D. 4, 1, 3, 2, 5

解答：简化为栈+队列。观察选项，D不正确，整体顺序如下：1从A端入队→2从A端入队→3从B端入队→4从B端入队→5从B端入队→5从B端出队→4从B端出队→3从B端出队→1从B端出队→2从B端出队，故本题选D。

03. 二维数组A按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地址是100, A[3][3]的存储地址是220 ，则元素A[5][5]的存储地址是（ ）。

A. 295

B. 300

C. 301

D. 306

解答：列出二元一次方程组，解得A[5][5]的存储地址为300，故本题选B。

04. 某森林F对应的二叉树为T，若T的先序遍历序列是a, b, d, c, e, g, f，中序遍历序列是b, d, a, e, g, c, f，则F中树的棵数是（ ）。

A. 1

B. 2

C. 3

D. 4

解答：构造二叉树，右轴定义为根结点的所有后代结点只能通过从根结点开始通过右指针才能访问。本题选C。

05. 若某二叉树有5个叶结点，其权值分别为10, 12, 16, 21, 30，则其最小的带权路径长度(WPL)是（ ）。

A. 89

B. 200

C. 208

D. 289

解答：构造哈夫曼树，使得带权路径长度最小，故本题选B。

06. 给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（ ）。

A. 16

B. 20

C. 23

D. 25

解答：插入关键字23，进行调整，本题选D。

07. 给定如下有向图，该图的拓扑有序序列的个数（ ）。

A. 1

B. 2

C. 3

D. 4

解答：根据图的拓扑排序过程，只有一种可能，故本题选A。

08. 使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2, 3, 4, 5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新为（ ）。

A. 2