对关键码序列（12，24，15，56，20，87，69，9）采用散列法进行存储和查找，并设散列函..

2017年下半年上午试卷综合知识

第 39 题


知识点	哈希表查找
关键词	冲突存储单元关键码散列函数线性探查函数
章/节	常用算法

对关键码序列（12，24，15，56，20，87，69，9）采用散列法进行存储和查找，并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性探查法（顺序地探查可用存储单元）解决冲突所构造的散列表为（）。

相关试题常用算法

第38题

2017年下半年

对关键码序列（9，12，15，20，24，29，56，69，87）进行二分查找（折半查找），若要查找关键码15；则需依次与（）进行比较。

第37题

2011年下半年

在有11个元素的有序数组a[1...11]中进行二分查找（即折半查找），依次与(37)比较后，成功找到元素a[5]。

第31题

2013年下半年

Fibnacci 数列的定义为：F₀=0，F₁=1，F_n=F_n-1+F_n-2(n≥2，nєN^*，)，要计算该数列的..

知识点讲解

· 哈希表

· 查找

哈希表

1）哈希表的定义

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。当选择了某个散列函数后，不同的关键字可能与同一个散列地址相对应，这种现象称为冲突。

对于哈希表，主要考虑两个问题：一是如何构造哈希函数，二是如何解决冲突。

2）哈希函数的构造方法

常用的哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

3）处理冲突的方法

解决冲突就是为出现冲突的关键字找到另一个"空"的哈希地址。常见的冲突处理方法有：开放地址法、链地址法、再哈希法等。

查找

1）顺序查找

顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。

2）折半查找

折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。

3）分块查找

在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。

4）哈希表及其查找

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5