2021年408计算机学科专业基础考研真题答案及解析

本文提供2021年408计算机学科专业基础考研真题答案及解析，以下为具体内容

1、已知头指针 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);

2、已知初始为空的队列 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

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

A、 295

B、 300

C、 301

D、 306

4、某森林 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

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

A、 89

B、 200

C、 208

D、 289

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

A、 16

B、 20

C、 23

D、 25

7、给定如下有向图，该图的拓扑有序序列的个数是（ ）。

A、 1

B、 2

C、 3

D、 4

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

A、 26，3，14，6

B、 25，3，14，6

C、 21，3，14，6

D、 15，3，14，6

1、试题答案：D

试题解析：

【考点】本题考查单循环链表的删除操作
【解析】该单循环链表带头结点，因此要删除的元素在头结点之后的元素。首先看A选项，h->next = h->next->next;此时q = h->next；q指向的是第一个元素的next元素，free(q);操作删除的不是第一个元素，因此A选项错误。在B选项中，没有考虑仅有一个元素的情况。若只有一个元素，删除后尾指针应当指向头结点，因此B选项错误。在C选项中，if条件语句错误。D选项能正确删除第一个元素且考虑了仅有一个元素的情况，故本题选D。

2、试题答案：D

试题解析：

【考点】本题考查队列的基本操作
【解析】本题的队列与传统的队列不同，我们将入队列的一端称为A端，将既能入队又能出队的一端称为B端，能够从一端插入另一端出队的结构为队列，能够从一端插入一端出队的结构为栈。因此本题中的A端插入+B端出队构成一个队列；B端的插入+B端的出队构成一个栈。对上述选项分别进行模拟。A选项5、4、3、1为倒序，是栈的出栈序列，因此5、4、3、1从B端插入，2从A端插入。具体过程为：1从B插入->2从A插入->3从B插入->4从B插入->5从B插入->5从B端出队->4从B端出队->3从B端出队->1从B端出队->2从B端出队。因此A选项正确。B选项5、3为逆序，1、2、4为正序。由此可知5、3从B插入从B端出队，1、2、4从A端插入，从B端出队。具体过程为：1从A插入->2从A插入->3从B插入->4从A插入->5从B插入->5从B端出队->3从B端出队->1从B端出队->2从B端出队->4从B端出队。因此B选项正确。C选项中4、2、1逆序，从B端插入从B端出队，3、5正序，从A端插入从B端出队。。具体过程为：1从B插入->2从B插入->3从A插入->4从B插入->4从B端出队->2从B端出队->1从B端出队->3从B端出队->5从A端插入->5从B端出队。因此C选项正确。D选项中4之前1、2、3已经入队，在这种情况下3不能在A、B之间，因此D选项错误，故本题选D。

3、试题答案：B

试题解析：

【考点】本题考查二维数组的存储
【解析】注意本题是按行优先存储，并且元素存储的首地址为A[0][0]。设将数组有J列，则A[3][3]之前存储了第0行全部元素，共J个；第1行的元素，共J个；第2行全部的元素，共J个；第3行的三个元素A[3][0]、A[3][1]、 A[3][2]，因此add(A[3][3])=100+3*J+3=220。解得，J=39。add(A[5][5])=100+5*J+5=300。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查森林与二叉树的转换以及二叉树的遍历
【解析】根据二叉树的先序和中序得到二叉树的结构如下图所示：

二叉树转换为森林的步骤为：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连续删除。直到所有这些根结点与右孩子的连线都删除为止。
将每棵分离后的二叉树转换为树。将二叉树转为森林后的结构为：

故本题选C。

5、试题答案：B

试题解析：

6、试题答案：D

试题解析：

【考点】本题考查平衡树的插入
【解析】一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
（1）左子树与右子树的高度之差的绝对值小于等于１；（2）左子树和右子树也是平衡二叉排序树。
根据上述平衡树的性质插入关键字23后的树结构如下所示：

检查结点，发现结点20的左右子树的高度分别为1、3，因此不平衡。从20向下搜寻三个结点，分别为20、30、25，调整后的平衡二叉树为：

根结点关键字为25，故本题选D。

7、试题答案：A

试题解析：

【考点】本题考查拓扑排序的应用
【解析】拓扑排序的针对有向图的排序方法，求拓扑排序的方法为：初始时拓扑序列为空；任选一个入度为0的点放入拓扑序列中，同时删除该顶点以及从该顶点出发的弧；重复上述操作直至不存在入度为0的顶点。按照该方法，初始时入度为0的点仅有A，将A加入拓扑序列，删除从A出发的弧，此时入度为0的点仅有B。将B加入拓扑序列，删除从B出发的弧，此时入度为0的点仅有C。将C加入拓扑序列，删除从C出发的弧，此时入度为0的点仅有D。将D加入拓扑序列，删除从D出发的弧，此时入度为0的点仅有E。将E加入拓扑序列，删除从E出发的弧，此时入度为0的点仅有F。将F加入拓扑序列。因此上图仅有一个拓扑序列为：A->B->C->D->E->F。故本题选A。

8、试题答案：C

试题解析：