数据结构-课件9

第九章查找9.1静态查找表9.2动态查找表9.3哈希表9.4例题解析1数据结构---第九章查找[相关概念]查找表是同一类型的记录(数据元素)的集合。查找指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值。关键字是记录(数据元素)中的某个数据项的值。

主关键字该关键字可以唯一地标识一个记录。

次关键字该关键字不能唯一标识一个记录。静态查找表对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找成功查找表中存在满足查找条件的记录。查找不成功查找表中不存在满足查找条件的记录。内查找整个查找过程都在内存中进行。外查找在查找过程中需要访问外存。2数据结构---第九章查找平均查找长度ASL

为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：

n：记录的个数

pi：查找第i个记录的概率(不特别声明时认为等概率pi=1/n)

ci：找到第i个记录所需的比较次数本章约定：关键字的类型为整型

keyotherinfo记录3数据结构---第九章查找[静态查找表上的基本运算](1)生成操作creat(st,n)(2)查找函数

search(st,K)返回元素/它在表中的位置(3)遍历操作traverse(st)[动态查找表上的基本运算](1)初始化操作initialize(dt)(2)查找函数

search(dt,K)

返回元素/它在表中的位置

(3)插入操作

insert(dt,e)(4)删除操作

delete(dt,K)

(5)遍历操作traverse(dt)4数据结构---第九章查找9.1静态查找表9.1.1顺序表的查找

(a1,a2,......an)

12nn+1r[1..n+1]a1a2anK

r[n+1].key=K

TYPErectype=RECORDkey：keytype；otherinfo：otherinfotype；END；

sqlisttp=ARRAY[1..n+1]OFrectype;5数据结构---第九章查找[算法描述]FUNCseqsrch(r:sqlisttp;K:keytype):integerr[1+n].key:=K;i:=1;WHILEr[i].keyKDOi:=i+1;IFi=n+1THENRETURN(0)ELSERETURN(i)ENDF;{seqsrch}[程序设计技巧]设置监视哨，提高算法效率。6数据结构---第九章查找[性能分析]空间复杂度：一个辅助空间。时间复杂度：1)查找成功时的平均查找长度设表中各记录查找概率相等

ASLs(n)==(1+2+...+n)/n=(n+1)/22)查找不成功时的平均查找长度ASLf

=n+1[算法特点]算法简单，对表结构无任何要求n很大时查找效率较低改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。7数据结构---第九章查找9.1.2有序表的查找

满足r[i].keyr[i+1].key,1i<n[折半(对半/二分)查找法的算法思想]12345678910110513192137566475808892

lowmidhigh=(low+high)/2

K=21lhmK=85lhm1116111615371194541011101098数据结构---第九章查找[性能分析]

h=log2n+1{同完全二叉树，二叉树性质4}成功查找时的平均查找长度：

ASLs=

例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找时的查找长度：h-1或h次-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h判定树（描述查找过程的二叉树）外结点内结点(n>50)><=9数据结构---第九章查找[算法特点]比顺序查找效率高查找之前需使顺序表有序不宜用于链接结构由“判定树”的启发，有序表的存储结构本身可按树状组织。对于非等概率查找，理想状态建立静态最优查找树(查找性能最佳的判定树)。带权内路径长度之和PH为最小值。

PH=与ASL成正比

其中n：二叉树上结点的个数(有序表长度)

hi：第i个结点在二叉树上的层次数

wi=cpi：c为某个常量；

pi：第i个结点的查找概率10数据结构---第九章查找由于静态最优查找树的构造开销较大，实用中建立次优查找树PH值近似为最小比静态最优查找树易于构造，时间开销少次优查找树构造原则使被访问结点两边尚未访问的结点的被访概率之和尽可能相等使高概率访问结点靠近根

例123456789101112关键字ABCDEFGHIJKL

权值823493267114次优查找树上的查找比较次数不超过树的深度，O(log2n)11数据结构---第九章查找9.1.4索引顺序表的查找

[表的构造]

索引表index[1..b]

最大关键字值224286起始地址159

主表r[1..n]（分块有序/有序）

key12221382833384286765063

其它项

123456789101112[分块查找步骤]1)折半或者顺序查找索引表，确定所在块2)在已确定的块中顺序查找(若块中有序也可折半查找)maxkeyaddr12数据结构---第九章查找[性能分析]

设b为索引表长度，s为块中记录个数顺序查找索引表+顺序查找被确定的块

ASLbs=

当s取时，ASLbs取最小值折半查找索引表+顺序查找被确定的块

ASLbs=[log2(b+1)-1]+(s+1)/2log2(n/s+1)+s/2分块查找效率介于顺序查找和折半查找之间13数据结构---第九章查找[算法特点]实用中，各块大小不一定相等分块查找的代价是附加索引表的存储空间开销和建立索引表的时间开销可以在主表的每块后预留空闲位置，以便进行插入和删除操作时只涉及相应的块和该块的索引项。主表中各块可以集中顺序存储，也可以按块分别顺序存储；主表中的记录还可以采用单链表，或每块组成一个单链表。14数据结构---第九章查找9.2动态查找表9.2.1二叉排序树9.2.2平衡二叉树9.2.3B-树9.2.4B+树9.2.5键树15数据结构---第九章查找9.2.1二叉排序树BST(二叉查找/搜索树)9.2.1.1定义

二叉排序树或者是空树，或者是满足如下性质的二叉树：1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；3)其左右子树本身又各是一棵二叉排序树9.2.1.2性质中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列45245312289016数据结构---第九章查找9.2.1.3在二叉排序树上的操作1)查找

K=28K=324545

24532453122890122890

32

srch_bst()2)插入

插入一定发生在叶结点上。

ins_bstree()bstbstff17数据结构---第九章查找3)

生成

反复执行以下操作

a.读入一个记录，设其关键字为K；b.调用srch_bst()，确定插入位置；

c.调用ins_bstree()，实施插入结点的操作；4)删除

53

20901050869541241528891304587899239(1)(2)(2)(3)18数据结构---第九章查找[被删除结点的不同情况分析]p^是叶子结点：修改其双亲指针即可p^只有左孩子：用p^的左子树代替以p^为根的子树

p^只有右孩子：用p^的右子树代替以p^为根的子树p^有两个孩子：找到p^的中序后继(或前趋)结点q^，q^的数据复制给p^，

删除只有右孩子(或左孩子)/无孩子的q^9.2.1.4性能分析给定树的形态，等概率查找成功时的ASL=

ci/n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2n关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树19数据结构---第九章查找9.2.2平衡二叉树(AVL树)9.2.2.1定义

平衡二叉树或者是空树，或者是满足如下性质的二叉排序树：1)它的左、右子树的高度之差的绝对值不超过1；2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子：该结点的左子树高度减去右子树的高度。

A1A-2B-1C-1B0C2D0E1F0D-1G0E0平衡二叉树非平衡二叉树20数据结构---第九章查找9.2.2.2定理一个具有n个结点的平衡二叉树形，其高度h为

log2(n+1)h1.4404log2(n+2)-0.328

结论：最坏情况下，AVL树的高度约为1.44log2n，而完全平衡的二叉树高度约为log2n，因此AVL树是接近最优的，其平均查找长度与log2n同数量级。9.2.2.3结点的存储结构

lchild

bfkeyotherinfo

rchild

lchild：左孩子指针

rchild：右孩子指针

bf：平衡因子

key：记录的关键字

otherinfo：记录的其它数据成分21数据结构---第九章查找9.2.2.4在平衡二叉树上的操作1)查找查找方法同二叉排序树。2)插入平衡二叉树的生成过程15-115-225015025025-1150350350

25-125-225-115035-115035-215065090090135090065022数据结构---第九章查找[调整范围的确定]插入结点后，找到离插入结点最近且平衡因子绝对值超过1的祖先结点，则以该结点为根的子树将是可能不平衡的最小子树，可将重新平衡的范围局限于这棵子树。[调整的规律]

设失去平衡的最小子树的根结点指针为aLL型平衡旋转——一次顺时针旋转

A1A2B0B0B1A0BLBRARARBRBL插入的结点ARBRBLa23数据结构---第九章查找RR型平衡旋转——一次逆时针旋转

aA-1A-2B0B0B-1A0LR型平衡旋转——一次逆时针旋转+一次顺时针旋转

A1A2C0B0

B-1B0(1)

A-1(0)C0C1(-1)BLBRALALBRBLBRBLALBLCLCRARBLCLCRARaBLCLARCR24数据结构---第九章查找RL型平衡旋转——一次顺时针旋转+一次逆时针旋转

A-1A-2

C0B0B1

A0(1)

B-1(0)C0C1(-1)3)删除（思路同插入）将删除结点q转化为q最多有一个孩子的情形，即若q有两个孩子，则以其中序前驱/后继结点r取代它，删除r；若树的平衡性被破坏，利用单一/双重旋转恢复。ALCRCLBRALCRCLBRALCLBRCR25数据结构---第九章查找9.2.3B-树B-树是一种平衡的多叉查找树。可应用于文件系统。9.2.3.1定义一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：（1）树中每个非叶结点至多有m棵子树；（2）若根结点是非叶结点，则至少有两棵子树；（3）除根之外的所有非叶结点至少有

m/2

棵子树；（4）所有的非叶结点中包含下列信息数据：

(n,P0,K1,P1,K2,……,Pn-1,Kn,Pn)

其中Ki为关键字，且Ki<Ki+1；Pi为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pn所指子树中所有结点的关键字均大于Kn（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。26数据结构---第九章查找

结点结构(n,A0,K1,A1,K2,A2,...,Kn,An)

[例]一棵4阶B-树(m=4)

1

40非叶根则2~m棵子树

1

203495872

1

^10^

1

^25

^

2^41^43^

1

^51^

1^65^

1^99^

m/2~m棵子树叶27数据结构---第九章查找9.2.3.2B-树的用途

当内存中不可能容纳所有数据记录时，在磁盘等直接存取设备上组织动态的查找表。B-树的根结点可以始终置于内存中；其余非叶结点放置在外存上，每一结点可作为一个读取单位（页/块）选取较大的阶次m，降低树的高度，减少外存访问次数B-树的信息组织方法每个记录的其它信息与关键字一起存储。查到关键字即可获取记录的完整信息。将记录的外存地址(页指针)与关键字一起存储。查到关键字时，还需根据该页指针访问外存。28数据结构---第九章查找9.2.3.3B-树上的基本运算1)查找[算法思想]设查找时给定值为K，从根结点开始(a)在当前结点p^中顺序或者折半查找若找到某个i，满足key[i]=K，则查找成功，返回p^、i、1

否则，确定满足key[i]<K<key[i+1]的i值(b)若p^结点中的ptr[i]为空指针，则查找失败，返回p^、i、0(c)从磁盘上读入ptr[i]指示的结点DiskRead(p^.ptr[i])，将此结点作为当前结点，转(a)[例]

K=43（查找成功）K=60（查找失败）29数据结构---第九章查找2)插入

设插入的关键字为K(a)在B-树中查找K，若查找到，则返回否则查找失败，查找操作定位于某个最低层的非叶结点(q^,i)，在相应的位置插入偶对[K,^](b)keynum加1，若当前结点未溢出(keynum<m)，

则写盘DiskWrite(q^)，返回(c)以key[m/2]为划分点，分裂当前结点为两个结点：(

m/2-1,ptr0,key1,...,keym/2-1,ptrm/2-1)——q^(m-m/2,ptrm/2,keym/2+1,...,keym,ptrm

)——新结点q1^

写盘DiskWrite(q^)，DiskWrite(q1^)(d)读当前结点的父结点到内存DiskRead(q^.parent)

将偶对(key[m/2],q1^)插入该父结点，以该父结点为当前结点q^，转(b)30[例1]

m=4的B-树

插入K=47

140

120

3495872

1^10^1^25^3^41^43^47^

1^51^1^65^1^99^[例2]插入K=45

140

120

3495872

1^10^1^25^4^41^43^45^47^1^51^1^65^1^99^(41)43(4547)q^q^31数据结构---第九章查找

140(43)49(5872)

120

443495872

1^10^1^25^1^41^2^45^47^1^51^1^65^1^99^

24049

120

14325872

1^10^1^25^1^41^2^45^47^1^51^1^65^1^99^

若由底向上至根结点仍需分裂时，需要构造新的根结点，B-树会增加一层。q1^q1^q^q^32数据结构---第九章查找3)生成

从空树起，逐个插入关键字得到。4)删除

设删除的关键字为K(a)在B-树中查找K，若未查找到，则返回否则查找成功，查找操作定位于某个结点q^，

且q^.key[i]为K(b)若q^结点不是最下层的非叶结点，则查找q^.ptr[i]所指子树的最小关键字x，用x替换key[i]，使问题转换为删除最下层的非叶结点上的关键字33数据结构---第九章查找

删除K=4924049

120

1

4325872

1^10^1^25^1

^41^2^45^47^1^51^1^65^1^99^(c)删除h层上的关键字，分三种情况处理：其所属结点的关键字个数>

m/2-1：简单删除

m=4，K=70

150150

1^45^

2^70^80^1^45^1^80^ptr[i]子树的最左下关键字(49的后继)34数据结构---第九章查找其所属结点的关键字个数=

m/2-1，

其左/右兄弟结点关键字个数>

m/2-1m=4，K=10

2

13302

1530

1^10^2^15^17^1^35^

1^13^1^17^1^35^其所属结点的关键字个数=

m/2-1，

其左/右兄弟结点关键字个数=

m/2-1

1^100^1^120^

2^160^190^2^110^120^2^160^190^“调剂”2

1101501150“合并”35数据结构---第九章查找

“连接”时出现的较为复杂情况的处理：

m=4，删除K=80

11001

100

1

50

1150

1150

1^25^1^80^1^120^

1^170^2^25^50^1^120^

1^170^

2100150

2^25^50^1^120^

1^170^“合并”“合并”36数据结构---第九章查找9.2.3.5B-树的高度及性能分析定理：对于任一棵具有n(n>0)个关键字的m(m>2)阶B-树，其树高h至多为logt((n+1)/2)+1。其中t=m/2决定B-树上操作的时间开销的两个主要因素外存的访问次数O(h)——O(logtn)CPU的在结点上的比较定位时间O(hm)/O(h*log2m)前者起主导作用作为外存上的动态查找表，m越大，则B-树的高度越小，时间性能越好；仅在内存中使用的B-树必须取较小的m，通常取最小值m=337数据结构---第九章查找9.2.4B+树

B+树是一种B-树的变形树。应用于索引顺序文件系统（参见第十二章文件VSAM文件）。9.2.4.1定义

m阶B+树每个非叶结点至多可以有m个子树若根结点不是叶子结点，则至少有两棵子树除根结点之外的所有非终端结点则至少有

m/2棵子树有n个子树的非叶结点必须有n个关键字所有的叶子结点都在同一层上38数据结构---第九章查找[结点结构]非叶结点(A1,K1,...,Ai,Ki,...,Kn,An)索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字叶结点全部关键字及指向关键字记录的指针数据集

2153344047586727985390961052851323336785210513221141324阶B+树rootsqt39数据结构---第九章查找9.2.4.2B+树上的基本运算1)查找方式1：从根结点开始，利用索引集结构，向下查找直到叶子结点方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入

仅在叶子结点上进行，关键字个数大于m则分裂3)删除也仅在叶子结点上进行，关键字个数小于

m/2时，需进行合并40数据结构---第九章查找9.2.5键树(数字查找树/字符树)9.2.5.1概念

将关键字分解为字符的多叉树，多叉树中的每个结点只代表关键字中的一个字符，叶结点用于表示字符串的结束符(如‘$’)，并含有指向该关键字记录的指针。从根到叶子的路径上所有的结点对应的字符连接起来就代表一个关键字。约定键树是有序树结束符小于任何字符[例1]关键字集合{beg,bell,big,log,long,nil}blneiog$ll$gng$$il$g$41数据结构---第九章查找[例2]{6，71，78，99，235，243，467}24679024346$189079346537$$$6189537$$$$$$$$$$

按纯字符串考虑按整形数考虑9.2.5.2键树的存储结构及其操作1)双链树——以树的孩子兄弟链表表示2)Trie树——以多重链表表示42数据结构---第九章查找9.3哈希表(杂凑表、散列表)9.3.1概述[哈希表的技术特点]

通过对记录的关键字进行某种运算后，直接寻址，进行关键字查找时不需比较，使查找的期望时间为O(1)。[术语]

哈希表：一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。

哈希函数：记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)

冲突：对于keyi

keyj，ij，出现的H(keyi)=H(keyj)的现象。

43数据结构---第九章查找

同义词：在同一地址出现冲突的各关键字。

哈希(散列)地址：根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。

装填因子：表中填入的记录数n和哈希表表长m之比。

=n/m[设计哈希表的过程]

1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。哈希表bb+(m-1)L44数据结构---第九章查找9.3.2哈希函数的基本构造方法

构造原则：算法简单，运算量小；均匀分布，减少冲突。[直接定址法]H(key)=a*key+b

特点：计算简单，冲突最少。[数字分析法]取关键字的若干数位作为哈希地址。[平方取中法]取关键字平方后的中间几位作为哈希地址。45数据结构---第九章查找[折叠法]将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几个部分的叠加和(舍去进位)作为哈希地址。[除留余数法]H(key)=keyMODp(pm)m:哈希表的表长；p:最好为素数[随机数法]H(key)=random(key)

特点：较适于关键字长度不等时的情况。46数据结构---第九章查找9.3.3处理冲突的常用方法[开放定址法(空缺编址法)]

Hi=(H(key)+di)MODm0H(key)m-1i=1,2,...,k(km-1)m:哈希表的表长；di:增量序列

1)线性探测再散列：di=1,2,...,m-1

缺陷：有聚集(堆积)现象—非同义词地址冲突。2)二次探测再散列：di=12,-12,22,-22,32,...,k2

km/2

缺陷：不易探查到整个散列空间。3)伪随机探测再散列：di=伪随机数序列47数据结构---第九章查找

4)双重散列函数探查法：di=i*h1(key)

0<im-1

要求：h1(key)的值与m互素。

m为素数时，h1(key)可取1到m-1之间的任何数，建议h1(key)=keymod(m-2)+1m为2的方幂时，h1(key)可取1到m-1之间的任何奇数开放定址法不宜执行删除操作[再哈希法]

Hi

=RHi(key)i=1,2,...,k48数据结构---第九章查找[链地址法]为每个哈希地址建立一个单链表，存储所有具有同义词的记录。

b^b+Lfireto

^b+(m-1)Lseeks^冲突处理简单，无堆积现象，平均查找长度较短；较适合于事先无法确定表长的情况；可取1，当结点信息规模较大时，节省空间删除结点的操作易于实现[建立一个公共溢出区]基本表

溢出表49数据结构---第九章查找9.3.4哈希表的查找及其分析[例]

key=entotrefirefemseks

syvH(key)=2030481

解决冲突方法：线性探测再散列012345678

ASLs=(1+1+1+2+1+1+5)=

ASLf

=(7+6+5+4+3+2+1+1+8)/9=37/9entotrefirefemsekssyv50数据结构---第九章查找[平均查找长度与哈希表的装填因子的关系]在一般情况下，，冲突的可能性，ASL，但空间的浪费。

成功ASL失败ASL

线性探测再散列

伪随机探测再散列链地址法51数据结构---第九章查找9.4例题解析选择题1.(北邮2001)将10个元素散列到100000个单元的哈希表中，则（一定会/一定不会/仍可能会）产生冲突。2.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A.nB.(n+1)/2C.n/2D.(n-1)/23.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，（）次比较后查找成功。

A.1B.2C.4D.84.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。

A.2k-1B.2k-1+1C.2k-1D.2k52数据结构---第九章查找5.某棵二叉排序树上的结点关键字的集合是(16,22,31,46,49,53,70)，若指定查找关键字44，查找过程中，与44比较的关键字序列不可能出现的是（）。

A.22,46,31B.31,53,49,46C.31,53,46D.46,22,16,316.m路B+树是一棵（）。

A.m路平衡查找树

B.m路平衡索引树

C.m路trie树

D.m路键树7.假定有K个关键字互为同义词，若用线性探测法把它们存入散列表中，至少要进行（）次探测。

A.K-1

B.KC.K+1D.K（K+1）/2

1+2+…+K=K（K+1）/253数据结构---第九章查找判断题1.(北邮2002)查找相同结点的效率折半查找总比顺序查找高。

2.折半查找和二叉排序树的时间性能相同。

2.在散列存储中，装填因子的值越大，则存取元素时发生冲突的可能性就越大。

3.长度为625的表，采用分块查找法，每块的最佳长度是25。

4.查找表是以集合为逻辑结构。

5.完全二叉树属于树表。

6.散列函数一般是多对一的函数。

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

54数据结构---第九章查找8.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

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

10.装填因子是散列表的一个重要参数，它反映散列表的装满程度。

55数据结构---第九章查找填空题1.最优二叉树（哈夫曼树）、最优查找树均为表达式最小的树，其中对最优二叉树，n表示（叶结点数），对最优查找树，n表示（结点数）。2.高度为8的平衡二叉树的结点数至少为（54）。

f(8)=1+f(7)+f(6)=…….=33+21f(1)+13f(0)=33+21*1+13*0=543.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，且A的左子的平衡因子为-1，右子的平衡因子为0，则应做（LR）调整以使其平衡。f(7)f(6)A56数据结构---第九章查找求解题1.(北邮2001)画出按下表中元素的顺序构造的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度，{15,12,24,3,27,21,18,6,36,33,30,26,32}[解]241530621273331218263236

ASL=（1*1+2*2+3*4+4*6）/13=41/13=3.1557数据结构---第九章查找2.(北邮2002)长度为12的表{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec}，按此顺序建立一棵3阶B-树。

Jan

Aug

MarOct

Apr

DecFeb

JunJul

MayNov

Sep58数据结构---第九章查找3.(北邮2002)有一组关键字序列{15,92,124,5,27,28,18,6,36,34,30,26,32,259}，将它们用散列函数H(key)=keymod10按顺序散列到哈希表HT(0:9)中，用链地址法解决冲突，画出最终的哈希表，并求等概率情况下查找成功和不成功时的平均查找长度。[解]012345678930^^^9232^12434^155^2818^63626^27^259^ASL成功=(8*1+5*2+1*3)/14=21/14ASL不成功=(3*1+4*2+1*3)/10=14/1059数据结构---第九章查找4.已知含12个关键字的有序表及其相应权值为：123456789101112关键字ABCDEFGHIJKL

权值823493267114(1)画出对以上有序表进行折半查找的判定树，并计算它的PH值。(2)若为等概率查找，求折半查找时查找成功的平均查找长度ASL60数据结构---第九章查找(1)639147112581012

PH=31+(3+7)2+(8+4+2+1)3+(2+9+6+1+4)4=156(2)ASL=(11+22+43+54)/12=37/1261数据结构---第九章查找5.已知如下长度为12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)

试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度ASL。

JanFebMarAprJuneMayAugJulySepDecOct

NovASL=(11+22+33+34+25+16)/12=42/1262数据结构---第九章查找6.

试从空树开始，画出按以下次序向3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后B-树的状态。

建树过程

20

2030

30

20

50

30

20

5052

3052

20

50

60

3052

20

50

6068

52

30

68

20

50

60

7063数据结构---第九章查找删除50再删除68

5268

2030

60

70

52

2030

607064数据结构---第九章查找7.选取哈希函数H(k)=(3k)MOD11。1)用线性探测开放定址法处理冲突，2)用链地址法处理冲突试在0~10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表，并求等概率情况下查找成功时的平均查找长度和不成功时的平均查找长度以及装填因子。1）0123456789102241300153461367H(K)02235663

成功ASL=(1+1+2+2+1+1+2+6)/8=2

不成功ASL=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11

=8/1165数据结构---第九章查找2）022^1^24130^30167^4^553^64613^7^8^9^10^

成功ASL=(1+1+2+1+2+1+1+2)/8=11/8不成功ASL=(1+2+2+1+2)/11=8/11

=8/1166数据结构---第九章查找算法题1.(北邮2001)将一组数组元素按哈希函数H(key)散列到哈希表HT(0:m)中，用线性探测法处理冲突(H(key)+1,H(key)+2,…，H(key)-1)，假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。TYPEtable=array[0..m]ofrecorddue:(EMPTY,INUSE,DELETED);key:keytypeend;67数据结构---第九章查找FUNCsearch(HT:table;key:keytype;

varaddrkey:integer):boolean;

addr:=H(key);s:=false;whilenot(s)and(HT[addr].dueEMPTY)do[ifHT[addr].due=INUSEthenifHT[addr].key=keythen[s:=true;addrkey:=addr]

addr:=(addr+1)mod(m+1)]return(s)ENDF;{search}68数据结构---第九章查找PROCinsert(HT:table;key:keytype);

addr:=H(key);while(HT[addr].due=INUSE)do

addr:=(addr+1)mod(m+1);HT[addr].due:=INUSE;HT[addr].key:=keyENDP;{insert}69数据结构---第九章查找PROCdelete(HT:table;key:keytype);ifsearch(HT,key,addr)then[HT[addr].due:=DELETED;addr1:=(addr+1)mod(m+1);

ifHT[addr1].due=EMPTYthenHT[addr].due:=EMPTY;

addr:=(addr-1)mod(m+1);whileHT[addr].due=DELETEDdo[HT[addr].due:=EMPTY;

addr:=(addr-1)mod(m+1)]]ENDP;{delete}70数据结构---第九章查找2.二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的构造为：lcdatarc

设计算法，从小到大输出该二叉排序树中所有数据值大于x的结点的数据。

PROCdisplay(T:bitreptr;x:datatype);ifTnilthen[display(T^.lc,x);ifT^.data>xthenwrite(T^.data);display(T^.rc,x);]ENDP;TYPEbitreptr=^node;node=recorddata:datatype;

lc,rc:bitreptr

end;71数据结构---第九章查找3.设计一个算法判定二叉树是否为二叉排序树。算法一：按照二叉排序树的递归定义FUNCdecide(bt:bitreptr;min,max:datatype):boolean;{初值设定：min为负无穷大，

max为正无穷大}

IF(bt=NIL)THENreturn(true);IF((bt^.data<min)OR