哈希表相关笔试题

今天药忘吃喽~ 2022-06-08 01:28 408阅读 0赞

> 牛客网专项练习题

--------------------

### 哈希表的平均查找长度与处理冲突的方法无关() ###

A. 对
    B. 错

> 正确答案: B
> 
> \[摘抄\] 哈希表在查找过程中进行比较的关键字个数取决于哈希函数，处理冲突的方法和哈希表的装填因子，哈希表的装填因子标志哈希表的装满程度，与哈希表的长度有直接联系。

--------------------

### 有B+Tree/Hash\_Map/STL Map三种数据结构。对于内存中数据，查找性能较好的数据结构是（），对于磁盘中数据，查找性能较好的数据结构是（）。 ###

A. Hash_Map/B+Tree
    B. STL_Map/B+Tree
    C. STL_Map/Hash_Map
    D. B+Tree/Hash_Map

> 正确答案: A
> 
> Hash操作能根据散列值直接定位数据的存储地址，设计良好的hash表能在常数级时间下找到需要的数据，但是更适合于内存中的查找。  
> B+树是一种是一种树状的数据结构，适合做索引，对磁盘数据来说，索引查找是比较高效的  
> STL\_Map的内部实现是一颗红黑树，但是只是一颗在内存中建立二叉树树，不能用于磁盘操作，而其内存查找性能也比不上Hash查找。  
> 因此对于内存中数据，查找性能较好的数据结构是Hash\_Map，对于磁盘中数据，查找性能较好的数据结构是B+Tree。

--------------------

### 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若使用H（K)=K%9作为散列函数，则散列地址为1的元素有（）个 ###

A. 1
    B. 2
    C. 3
    D. 4

> 正确答案: D
> 
> 其实就是用关键字去套哈希函数为H(key)=key MOD 9,  
> 7%9=7  
> 34%9=7  
> 55%9=1  
> 25%9=7  
> 64%9=1  
> 46%9=1  
> 10%9=1  
> 就是55、64、46、10这四个数了。

--------------------

### 采用哈希表组织100万条记录，以支持字段A快速查找，则（） ###

A. 理论上可以在常数时间内找到特定记录
    B. 所有记录必须存在内存中
    C. 拉链式哈希曼最坏查找时间复杂度是O（n）
    D. 哈希函数的选择跟A无关

> 正确答案: C
> 
> A，记录共有100万条，一般的哈希表长度不可能做这么长，因此要解决散列冲突问题，因此一般不能再常数时间内找到记录  
> B，哈希查找可以在外存中查找，可以用哈希表映射到文件，分级查找  
> C，最坏情况是所有记录的散列值都冲突，这样就退化为线性查找，时间复杂度为O（n）  
> D，哈希函数的选择跟A关系密切，跟A的字段类型有关，哈希函数设计的好坏也影响着查找的速度

--------------------

### 查找哈希表，解决冲突的方法包括（） ###

A. 链地址法
    B. 除留余数法
    C. 直接地址法
    D. 线性探测再散列法

> 正确答案: A D
> 
> 链地址法：将哈希值相同的元素用链表进行相连  
> 线性探测再散列法：冲突后依次向下循环查找空位进行放置  
> BC为哈希值构造方法，并非解决冲突方法

--------------------

### 以下那种结构，平均来讲获取任意一个指定值最快？() ###

A. 二叉排序树
    B. 队列
    C. 栈
    D. 哈希表

> 正确答案: D
> 
> 二叉排序树中，查找的平均时间复杂度是O(logn)；  
> 对于栈和队列来说，查找就意味着把元素挨个出栈或者出队，故平均时间复杂度是O(n)；  
> 而哈希表，直接通过关键码查找元素，平均为O(1)；  
> 故哈希表速度是最快的

--------------------

### hash表示用于数据存储的一种有效的数据结构，Hash表等查找复杂依赖于Hash值算法的有效性，在最好的情况下，hash表查找复杂为? ###

A. O(1)
    B. O(n)
    C. O(log n)
    D. O(n2)

> 正确答案: A

--------------------

### 为了方便的在线性结构的数据中连续插入新的元素，则其数据结构最宜采用（） ###

A. 顺序存储
    B. 散列存储
    C. 索引存储
    D. 链式存储

> 正确答案: D
> 
> 线性结构和非线性结构同属于数据结构中的逻辑结构类型 线性结构是指该结构中的节点之间存在一对一的关系.其特点是开始节点和终端节点都是唯一的。不断插入新元素，最宜采用链式存储

--------------------

### 稀疏矩阵压缩的存储方法是：（） ###

A. 三元组
    B. 二维数组
    C. 散列
    D. 十字链表

> 正确答案: A D

--------------------

### 解决hash冲突的方法描述错误的有？ ###

A. 开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止。
    B. 拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中
    C. 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短
    D. 当结点规模较大时，开放定址法较为节省空间

> 正确答案: D
> 
> 答案：D。 ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。

--------------------

### 负载因子(装填因子)是哈希表的一个重要参数,它反映哈希表的装满程度() ###

A. 对
    B. 错

> 正确答案: A
> 
> 哈希表装填因子定义为：α= 填入表中的元素个数 / 哈希表的长度  
> α是哈希表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

--------------------

### 设哈希表长度为11,哈希函数H(K)=(K的第一个字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),采用内散列表,处理冲突方法为线性探测法,要求构造哈希表,在等概率情况下查找成功平均查找长度为() ###

A. 4
    B. 3
    C. 20/9
    D. 23/9

> 正确答案: C
> 
> 线性探测：本位置x被占据，就寻找下一位x+1，直至找到空位置，所以：  
> （注意看清题目“K的第一个字母在字母表中的序号 ”）  
> D=4mode11=4，1次  
> B=2mod11=2，1次  
> T=20mod11=9，1次  
> M=13mod11=2->3，2次  
> C=3mod11=3->4->5，3次  
> I=9mod11=9->10，2次  
> K=11mod11=0，1次  
> X=24mod11=2->3->4->5->6，5次  
> T=20mod11=9->10->0->1，4次  
> 9个数字，共20次，所以20/9。

--------------------

### 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(32，24，15，27，20，13)，计算用链地址法作为解决冲突方法的平均查找长度是（ ） ###

A. 1.4
    B. 1.5
    C. 1.6
    D. 2

> 正确答案: B
> 
> 链地址法作为解决冲突 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。

0   1    2    3   4   5   6
        15        24  32      27
                              20
                              13

因此查找长度为 1、 1、 1、1、 2、3 等概率情况下查找成功时的平均查找长度为 9/6=1.5

--------------------

### 既希望较快的查找又便于线性表动态变化的查找方法是() ###

A. 顺序查找
    B. 折半查找
    C. 分块查找
    D. 哈希法查找

> 正确答案: C
> 
> 索引查找（又称分块查找）是在索引表和主表(即线性表的索引存储结构)上进行的查找。索引查找的过程是：首先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定K1对应的子表在主表中的开始位置和长度，然后再根据给定的关键字K2，在对应的子表中查找出关键字等于K2的元素(结点)。  
> 对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找。否则只能进行顺序查找。

--------------------

### 下面属于构造散列函数的方法是（） ###

A. 直接定址法
    B. 数字分析法
    C. 除留余数法
    D. 平方取中法

> A B C D
> 
> **直接定址法**  
> 例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
> 
> **数字分析法**  
> 有学生的生日数据如下：  
> 年.月.日  
> 75.10.03  
> 75.11.23  
> 76.03.02  
> 76.07.12  
> 75.04.21  
> 76.02.15  
> …  
> 经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
> 
> **平方取中法**  
> 取关键字平方后的中间几位为哈希地址。
> 
> **折叠法**  
> 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。  
> 例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。
> 
> **除留余数法**  
> 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。  
> H(key)=key MOD p (p <= m )
> 
> **随机数法**  
> 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即  
> H(key)=random(key），其中random为随机函数。通常用于关键字长度不等时采用此法。  
> 若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：  
> Step1.　取出一个数据元素的关键字key，计算其在哈希表中的存储地址D=H(key）。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。  
> Step2.　根据规定的冲突处理方法，计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。  
> 冲突
> 
> 无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，**有一些方法可以避免冲突**。
> 
> **拉链法**  
> 拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。
> 
> **多哈希法**  
> 设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（除非人品太差，否则几乎不可能冲突）。
> 
> **开放地址法**  
> 开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1）  
> 其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。  
> 如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,…k\*k,-k\*k(k<=m/2）  
> 称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。
> 
> **建域法**  
> 假设哈希函数的值域为\[0,m-1\]，则设向量HashTable\[0..m-1\]为基本表，另外设立存储空间向量OverTable\[0..v\]用以存储发生冲突的记录。

--------------------

###  ###