🏷️ 知识点：查找
只能在顺序存储结构上进行的查找方法是()。
A. 顺序查找法 B. 折半查找法 C. 树形查找法 D. 散列查找法
[tag_link]
正确答案：B
散列查找一般适用于()的情况下的查找。
A. 查找表为链表 B. 查找表为有序表 C. 关键字集合比地址集合大得多 D. 关键字集合与地址集合之间存在对应关系
[tag_link]
正确答案：D
下列关于散列表的说法中，正确的是()。 I. 若散列表的填装因子a<1, 则可避免碰撞的产生 II. 散列查找中不需要任何关键字的比较 II. 散列表在查找成功时平均查找长度仅与表长有关 IV. 若在散列表中删除一个元素，不能简单地将该元素删除
A. I 和 IV B. Ⅱ 和 Ⅲ C. Ⅲ D. IV
[tag_link]
正确答案：D
在开放定址法中散列到同一个地址而引起的“堆积”问题是由()引起的。
A. 同义词之间发生冲突 B. 非同义词之间发生冲突 C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”
[tag_link]
正确答案：C
下列关于散列冲突处理方法的说法中，正确的有()。 I. 采用平方探测法处理冲突时不易产生聚集 II. 采用线性探测法处理冲突时，所有同义词在散列表中一定相邻 Ⅲ.采用链地址法处理冲突时，若限定在链首插入，则插入任意一个元素的时间相同 IV. 采用链地址法处理冲突易引起聚集现象
A. I 和 Ⅲ B. I 、Ⅱ和 Ⅲ C. Ⅲ和IV D. I 和 IV
[tag_link]
正确答案：A
设有一个含有200个元素的散列表，用线性探测法解决冲突，按关键字查询时找到一个 表项的平均探测次数不超过1.5,则散列表应至少能够容纳()个元素(设查找成功的 平均查找长度为ASL=[1+1/(1-a)]/2, 其中α为装填因子)。
A. 400 B.526 C.624 D.676
[tag_link]
正确答案：A
假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关键字填入散列表，至少要 进行()次探测。
A. K- 1 B. K C.K+1 D.K(K+1)/2
[tag_link]
正确答案：D
对包含n 个元素的散列表进行查找，平均查找长度()。 A . 为 O(log₂n) B. 为0(1) C. 不直接依赖于n D. 直接依赖于表长m
[tag_link]
正确答案：C
采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是()。
A. 数据元素过多 B. 负载因子过大 C. 散列函数选择不当 D. 解决冲突的方法选择不当
[tag_link]
正确答案：D
当用线性探测再散列法解决冲突时，计算出的一系列“下一个空位”的要求是()。
A. 必须大于或等于原散列地址 B. 必须小于或等于原散列地址 C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制
[tag_link]
正确答案：C
一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表，散 列函数为H(key)=key mod 13, 散列地址为1的链中有()个记录。
A. 1 B.2 C.3 D.4
[tag_link]
正确答案：D
在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下， 所探测的这些位置上的关键字值();若采用线性探测法，则()。
A. 一定都是同义词 B. 不一定都是同义词 C. 都相同 D. 一定都不是同义词
[tag_link]
正确答案：
若采用链地址法构造散列表，散列函数为H(key)=key mod 17, 则需(①)个链表。这 些链的链首指针构成一个指针数组，数组的下标范围为(②)。 ① A.17 B.13 C.16 D. 任意 ②A.0～17 B.1～17 C.0～16 D.1~16
[tag_link]
正确答案：
设散列表长m=14, 散列函数为H(key)=key%11, 表中仅有4个结点H(15)=4,H(38) =5, H(61)=6,H(84)=7, 若采用线性探测法处理冲突，则关键字为49的结点地址 是 ( ) 。
A. 8 B.3 C.5 D.9
[tag_link]
正确答案：A
现有长度为17、初始为空的散列表HT, 散列函数H(key)=key%17, 用线性探查法解 决冲突。将关键字序列26,25,72,38,8,18,59依次插入HT 后，查找59需探查()次。 A.2 B.3 C.4 D.5
[tag_link]
正确答案：C
现有长度为17、初始为空的散列表HT, 散列函数H(key)=key%17, 用平方探测法解 决冲突：H,(key)=(H(key)±i²)%17 。 将关键字序列6,22,7,26,9,23依次插入HT 后 ， 则关键字23存放在散列表中的位置是()。
A. 0 B.2 C.6 D.15
[tag_link]
正确答案：B
将10个元素散列到100000个单元的散列表中，则()产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会 D. 不确定
[tag_link]
正确答案：C
若要在散列表中删除一个记录，应如何操作?为什么?按照处理冲突的方法为开放地 址法和拉链法分别说明。
[tag_link]
B
假定把关键字key 散列到有 n 个表项(从0到n-1 编址)的散列表中。对于下面的每 个函数H(key)(key 为整数),这些函数能够当作散列函数吗?若能，它是一个好的散 列函数吗?说明理由。设函数random(n) 返回一个0到n-1 之间的随机整数(包括0与 n - 1 在内)。 1)H(key)=key/n。 2)H(key)=1。 3)H(key)=(key +random(n)%n。 4)H( key)=key%p(n); 其中p(n)是不大于n 的最大素数。
[tag_link]
D
使用散列函数H(key)=key%11, 把一个整数值转换成散列表下标，散列表的长度为11,现 在要把数据{1,13,12,34,38,33,27,22}依次插入散列表。 1)使用线性探测法来构造散列表。 2)使用链地址法构造散列表。 试针对这两种情况，分别确定查找成功所需的平均查找长度，及查找不成功所需的平均 查找长度。
[tag_link]
D
已知一组关键字为{26,36,41,38,44,15,68,12,6,51,25},用链地址法解决冲突，假设 装填因子α=0.73,散列函数的形式为H(key)=key%P,P 为不大于表长的最大素数， 请回答以下问题： 1)构造出散列函数。 2)分别计算出等概率情况下查找成功和查找失败的平均查找长度(查找失败的计算中 只将与关键字的比较次数计算在内即可)。
[tag_link]
C
设散列表为HT[0…12], 即表的大小为 m=13 。 现采用双散列法解决冲突，散列函数和 再散列函数分别为： H₀(key)=key%13 注：%是取模运算(=mod) H₁=(H₁-1+REV(key+1)%11+1)%13;i=1,2,3,…,m-1 其中，函数REV(x)表示颠倒十进制数x 的各位，如REV(37)=73 、REV(7)=7 等。若插 入的关键码序列为(2,8,31,20,19,18,53,27),请回答： 1)画出插入这8个关键码后的散列表。 2)计算查找成功的平均查找长度ASL。
[tag_link]
A