9．给出折半查找的递归算法，并给出算法时间复杂度性分析。
类似本题的另外叙述有：
（1）写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。
10．请用类C或用类PASCAL语言编写算法：键树，又称数字查找树。它是一棵度为>=2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键（TIRE）树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
11．写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
12．用PASCAL或C编写一用链接表（LINKED LIST）解决冲突的哈希表插入函数。 13．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。 14．设排序二叉树中结点的结构为下述三个域构成:
data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。
15．已知二叉树T的结点形式为(llink, data,count,rlink,),在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
16．假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法，求平衡二叉树的高度。
17．设从键盘输入一个整数的序列：n,a1,a2，?，an,其中n表示连续输入整数的个数。 （1）试编写一程序按整数值建立一个二叉排序树（单考生做）。
（2）在（1）基础上将此二叉树上的各整数按降序写入一磁盘文件中（统考生做）。 18．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
19．在单链表中，每个结点含有5个正整型的数据元素若（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
20．编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
21．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。 22. 设二叉排序树的存储结构为：
TYPE tree=^node； node=RECORD
key: keytype; size:int;
lchild, rchild, parents: tree； END;
一个结点x^的size域的值是以该结点为根的子树中结点的总数（包括x^本身）。例如，下图中x所指结点的sixe值为4。设树高为h，试写一时间为O(h)的算法
Rank(T:tree;x:^node)返回x所指结点在二叉排序树T的中序序列里的排序序号，即：求x^结点是根为T的二叉排序树中第几个最小元素。例如，下图x所指结点是树T中第11个最小元素。（提示：你可利用size值和双亲指针parents）
23．已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
（1） 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出
哈希表中所有关键字的程序。
（2） 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平
均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
24．有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法（注：此算法不需要写出，仅需说明存取的方法和所用时间）进行比较。
25．将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线性探测法处理冲突（H（key）+1、H（key）+2、?、H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。
26. 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？
类似本题的另外叙述有：
(1) 已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为０～１１。设计一个哈希表函数把上述关键字散到０～１１中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。
27.已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到）O(m).
参考答案： 一．选择题 1.C 2.A 3.1D 3.2C 4.D 5.B 6.D 7.D 8.C 9.A 10.D 11.B 12.1C 12.2C 13.1C 13.2D 13.3G 13.4H 14.1E 14.2B 14.3E 14.4B 14.5B 15.1B 15.2A 16.A 26.2C 27.B 二．判断题 1.√ 2.√ 3.× 4.× 5.× 6.√ 7.√ 8.× 9.× 10.× 11.× 12.√ 17.C 28.D 18.C 29.D 19.C 30.C 20.D 31.D 21.B 22.C 23.B 24.D 25.C 26.1A 32.1D 32.2C 33.C 13.√ 14.× 15.× 16.× 17.√ 18.× 19.√ 20.× 21.× 22.× 23.× 24.× 25.√ 26.× 27.× 28.√ 29.√ 30.× 31.√ 32.√ 33.× 34.√ 35.√ 部分答案解释如下。
4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。 8．哈希表的结点中可以包括指针，指向其元素。 11．单链表不能使用折半查找方法。
20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下面。
21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。
24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。 26．只有被删除结点是叶子结点时命题才正确。
三．填空题
1．n n+1 2．4 3．6,9,11,12 4．5
5．26（第4层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2?-1 9．2,4,3
10．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单
11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。
12．小于等于表长的最大素数或不包含小于20的质因子的合数 13．16 14．?㏒2」+1
15．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2
17．30，31.5（块内顺序查找）
18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储
19．(n+1)/2 20．(n+1)/n*log2(n+1)-1 21．结点的左子树的高度减去结点的右子树的高度
22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区
23．直接定址法 24．O(N) 25．n(n+1)/2 26．54 27．31 28．37/12 29．主关键字 30．左子树 右子树
n
31．插入 删除 32．14 33．(1)126 (2)64 (3)33 (4)65 34．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 35．(1) k (2) I
四．应用题
1．概念是基本知识的主要部分，要牢固掌握。目的是引起重视，解答略。 2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：
① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：
a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b．di =1，-1，2，-2，? ，?k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。
c．di =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。
（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i（0≤i≤m-1）的第一个关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向
2
2
2
2
2