2023考研408真题
★注意：黑色字体为题目，红色字体为答案。
选择题
1、下列对顺序存储的有序表(长度为 n)实现给定操作的算法中平均时间复杂度为O(1)的是(D )。
查找包含指定值元素的值 B.插入包含指定值元素的算法
删除第i个元素的算法 D.获取第i个值的算法
【答案】
【解析】线性表的顺序存储结构采用一组地址连续的存储单元依次存储线性表的数据元素。特点是逻辑上相邻的数据元素在理位置上相邻。线性表顺序存储结构是一种随机存取的存储结构，设线性表的每个元素占L个存储单元，第一个元素a
1
的存储地址是LOC(a
1
)，则任意元素a
i
的LOC(a
i
)=LOC(a
1
)+(i-1)*L。因此获取第i个值的算法为常量阶O(1)。
2、现有非空双向链表 L，其结点结构为
Prer
Data
Next
prer是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p所指向的结点(非尾结点)之后插入指针s指向的新结点，则在执行了语句序列：
“s- > next=p-> next;p- > next=s”，后，还要执行( C)。
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
【答案】C？
”
3、若采用三元组表存储结构存储稀疏矩阵M。则除三元组外，下列数据中还需要保存的是（ ） 。
I、M 的行数 II、M中包含非零元素的行数
III、M 的列数 IV、M 中包含非零元素的列数
仅I、III B.仅I、II C.仅III、IV D.I、II、III、I
【答案】A
【解析】为运算方便，还需知道矩阵的行数和列数。
4、
在有6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3,4,5,6,8,10,为 S 构造的哈夫曼树的加权平均长度为( )。
2.4 B.2.5 C.2.67 D.2.75
【答案】B？
【解析】WPL=
=（3+4+5+6）*3+（8+10）*2=90
5、已知一棵二叉树的树形如图，若其后序遍历为 f,d,b,e,c,a，则其先序列为（ ）。
A. aedfbc
B.acebdf C.cabefd D.dfebac
【答案】A
【解析】由后序遍历序列可知，“a”为整个二叉树的根，“e”为左子树根，“c”为右子树根，在以“e”为根的二叉树上，“d”是其左子树跟，“b”是其右子树根，“f”是“d”的右子树根。
6、
已知无向连通图G中各边的权值均为1.下列算法中定能够求出图G中从某顶点到其余各个顶点最短路径的是( )。
I. 普利姆算法
II. 克鲁斯卡尔算法
III.图的广度优先搜索
仅 I B.仅I、II
C.仅 I 、III DI、II 、II
【答案】III
D:题中说了权值均为1，最小生成树的路径就是最短路径
【解析】普里姆和克鲁斯卡尔算法都是求最小生成树的算法啊
7、
下列关于非空B树的叙述中，正确的是( )。
I 插入操作可能增加树的高度
II 删除操作一定会导致叶结点的变化
III 查找某关键字一定是要查找到叶结点
IV 插入的新关键字最终位于叶结点中
A.仅I B.仅I、II
C.仅III、IV D.仅I、II、IV
【答案】B
【解析】
在B_树中查找与二叉排序树查找类似。从根结点出发，沿指针搜索结点和在结点内顺序（或折半）查找关键字两个过程交替进行。若查找成功，返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，返回插入位置。从根开始查找，如果 Ki = KEY，查找成功。若 Ki < KEY < Ki+1， 查找 Ai 指向的结点。若 KEY < K1，查找 A0 指向的结点，若 KEY > Kn，查找 An指向的结点。若找到叶子，查找失败。
8、
对含有600个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。
A.9 B.10
C.30 D.300
【答案】B
【解析】关键字的比较次数不会超过折半查找的判定树的深度，有600个元素的判定树深度不超过10。因此选B。
9、
现有长度为5，初始为空的散列表HT，散列表函数H(K)=(k+4)%5用线性探查再散列法解决冲突。若将关键字序列2022,12,25依次插入HT中，然后删除关键字25，则HT中查找失败的平均查找长度( )。
A.1 B1.6
C.1.8 D.2.2
【答案】C？
【解析】查找不成功平均查找长度：查找不成功时和给定值进行比较的关键字个数的期望值。
地址
0
1
2
3
4
key
2022
12
查找不成功的比较次数
1
3
2
1
1
ASL=(1+3+2+1+1)/5=1.6
10、
下列排序算法中，不稳定的是( )
I 希尔排宁 II 归并排序 III 快速排序
IV 堆排序 V 基数排序
仅 I和 II B.仅 II和 V
C.仅 I，III，IV D.Il，IV，V
【答案】C
【解析】希尔排序、快速排序、简单选择排序和堆排序均是不稳定的排序方法，因此选C。
11、使用快速排序算法对数据进
2023考研408答案.docx
