《查找 补充练习》由会员分享，可在线阅读，更多相关《查找 补充练习（4页珍藏版）》请在金锄头文库上搜索。
1、一、单项选择题。一、单项选择题。 1. 已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折半查找法查找 一个不存在的元素，则比较次数最多是（ A ） 。 A. 4 B. 5 C. 6 D. 7 2. 下列选项中，不能构成折半查找中关键字比较序列的是（ A ） 。 A. 500，200，450，180 B. 500，450，200，180 C. 180，500，200，450 D. 180，200，500，450 3. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ） 。A. 95,22,91,24,94,71 B. 92,20,91,34,88,35 C
2、. 21,89,77,29,36,38 D. 12,25,71,68,33,24 4. 在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2，再将 v 插入 T2 形成二叉排序树 T3。下列关于 T1 与 T3 的叙述中，正确的是（ ） 。 I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同 II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同 III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同 IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同 A. 仅 I、III B. 仅 I、IV C. 仅 II、III D. 仅 II、
3、IV 5. 设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找长度为（ ） 。 A. O(1) B. O(log2n) C. O(n) D. O(n2) 6. 下列二叉排序树中，满足平衡二叉树定义的是（ ） 。A. B. C. D. 7. 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则平衡二叉树的结 点总数为（ ） 。 A. 10 B. 20 C. 32 D. 33 8. 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ） 。 A. 0 B. 1 C. 2 D. 3 9. 在下列所示的平衡二
4、叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二 叉树中，关键字 37 所在结点的左、右子节点中保存的关键字分别是（ ） 。. 13，48 B. 24，48 . 24，53 D. 24，90 10. 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则平衡二叉树的结 点总数为（ ） 。 A. 10 B. 20 C. 32 D. 33 11. 若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ） 。 A. 0 B. 1 C. 2 D. 3 12. 现在有一棵无重复关键字的平衡二叉树（AVL 树） ，
5、对其进行中序遍历可得到一个 降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ） 。 A. 根节点的度一定为 2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 13. 现在有一颗无重复关键字的平衡二叉树（AVL 树） ，对其进行中序遍历可得到一个 降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ） 。 A. 根节点的度一定为 2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 14. 下列叙述中，不符合 m 阶 B 树定义要求的是（ ） 。 A. 根节点最多有 m 棵子树 B. 所有
6、叶结点都在同层上 C. 各结点内关键字均升序或降序排列 D. 叶结点之间通过指针链接 15. 已知一棵 3 阶 B 树，如图 8-27 所示，删除关键字 78 得到一棵新 B 树，其最右叶 结点中的关键字是（ ） 。4517 352555 653760 62477821图 8-27 一棵 3 阶 B 树A. 60 B. 60,62 C. 62,65 D. 65 16. 在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点数最多是（ ） 。 A. 5 B. 6 C. 10 D. 15 17. 在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（ ） 。 A.5 B. 7 C
7、. 8 D. 14 18. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H(K) =K %9 作为散列函数，则散列地址为 1 的元素有（ ）个。 A1 B2 C3 D4 19. 为提高散列表的查找效率，可以采取的正确措施是（ ） 。 I. 增大装填因子 II. 设计冲突（碰撞）少的散列函数 III. 处理冲突（碰撞）时避免产生聚集现象 A. 仅 I B. 仅 II C. 仅 I、II D. 仅 II、III 20. 用 Hash（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项 中，会受堆积现象直接影响的是（ ） 。 A. 存储效率 B. 散
8、列函数 C. 装填（装载）因子 D. 平均查找长度二、填空题。二、填空题。 1. 设查找表中有 100 个元素，如果用折半查找法查找数据元素 X，则最多需要比较次就可以断定数据元素 X 是否在查找表中。 2. 设一组初始记录关键字序列为 （11，16，25，36，48，50，65，86，90，101，126）,则利用折半查找法查找关键字 90， 需要比较 次。 3. 设一组初始记录关键字序列为（19，11，40，30，16，12，29） ，则根据这些记录 关键字构造的二叉排序树的平均查找长度是 。 4. 假定一个线性表为（12，23，74，55，63，40） ，若按 Key % 4 条件进行划
9、分，使得 同一余数的元素成为一个子表，则得到的四个子表分别为 、 、和_。 5. 向一棵 B 树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 。 6. 散列表中解决冲突的两种方法是 和 。三、简答题。三、简答题。 1. 设有序顺序表中的元素依次为 17，54，67，75，85，93，94，112，203，261。试 画出对其进行折半查找时的二叉判定树，并计算查找成功的平均查找长度和查找不成功的 平均查找长度。 2. 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列 3 种情况分别 讨论两者在等查找概率时的平均查找长度是否相同？ （1）查找失败。 （2）查找成功
10、，且表中只有一个关键字等于给定值 k 的记录。 （3）查找成功，且表中有若干个关键字等于给定值 k 的记录，要求一次查找找出所有 记录。 3. 按照分块查找，对 144 个元素的表分成多少块最好？每块的最佳长度是多少？假定 每块的长度为 8，其平均查找长度是多少？ 4. 设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个 输入各个数据而生成的二叉排序树。 5. 一棵 3 阶 B 树如图 8-28 所示。试分别画出在插入 65、15、40、30 之后 B 树的形状。554525 3580 905060 708595图 8-28 一棵
11、3 阶 B 树6. 一棵 4 阶 B 树如图 8-29 所示。试画出插入关键字 87 后树的形状。82 85 9061 70 7520 2535 5030 60 80图 8-29 一棵 4 阶 B 树7. 假定一个文件由 15 个记录组成，每个记录的关键码均为整数，分别为1，4，9，16，25，225，每个数据页块存放 3 个记录，要求： （1）用 B 树组织索引，设阶 m=3，依次将上述 15 个关键码插入 B 树，画出插入后的 B 树。 （2）用 B+树组织索引，设阶 m=3，依次将上述 15 个记录插入文件中，画出插入后的 整个文件的结构图（包括 B+树索引） 。 8. 将关键字序列（7
12、、8、11、18、9、14）散列存储到散列表中，散列表的存储空间 是一个下标从 0 开始的一维数组，散列函数为：H(key)=(key*3) mod 7，处理冲突采用线性 探测再散列法，要求装填（载）因子为 0.7。 （1）请画出所构造的散列表； （2）分别计算等概率情况下，查找成功和查找不成功地平均查找长度。 9. 设包含 4 个数据元素的集合 S= “do“，“for“，“ repeat“，“ while“，各元素的查 找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将 S 保存在一个长度为 4 的顺 序 表中，采用折半查找法，查找成功时的平均查找长度为 2.2。 （1）若采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应 使用 何种查找方法？查找成功时的平均查找长度是多少？ （2）若采用链式存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应 使用 何种查找方法？查找成功时的平均查找长度是多少？
