mbnode=record keynum:integer; parent:mblink;
key:array[1..m] of keytp {关键字} ptr:array [0..m] of mblink end;
result=record pt:mblink; i:integer; tag:(0..1) end;
（注：所用语言C, PASCAL等都可使用编制算法。若算法不用类PASCAL描述，要给出相应语言的结构描述。题目中给出的结构说明可供参考，也可自行给出）【北京轻工业学院 1997 八 （10分）】
9. 元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i](1<=i<=n)构造一棵二
叉排序树T的非递归算法：CSBT(T,A) 【北京科技大学 2000 八、2】 10．给出折半查找的递归算法，并给出算法时间复杂度性分析。【河南大学 1998 五（5分）】 类似本题的另外叙述有：
（1）写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。
【山东师范大学 2000 二、3 （12分） 2001 二、4（10分）】
11．请用类C或用类PASCAL语言编写算法：键树，又称数字查找树。它是一棵度为>=2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键（TIRE）树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。【上海大学 2002 七、2 （10分）】
12．写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
【上海交通大学 1999 五 (12分)】
13．用PASCAL或C编写一用链接表（LINKED LIST）解决冲突的哈希表插入函数。【浙江大学 1996 七 (8分 )】
14．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。【中科院计算所 2000 八 （15分）】
15．设排序二叉树中结点的结构为下述三个域构成:
data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树树根结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。【上海交通大学 2000 十一 (12分)】
16．已知二叉树T的结点形式为(llink, data,count,rlink,),在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。【中山大学 1999数 三 (10分)】
17．假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法，求平衡二叉树的高度。
【燕山大学 2001 四、3 （8分）】
18．设从键盘输入一个整数的序列：n,a1,a2，?，an,其中n表示连续输入整数的个数。（10分）。
（1）试编写一程序按整数值建立一个二叉排序树（单考生做）。
（2）在（1）基础上将此二叉树上的各整数按降序写入一磁盘文件中（统考生做）。【南京航空航天大学 1998 十（10分）】
19．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非
递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。【北方交通大学 1998 七 （20分）】
20．在单链表中，每个结点含有5个正整型的数据元素若（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
【北京邮电大学 2001 五、1 （10分）】
21．编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。 【清华大学 1995 七（20分）】
22. 在二叉排序树的结构中，有些数据元素值可能是相同的 ，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42．滤掉3个元素。【北京工业大学 1995 六 (18分)】
23．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。【北京航空航天大学 1996】 24. 设二叉排序树的存储结构为：
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）【中科院软件所 1997 四(12分)】【中国科学技术大学 1997】
17/12 T 21/4 x 14/7
22/1 16/2 19/2 10/4 20/1 12/1 14/1 7/2
size key 9/1 25． 已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字 母表中的序号。
（1） 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈
希表中所有关键字的程序。
（2） 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均
查找长度的算法。注意，此算法中规定不能用公式直接求解计算。【西北大学 2001】
26． 有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储
结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法（注：此算法不需要写出，仅需说明存取的方法和所用时间）进行比较。【北方交通大学 1994 六 （16分）】
27．将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线性探测法处理冲突（H（key）+1、H（key）+2、?、H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001 五、2 （10分）】
28. 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？
【东北大学 1996 四 (12分)】 类似本题的另外叙述有：
(1) 已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为０～１１。设计一个哈希表函数把上述关键字散到０～１１中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。
【东北大学 1997 五 (15分)】 29. 已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m).
【清华大学 1994 八 （15分）】
第9章 集合
一．选择题 1.C 12.1C 15.2A 25.3I 35.2C 2.A 12.2C 3.1D 3.2C 4.D 13.1C 13.2D 13.3G 5.B 13.4H 6.D 14.1E 7.D 14.2B 8.C 14.3E 9.A 14.4B 10.D 11.B 14.5B 15.1B 25.2F 16.A 17.C 18.C 19.C 20.D 21.B 22.C 23.B 24.C 25.1B 26.A 27.D 28.C 29.1A 36.C 29.2C 30.B 31.D 32.D 33.C 34.D 35.1D 二．判断题 1.√ 2.√ 3.× 4.× 5.× 6.√ 7.√ 8.× 9.× 10.× 13.√ 25.√ 14.× 26.× 15.× 27.× 16.× 28.√ 17.√ 29.√ 18.× 30.× 19.√ 31.× 20.× 32.√ 21.× 33.√ 22.× 34.× 11.× 23.× 35.√ 12.√ 24.× 36.√ 部分答案解释如下。
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．?㏒n
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．log?m/2?(
)+1 25．O(N) 26．n(n+1)/2
27．54 28．31 29．37/12 30．主关键字 31．左子树 右子树
32．插入 删除 33．14 34．(1)126 (2)64 (3)33 (4)65 35．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36．(1) k (2) I
四．应用题
1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。