一、单项选择题
1. 下列对顺序存储的有序表（长度为n）实现给定操作的算法中平均时间复杂度为O(1)的是（  ）。
A、查包含指定值元素的值
B、插入包含指定值元素的算法
C、删除第i(1≤i≤n)个元素的算法
D、获取第i(1≤i≤n)个值的算法
2、现有非空双向链表L，其结点结构为，prev是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：“s->next=p->next;p->next=s;”，后，还要执行（ ）。
A、s->next->prev=p;s->prev=p;
B、p->next->prev=s;s->prev=p;
C、s->prev=s->next->prev; s->next->prev=s;
D、p->next->prev=s->prev;s->next->prev=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
2023年考研时间定了注：
每个关键字的查长度为：
图片
加权平均长度为 ：
(3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5。
如果不考虑权重，会错误计算为
(3+3+3+3+2+2)/6≈2.67，从而误选C。
5、已知一棵二叉树的树形如下图所示，若其后序遍历为fdbeca，则其先序列为（ ）。
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
注：无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更加高效。III正确。I 和 II 是最小生成树算法，也可直接排除。
7、下列关于非空B树的叙述中，正确的是（ ）。
I.插入操作可能增加树的高度；II.删除操作一定会导致叶结点的变化；III.查某关键字一定是要查到叶结点；IV.插入的新关键字最终位于叶结点中。
A、仅I
B、仅I、II
C、仅III、IV
D、仅I、II、IV
解答：I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高度加一。I 正确。
II. 如果删除的关键字位于叶结点，则该B树叶结点一定发生变化。如果删除的关键字位于非叶结点，叶结点也会发生变化。II 正确。
III. B树中所有结点均可以存储关键字，若查的关键字位于非叶结点，则不需要查到叶结点。III错误。
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
注：经过上述操作后，散列表为：
如果查的关键字散列函数值为0，查1次失败。
如果是1，查3次才能判断失败。
如果是2，查2次才能判断失败。
如果是3，查1次才能判断失败。
如果是4，查2次才能判断失败。
所以，失败的平均查长度为：(1+3+2+1+2)/5 = 1.8