数据结构8 散列函数

1-1

分数 1

作者 DS课程组单位 浙江大学

Store M elements in a hash table which is represented by an array of size S, the loading density is then M/S.

将M个元素存储在哈希表中，哈希表由大小为S的数组表示，则加载密度为M/S。

T

F

1-2

分数 1

作者 冯雁单位 浙江大学

In hashing, functions “insert” and “find” have the same time complexity.

在哈希运算中，函数“insert”和“find”具有相同的时间复杂性。

T

F

1-3

分数 5

作者 杨红梅单位 山东科技大学

Hash表的平均查找长度与处理冲突的方法无关。

T

F

1-4

分数 5

作者 杨红梅单位 山东科技大学

负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。

T

F

1-5

分数 1

作者 DS课程组单位 临沂大学

当记录个数小于哈希表长度时，哈希查找平均查找长度必然为0。

T

F

1-6

分数 1

作者 陈越单位 浙江大学

There must be a collision if we insert a new element into a hash table with the loading density being 1.

如果我们在哈希表中插入一个加载密度为1的新元素，那么一定会发生冲突。

T

F

1-7

分数 3

作者 DS课程组单位 浙江大学

采用平方探测冲突解决策略（hi(k)=(H(k)+i2)%11, 注意：不是±i2），将一批散列值均等于2的对象连续插入一个大小为11的散列表中，那么第4个对象一定位于下标为0的位置。

T

F

1-8

分数 1

作者 DS课程组单位 浙江大学

若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。

T

F

1-9

分数 1

作者 DS课程组单位 浙江大学

In a hash table, “synonyms”(同义词) means two elements being hashed into the same slot by two different hash functions.

在哈希表中，“同义词“意味着两个元素被两个不同的散列函数散列到同一个槽中。

T

F

1-10

分数 3

作者 DS课程组单位 浙江大学

If quadratic probing (hi(k)=(H(k)+i2)%11. Note: it’s not ±i2) is used to resolve collisions, to insert several elements, all with hash value being 2, into a hash table of size 11, then the 4th element must be placed at the position 0.

如果二次探测（hi（k）=（H（k）+i2）%11。注意：它不是±i2）用于解决冲突，将多个元素（哈希值均为2）插入大小为11的哈希表中，然后第4个元素必须放置在位置0。

T

F

1-11

分数 1

作者 陈越单位 浙江大学

It is still possible to have a collision even if we hash only 2 elements into a hash table of 100 cells.

即使我们只将2个元素哈希到100个单元的哈希表中，仍然有可能发生冲突。

T

F

1-12

分数 1

作者 杨红梅单位 山东科技大学

采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。

T

F

1-13

分数 5

作者 杨红梅单位 山东科技大学

在散列检索中，“比较”操作一般也是不可避免的。

T

F

1-14

分数 2

作者 徐镜春单位 浙江大学

If 7 elements have been stored in a hash table of size 13 at positions { 0, 1, 2, 4, 5, 10, 11 }, and the hash function is H(x)=x%13. Then an empty spot can’t be found when inserting the element 40 with quadratic probing.

如果7个元素已存储在大小为13的哈希表中的位置｛0，1，2，4，5，10，11｝处，并且哈希函数为H（x）=x%13。然后，当用二次探测插入元件40时，不能找到空点。

T

F

1-15

分数 2

作者 朱建科单位 浙江大学

Linear probing is equivalent to double hashing with a secondary hash function of Hash2(k)=1 .

线性探测相当于使用Hash2（k）=1的二级散列函数进行双重散列。

T

F

1-16

分数 2

作者 朱建科单位 浙江大学

Quadratic probing is equivalent to double hashing with a secondary hash function of Hash2(k)=k.

二次探测等价于具有Hash2（k）＝k的二次散列函数的双重散列。

T

F

1-17

分数 1

作者 徐镜春单位 浙江大学

将 10 个元素散列到 100 000 个单元的哈希表中，一定不会产生冲突。

T

F

1-18

分数 2

作者 徐镜春单位 浙江大学

In hashing with open addressing to solve collisions, the operarion FIND will be seriously slowed down if there are too many deletions intermixed with insertions.

在使用开放寻址来解决冲突的哈希中，如果有太多的删除与插入混合，则FIND操作将严重减慢。

T

F

1-19

分数 2

作者 徐镜春单位 浙江大学

In hashing, when the loading density approaches 1, the operarion INSERTION will be seriously slowed down if the separate chaining method is used to solve collisions.

在哈希中，当加载密度接近1时，如果使用单独的链接方法来解决冲突，则操作插入将严重减慢。

T

F

2-1

分数 2

作者 DS课程组单位 浙江大学

假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测？

A.K−1

B.K

C.K+1

D.K(K+1)/2

2-2

分数 1

作者 DS课程组单位 浙江大学

采用线性探测法解决冲突时所产生的一系列后继散列地址：

A.必须大于等于原散列地址

B.必须小于等于原散列地址

C.可以大于或小于但不等于原散列地址

D.对地址在何处没有限制

解析：进行循环之后散列地址会在原散列地址前。

2-3

分数 3

作者 DS课程组单位 浙江大学

将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？

A.0.27

B.0.45

C.0.64

D.0.73

2-4

分数 2

作者 DS课程组单位 浙江大学

给定散列表大小为11，散列函数为H(Key)=Key%11。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%11将关键字序列{ 6，25，39，61 }依次插入到散列表中。那么元素61存放在散列表中的位置是：

A.5

B.6

C.7

D.8

2-5

分数 2

作者 DS课程组单位 浙江大学

给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问：此时该散列表的平均不成功查找次数是多少？

A.1

B.4/11

C.21/11

D.不确定

2-6

分数 2

作者 DS课程组单位 浙江大学

从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？

A.N/2

B.N

C.(N−1)/2

D.(N+1)/2

2-7

分数 1

作者 DS课程组单位 浙江大学

若用平方探测法解决冲突，则插入新元素时，以下陈述正确的是：

A.插入一定可以成功

B.插入不一定能成功

C.插入一定不能成功

D.若散列表容量为质数，插入就一定可以成功

2-8

分数 2

作者 DS课程组单位 浙江大学

给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）

A.1, 3, 3, 9, 4, 9, 9

B.1, 3, 4, 9, 7, 5, -1

C.1, 3, 4, 9, 5, 0, 8

D.1, 3, 4, 9, 5, 0, 2

2-9

分数 2

作者 DS课程组单位 浙江大学

给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用线性探测解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）

A.1, 3, 3, 9, 4, 9, 9

B.1, 3, 4, 9, 7, 5, -1

C.1, 3, 4, 9, 5, 0, 8

D.1, 3, 4, 9, 5, 0, 2

2-10

分数 2

作者 DS课程组单位 浙江大学

给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用平方探测解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）

A.1, 3, 3, 9, 4, 9, 9

B.1, 3, 4, 9, 7, 5, -1

C.1, 3, 4, 9, 5, 0, 8

D.1, 3, 4, 9, 5, 0, 2

2-11

分数 2

作者 DS课程组单位 浙江大学

给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用开放定址法以及一个二次散列函数h2(X)=7−(X%7)解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）

A.1, 3, 3, 9, 4, 9, 9

B.1, 3, 4, 9, 7, 5, -1

C.1, 3, 4, 9, 5, 0, 8

D.1, 3, 4, 9, 5, 0, 2

2-12

分数 3

作者 DS课程组单位 浙江大学

设数字 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 在大小为10的散列表中根据散列函数 h(X)=X%10得到的下标对应为 {1, 3, 4, 9, 5, 0, 2}。那么继续用散列函数 “h(X)=X%表长”实施再散列并用线性探测法解决冲突后，它们的下标变为：

A.11, 3, 13, 19, 4, 0, 9

B.1, 3, 4, 9, 5, 0, 2

C.1, 12, 9, 13, 20, 19, 11

D.1, 12, 17, 0, 13, 8, 14

2-13

分数 2

作者 冯雁单位 浙江大学

若N个关键词被散列映射到同一个单元，并且用分离链接法解决冲突，则找到这N个关键词所用的比较次数为：

A.N(N+1)/2

B.N(N−1)/2

C.N+1

D.N

2-14

分数 2

作者 冯雁单位 浙江大学

若N个关键词被散列映射到同一个单元，并且用分离链接法解决冲突，则找到这N个关键词所用的比较次数为：

A.N(N−1)/2

B.N(N+1)/2

C.N

D.N+1

2-15

分数 2

作者 冯雁单位 浙江大学

若N个关键词被散列映射到同一个单元，并且用分离链接法解决冲突，则找到这N个关键词所用的比较次数为：

A.N

B.N+1

C.N(N−1)/2

D.N(N+1)/2

2-16

分数 3

作者 冯雁单位 浙江大学

给定散列表大小为17，散列函数为H(Key)=Key%17。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%17将关键字序列{ 6, 22, 7, 26, 9, 23 }依次插入到散列表中。那么元素23存放在散列表中的位置是：

A.0

B.2

C.6

D.15

2-17

分数 3

作者 冯雁单位 浙江大学

给定散列表大小为17，散列函数为H(Key)=Key%17。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%17将关键字序列{ 6, 22, 7, 26, 9, 40 }依次插入到散列表中。那么元素40存放在散列表中的位置是：

A.2

B.6

C.8

D.15

2-18

分数 3

作者 冯雁单位 浙江大学

给定散列表大小为17，散列函数为H(Key)=Key%17。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%17将关键字序列{ 23, 22, 7, 26, 9, 6 }依次插入到散列表中。那么元素6存放在散列表中的位置是：

A.15

B.10

C.6

D.2

2-19

分数 3

作者 冯雁单位 浙江大学

Insert {18, 23, 4, 26, 31, 33, 17, 39} one by one into an initially empty hash table of size 13 with the hash function H(Key)=Key%13, and linear probing is used to resolve collisions. What is the loading density when the first collision occurs?

将｛18，23，4，26，31，33，17，39｝逐个插入到大小为13的初始空哈希表中，哈希函数H（Key）=Key%13，并且使用线性探测来解决冲突。第一次碰撞时的装载密度是多少？

A.0.54

B.0.63

C.0.31

D.0.62

2-20

分数 3

作者 冯雁单位 浙江大学

将元素序列{18, 23, 4, 26, 31, 33, 17, 39}按顺序插入一个初始为空的、大小为13的散列表中。散列函数为：H(Key)=Key%13，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？

A.0.54

B.0.63

C.0.31

D.0.62

2-21

分数 2

作者 冯雁单位 浙江大学

Given a hash table of size 11 with the hash function H(Key)=Key%11. Insert 5 elements with the same hash value into an initially empty hash table, and use linear probing to resolve collisions. What is the average time for unsuccessful searches?

给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？

A.26/11

B.5/11

C.1

D.cannot be determined

2-22

分数 2

作者 冯雁单位 浙江大学

给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？

A.26/11

B.5/11

C.1

D.不确定

2-23

分数 2

作者 何钦铭单位 浙江大学

Given a hash table of size 13 and the hash function h(x)=x mod 13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence {2, 15, 3, 16, 6, 25, 20, 7}, which number is placed in the position of index 7?

给定大小为13的哈希表和哈希函数h（x）＝x mod 13。假设使用二次探测来解决冲突。用输入序列｛2，15，3，16，6，25，20，7｝逐一填写哈希表后，哪个数字放在索引7的位置？

A.7

B.16

C.20

D.none

2-24

分数 2

作者 何钦铭单位 浙江大学

Given a hash table of size 13 and the hash function h(x)=x mod 13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence {2, 15, 3, 29, 6, 25, 33, 7}, which number is placed in the position of index 7?

给定大小为13的哈希表和哈希函数h（x）＝x mod 13。假设使用二次探测来解决冲突。用输入序列｛2，15，3，29，6，25，33，7｝逐一填写哈希表后，哪个数字放在索引7的位置？

A.29

B.7

C.33

D.none

2-25

分数 2

作者 杨红梅单位 山东科技大学

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )

A.k-1次

B.k次

C.k+1次

D.k（k+1）/2次

2-26

分数 2

作者 考研真题单位 浙江大学

现有长度为 7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到HT后，查找成功的平均查找长度是：

A.1.5

B.1.6

C.2

D.3

2-27

分数 2

作者 考研真题单位 浙江大学

现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87,40,30,6,11,22,98,20 依次插入到 HT 后，HT 查找失败的平均查找长度是：

A.4

B.5.25

C.6

D.6.29

2-28

分数 2

作者 陈越单位 浙江大学

Insert {20, 25, 13, 22, 4, 9, 29, 35, 14, 17} one by one into an initially empty hash table of size 13 with the hash function H(Key)=Key%13, and quadratic probing is used to resolve collisions. How many numbers can be inserted without collisions?

A.5

B.6

C.7

D.8

2-29

分数 2

作者 陈越单位 浙江大学

Suppose that the range of a hash table is [0, 18], and the hash function is H(Key)=Key%17. If linear probing is used to resolve collisions, then after inserting { 16, 32, 14, 34, 48 } one by one into the hash table, the index of 48 is:

假设哈希表的范围为[0，18]，哈希函数为H（Key）=Key%17。如果使用线性探测来解决冲突，那么在将{16，32，14，34，48}逐个插入哈希表之后，48的索引为：

A.14

B.0

C.17

D.1

2-30

分数 2

作者 M单位 西南石油大学

选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。

A.15/10

B.15/8

C.17/10

D.15/6

2-31

分数 3

作者 陈越单位 浙江大学

Given a hash table of size 13 and the hash function h(x)=x%13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence { 10, 23, 1, 36, 19, 5 }, which number is placed in the position of index 6?

给定大小为13的哈希表和哈希函数h（x）=x%13。假设使用二次探测来解决冲突。用输入序列｛10，23，1，36，19，5｝逐一填写哈希表后，哪个数字放在索引6的位置？

A.5

B.19

C.36

D.none

2-32

分数 3

作者 陈越单位 浙江大学

Given a hash table of size 13 and the hash function h(x)=x%13. Assume that quadratic probing is used to solve collisions. After filling in the hash table one by one with input sequence { 10, 23, 1, 36, 19, 5 }, which number is placed in the position of index 0?

给定大小为13的哈希表和哈希函数h（x）=x%13。假设使用二次探测来解决冲突。用输入序列｛10，23，1，36，19，5｝逐一填写哈希表后，哪个数字放在索引0的位置？

A.23

B.36

C.10

D.none

2-33

分数 2

作者 徐镜春单位 浙江大学

Given a hash table of size 13 (indexed from 0 to 12) with the hash function H(Key)=Key%11. Quadratic probing Hi(key)=(H(key)+i2 )%13 is used to resolve collisions when the i-th(i>0) collision occurs. Then after inserting { 9, 21, 20, 33, 31, 5 } one by one into the initially empty hash table, which one of the following statements is false?

给定大小为13的哈希表（索引从0到12），哈希函数H（Key）=Key%11。二次探测Hi（key）=（H（key）+i2）%13用于在发生第i次（i>0）冲突时解决冲突。然后，在将{9，21，20，33，31，5}逐个插入初始空哈希表之后，以下哪一个语句是错误的？

A.the loading density is less than 0.5

负载密度小于0.5

B.the key 5 is at position 6

C.the key 20 is at position 0

D.the average search time is less than 2

平均搜索时间小于2

2-34

分数 3

作者 徐镜春单位 浙江大学

Given a hash table of size 13 (indexed from 0 to 12) with the hash function H(Key)=Key%11， Quadratic probing Hi(key)=(H(key)+i2 )%13 is used to resolve collisions when the i-th(i>0) collision occurs. Then after inserting {10, 21, 32, 33, 65, 12 } one by one into the hash table, which one of the following statements is false?

给定大小为13的哈希表（索引从0到12），哈希函数H（Key）=Key%11，当发生第i次（i>0）冲突时，使用二次探测Hi（Key）=（H（Key）+i2）%13来解决冲突。然后在将{10，21，32，33，65，12}逐个插入哈希表之后，以下哪一个语句是错误的？

A.the loading density is less than 0.5

B.the key 65 is at position 6

C.the key 12 is at position 1

D.the average search time is greater than 2

2-35

分数 3

作者 徐镜春单位 浙江大学

In hashig with open addressing method，rehashing is definitely necessary when __.

在使用开放寻址方法的散列中，当__时，重新散列是绝对必要的。

A.an insertion fails

插入失败

B.the hash table is half full

哈希表满了一半

C.primary clustering occurs

发生主要群集

D.the hash function is not uniform

哈希函数不统一