数据结构与算法-考研试题(计算机统考 2023年有序表查找)

单项选择（2023年计算机统考）

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

A、9

B、10

C、30

D、300

答案解析

B

【解析】

若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 n ，

二叉搜索树高度为 h=[log₂n]+1 。

代入 n=600，解得h=10。

讨论

查找

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【】次元素间的比较。

下列哪两个数据结构，同时具有较高的查找和删除性能【】？

在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。

在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。

已知序列17，31，13，11，20，35，25，8，4，11，24，40，27，请画出该序列的二叉排序树，并分别给出下列操作后的二叉排序树：① 插入数据9；② 删除结点17；③ 再删除结点13。

一棵满二叉排序树深度为k，节点数为2k-1；节点值为1至（2k - 1），给出k和任意三个节点的值，输出包含该三个节点的最小子树的根节点。样例输入：4 10 15 13样例输出：12

最佳二叉树是AVL树（平衡二叉树）。

在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么查找失败到达失败结点时所做的数据比较次数是多少？

某二叉排序树如下所示，新的元素45应作为【】插入该二叉树中。

在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【】等元素进行了比较。

静态查找表

在一个线性表上可以进行二分查找(折半查找)的充分必要条件是【】。

折半(二分)查找法适用的线性表应该满足【】的要求。

对关键码序列(9，12，15，20，24，29，56，69，87)进行二分查找(折半查找)，若要查找关键码15，则需依次与【】进行比较。

最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度wihi最小的树，其中对最优二叉树，n表示__________，对最优查找树，n表示__________，构造这两种树均__________。（1）结点数（2）叶结点数（3）非叶结点数（4）度为2的结点数（5）需要一张n个关键字的有序表（6）需要对n个关键字进行动态插入（7）需要n个关键字的查找概率表（8）不需要任何前提

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

若在线性表中采用折半查找元素，该线性表应该【】。

在分块检索中，对256个元素的线性表分成__________块最好，每块的最佳长度是__________；若每块的长度为8，其平均检索长度为__________。

有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

在n个记录的有序顺序表中进行折半查找，最大的比较次数是__________。

用二分法查找一个线性表时，该线性表必须具有的特点是____________。

有序表查找

已知有向图G采用邻接矩阵存储，其定义如下：typedef struct{//图的定义 int numberVertices,numEgges;//图中实际的顶点数和边数 char verticesList[maxV];//顶点表 int edge[maxV][maxV];//邻接矩阵}MGraph;将图中出度大于入度的顶点称为K顶点，如图，a和b都是K顶点，设计算法 int printVertices(MGraph G)对给定任意非空有向图G，输出G中所有K顶点，并返回K顶点的个数。(1)给出算法的设计思想。(2)根据算法思想，写出C/C++描述，并注释。

对含有n (n>0)个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作，工作区中能保存m个记录，请回答下列问题。(1) 如果文件中有19条记录，其关键字分别为：51，94，37，92，14，63，15，99，48，56，23，60，31，17，43，8，90，166，100，当m=4时，可生成几个初试归并段，各是什么？(2)对任意m (n≫m>0)，生成的第一个初试归并段长度最大值和最小值分别多少？

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

下列排序算法中，不稳定的是【】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢【】。

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

下列关于非空 B 树的叙述中，正确的是【】Ⅰ. 插入操作可能增加树的高度Ⅱ. 删除操作一定会导致叶结点的变化Ⅲ. 查找某关键字一定是要查找到叶结点Ⅳ. 插入的新关键字最终位于叶结点中

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

若采用三元组表存储结构存储系数矩阵 M.则除三元组外，下列数据中还需要保存的是【】Ⅰ. M 的行数；Ⅱ. M 中包含非零元素的行数；Ⅲ. M 的列数；Ⅳ. M 中包含非零元素的列数.

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