《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)

0 ①

要求写出计算过程 哈希表表如下： 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 ②查找63,首先要与H(63)=63=15号单元内容比较，即63与31比较 ,不匹配;

然后顺移，与46,47,32,17,63相比，一共比较了6次

③查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

④ ASL=（6＋2＋3×3+6）/11＝23/11

（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。限定di=12,22,…k2(k<=m/2)

答案：

要求写出计算过程

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

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突） H2=（6+22）=0（冲突） H3=（6+33）=5 所以比较了4次。

3．算法设计题

（1）试写出折半查找的递归算法。 [算法描述]

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

//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。

{if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2；

17

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）；//查找失败。 }

18