HASH GAME - Online Skill Game GET 300

　　第五章习题 1、 选取哈希函数 H(k) = (3k) MOD 11。用开放定址法处理冲突，di = i ((7k) MOD 10+1) (i=1，2，3，…)。试在 0～10 的散列地址空间中对关键字序列 (22，41，53，46，30，13，01，67) 构造哈希表，并求等概率情况下查找成功时的平均查找长度。 2、 设有关键字序列，表示为一个线]~HT[12]，散列函数 H(k)=k%13，试用线性探查法和拉链法解决冲突，实现散列存储，画出每种形式的散列表，并求出每种查找的成功平均查找长度。 3、 给定关键字序列 22，41，53，46，30，13，1，67，散列函数 H(k)=3k%11，解决冲突时，d0=H(k)，di= i((7k)%10+1) (i=1,2,3,...

　　第五章习题 1、 选取哈希函数 H(k) = (3k) MOD 11。用开放定址法处理冲突，di = i ((7k) MOD 10+1) (i=1，2，3，)。试在 0～10 的散列地址空间中对关键字序列 (22，41，53，46，30，13，01，67) 构造哈希表，并求等概率情况下查找成功时的平均查找长度。 2、 设有关键字序列，表示为一个线]~HT[12]，散列函数 H(k)=k%13，试用线性探查法和拉链法解决冲突，实现散列存储，画出每种形式的散列表，并求出每种查找的成功平均查找长度。 3、 给定关键字序列 22，41，53，46，30，13，1，67，散列函数 H(k)=3k%11，解决冲突时，d0=H(k)，di= i((7k)%10+1) (i=1,2,3,)，试构造出散列表，并求等概率时的成功平均查找长度。 4、 设有一组关键字(19,1,23,14,55,20,84,27,68,11,10,77)，散列函数为：H(key)=key%13。若采用开放地址法中的线性探查法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造散列表（要求给出计算过程），并求出等概率时查找成功的平均查找长度。 5、 顺序查找的时间复杂度为 0(n)，二分查找的时间复杂度为 O(log2n)，散列查找的时间复杂度为 O(1)。为什么有高效率的检索方法而低效率的方法不被放弃? 6、 已知一个含有 100 个元素的表，关键字为中国姓氏的拼音，若采用散列方式存储此表，请给出一种散列表的设计方案，要求它在等概率下查找成功的平均查找长度不超过 3。 7、 假定有一个 100*100 的稀疏矩阵，其中 1%的元素为非零元素，现要求对其非零元素进行散列存储，使之能够按照元素的行、列值存取矩阵元素（即元素的行、列值联合为元素的关键字），试采用除留余数法构造散列函数和线性探查法处理冲突，分别写出建立散列表和散列查找的算法。 8、 线性表中各元素的查找概率不相等，则可以用如下策略提高顺序查找的效率。若找到顶定元素，将它与前面的（若存在）交换，使得经常被查找的元素尽量位于表的前端。试设计在线性表的顺序存储和链式存储上实现上述策略的查找算法。 湖南省高校数字教学资源中心202.197.127.140