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