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

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

1、下列对顺序存储的有序表（长度为n）实现给定操作的算法中平均时间复杂度为O(1)的是（ ）。

A、查找包含指定值元素的值

B、插入包含指定值元素的算法

C、删除第i个元素的算法

D、获取第i个值的算法

2、现有非空双向链表L，其结点结构为prer是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：“s->next=p->next;p->next=s;”，后，还要执行（ ）。

A、s->next->prer=p;s->prer=p;

B、p->next->prer=s;s->prer=p;

C、s->prer=s->next->prer;s->next->prer=s;

D、p->next->prer=s->prer;s->next->prer=p;

3、若采用三元组表存储结构存储稀疏矩阵M，则除三元组外，下列数据中还需要保存的是（ ）。I.M的行数II.M中包含非零元素的行数III.M的列数IV.M中包含非零元素的列数

A、仅I、III

B、仅I、II

C、仅III、IV

D、I、II、III、IV

4、在有6个字符组成的字符集S中，各个字符出现的频次分别为3，4，5，6，8，10，为S构造的哈夫曼树的加权平均长度为（ ）。

A、2.4

B、2.5

C、2.67

D、2.75

5、已知一棵二叉树的树形如图，若其后序遍历为f，d，b，e，c，a，则其先序列为（ ）。

A、aedfbc

B、acebdf

C、cabefd

D、dfebac

6、已知无向连通图G中各边的权值均为1，下列算法中一定能够求出图G中从某顶点到其余各个顶点最短路径的是（ ）。I.普利姆算法II.克鲁斯卡尔算法III.图的广度优先搜索

A、仅III

B、仅I、II

C、仅I、III

D、I、II、III

7、下列关于非空B树的叙述中，正确的是（ ）。I.插入操作可能增加树的高度II.删除操作一定会导致叶结点的变化III.查找某关键字一定是要查找到叶结点IV.插入的新关键字最终位于叶结点中

A、仅I

B、仅I、II

C、仅III、IV

D、仅I、II、IV

8、对含有600个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。

A、9

B、10

C、30

D、300

9、现有长度为5，初始为空的散列表HT，散列表函数H（K）=（k+4）%5，用线性探查再散列法解决冲突。若将关键字序列2022，12，25依次插入HT中，然后删除关键字25，则HT中查找失败的平均查找长度（ ）。

A、1

B、1.6

C、1.8

D、2.2

1、试题答案：D

试题解析：

本题是针对顺序有序表的基本操作。对于A，若采用顺序查找则平均时间复杂度为O(n)，若采用折半查找则平均时间复杂度为O(logn)，因此A错误。对于B，若要在顺序有序表中插入指定值的元素，首先需要查找该值待插入的位置，之后再在该位置插入值。查找操作的时间复杂度如选项A，插入操作由于需要移动待插入位置之后的所有元素，因此其时间复杂度为O(n)，综上插入包含指定值元素的算法的平均时间复杂度为O(n)，因此B错误。对于C，删除第i个元素需要将第i元素之后的所有元素向前移动一个单位，因此该删除操作的平均时间复杂度为O(n)，因此C错误。对于D，顺序表具有随机存储的特点，可以通过下标直接访问该值，因此获取第i个值的算法的平均时间复杂度为O(1)。故本题选D。

2、试题答案：C

试题解析：

对于A，s->next->prer此时指向的是s而非p，因此A错误。对于B，经过p->next=s这一步之后，p->next此时指向s，p->next->prer=p而非s，因此B错误。对于C，s->prer指向p，而s->next->prer指向s，该语句等价于s->prer=p，第二步s->next->prer指向s正确，因此C正确。对于D，s->prer指向null，s->next->prer指向s而非p，因此D错误。将C选项所示的步骤画图如下：

故本题选C。

3、试题答案：A

试题解析：

稀疏矩阵是指矩阵中非零元素<=50%，且分布无规律的矩阵。在存储稀疏矩阵时，仅存储非零元素即可。采用三元组的方法存储稀疏矩阵时，需要存储稀疏矩阵中非零元素的行号、列号、非零元素的值，无需再额外存储M中包含的非零元素的行数和列数，因此II和IV错误。除了要存储非零元素，三元组还需要存储矩阵的规模，即存储矩阵的行数和列数，因此I和III正确，故本题选A。

4、试题答案：B

试题解析：

构造Huffman树的思想为：给定n个权值，构成n棵二叉树的集合F，在F中选取两棵根结点的权值最小的树，作为左右子树，构建一个新的树，使新树的权值为左右子树的和。在F中删除这两棵树，并在F添加新的二叉树的根结点的值。重复上述步骤直至F中只有一棵树，该树即为Huffman树。根据题干所示的字符频次构造哈夫曼树如下：

树的带权路径长度为树中所有叶子结点的带权路径长度之和。哈夫曼树为带权路径长度最小的二叉树。树的带权路径长度为树中所有叶子结点的带权路径长度之和。哈夫曼树为带权路径长度最小的二叉树。一个结点的带权路径长度为叶子结点的权值*从根到叶子的路径长度，将所有叶子结点的带权路径长度相加即为树的带权路径长度。根据上述哈夫曼树得出其加权长度=(3+4+5+6)*3+(8+10)*2=90。因此平均加权长度=90/36=2.5。故本题选B。

5、试题答案：A

试题解析：

后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。根据二叉树的后序遍历得出二叉树的结构如下：

先序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。根据上述二叉树的结构得出其先序序列为：a，e，d，f，b，c。故本题选A。

6、试题答案：A

试题解析：

根据题干可知图G的各边权值均为1，因此该图可以视为无权图。I和II算法是求图的最小生成树算法，无法求图G的最短路径。从某顶点出发的图的广度优先搜索可以求出该点到其余各点的最短路径，故本题选A。

7、试题答案：B

试题解析：

对于I，根据B树的性质，B树每个结点最多有m-1个关键字，若结点的关键字个数超过最大值，则插入关键字则可能引起结点的分裂，从而增加树的高度，因此正确。
对于II，如果在叶结点中删除关键字，则删除操作必然导致叶子结点的变化；如果在非叶结点中删除关键字则会导致树的结构不满足B树的性质从而导致叶子结点发生变化，因此II正确。
对于III，B树的非叶子结点也可以存储关键字，则查找的关键字可能在非叶子结点上，因此III错误。
对于IV，B树中插入操作不是在树中添加一个叶结点，而是首先在某个非叶结点中添加一个关键字，若该关键字个数不超过m-1个，则插入完成，否则产生结点的分裂，因此插入结点不一定在叶结点上，IV错误。故本题选B。

8、试题答案：B

试题解析：

对于含n个记录的有序表，在查找成功和查找失败情况下至多比较次数=⎿log₂n⏌+1。将n=600代入，求得关键字至多比较次数为10，故本题选B。

9、试题答案：C

试题解析：

将关键字2022、12、25依次插入散列表HT之后，构造HT如下表所示：

在散列表中删除25不能直接将key置为NULL，而是把关键字标记，标记后的HT如下表所示：

查找失败情况下，各地址的失败查找长度表如下所示：

由上表可知，HT中查找失败的平均查找长度=(1+3+2+1+2)/5=1.8。故本题选C。