数据结构第九章 查找 习题及答案(3)

数据结构课件

较次数为__________。（提示：此时二叉排序树与折半查找的二叉判定树一样了） 10. 平衡因子的定义是______ ____ 11. 查找是非数值程序设计的一个重要技术问题，__(1)__查找，__(2)__查找和

__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。

12. 具有N个关键字的B树的查找路径长度不会大于__________。在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为________ 13. 高度为5（除叶子层之外）的三阶B-树至少有__________个结点。 14. 可以唯一的标识一个记录的关键字称为__________。

15. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。

16. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。( 提示：这时需要找的是最后一个大于等于X的下标，若查找成功其下标若为m，则有m个学生成绩大于或等于X，若查找不成功，若这时low所指向的值小于X，则有low-1个学生成绩大于或等于X，注意这时表中可能不止一个数值为X的值，这时我们要查找的是下标最大的) #define N /*学生人数*/

int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int low=1,mid,high=N; do {mid=(low+high)/2;

if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__);

if (a[low]<x) return low-1; return low; }

四、应用题 1. 名词解释：

哈希表

叙述B-树定义，主要用途是什么？ 平衡二叉树（AVL树） 平衡因子

平均查找长度（ASL）

3. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法解决冲突Hi=(H(key)+di) mod

222

10(di=1,2,3, ,)。要求：对该关键字序列构造哈希表，并确定其装填因子，查找成功所需的平均探查次数。

4. 设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13， 即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。

7. 设有一棵空的３阶B-树，依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99，请画出该树。

9. 已知2棵2-3 B-树如下（省略外结点）：

（1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2