给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h（key)=key%13，请向散列表依次插入关键字为78,96,18,2,40的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 91 45 84 32 97
题目
给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h（key)=key%13，请向散列表依次插入关键字为78,96,18,2,40的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 91 45 84 32 97
相似考题
更多“给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h（key)=key%13，请向散列表依次插入关键字为78,96,18,2,40的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 91 45 84 32 97”相关问题
-
第1题：
已知一个线性表(38,25,74,63,52,48)，假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为(63)。
A．1.4
B．1.6
C．2.0
D．2.2
正确答案：C
解析：按照散列函数h(key)=key%7和线性探测方法解决冲突将线性表 (38,25,74,63,52,48)散列存储在散列表A[0…6]中如图3-15所示。
在该散列表上进行等概率成功查找的平均查找长度
-
第2题：
设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{13,28,72,5,16,8,7,9,11,29}在地址空间为0－10的散列区中建散列表,画出此表,并求等概率情况下查找成功时的平均查找长度。参考答案：
-
第3题：
设散列表的地址空间为0到12，散列函数为h(k)=k mod 13，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值14，95，24，61，27，82，69，则最后一个关键码69的地址为【 】。
正确答案：6
6 解析：将序列mod 13，则14mod13=1，95modl3=4.24mod13=11，61mod13=9，27rood13=1，82mod13=4.69mod13=4。将它们放入地址中，则14放入1，95放入4，24放入11，61放入9，27放入2，82放入5，69放入6。 -
第4题：
对关键码序列（12，24，15，56，20，87，69，9）采用散列法进行存储和查找，并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性探查法（顺序地探查可用存储单元）解决冲突所构造的散列表为（）。
A.
B.
C.
D.
正确答案：B
-
第5题：
● 若线性表（23, 14, 45, 12, 8, 19, 7）采用散列法进行存储和查找。设散列函数为H(Key)=Key mod 7并采用线性探查法（顺序地探查可用存储单元）解决冲突，则构造的散列表为 （38） ，其中，mod表示整除取余运算。
正确答案：A
-
第6题：
若线性表(23，14，45，12，8，19，7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7并采用线性探查法(顺序地探查可用存储单元)解决冲突，则构造的散列表为(38)，其中，mod表示整除取余运算。
A．
B．
C．
D．
正确答案：A
解析：本题考查哈希存储方法。
对于关键字23、14、45、12、8、19，由哈希函数得到的哈希地址没有冲突，元素直接存入，如下所示。
对于元素7，其哈希地址为0，但是该地址中已经存入元素14，因此由H1=(Hash(12)+1) mod 7=1，再试探哈希地址1，但该地址已被元素8占用，发生冲突；再计算H2=(Hash(12)+2) mod 7=2，发生冲突(地址2被元素23占用)；再计算H3=(Hash(12)+3)mod 7=3，发生冲突；再试探哈希地址4，空闲，因此将元素7存入哈希地址为4的单元，如下所示。
-
第7题：
设有一个用线性探测法解决冲突得到的散列表，该表共有0～10个地址单元，其中地址单元2～8中的内容依次为13，25，80，16，17，6，14。散列函数为： H(k)=k mod 11 若要查找元素14，探测(比较)的次数是( )。
A．8
B．9
C．3
D．6
正确答案：D
解析：由散列函数为：H(k)=k mod11可计算出13，25，80，16，17，6， 14的散列地址依次为2、3、3、5、6、6、3，在存储14时，2、3、4、5、6、7连续6个单元已经被占用，如表13-17所示。而14的散列地址为3，因此在查找时需从地址为3的位置开始比较，一直到14存储的地址8(包括8)，共比较了6次。
-
第8题：
若关键码序列(23，35，14，49，8，12，30，7)采用散列法进行存储和查找。设散列函数为H(Key)=Key%11，采用线性探查法（顺序地探查可用存储单元）解决冲突，尚未构造完成的散列表如下所示，则元素12应存入哈希地址单位（）
A.0
B.4
C.11
D.12
正确答案：B
本题考查数据结构基础知识。根据构造哈希表的方式，先由哈希函数计算12在哈希表中的存储位置为1(12%11)，此时因1号单元被23占用而发生冲突，线性探查法解决冲突的方式是顺序地探查2号单元，仍然冲突，再探查3号单元，继续冲突，再探查4号单元，不再冲突，从而在经过4次探查后把12存入空闲的4号单元。
-
第9题：
● 若线性表（24, 13, 31, 6, 15, 18, 8）采用散列（Hash）法进行存储和查找，设散列函数为H(Key)=Key mod 11，则构造散列表时发生冲突的元素为 （1） 。（其中的mod表示整除取余运算）
（1）
A. 24和13
B. 6 和15
C. 6 和24
D. 18和8
正确答案：A
-
第10题：
设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：求等概率下查找成功的平均查找长度ASL。
正确答案:ASL成功=(1+1+2+1+2+1+1+3+1+1+2+4+3)/13=23/13 -
第11题：
设散列表的地址空间为0到12，散列函数为h（k）=kmod13，用线性探查法解决碰撞。现从空的教列表开始，依次插入关键码值14，95，24，61，27，82，69，则最后一个关键码69的地址为（）。
正确答案:6 -
第12题：
问答题设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：查找关键字98（失败）时，需要依次与哪些关键字比较。正确答案： 分别于关键字20,84比较。解析： 暂无解析 -
第13题：
● 若线性表（24, 13, 31, 6, 15, 18, 8）采用散列（Hash）法进行存储和查找，设散列函数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为 （36） 。 （其中的 mod表示整除取余运算）
（36）
A. 24 和 13
B. 6 和 15
C. 6 和 24
D. 18 和 8
正确答案：A
-
第14题：
已知散列表的存储空间为T[0…18]，散列函数H(key)=key%17，并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是 ( )
A．T[2]
B．T[4]
C．T[8]
D．T[10]
正确答案：D
解析：由题意可得H(23)=6，而T[6]中已有关键字，产生冲突，此时采用二次探测法，则当i=1时，h1=(6+1×1)%17=7，又T[7]中也已有关键字仍然冲突。则选i=2，此时h2=(6+2×2)%17=10，此时可判定此关键字可插入T[10]单元中。 -
第15题：
若线性表(24，13，31，6，15，18，8)采用散列(Hash)法进行存储和查找，设散列函数为H(Key)=Key mod 11，则构造散列表时发生冲突的元素为(1) (其中的mod表示整除取余运算)。
A．24和13
B．6和15
C．6和24
D．18和8
正确答案：A
解析：本题考查数据结构基础知识。构造散列表时，若关键字k1≠k2，而H(k1)＝H(k2)，即关键字不同的元素被映射到同一个散列地址，称发生了冲突，称k1和k2互为同义词。根据题中给出的散列函数H(Key)=Key mod 11，H(24)＝2，H(13)＝2，H(31)=9，H(6)=6，H(15)=4，H(18)=7，H(8)＝8，则发生冲突的元素为24和13。 -
第16题：
设线性表(59，53，46，48，37，31，25)采用散列(Hash)法进行存储和查找，散列函数为H(Key)=Key MOD 7(MOD表示整除取余运算)。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址 (38) 对应的单链表最长。
A.2
B.3
C.4
D.6
正确答案：C
53,48,25对应的地址都为4. -
第17题：
设有一个用线性探测法解决冲突得到的散列表:
0 1 2 3 4 5 6 7 8 9 10
散列函数为H(k)=k mod 11若查找元素15，则探测的次数(比较的次数)为（ ）。
A)7
B)9
C)3
D)6
正确答案：C
根据散列函数H(k)=kmod11，我们知道15本应该存放在索引号为4的位置上，但这里已经存放了50，根据线性探测法，它的存放位置必须往后延，所以采用线性探测法查找15就会从索引号4开始一直往后比较，直到找到15时已经比较了3次。 -
第18题：
设散列表的存储空间大小为19，所用散列函数为h(key)=key mod 19，用开放地址线性探查法解决碰撞。散列表的当前状态如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 194 768 559 582 93 208 现要将关键码值75插入到该散列表中，其地址应为______。
A．1
B．11
C．5
D．15
正确答案：A
-
第19题：
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则在所构造的哈希散列表上进行等概率成功查找的平均查找长度为(60)(为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值，称为查找算法在查找成功时的平均查找长度)。
A．(8×1)/8
B．(8×1)/9
C．(5×1+2+3+6)/8
D．(5×1+2+3+6)/9
正确答案：C
解析：本题考查数据结构中哈希表的基础知识。线性探测法解决冲突的方法是：若在地址r处发生冲突，则探测地址 r+1，若已到达表尾，则再从表头出发进行探测。若是插入元素，则找到一个空闲单元为止。若表已满则采用其他策略解决冲突；若是访问元素，则找到元素或一个空闲单元为止。
初始哈希表为空，根据序列(16，25，35，43，51，62，87，93)和哈希函数H(Key)=Key mod 7构造哈希表的过程如下。
①16 mod 7=2 25 mod 7=4 35 mod 7=0 43 mod 7=1，地址2、4、0、1空闲，所以插入对应元素。
②51 mod 7=2，地址2处冲突，因此探测地址3，该单元空闲，因此51存入地址3。由于62 mod 7=6，地址6处空闲，所以将62插入地址6。
③87 mod 7=3，地址3处冲突，因此依次探查地址4、5，地址5空闲，因此87存入地址5；93 mod 7=2，地址2处冲突，因此依次探查地址3、4、5、6、7，地址7空闲，因此93存入地址7。
为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对于含有n个记录的表，查找成功时的平均查找长度定义为：
，其中，Pi为对表中第i个记录进行查找的概率，且
，一般情况下，均认为查找每个记录的概率是相等的，即 Pi=1/n。Ci为找到表中其关键字与给定值相等的记录时(为第i个记录)，和给定值已进行过比较的关键字个数。对于本试题所构造的哈希表，平均查找长度ASL=(1+1+1+1+2+1+3+6)/8=2。
-
第20题：
假定用散列函数H1=k mod 13计算散列地址，当发生冲突时，用散列函数 H2=k mod 11+1来计算下一个探测地址的地址增量。设散列表的地址空间为0～12，在地址2、3、8中，散列表相应的内容为80，85，34。下一个被插入的关键码是42，其插入的位置是【 】。
正确答案：×
0 解析：H1=42 mod 13=3，地址3中已分配给85，所以计算H2,H2=42 mod 11+1=10，这是地址增量。下一个探测地址应为3+10=13,13 mod 13=0,0地址为空，故42可插入在该地址中。 -
第21题：
设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为1的链中有()个记录。A.1
B.2
C.3
D.4答案：D解析：由散列函数H(key)=keyMOD13计算每个记录的散列地址，散列地址为1的关键字有14，1，27，79，共4个记录。 -
第22题：
设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：查找关键字98（失败）时，需要依次与哪些关键字比较。
正确答案:分别于关键字20,84比较。 -
第23题：
问答题设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：求等概率下查找成功的平均查找长度ASL。正确答案： ASL成功=(1+1+2+1+2+1+1+3+1+1+2+4+3)/13=23/13解析： 暂无解析 -
第24题：
单选题散列表的地址区间为0-17，散列函数为H（K）=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则元素59存放在散列表中的地址是（）A9
B11
C10
D8
正确答案： B解析： 暂无解析