单项选择(2023年计算机统考

下列关于非空 B 树的叙述中,正确的是【 】

Ⅰ. 插入操作可能增加树的高度

Ⅱ. 删除操作一定会导致叶结点的变化

Ⅲ. 查找某关键字一定是要查找到叶结点

Ⅳ. 插入的新关键字最终位于叶结点中

A、仅Ⅰ

B、仅Ⅰ、Ⅱ

C、仅Ⅲ、Ⅳ

D、仅Ⅰ、Ⅱ和Ⅳ

答案解析

B

【解析】

Ⅰ. 插入操作可能会导致上溢根结点,树的高度加1。正确。

Ⅱ. 如果删除的关键字位于叶结点:

如果删除该结点后关键字个数n≥[m/2]-1,则没有后续操作;

如果该结点删除关键字后关键字个数n<[m/2]-1,则需要从兄弟结点借一个关键字,并根据兄弟够借和不够借两种情况,进行继续分析。

无论上述哪种情况,此时叶结点一定发生变化。

如果删除的关键字位于非叶结点:

用被删除关键字的前驱关键字替换被删除关键字,该前驱关键字或一定位于叶结点,该叶结点一定发生变化。

如果删除该结点后关键字个数n≥[m/2]-1,则没有后续操作;

如果该结点删除关键字后关键字个数n<[m/2]-1,则需要从兄弟结点借一个关键字,并根据兄弟够借和不够借两种情况,进行继续分析。

此时叶结点一定发生变化。

综上,无论删除关键字是位于叶结点还是位于非叶结点,一定有叶结点发生变化。正确。

Ⅲ. B树中所有结点均可以存储关键字,若查找的关键字位于非叶结点,则不可能查找到叶结点。错误。

Ⅳ. 插入新的关键字,插入后进行调整,新插入的关键字不一定位于叶结点中。可以用依次将关键字5, 6, 9, 14, 8, 2, 12, 15, 13插入初始为空的4阶B树进行模拟,最后13位于非叶结点中。

讨论

设有关键码序列(10,40,30,20),根据该序列构建的二叉排序树是【 】。

【 】不符合二叉排序树的定义。

设有二叉排序树如下图所示,根据关键码序列【 】可构造出该二叉排序树。

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

分块查找要求将待查找的表均匀地分成若干块,块中诸记录的顺序可以是任意的,但块与块之间____________。

在分块检索中,若索引表和各块内均用顺序查找,则有900个元素的线性表分成__________块最好;若分成25块,其平均查找长度为__________。

负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度。

假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。

若杂凑表(Hash)的地址范围为[0,9],杂凑函数为H(key)=(key2+2) MOD 9,并采用链地址法处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。

设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大?② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

利用逐点插入法建立序列(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应作为【 】插入该二叉树中。

已知有向图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”后,还要执行【 】

已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】

已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索

现有长度为 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 构造的哈夫曼树的加权平均长度为【 】