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分）】

上一页345下一页