数据结构8 散列函数 | 您所在的位置:网站首页 › 哈希表二次探测平均查找长度 › 数据结构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单位 西南石油大学 选取哈希函数H(key)=key mod 7,用链地址法解决冲突。试在0-6的散列地址空间内对关键字序列{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 哈希函数不统一 |
CopyRight 2018-2019 实验室设备网 版权所有 |