严蔚敏-数据结构集合习题

第九章 集合

一、 选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n

2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】

2

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N 4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列

B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储

5. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】

A． 必然快 B. 必然慢 C. 相等 D. 不能确定

8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )

A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997 一、7 （2分）】 9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10 （2分）】

A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为（ ）【中山大学 1999 一、15】

2nn

A. O（n） B. O（n） C. O（nlog） D. O（log）

11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】

(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存

储，也可以链式方式存储；

D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。

nn

（3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2 F.nlog2 G.(n+1)/2 H.log2(n+1)

14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为( （1） ),有序表的折半查找的ASL为( （2） ),对静态树表,在最坏情况下,ASL为( （3） ),而当它是一棵平衡树时,ASL为 ( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案：【上海海运学院 1999 二、3 （5分）】

nn2n

（1）（2）（3）（4）（5）: A. O(1) B. O( log2 ) C. O((log2)) D.O(nlog2) E. O(n)

15. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找

失败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案: 【上海海运学院 1997 二、4 （3分）】 A. 相同的 B.不同的

16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找

法。

A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用一、8 （2分）】

17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】

A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)

19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工业大学 2001 一、4 （2分）】

A. LL B. LR C. RL D. RR

20．下列关于m阶B-树的说法错误的是( ) 【南京理工大学 1997 一、9 （2分）】

A．根结点至多有m棵子树 B．所有叶子都在同一层次上 C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的

21. 下面关于m阶B树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】 ①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。

A． ①②③ B. ②③ C. ②③④ D. ③

22. 下面关于B和B+树的叙述中，不正确的是( ) 【北方交通大学 2001 一、17 （2分）】

A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 23. m阶B-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】 A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 24. 在一棵含有n个关键字的m阶B-树中进行查找，至多读盘( )次。【中科院计算所 2000 一、6 （2分）】 A. log2 B. 1+log2 C. 1+log

n

n

D. 1+log

25. m路B+树是一棵(（1）) ，其结点中关键字最多为(（2）)个，最少(（3）)个。【中科院计算机 1999 一、5】

A. m路平衡查找树 B. m路平衡索引树 C. m路Ptrie树 D. m路键树 E. m-1 F. m G. m+1

H. -1 I. J. +1

26在一棵m阶的B+树中, 每个非叶结点的儿子数S 应满足 ( ). 【武汉交通科技大学 1996 一、3 (4分) 】

A.

≤S≤m B.

≤S≤m C. 1≤S≤

D. 1≤S≤

27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链

地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。【南京理工大学 1997 一、4 （2分）】 A．1 B. 2 C. 3 D. 4

28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

29. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链

表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) 【南京理工大学 1999 一、12(13) （4分）】

（1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16

30. 关于杂凑查找说法不正确的有几个( ) 【南京理工大学 2000 一、16 （1.5分）】 （1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是

相同的

（3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集

A. 1 B. 2 C. 3 D. 4

31. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，

84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】

A．8 B．3 C．5 D．9 32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 【中国科技大学 1998 二、3 （2分）】【中科院计算所1998 二、3 （2分）】 33. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存

入哈希表中，至少要进行( )次探测。【西安电子科技大学 1998 一、8 （2分）】 A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2

34. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【西安电子科技大学2001应用一、7 （2分）】 【北京邮电大学 1999 一、4 （2分）】

35. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并

将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20）（4分）】地址是（ ）。

A． 8 B. 9 C. 10 D. 11

（2）存放元素59需要搜索的次数是（ ）。

A． 2 B. 3 C. 4 D. 5

36. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。【北京邮电大学 2001 一、4 （2分）】

A. 一定会 B. 一定不会 C. 仍可能会

二、 判断题

1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。【长沙铁道学院 1998 一、3 (1分)】 2．在散列检索中，“比较”操作一般也是不可避免的。【华南理工大学 2001 一、4 （1分）】 3．散列函数越复杂越好，因为这样随机性好，冲突概率小. 【南京理工大学 1997 二、5 （2分）】

4．哈希函数的选取平方取中法最好。 【青岛大学 2000 四、7 （1分）】

5．Hash表的平均查找长度与处理冲突的方法无关。 【南京航空航天大学 1997 一、9 （1分）】

6．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。【中科院软件所1999 六（1-3）（2分）】

7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。【中山大学 1994 一、8 (2分)】

8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 【山东大学 2001 一 、6 (1分)】

9. 若散列表的负载因子α<1，则可避免碰撞的产生。 【北京大学 1994 】

10．查找相同结点的效率折半查找总比顺序查找高。 【北京邮电大学 2002 一、8 （1分）】 11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 【中科院软件所 1997 一、6 （1分）】

12. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。【上海交通大学 1998 一、17】 13. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 【山东大学 2001 一、 1 (1分)】

14. 折半查找法的查找速度一定比顺序查找法快 。【山东大学 2001 一、 8 (1分)】 15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。【西安交通大学 1996 二、 3 (3分)】

16．对无序表用二分法查找比顺序查找快。【青岛大学 2002 一、8 （1分）】

17．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找

成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。【上海海运学院 1995 一、11 （1分） 1998 一、12 （1分）】

18．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表

的平均查找时间.

【上海海运学院 1997 一、10 （1分）】 19． 最佳二叉树是AVL树（平衡二叉树）。【北京大学 1994 】

20．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 【上海海运学院 1999 一、8 （1分）】

21．完全二叉树肯定是平衡二叉树。 【南京航空航天大学 1996 六、5 （1分）】

22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 【南京航空航天大学 1995 五、4 （1分）】

23．二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。【北京邮电大学 1998

一、4 （2分）】

24．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

【北京邮电大学 1998 一、6 （2分）】

25. N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 【上海交通大学 1998 一、9】

26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。

【中科院软件所 1997 】

27. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1

必定相同。

【上海交通大学 1998 一、11】

28. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。 【中山大学 1994 一、9 (2分)】 29. B-树中所有结点的平衡因子都为零。 【大连海事大学2001 一、（1，17） (1分)】

30. 在m阶B-树中每个结点上至少有个关键字，最多有m个关键字。 【东北大学 1997 二、 4 (2分)】

31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。【长沙铁道学院 1998 一、9 (1分)】 32. 在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。【合肥工业大学 2001 二、9 （1分）】 33. B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。【华南理工大学 2001 一、3 （1

分）】

34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。

【南京理工大学 1997 二、3 （2分）】

35. 二叉排序树删除一个结点后，仍是二叉排序树。【青岛大学 2000 四、4 （1分）】 36. B+树既能索引查找也能顺序查找。【青岛大学 2002 一、10 （1分）】

三、填空题

1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。【华中理工大学 2000 一、8 （2分）】

2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.

【北方交通大学 2001 二、2】

3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。

【中国人民大学 2001 一、2 （2分）】 4. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________

【合肥工业大学 1999 三、9 （2分）】

5. 高度为4的3阶b-树中，最多有__________个关键字。【合肥工业大学 2000 三、9 （2分）】

6. 在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________

【合肥工业大学 2000 三、10 （2分）】

7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。 【南京理工大学 1997 三、4 （2分）】

8. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点

中原有的关键字的个数是__________。 【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】

9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。【南京理工大学 2000 二、7 （4.5分）】

10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行

存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 【青岛大学 2000 六、2 （2分）】 11. 平衡二叉树又称__________，其定义是__________。【青岛大学 2001 六、3 （3分）】

12. 在哈希函数H（key）=key%p中，p值最好取__________。【青岛大学 2002 三、9 （2分）】

13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。【青岛大学 2002 三、10 （2分）】

14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。【中国科技大学 1998 一、4 （3分）】

15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。【中国矿业大学 2000 一、6 （3分）】

16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。

【西安电子科技大学2001软件一、7 （2分）】

17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。【北京工业大学 1999 一、 5 ( 2分)】

18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。【山东大学 1998 一 、1 (3分)】

19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序

树检索时，平均比较次数为__________。 【山东大学 1999 二、1 (４分)】 20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树

中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。【山东大学 1999 二、２ (４分)】

21. 平衡因子的定义是__________【北京轻工业学院 2000 一、2 （2分）】 22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和

__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。【华北计算机系统工程研究所 1999 一 （5分）】

23. __________法构造的哈希函数肯定不会发生冲突。【重庆大学 2000 一、3】 24. 具有N个关键字的B树的查找路径长度不会大于__________。【中科院计算机 1999 二、2】

25. 在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况

平均时间复杂度）为________ 。 【西南交通大学 2000 一、8】

26. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做__________次插入和探测操作。【武汉大学 2000 一、8】

27. 高度为8的平衡二叉树的结点数至少有__________个。【武汉大学 2000 一、6】 28. 高度为5（除叶子层之外）的三阶B-树至少有__________个结点。【武汉大学 2000 一、4】

29. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度

为__________

【燕山大学 2001 二、4 （3分）】

30. 可以唯一的标识一个记录的关键字称为__________。【燕山大学 1998 一、7 （1分）】 31. 已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。【燕山大学 1998 一、8 （2分）】 32. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。

【厦门大学 2001 一、3 （14%/5分）】

33. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________.

【北方交通大学 2001 二、8】

34. 127阶B-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶B+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；【北方交通大学 1999 二、5 （4分）】 35. 若静态查找表的类型定义如下：

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； 【福州大学 1998 二、8 (2分)】

36. 顺序查找

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; 【中山大学 1998 四、4 (4分)】

37. 已知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]

return head; } 【西南交通大学 2000 一、12】

38. 假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success 为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，

既是根结点，也是叶子结点。 #include

typedef struct node { int key;

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 (kkey ) p=p->left; else p=p->right; }

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);*/ 【上海大学 1999 一、2 （8分）】

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

哈希表【燕山大学 1999 一、4（2分）】【哈尔滨工业大学 1999 一、3 （3分）】【首都经贸大学 1997 一、2 （4分）】

同义词： 【山东大学 1998 二、1 (2分)】【山东工业大学 2000 二、1 （2分）】 叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学 2001 五 （5分）】

B-树【南开大学 1996 五、4 (3分) 1998 五、4 (4分) 2000 二、2 （2）】【山东大学 2000 三 ( 8分)】

平衡二叉树（AVL树）？【南开大学 1996 五 、3 (3分) 1998 五、3 (4分)】【厦门大学 1998 四、2 （5分）】

平衡因子【西北工业大学 1999 一、2 (3分)】 平均查找长度（ASL）【西北工业大学 1999 一 、3 (3分)】

trie树。【中山大学 1997 一、3 （3分）】 2. 回答问题并填空 （1）（2分）散列表存储的基本思想是什么？ （2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）（４分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方

法？他们各有何特点？

（4）（３分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ （5）（２分）散列法的平均检索长度不随( )的增加而增加，而是随( )的增大而增加。

【山东工业大学 1999 四（15分）】

3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。

【南京航空航天大学 1996 九、2 （6分）】

4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？

【中国人民大学 2000 一、4 （4分）】

5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？

【西安电子科技大学2000计应用一、8 （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,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学 2002 二 、2 （5分）】

7. 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探

测再散列方法解决冲突，做：

（1）设计哈希函数； （2）画出哈希表；

（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法；

【东北大学 2001 六 (18分)】

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。【北京工业大学 1998 三 (8分)】 9. 采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。

【北京工业大学 2000 三 (8分)】

10. 设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=key MOD 13， 即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。【南京理工大学 1996 三、3 （5分）】 11. 设散列表长度为14 ，散列函数h(x)=?，其中 i为健值中第一个字母在字母表中

的序号，若健值的输入顺序为Jan, Feb,

Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理冲突，要求：

（1）构造散列表 （2）求出在等概率情况下，查找成功的平均查找长度。【厦门大学 2001 二、2 （24%/3分）】

12. 常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数 H(Key)=Key MOD 13和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。【燕山大学 1999 八 （14分）】

13. 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。【北方交通大学 1998 三 （18分）】

14. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（5分） （2）使用链地址法构造散列表。（5分）

针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（5分）

【清华大学 1998 五（15分）】

15. 已知长度为12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)

(1) 试按表中元素的顺序依次插入一棵初始为空的分类二叉树，试画出插入完成之后

的分类二叉树并计算其在等概率查找情况下，查找成功的平均查找长度。

(2) 试用以下两种方法构造两个Hash表，Hash函数H(K)=[i/2],其中i为关键字K中

第一个字母在字母表中的序号，[x]表示取整数。

a. 用线性探测开放定址法处理冲突(散列地址空间为0～16);

b. 用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。

【上海海运学院 1996 五 （15分）】

222

16. 设散列函数为H（K）=K MOD 13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。【福州大学 1998 三、3 (6分)】

17. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计应用 一、5 （5分）】

18. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。

【大连海事大学2001 八 (10分)】

19. 设散列函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。【首都经贸大学 1997 三 （10分）】

20. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 【合肥工业大学 2000 四、3 （5分）】 21. 设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学 1998 二 （10分）】

22. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题：

(1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较?

(3) 若查找关键字60，需要依次与哪些关键字比较?

(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 三 （10分）】

23. 试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过

2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG） 【清华大学 1996 五】

24. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：

ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。

（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。

写出上述各关键字在表中位置。【南开大学 1998 六 (10分)】

25. 对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学 2000 二、3 (5分)】 26. 设散列表为HT [0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：

H0(key)=key % 13; 注:%是求余数运算(=mod)

Hi=(Hi-1+REV(key+1)+1) % 13; i=1,2,3,?,m-1

其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若插入的关键码序列为(2,8,31,20,19,18,53,27)。

(1)(8分)试画出插入这8个关键码后的散列表；(2)(5分)计算搜索成功的平均搜索长度ASL。【清华大学2000八(13分）】

27. 设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键码{10,100,32,45,58,126,3,29,200,400,0}散列到表中。

（1）散列函数采用除留余数法，用%hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。 （7分）

（2）散列函数采用先将关键码各位数字折叠相加，再用%hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。【清华大学 2001 五 （15分）】

28. 已知一组关键字为（26,36,41,38,44,15,68,12,06,51,25），用链地址法解决冲突。假

设装填因子a=0.75，散列函数的形式为H（K）=K MOD P，回答下列问题： （1） 构造出散列函数；（3分） （2） 计算出等概率情况下查找成功的平均查找长度；（3分） （3） 计算出等概率情况下查找失败的平均查找长度；（3分）【东北大学 1999 一、3 (共9分)】

29. 在B-树和B+树中查找关键字时，有什么不同？【东北大学 2002 一 、5 (2分)】

30. 简要叙述B树(有些教材中称为B-树)与B+树的区别?【南京航空航天大学 1999 六 （5分）】31. 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。）【北京大学 1997 五、2 （6分）】

32. 给定关键码序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，规定负载因子α=0.6。

（1）请给出除余法的散列函数。

（2）用开地址线性探测法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。

【北京大学 1997 三（6分）】

33. 已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）【东北大学1998一、2 (10分)】 34. 设有一棵空的３阶B-树，依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99，请画出该树。

【华南理工大学 2001 一、5 （4分）】

35．设依以下次序给出关键字：34,16,19,21,5,49,24,62,3,17,45,8，构造3阶B-树。要求从空树开始，每插入一个关键字,画出一个树形。【南开大学 1997 六 (10分)】 36.高度为h的m阶B树至少有多少个结点？【西安电子科技大学2000软件一、6 （5分）】

37. 对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。【合肥工业大学 1999 四、3 （1）插入90 （2） 插入25 （3） 插入45 （4）删除60 （5）删除80

38. 已知2棵2-3 B-树如下（省略外结点）：【吉林大学 1999 一、4 (4分)】 （1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2）对树（b）,请分别画出先后删除53，37两个结点后的树形。

(a)

5分）】 （

（b） 39. 四阶B树中（如图所示），插入关键字87，试画出插入调整后树的形状【东南大学 1999 五 （15分）】

30 60 80

20 25 35 50 60 70 75 82 85 90

40. 下图是5阶B树 ，画出删去P后的B树，再画出删去D后的B树。【厦门大学 2000 二、2 （20/3分）】

41. 满二叉检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？【东南大学 1995 五 （6分）】

42. 设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。试按照最大关键码复写原则绘出相应的2阶 B+ 树。

【山东工业大学 1996 二、1 （6分）】

43. 在一棵B+树上一般可进行那两种方式的查找运算?【北京科技大学 2001 一、8 （2分）】 44. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

【北京轻工业学院 2000 八 （10分）】

45. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？【长沙铁道学院 1997 三、4 (3分)】

46. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

【厦门大学 2002 八、2 （5分）】

47. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

【山东大学 2001 七 ( 7分)】

48. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.【北京邮电大学 1999 七 （10分）】

49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树

【华中理工大学 2000 五 （10分）】

(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;

(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 50. 已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学 1996 四】 （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分）

（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。（8分）

51. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1） 按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小

的有序序列？

（2） 画出在此二叉排序树中删除“66”后的树结构。【同济大学 2001 一 (10分)】 52. 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。【东北大学 2002 一 、3 (4分)】

（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363

53. 用关键字1,2,3,4的四个结点（1）能构造出几种不同的二叉排序树？其中（2）最优查找树有几种？（3）AVL树有几种？(4)完全二叉树有几种？试画出这些二叉排序树。【北京工业大学 1997 二、 3 ( 5分)】 类似本题的另外叙述有：

(1)设有关键字A、B、C和D，依照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。 【北京大学 1995 】

54. 一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？【浙江大学 1995 六 (8

分)】

55. 设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。

【吉林大学 1996 四、2】

56．设二叉树HT是一棵高度平衡树，当使用二叉查找与插入算法插入一个新的结点时，该操作可能会破坏HT的平衡性。试列举出可能破坏HT的平衡性的所有情况，并论证你的结论的正确性（即要证明你所列举的情况恰好是可能破坏HT的平衡性的所有情况）【吉林大学1998 四 1997 六 (14分)】 57. 按下述次序输入关键字：e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。（要求画出每插入一个关键字检索树的形状及调整后的结果）。【山东大学 1992 一 、5 (3分)】 58. 已知一棵高度平衡树如下，其中各结点间大小关系（中根次序）按字典序排列，请画出

插入结点JUN后，该二叉树经平衡过程而形成的树形，并说明采用何种转动方式，标出平衡后树中各结点的平衡系数。【吉林大学 1999 一 、1 (4分)】

59. 已知长度为l2的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

（1） 试按表中元素的次序依次插入一棵初始为空的二叉排序树，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找成功的平均查找长度。 （3） 按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。

【中国矿业大学 2000 七（10分）】

60. 试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。

【清华大学 1994 三（10分）】

61. 给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO}，假定关键词

比较按英文字典序，

（1）试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用高度平衡树的查找和插入算法生成一棵高度平衡树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。

（2）试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除结点CAN和AQU后的树形，要求删除后的树形仍为一棵高度平衡树，并说明删除过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。 【吉林大学 2000 一 、5 (6分)】

62. 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 (1) 请画出调整后的AVL树。

(2) 假设AVL树用llink-rlink法存储，t是指向根结点的指针，请用Pascal(或C)语句

表示出这个调整过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题中所给出的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用。【北京大学 1997 六）（10分）】

t .

100 -- 60 + 120 · -

40 ·-- 80 -

·- 70

63. 若以序列 {Thu,Tue,Wed,Last,Fri,Sat,Mon,Sun,Next} 作为输入序列

(1) 按算法AVL-INSERT构造均高树，画出构造过程和进行平衡转换的类型。

(2) 若均高树中有n个结点，其高度为h，指出在最坏情况下，对该树的插入、删除和依次输出操作的时间复杂性。 【东南大学 1992 五（18分）】

64. 在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为

1-N。要查找给定的X落入的区间号，您认为应怎样组织数据结构，选择什么方法最快，简述原因。

【西北大学 2000 二、4 (5分)】

65. 有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况

下，查找成功所需的平均比较次数是多少？【吉林大学 2001 一、 1 (3分)】

66. 若对一个线性表进行折半查找，该线性表应满足什么条件？【北京航空航天大学 1998 一、8 （4分）】

67. 在查找和排序算法中，监视哨的作用是什么？【长沙铁道学院 1997 三、3 (3分)】 68. 长度为255的有序表采用分块查找，块的大小应取多少？【首都经贸大学 1997 一、1 （4分）】

69. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【厦门大学 1999 三、2】

70. 设有n个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这n个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。【西安电子科技大学 1996 四 （10分）】 71. 对有14个元素的有序表A[1?14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？

【燕山大学 2000 一、2 （1分）】 72. 解答下面的问题

（1）画出在递增有序表A[1..21]中进行折半查找的判定树。

（2）当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？ （3）折半查找的平均查找长度是多少？【西安电子科技大学2000计应用 八 （10分）】 73. 设有一组数据black,blue,green,purple,red,white,yellow，它们的查找概率分别为0.10,0.08,0.12,0.05,0.20,0.25,0.20。 试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997 七 （12分）】 74. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 二 (10分)】

75. 在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Li，那么查找失败到达失败结点时所作的数据比较次数是多少？【清华大学 1999 一、4 （2分）】

76. 设有五个数据do，for，if,repeat，while，它们排在一个有序表中，其查找概率分别

为p1 =0.2, p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。 do for if repeat while

q0 p1 q1 p2 q2 p3 q3 p4 q4 p5 q5

(1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。（6分） (2) 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（4分）

(3) 判定是顺序查找好？还是折半查找好？（2分） 【清华大学 1999年 二 （12分）】

77. 顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？【北京邮电大学 1993 一、2 (5分)】

五、 算法设计题

2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：

① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

22222

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个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。 （4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。 （5）记录 负载因子

3．评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。

4．哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。

5．不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。 6．

散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

23

H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。 7．由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。 （1）用除留余数法，哈希函数为H（key）=key % 7

（2）

散列地址 0 关键字 21 比较次数 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败时的平均查找长度为：

ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 ASLsucc =16/8=2 （4）int Delete（int h[n]，int k）

// 从哈希表h[n]中删除元素k，若删除成功返回1，否则返回0 {i=k%7；// 哈希函数用上面（1），即H（key）=key % 7

if（h[i]== maxint）//maxint解释成空地址

printf（“无关键字%d\\n”，k）；return （0）；}

if（h[i]==k）{h[i]=-maxint ；return （1）；} //被删元素换成最大机器数的负数

else // 采用线性探测再散列解决冲突 {j=i;

for（d=1；d≤n-1；d++）

{i=（j+d）%n； // n为表长，此处为10

if（h[i]== maxint）return (0); //maxint解释成空地址

if（h[i]==k）{ h[i]=-maxint ；return （1）；} }//for }

printf（“无关键字%d\\n”，k）；return (0) } 8． 散列地址 0 关键字 比较次数 散列地址 0 关键字 比较次数 1 15 1 1 15 1 2 2 17 3 3 24 1 3 24 1 4 10 2 4 10 2 5 19 1 5 19 1 6 17 4 6 40 2 7 38 5 7 38 4 8 18 5 8 18 4 9 40 5 9 哈希表a: ASLsucc=24/8=3；

哈希表b: ASLsucc =18/8 9．（1）

散列地址 0 关键字 13 比较次数 1 1 22 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13

10． 11．ASLsucc=19/12 12．常用构造哈希函数的方法有：

（1）数字分析法 该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。

（2）平方取中法 将关键字值的平方取中间几位作哈希地址。

（3）除留余数法 H（key）=key%p，通常p取小于等于表长的最大素数。

（4）折叠法 将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。

（5）基数转换法 两基数要互素，且后一基数要大于前一基数。

在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。

散列地址 0 1 关键字 13．（1） 散列地址 0 关键字 比较次数 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 比较次数 1 2 2 3 1 4 4 5 3 6 1 7 1 8 3 9 9 10 11 12 13 14 15 1 1 3 14 01 68 27 55 19 20 84 79 23 11 10 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8 ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

（2）

13题图ASLsucc =11/8 ASLunsucc=19/11 14题（2） ASLsucc=13/8 ASLunsucc=19/11

值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11

14．由hashf(x)=x mod 11 可知，散列地址空间是0到10，由于有8个数据，装载因子取0.7。 （1） 散列地址 0 关键字 33 比较次数 1 1 1 1 2 13 1 3 12 3 4 34 4 5 38 1 6 27 2 7 22 8 8 9 10 ASLsucc=21/8 ASLunsucc=47/11 15．

（1）ASL=42/12

（2）a：ASLsucc=31/12 （2）b：ASLsucc=18/12 (注：本题[x]取小于等于x的最大整数) 16．

17．查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次

18．ASLsucc =15/10

19．ASLsuss =16/11

20． 散列地址 0 关键字 比较次数 1 ASLsucc =21/11 21． 散列地址 0 关键字 22． （1）

散列0 地址 关键字

1 1 2 1 3 1 4 2 5 1 6 2 7 3 8 2 9 4 10 3 11 231 89 79 25 47 16 38 82 51 39 151 1 33 2 2 46 1 3 13 2 4 01 4 5 67 5 6 7 8 41 1 9 53 1 10 30 3 22 比较次数 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10

比较1 次数 1 6 3 1 2 1 1 1 3 3 （2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。 （3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。 （4）ASLsucc=23/11

23．设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。

从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。 24．（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2） 散列地址 关键字 比较次数 0 be 1 1 cd 2 1 2 1 2 aa 1 3 ab 1 4 ac 1 6 1 5 ad 1 7 2 6 bd 1 8 3 7 bc 3 9 4 8 ae 3 9 ce 9 25．α=0.7，所以表长取m=7/0.7=10 散列地址 0 关键字 比较次数 6 3 4 5 1 SAT WED SUN MON TUE THU FRI ASLsucc=18/7 ASLunsucc=32/10 26．（1）

散列地址 0 关键字 比较次数 3 1 1 2 3 4 5 1 1 6 1 7 1 8 9 1 2 10 11 12 27 53 2 31 19 20 8 18 （2）ASLsuss =11/8 27．（1）

散列地址 0 1 2 3 4 关键字 0 比较次数 1 1 2 5 1 6 1 7 2 8 3 9 1 10 11 1 3 12 3 3 29 200 32 45 58 100 10 126 400 关键字29和45各发生一次碰撞，关键字58,126和400各发生两次碰撞，其余关键字无碰撞。 （2） 散列地址 0 关键字 比较次数 1 1 1 2 2 3 4 1 3 5 1 6 3 7 8 9 8 1 10 2 11 12 1 58 10 100 3 200 32 400 0 45 126 29 发生碰撞次数：100，126一次；200，400两次；0七次。其余关键字无碰撞。 28．由α=0.75，得表长m=11/0.75=15

（1）散列函数H（k）=k MOD 13（p取小于等于表长的最大素数）

（2）因为p=13，散列地址取0到12，用链地址法解决冲突，实际长就取13。

（2）ASLsucc=18/11 （3）ASLunsucc=24/13

29．在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

30．m阶的B+树和B-树主要区别有三：（1）有n棵子树的结点中含有n（B-树中n-1）个关键字；（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能顺序查找。

31．本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有?m/2?

l-1

棵子树，则第三层至少有?m/2?*2个结点，第l+1层至少有2*?m/2?个结点。设B-树深度

l-1

为l+1，即第l+1层是叶子结点，叶子结点数是n+1（下面推导），故有n+1≥2*?m/2?，

即l≤log?m/2?（

）+1。

附：推导B-树中叶子结点数s与关键字数n的关系式：s=n+1

设B-树某结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树，有

∑Ni=∑(Ci-1)=∑Ci-k（1≤i≤k） ??（1）

因为B树上的关键字数，即∑Ni=n （1≤i≤k） ??（2）

而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为s；则

∑Ci=(k-1)+s （1≤i≤k） ??（3）

综合（1）（2）（3）式，有s=n+1。证毕。 32．表长m=12/0.6=20 （1）H（key）=key MOD 19

（2）两次碰撞。开地址线性探测法解决冲突，即是用拉链法解决冲突。见本章四第2题（2）③

第32题用拉链法解决冲突

33．由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。

散列地址 100 101 102 103 104 105 106 107 108 109 关键字 98 63 2 79 1 17 1 53 1 19 1 61 2 75 3 46 5 49 10 比较次数 1 用线性探测再散列解决冲突，ASLsucc=27/10

34．

35．

36．第一层有1个结点，第二层至少有2个结点，第三层有2*?m/2?个结点，第四层有2*?m/2?

h-2

个结点，??，第h层至少有2*?m/2?个结点（h≥2）。结点总数是

2h-2h-1

1+2+2*?m/2?+2*?m/2?+?+2*?m/2?=2*?m/2?-1

2

37．

38.

39．

40．（该题答案不唯一。如删P时，亦可将双亲结点中M下来与N一起并入左兄弟成为（K L M N）

41．满二叉检索树可以看作是三阶B-树（2—3树）。B-树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。 42．

43．B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。

44．含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到最大值8个，其中第一层一个，第二层两个，第三层五个非叶子结点。

45．在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。

46．按中序遍历序列将值1~9依次标上。 47．

ASLsucc=(1*1+2*2+4*3+4*4)/11=33/11

48.

ASLsucc=32/10

49. （2）10,12,15,20,24,28,30,35,46,50,55,68

（3）ASLsucc=41/12 50．

51．

52．序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。

53．（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，也即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的

n

数目为1/（n+1）C2n，这里n=4，故有14种。图示如下：

（2）最优查找树有4种，上面中⑽ ⑾ ⑿ ⒀ （3）AVL树有，也是（2）中的那4种 （4）完全二叉树有1种，上图中⑽

54．设以Nm表示深度为m的AVL树中含有的最少结点数。显然，N0=0，N1 =1，N2 =2，且Nm = Nm-1 + Nm-2 +1（m≥2）。这个关系与斐波那契序列类似，用归纳法可以证明：当m≥0时，Nm = Fm+2 -1，而Fm约等于Φ/

m

（其中Φ=（1+）/2），则Nm约等于Φ/

m+2

-1（即深

度为m的AVL树具有的最少结点数）

m

当m层的AVL树是满二叉树时，结点数为最大值2-1。

55．树的高度一定增加。因为“查找路径上的任一结点的平衡系数皆为零”，从根结点开始查找，根结点的平衡系数为零，说明根的左右子树等高（不一定是满二叉树）。沿左（或右）子树向下查找时，查找路径上所有结点的平衡系数皆为零，说明任一结点的左右子树等高，查找失败是在叶子结点，插入也是在叶子结点，树的高度自然增加。 56．

四种破坏平衡的情况，a,b,c是结点指针，虚线部分是在失去平衡前的图中未画出部分，该部分若存在，则在调整后应按虚线指出的连接。其它，如LL型，a指针所指结点可能有右子树，c指针所指结点可能有左右子树，这些在调整后均不受影响，故没画出。 57．

58．LR型旋转

59．

（1）ASLsuss =（1*1+2*2+3*3+4*3+5*2+6*1）/12=42/12 （2）ASLsuss =（1*1+2*2+4*3+5*4）/12=37/12 （3）ASLsuss =（1*1+2*2+4*3+4*4+5*1）/12=38/12 60．

61．

说明：在（3）后，先删除结点CAN并未破坏平衡，在删AQU后破坏了平衡，根结点CAP的平衡因子为-2。需作何种调整，要看CAP右子树PIS的平衡因子，若该平衡因子是1，则作RL型调整；若为-1，则作RR型调整；若为0，则RR和RL均可，为简单计，选RR型。当然，在PIS平衡因子为零后，还可继续往下分析。

62． 63．（1）

（2）最坏情况下，对该树的插入、删除和依次输出的时间复杂性分别是O(h)，O(nlog2h)和O(n)。

64．按索引顺序查找分块组织数据。N个区间分块有序，区间（块）内无序，将块内最大关键字置于块内最后一个位置，即向量下标为ik-1，其中i=1，2，?，N-1，k为每区间的长度（最后一个区间的最大关键字置于向量最后一个位置）。查找时，若N较小，可用顺序查找，依次将x与r[ik-1]*key进行比较，找到合适块后在块内顺序查找；若N很大，也可用折半查找，以确定x所在块，在块内顺序查找。 65．37/12

66．线性表应顺序存储且数据有序。

67．监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

68．表长为n，每块大小取n时，平均查找长度取最小值n+1。若n=255，则每块长度为16。

69．表长2000，分成45块，每块的理想长度为45（最后一块长20）。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5（顺序查找确定块），或ASL=19（折半查找确定块）。

70．将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较，??，比较中的小者放前半部，大者放后半部，用了?n/2?次比较。再在前后两部分中分别简单选择最小和最大元素，各用?n/2?-1次比较。总共用了3*?n/2?-2次比较。 71．在有序表A[1..14]中，比较到A[4]时，已查找元素依次是A[7]，A[3]，A[5]。 72．（1）图中结点中的数字为元素在有序表中的下标

1/21/2

（2）插入排序中，用折半查找确定待插入元素位置，比直接插入排序减少了比较次数，但数据移动次数没有改变，排序的时间复杂度也未改变。

（3）折半查找的平均查找长度是((n+1)/n)log2(n+1)-1≈log(n+1)-1。本例ASL=79/21。 73．根据次优查找树的定义，首先取第i个记录（l≤i≤h）构造根结点，使

△Pj=|-| 取最小值。

关键字 black blue green purple red white yellow 权值 0.10 0.08 0.12 0.05 0.20 0.25 0.20 j 1 2 3 4 5 6 7 SWj 0.1 0.18 0.30 0.35 0.55 0.80 1.00 △Pj 0.9 0.72 0.52 0.35 0.10 0.35 0.80 （根） ↑i

△Pj 0.25 0.07 0.13 0.30 0.20 0.25 ↑i ↑i △Pj 0.05 0.12 ↑i

red blue black white white yellow green black blue red green yellow purple

purple

73题（1）次优查找树 73题（2）调整后的次优查找树

查找成功的平均查找长度是=1*0.25+2*(0.12+0.20)+3*(0.1+0.08+0.20)+4*0.05=2.23 由于在构造次优查找树的过程中，没有考查单个关键字的相应权值，可能出现根的关键字的权值比之相邻的关键字的权值小，这时要作调整：选邻近的权值较大的关键字作次优查找树的根结点。调整后的次优查找树如图73（2）。 74．

75．这里失败结点是不存在的结点，在其双亲结点处查找失败，这时的比较次数为Li-1。

76．

（1） 顺序查找判定树

（2）ASL顺序成功 =（1p1 +2p2+3p3+4p4+5p5)=0.97 ASL折半成功 =（1p3+2（p1+p4）+3（p2+p5)=1.04 ASL折半失败 =（2q0+3q1+3q2+2q3+3q4+3q5)=1.30 ASL顺序失败 =（1q0+2q1+3q2+4q3+5q4+5q5)=1.07 （3）本题中顺序检索好。

77．时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O（1），查找速度最快，但需构建哈希函数，进行计算哈希地址，查找时要有解决冲突的方法；二分检索时间O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间最差为O（n），但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。

五．算法设计题

1． 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱

结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 #define true 1 #define false 0

typedef struct node

{datatype data; struct node *llink,*rlink;} *BTree; void JudgeBST（BTree t,int flag）

// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if（t!=null && flag）

{ Judgebst（t->llink,flag）；// 中序遍历左子树

if（pre==null）pre=t；// 中序遍历的第一个结点不必判断

else if（pre->datadata）pre=t；//前驱指针指向当前结点 else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树 }//JudgeBST算法结束

本题的另一算法是照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：

int JudgeBST（BTree t）

//判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false {if（t==null）return true；

if（Judgebst（t->llink）&& Judgebst（t->rlink））//若左右子树均为二叉排序树

{m=max（t->llink）；n=min（t->rlink）；//左子树中最大值和右子树中最小值 return （t->data>m && t->data

int max（BTree p）//求二叉树左子树的最大值

{if（p==null） return -maxint；//返回机器最小整数 else{while（p->rlink！=null）p=p->rlink； return p->data；} }

int min（BTree p）//求二叉树右子树的最小值

{if（p==null） return maxint；//返回机器最大整数 else{while（p->llink！=null）p=p->llink； return p->data；} }

2．[题目分析]借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块（元素个数不一定相等），索引表中有两个域，一是各集合最后一个元素在数据表中的位置（一维数组中的下标），二是集合的个数（k）。实现数据运算时，根据给定的二元组（i，x），首先在索引表中找到集合i的位置，然后在数据表中查找x。如查到x ，则查找成功，返回x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。

typedef struct {datatype data；}rectype； typedef struct

{int a[]；//a数组容量够大，存储各集合最后一个数据在数据表中的下标 int k； //集合个数 }index；

int SetSearch_Insert（rectype R[]，index id，datatype x，int i）

//数据表R，查找第i个集合的元素x，若查找成功，返回其位置，否则将其插入第i个集合

{if（i<1 || i>id.k）printf（“无第%d个集合\\n”，i）；exit（0）；}

if（i==1）first=0；else first=id.a[i-1]+1； //first指向第i个集合在数据表的首址

last= id.a[i]；//last是第i个集合在数据表中的末址

for（j=first；j≤last；j++） if（R[j]==x）return （j）；//查找成功 for（j=id.a[id.k]；j>id.a[i]；j--） //查找失败，将x插入数据表 R[j+1]=R[j]；//元素后移

R[j+1]=x； //将x插入到原第i个集合最后一个元素之后。

for（j=i；j≤k；j++）id.a[j]++；//修改索引表中各集合最后一个元素的下标 }结束SetSearch_Insert

由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（2,11.2）和（1,5.3），数据表前后状态如下： 插0 入10.前 2 插10.入2 后 1 1.7 1.7 2 4.8 4.8 3 16.2 16.2 4 1.7 5.3 5 8.4 1.7 6 0.5 8.4 7 4.8 0.5 8 9 10 11 12 13 14 2.7 4.2 5.1 3.6 3.9 2.7 5.1 3.9 4.2 3.6 11.2 4.8 插入前,索引表中a数组的内容是3，6，12，插入后修改为4，8，14。 3．（1）非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 void Creat_BST（BiTree bst，datatype K[]，int n）

// 以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树。 {for（i=1；i≤n；i++）

{p=bst；f=null；//在调用Creat_BST时，bst=null while（p!=null）

if（p->dataRLINK； } // f是p的双亲 else if（p->data>K[i]）{ f=p；p=p->LLINK；}

s=（BiTree）malloc（sizeof （BiNode））；// 申请结点空间 s->data=K[i]；s->LLINK=null；s->RLINK=null； if（f==null）bst=s； //根结点 else if（s->datadata）f->LLINK=s；//左子女

else f->RLINK=s；//右子树根结点的值大于等于根结点的值 }//算法结束

（2）[题目分析]本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。

void Print（BiTree t）

//以嵌套括号表示结构打印二叉排序树 {if（t！=null）

{printf（t->data）；//打印根结点值

if（t->LLINK || t->LLINK）；//左子女和右子女中至少有一个不空 {printf（“（”）； //输出左括号

Print（t->LLINK）； //输出左子树的嵌套括号表示

if（t->RLINK）printf（“，”）；//若右子树不空，输出逗号 Print（t->RLINK）； //输出右子树的嵌套括号表示 printf（“）”）； //输出右括号 }//if }}//Print

4． void Delete（BSTree t，p）

// 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法

{if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q；

while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild） //p左子树的根结点无右子女

{p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} }

}//Delete

5．[题目分析]上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。

void Delete(BSTree bst,p,fp)

//在二叉排序树bst上，删除fp所指结点的左子女（由p所指向）的算法。

{if（!p->lchild）{fp->lchild=p->rchild；free（p）；} //p无左子女

else if（!p->rchild）{fp->lchild=p->lchild；free（p）；} //p无右子女

else // p有左子女和右子女

{q=p->rchild；s=q；//用p右子树中的最小值代替p结点的值

while（q->lchild）{s=q；q=q->lchild ；}//查p右子树中序序列最左结点 if（s==p->rchild） //p右子树的根结点无左子女

{p->data=s->data；p->rchild=s->rchild；free（s）；} else{p->data=q->data；s->lchild=q->rchild；free（q）；} }//Delete

6．[题目分析] 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。

void Delete(BSTree bst, keytype X)

//在二叉排序树bst上，删除其关键字为X的结点。 {BSTree f,p=bst;

while (p && p->key!=X) //查找值为X的结点 if (p->key>X) {f=p; p=p->lchild;} else {f=p; p=p->rchild;}

if (p==null) {printf(“无关键字为X的结点\\n”); exit(0);} if {p->lchild==null} //被删结点无左子树

if (f->lchild==p) f->lchild=p->rchild;//将被删结点的右子树接到其双亲上 else f->rchild=p->rchild;

else {q=p; s=p->lchild; //被删结点有左子树

while (s->rchild !=null) //查左子树中最右下的结点（中序最后结点） {q=s; s=s->rchild;}

p->key=s->key; //结点值用其左子树最右下的结点的值代替 if (q==p) p->lchild=s->lchild;//被删结点左子树的根结点无右子女 else q->rchild=s->lchild; //s是被删结点左子树中序序列最后一个结点

free(s); }

}//算法结束

7．int Search（rectype r[ ]，int n，keytype k）

//在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。 {r[n+1].key=MAXINT；//在高端设置监视哨 i=1；

while（r[i].key

if (r[n+1].key==k) return （i%（n+1））； else return (0) }//算法search结束

查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为（n+1）/2。 8．FUNC Srch_Mtree（t:mblink；k：keytp）：result；

//在根结点指针为t的m阶B-树上查找关键字k，返回记录（pt，i，tag）。若查找成

功，

//置tag=1，等于k的关键字即pt所指结点中第i个关键字；若查找失败，关键字k应插入

//pt所指结点的第i和第i+1个关键字之间。

p:=t；q:=null；found:=false；i:=0；//p指向待查结点，q指向p的双亲结点 WHILE（p<>NIL）AND NOT found DO

[n:=p↑.keynum；i:=search（p,k）；//在p↑.key[1..n]中查找 IF（i>0）AND（p↑.key[i]=k）THEN found：=true ELSE[q:=p；p:=p↑.ptr[i]；] ]

IF found THEN return （p,i,1）//查找成功

ELSE return （q，i，0）//查找失败，返回插入位置

[算法讨论] 插入时，若所在结点关键字keynum

9．请参见上面题3(1)。

10．int BinSrch（rectype r[ ]，int k，low，high）

//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2；

if（r[mid].key==k）return （mid）；

else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））;

}

else return （0）；//查找失败。 }//算法结束

算法时间复杂度为O（logn）。

11．[题目分析] 在Trie树上查找给定值KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和KEY相等，则查找成功；若分枝结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。

typedef enum{LEAF，BRANCH}NodeKind；//结点种类{叶子，分枝} typedef struct TrieNode {NodeKind kind；

union {struct{KeyType K；Record *infoptr} lf； //叶子结点 struct{TrieNode *ptr[27]；int num} bh； //分枝结点 }；

}TrieNode，*TrieTree；//键树类型

Record *SearchTrie（TrieTree T，KeyType KEY） //在Trie树T中查找关键字等于K 的记录。

{for（P=T，i=0； //对KEY的每个字符逐个查找 P && P->kind==BRANCH && i

P=P->bh.ptr[ord（KEY.ch[i]）]，++i）；//ord求字符在字母表中的序号 if（P && P->kind==LEAF && P->lf.K==KEY ）return P->lf.infoptr；//查找成功 else return null； }//结束SearchTrie

12．[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。

typedef struct node {keytype key；

struct node *next； }HSNode；*HSList

typedef struct node *HLK；

void Delete（HLK HT[]，keytype K）

//用链地址法解决冲突，从哈希表中删去关键字为K的记录 {i=H（K）；//用哈希函数确定关键字K的哈希地址

if（HT[i]==null）{printf（“无被删除记录\\n”）；exit（0）；} HLK p,q; p=H[i]；q=p； //p指向当前记录（关键字），q是p的前驱 while（p && p->key！=k）{q=p；p=p->next；}

if（p==null）{printf（“无被删除记录”）；exit(0); } if（q==H[i]） //被删除关键字是链表中第一个结点 {HT[i]=HT[i].next；free（p）；} else{q->next=p->next；free（p）；} }//结束Delete

13．[题目分析] 本题仍用上面第12题定义的存储结构。首先计算关键字k的哈希地址，若该哈希地址的头指针为空，则直接插入；否则，先在该链表上查找，若查找失败，则插入链表；若查找成功，则不再插入。

void Insert（HLK HT[]，keytype K）

// 用链接表解决冲突的哈希表插入函数 {i=H（K）；// 计算关键字K的哈希地址

if（HT[i]==null）// 关键字K所在链表为空 {s=(HSNode *)malloc（sizeof （HSNode））；s->key=k; s->next=HT[i]；HT[i]=s；}

else //在链表中查询关键字K {p=HT[i]；

while（p && p->key！=k）p= p->next； if（！p）//链表中无关键字K，应该插入

{ s=（HSNode *）malloc（sizeof （HSNode））；

s->next= HT[i]；HT[i]=s；} // 插入后成为哈希地址为i的链表中的第一个结点

}

}//Insert 14．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete（rectype HS[]，K）

//在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K {i=K % P； // 以造表所用的除余法计算关键字K的散列地址

if（HS[i]==null）{printf（“散列表中无被删关键字”）；exit（0）；} // 此处null代表散列表初始化时的空值 switch

{case HS[i]==K：del(HS，i，i，K)；break；

case HS[i]!=K：di=1；j=(i+ di)%m； // m为 表长

while（HS[j]!=null && HS[j]!=K && j!=i）// 查找关键字K {di=di+1；

j=(i+di)%m； }// m为 表长

if（HS[j]==K）del(HS，i，j，K)； else {printf（“散列表中无被删关键字”）；exit（0）;}

}// switch }算法结束

void del（rectype HS[]，in i，int j，rectype K）

//在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。

{di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置 while（x!=i） //可能要探测一圈

{if（HS[x]==null）break； // 探测到空位置，结束探测 else if（HS[x]%P==i）last=x；// 关键字K的同义词 di=di+1；x=(j+di) % m； // 取下一地址探测

}

HS[j]=HS[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j

}

[算法讨论] 由于用线性探测解决冲突，可能发生“二次聚集”（两个第一哈希地址不同的记录争夺同一后继哈希地址）。象上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其它记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。

15．[题目分析]利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。

typedef struct node

{int data； struct node *left，*right; }BiTNode，*BSTree；

void DelTree(BSTree r）

//非递归删除以r为根的二叉排序树

{BSTree S[]；// 栈，容量足够大，栈中元素是二叉排序树结点的指针 top=0；

while （r!=null || top>0）

{while（r!=null） // 沿左分枝向下 {S[++top]=r；r=r->left ；}

if（top>0） // 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 {p=S[top--]；r=p->right；free（p）；} }

}// DelTree

void DeleteAllx(BSTree Ｔ，int x）

//在二叉排序树Ｔ中，删除所有小于等于x的结点 {BSTree p=T，q；

while（T && T->data≤x） //根结点的值小于等于x {p=T；T=T->right；p->right=null；

DelTree（p）；} //删除二叉树p,删除持续到“根”结点值大于x或T为空树为止 if (T)

{q=T；p=T->left；

while（p && p->data>x） //沿根结点左分枝向下，查小于等于x的结点 {while（p && p->data>x） { q=p；p=p->left；} // q记p的双亲 if（p） //p结点的值小于等于x

{q->left=p->right；p->right=null；DelTree（p）； } p=q->left；// 再查原p的右子树中小于等于x的结点 }}

}// DeleteAllx

16．typedef struct node {datatype data；

int count；

struct node * llink，*rlink； }BiTNode，*BSTree；

void Search_InsertX(BSTree t，datatype X） //在二叉排序树t中查找值为X的结点，若查到，则其结点的count域值增1，否则，

//将其插入到二叉排序树中。

{p=t；

while（p!=null && p->data!=X） //查找值为X的结点，f指向当前结点的双亲 {f=p；

if（p->datarlink; else p=p->llink;} if（!p） // 无值为x的结点，插入之

{p=（BiTNode *）malloc(sizeof （BiTNode））； p->data=X；p->llink=null；p->rlink=null；

if（f->data>X）f->llink=p；else f->rlink=p； }

else p->count++；// 查询成功，值域为X的结点的count增1。 }// Search_InsertX

17．[题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p）

{level++； // 树的高度增1

if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下

//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存

储定义

else p=p->lchild； //bf>=0 沿左分枝向下

}//while

return （level）；//平衡二叉树的高度

} //算法结束

18．[题目分析]二叉排序树的建立问题请参见上面题3（1）。将二叉排序树上的各整数按降序写入磁盘的问题，要对二叉排序树进行“中序遍历”。这里的“中序遍历”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。

int i=0,a[n];//长度为n的整型数组 void InOrder(BSTree t)

//先右后左的中序遍历二叉排序树t，假定该树t已在本题（1）中生成 {if (t)

{ InOrder(t->rchild) a[i++]=t->key; InOrder(t->lchild) }

}//InOrder

void SaveToDisk()

//将二叉排序树上的各整数按降序写入磁盘 {FILE *fp;

if ((fp=fopen(“file1.dat”, “wb”))==null) {printf(“file can not open!\\n”);exit(0); }

fwrite(a,sizeof (int),n,fp);//将数组a中的n个整数写入磁盘 fclose(fp);//关闭文件 }//SaveToDisk

19．本题的分析同第18题。这里直接写出算法 （1）递归算法

void DecPrint(BSTree t）

//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 {if（t）

{DecPrint(t->rchild)；

if（!t->lchild && t->rchild）printf(t->data：4） DecPrint(t->lchild）； }

}//DecPrint （2）非递归算法

void DecPrint(BSTree t）

// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 {BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0；

while（t || top>0） {while（t）

{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；

if（!t->lchild && t->rchild）printf(t->data：4)； t=t->lchild； // 去左分枝

}//if

}//while }//算法结束

20．[题目分析]这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构：

typedef struct node

{int A[m]； //每个结点内含有m个正整数，本例中m为5 struct node *next；//指向下一结点的指针 }LNode，*LinkList； typedef struct

{int j；// 正整数在结点内的序号 struct node *s；// 结点的指针 }rcd;

rcd *LSearch(LinkList head,int n)

//在链表中查找正整数n，若查找成功，返回该结点指针及n在结点中的序号； //否则返回空指针表示失败。 {rcd *R;

P=head->next；// 假定链表带头结点，P指向链表第一元素结点 found=0；

while（P && !found） {for(i=0;i

if(P->A[i]==n) found=1 //查找成功 P=P->next; //下一结点 }

if（P==null）return （null）；

else {R.j=i; R.s=P; return （R）；} }//LSearch

21．int Search（rectype R[]，int n,K）

// 在具有n个元素的有序表R中，顺序查找值为K的结点，查找成功返回其位置， //否则返回-1表示失败 {i=0；

while（i

{if（R[i]==K） return （i）；

else if（R[i]>K） return （-1）； i++;

}//while

return （-1）； }//结束search

在等概率情况下，则查找成功的平均查找长度为（n+1）/2，查找失败的平均查找长度为（n+2）/2（失败位置除小于每一个，还存在大于最后一个）。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)/4。

22．[题目分析]本题采用中序遍历，将遍历结点与前驱比较，若相同，则不输出并记数。 void BSTPrint(BSTree t,int *count）

//递增序输出二叉排序树中结点的值，滤去重复元素

{if（t）

{BSTPrint(t->lchild)； //中序遍历左子树

if（pre==null）pre=t; //pre是当前访问结点的前驱,调用本算法时初值为null else if(pre->key==t->key)*count++;//*count记重复元素，调用本算法时初值为0

else {printf（“M”,t->key）；pre=t；} // 前驱后移

BSTPrint(t->rchild)； //中序遍历右子树 }//if

}//结束BSTPrint 算法

23．[题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有

从根结点开始查找，找到结点值

// 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； printf（t->data：4）； Print（t->rchild）； } }

void PrintAllx(BSTree bst，datatype x）

//在二叉排序树bst中，查找值≥x的结点并输出

{p=bst； if（p）

{while（p && p->datarchild；//沿右分枝找第一个值≥x的结点 bst=p; //bst所指结点是值≥x的结点的树的根 if（p）

{f=p; p=p->lchild ；//找第一个值

while（p && p->data≥x）//沿左分枝向下，找第一个值

{f=p；p=p->lchild ；} //f是p的双亲结点的指针，且指向第一个值≥x的结点

if(p) f->lchild=null; //双亲与找到的第一个值

Print(bst)；//输出以bst为根的子树

}//while }//内层if（p） }//第一层if（p）

}//PrintAllx

24．[题目分析] 因为T是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点*x。若T的左子树为空，则其中序序号为1，否则为T->lchild->size+1。设T的中序序号为r，其左子女p的中序序号和右子女q的中序序号分别为r-p->rchild->size-1和r+q->lchild->size+1。

int Rank（tree T，node *x）

// 在二叉排序树T上，求结点x的中序序号

{if（T->lchild）r=T->lchild->size+1；else r=1；//根结点的中序序号 while（T）

if（T->key>x->key）//到左子树去查找 {T=T->lchild；

if（T）{if（T->rchild）r=r-T->rchild->size-1；else r=r-1；} }

else if（T->keykey）//到右子树去查找 {T=T->rchild;

if（T）{if（T->lchild）r=r+T->lchild->size+1；else r=r+1；}

}

else return （r）；//返回*x结点的中序序号

return （0）； //T树上无x结点。

}//结束算法Rank

算法2：本题的另一种解法是设r是以*x为根的中序序号。同样，若x的左子树为空，r=1;否则，r=x->lchild->size+1。利用结点的双亲域，上溯至根结点，即可求得*x的中序序号。

int Rank（tree T，node *x）

// 在二叉排序树T上，求结点x的中序序号

{{if（x->lchild）r=x->lchild->size+1；else r=1；//x的这个序号是暂时的 p=x; //p要上溯至根结点T，求出*x的中序序号 while (p!=T)

{if (p==p->parents->rchild) //p是其双亲的右子女 {if (p->parents->lchild==null) r++; else r=r+p->parent->lchild->size+1; }

else r-- //p是其双亲的左子女 p=p->parents; }//while return (r); }//Rank

25．[题目分析] 本题未直接给出哈希表表长，但已给出装填因子小于1，且哈希函数H（k）为关键字第一个字母在字母表中的序号，字母‘A’的序号为1，表长可设为n（n≥27），而链地址法中，表长26。查找不成功是指碰到空指针为止（另一种观点是空指针不计算比较次数）。

（1）void Print(rectype h[ ]）

//按关键字第一个字母在字母表中的顺序输出各关键字 {int i,j；

for（i=0;i≤26；i++） // 哈希地址0到26 {j=1；printf（“\\n”）；

while（h[j]!=null） // 设哈希表初始值为null

{if（ord（h[j]）==i）// ord（）取关键字第一字母在字母表中的序号 printf（“%s”，h[j]）；j=(j+1)% n； }}}

（2）int ASLHash（rectype h[ ]）

// 求链地址解决冲突的哈希表查找不成功时的平均查找长度 {int i,j；count=0；//记查找不成功的总的次数

LinkedList p；

for（i=0;i≤26；i++）

{p=h[i]；j=1；//按我们约定，查找不成功指到空指针为止。 while（p!=null）{j++；p=p->next；} count+=j； }

return （count/26.0）； }

26．[题目分析]非零元素个数是100，负载因子取0.8，表长125左右，取p为127，散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127，i，j为行值和列值。

#define m 127 typedef struct

{int i，j；datatype v;}triple； void CreatHT（triple H[m]）

//100个非零元素生成稀疏矩阵的哈希表，表中元素值均初始化为0。 {for（k=0；k<100；k++）

{scanf（&i,&j,&val）；//设元素值为整型 h=(3*i+2*j)% m； //计算哈希地址

while（HT[h].v!=0）) h=(h+1) % m; //线性探测哈希地址 HT[h].i=i；HT[h].j=j；HT[h].v=val； //非零元素存入哈希表 }

}//算法CreatHT结束

datatype Search（triple HT[m]，int i，int j）

//在哈希表中查找下标为i，j的非零元素，查找成功返回非零元素，否则返回零值。 {int h=(3*i+2*j) % m；

while ((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=（h+1）% m； return （HT[h].v）； }//Search

27．[题目分析] 本题哈希函数H（key），用线性探测解决冲突，空单元用EMPTY，删除标记用DELETED，占用单元用INUSE，其它均符合哈希表标准操作。 （1）int Search(rectype HT[]，int m，datatype key） //在长度为m的哈希表HT中查找关键字key，若查找成功，返回true，否则返回false。

{i=H（key）； // 计算哈希地址

if（HT[i]==EMPTY）return （false）； //查找失败 else if（HT[i]== key）return （true）； else {j=(i+1)% m； //形成探测序列 while（j!=i） //至多循环哈希表长

{if（HT[j]==key） return （true）； //查找成功 else if（HT[j]==EMPTY）return （false）；//查找失败

j=（j+1）% m；

}

return （false）；//查遍哈希表，未查到给定关键字key

}//else

//结束Search

（2）int Insert（rectype HT[]，int m，datatype key） //在长为m的哈希表中插入关键字key {i=H（key）；//计算哈希地址

if（HT[i]==EMPTY || HT[i]==DELETED） //若HT[i]空或删除标记。 {HT[i]=key；return （true）；} //插入成功 else //探测插入元素的散列地址 {j=(i+1)% m； while（j!=i）

{if（HT[j]==EMPTY || HT[j]==DELETED）

{HT[j]=key；return （true）；} //找到合适哈希地址，插入

本文来源：https://www.bwwdw.com/article/u8ow.html