下列关于非空 B 树的叙述中,正确的是【 】
Ⅰ. 插入操作可能增加树的高度
Ⅱ. 删除操作一定会导致叶结点的变化
Ⅲ. 查找某关键字一定是要查找到叶结点
Ⅳ. 插入的新关键字最终位于叶结点中
A、仅Ⅰ
B、仅Ⅰ、Ⅱ
C、仅Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ和Ⅳ
下列关于非空 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依次插入杂凑表的状态。
利用逐点插入法建立序列(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
在分析二叉查找树性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若设失败结点i所在层次为li,那么查找失败到达失败结点时所做的数据比较次数是多少?
下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】
下列排序算法中,不稳定的是【 】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序
使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】
已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索
若采用三元组表存储结构存储系数矩阵 M.则除三元组外,下列数据中还需要保存的是【 】Ⅰ. M 的行数;Ⅱ. M 中包含非零元素的行数;Ⅲ. M 的列数;Ⅳ. M 中包含非零元素的列数.
在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】