32．B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。
33. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。 34．二叉排序树删除一个结点后，仍是二叉排序树。 35．B+树既能索引查找也能顺序查找。
三、填空题
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。
4. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 5. 高度为4的3阶b-树中，最多有__________个关键字。
6. 在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。
8. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。
10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 11. 平衡二叉树又称__________，其定义是__________。 12. 在哈希函数H（key）=key%p中，p值最好取__________。
13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。 14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。 15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。
16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。
18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。 19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。
20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树
中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 21. 平衡因子的定义是__________
22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和
__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。
23. 具有N个关键字的B树的查找路径长度不会大于__________。
24. 在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为________ 。
25. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做__________次插入和探测操作。 26. 高度为8的平衡二叉树的结点数至少有__________个。
27. 高度为5（除叶子层之外）的三阶B-树至少有__________个结点。
28. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为__________
29. 可以唯一的标识一个记录的关键字称为__________。
30. 已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。
31. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
32. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________.
33. 127阶B-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶B+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；
34. 若静态查找表的类型定义如下：
TYPE rectype=RECORD key：keytype； ??； END； ordlisttp=ARRAY[1..n] OF rectype； 请完成以下二分查找的算法：
FUNC binsrch（r：ordlisttp；k：keytype）：integer； BEGIN low:=1；hig:=n；suc:=false； WHILE ___(1)___ AND NOT（suc）DO [ mid：=__(2)____；
CASE
k>r[mid].key：low:=mid+1； k=r[mid].key：suc:=true； k IF suc THEN __(3)__ ELSE __(4)__ END； 35. 顺序查找 FUNC seq(a,n,k):integer; BEGIN I:=1; A[n+1]= __(1)____; WHILE a[I]<>k DO I:=I+1; IF __(2)___ THEN return(I) ELSE return(0); END; 36. 已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(C语言，PASCAL语言的考生不填） #define N /*学生人数*/ int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int head=1,mid,rear=N; do {mid=(head+rear)/2; if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__); if (a[head] 37. 假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success 为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。 #include struct node *left， *right; } node; node *root; int k，success; void del_leaf(node **t, int k, int *sn) { node *p, *pf; p=*t; *sn=0; while(_（1）_&&!*sn) if (k==p->key) *sn =1; else { _（2）_; if (k if (*sn && p->left==NULL && p->right==null) { if (_（3）_ ) if (pf->left ==p ) pf ->left=null; else pf->right=null; else _（4）_ ; free(p); } else *sn=0; /*call form :del_leaf( &root, k, &success);*/ 四、应用题 1. 名词解释： 哈希表 同义词：叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？ B-树 平衡二叉树（AVL树）？ 平衡因子平均查找长度（ASL） trie树。 2. 回答问题并填空 （1）散列表存储的基本思想是什么？ （2）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法？他们 各有何特点？ （4）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ （5）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。 3. 如何衡量hash函数的优劣？ 简要叙述hash表技术中的冲突概念，并指出三种解决冲 突的方法。 4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？ 5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？ 6. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 7.对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做： （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法； 8.设哈希表a 、b分别用向量a[0..9],b[0..9]表示 ，哈希函数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。 9.采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 10. 常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数 H(Key)=Key MOD 13和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。 11. 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列 （32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。 2 2 2