设散列函数为 H(key)=key%11，对于关键码序列（2340 91 17 19 10 31 65 26），用线性探..

免费智能真题库 > 历年试卷 > 软件设计师 > 2019年上半年软件设计师上午试卷综合知识

第60题

知识点：哈希表及其查找哈希表

关键词：冲突关键码哈希表散列函数线性探查哈希函数章/节：计算机软件知识

设散列函数为 H(key)=key%11，对于关键码序列（23,40, 91, 17, 19, 10, 31, 65, 26），用线性探查法解决冲突构造的哈希表为（）。

相关试题：计算机软件知识

更多>

第61题 2023年上半年

51%

设由三棵树构成的森林中，第一棵树、第二棵树和第三棵树的结点总数分别为n1、n2和n3。将该森林转换为一棵二叉树，那么该二叉树的..

第60题 2018年下半年

42%

图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是（60）。对G进行广度优先遍历（从v0开始），可能的遍历序..

第50题 2011年下半年

47%

函数t、f的定义如下所示，其中，a是整型全局变量。设调用函数t前a的值为5, 则在函数t中以传值调用（call by value)方式调用函数f..


知识点讲解
· 哈希表及其查找 · 哈希表

哈希表及其查找

定义

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

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

哈希函数的构造方法

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

处理冲突的方法

常见的处理冲突的方法有开放地址法、链地址法、再哈希法、建立一个公共溢出区。

哈希表的查找及其性能分析

从哈希表的查找过程可知以下两点。

（1）虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程，因此，仍须以平均查找长度衡量哈希表的查找效率。

（2）查找过程中须与给定值进行比较的关键字的个数取决于哈希函数、处理冲突的方法和哈希表的装填因子3个因素。哈希表的装填因子定义为

式中，α表示哈希表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

哈希表

1）哈希表的定义

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

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

2）哈希函数的构造方法

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

3）处理冲突的方法

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

题号导航 2019年上半年软件设计师上午试卷综合知识

本试卷我的完整做题情况



	第60题在手机中做本题