若设散列表的大小为m，利用散列函数计算出的散列地址为h-hash(x)。(1)试说明确定m的原则。(2)试

若设散列表的大小为m，利用散列丽数计算出的散列地址为h=hash（x)，试证明：如果二次探查的顺序为

(h+q²)，(h+(q-1)²)，…，(h+1)，h，(h-1)，…，(h-q^2*)，其中，q=(m-1)/2。闪此在相继被探查的两个桶之间地址相减所得的差取模(%m)的结果为m-2，m-4，m-6.…，5，3，1，1，3，5，…，m-6，m-4，m-2，

设散列表为，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：

其中，函数Rev(x)表示颠倒10进制数x的各位，如Rev(37)=73，Rev(7)一7等。若插入的关键码值序列为(2，8，31，20，70，59，25，28)。

(1)试画出插人这8个关键码值后的散列表。

(2)计算搜索成功的平均搜索长度。

设散列表长m=14，散列函数H（key)=key%11.表中已有4个结点，地址分别为addr（15)=4、addr（38)=5、ad

dr(61)=6、addr(84)=7.其余地址为空。如用二次探查法解决冲突，关键码值为49的散列地址是()。

A、8

B、3

C、5

D、9

已知一个线性序列38，25，74，63，52，48，假定采用散列函数h（key)=key%7计算散列地址，并散列存储在

散列表A[10]中，若采用线性探查方法解决冲突，则在该散列表上进行等概率成功搜索的平均搜索长度为()。

A、2.60

B、3.14

C、3.71

D、4.33

设散列表为HT[13]，散列函数为H（key)=key%13.用闭散列法解决冲突，对下列关键码序列12，23，45，57，

20，03，78，31，15，36建立表。

(1)采用线性探查法寻找下一个空位，画出机应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

(2)采用双散列法寻找下一个空位，再散列函数为RH(key)=(7×key)%10+1，寻找下一个空位的公式为H_i=(H_i-1+RH(key))%13，H₁=H(key)。画出相应的散列表，并计算等概率下搜索成功的平均搜索长度。

设一个散列表采用开散列（链地址)法构造，散列函数采用除留余数法，解决冲突的方法采用分离的同

义词子表法。

(1)设计用分离的同义词子表组织的开散列表的类。

(2)设计在做列表中搜索具有指定关键码值的表项的算法。

(3)设计在散列表中删除具有指定关键码值的表项的算法。

(4)设计在散列表中插人具有指定关键码值的表项的算法。

(5)设计由一组关键码值建立散列表的算法。

(6)设计输出散列表的算法。

(7)求搜索成功时的平均搜索长度的算法。

(8)求搜索不成功时的平均搜索长度的算法。

在地址空间为0~16的散列区中，对以下关键字序列构造两个散列表:

1)用线性探测开放定址法处理冲突;

2)用链地址法处理冲突。

并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。

比较次数不超过2次。试问散列表需要设计多大？请为这个散列表设计散列网数(除留余数法)和再散列函数。

设α是散列表的装钱因子，则应用双散列法解决冲突时的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为：(请根据题意选用合用的公式)

设散列函数H（key)=（3xkey)%11;用开放定址法处理冲突，探测序列为:di=ix（7xkey)%10+1),i=1,2,3....试在0~10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67)构造散列表，并求等概率情况下查找成功时的平均查找长度。

假定把关键码key散列到有m个表项（从0到m-1编址)的散列表中。对于下面的每一个函数Hash（key)（ke

y为整数)，这些函数能够当作散列函数吗(即对于插入和查找，散列程序能正常工作吗)？如果能够，它是一个好的散列函数吗？请说明理由。设函数random(m)返回一个0到m-1之间的随机整数(包括0与m-1在内)。

(1)Hash(key)==key/m;

(2)Hash(key)=1;

(3)IIash(key)==(key+random(m))%rn;

(4)Hash(key)=key%p(m);其中p(m)是不大于m的最大素数。