1、设有一组关键字(32，10，24，17，31,30，46，47，40，63，49)，假设每个元素 的查找概率相等，试求出：（1）若采用顺序查找，查找成功时的平均查找长度; （2）若在一棵空的二叉排序树中依次插入上述关键字得到二叉排序树，查找成功时 的平均查找长度：（3）采用散列函数H(kev)=kev%17，用线性探测法处理冲突，设表 长为18，求这组关键字的散列表，并计算查找成功和查找失败时的平均查找长度。

<think>嗯，这个问题看起来有点复杂，不过慢慢来应该没问题。首先，用户有三个小问题要解决，都是关于数据结构的查找算法和平均查找长度的计算。我需要分别处理每个部分，确保每个步骤都正确。 第一个问题是关于顺序查找的平均查找长度（ASL）。顺序查找的话，就是按顺序逐个比较，直到找到目标元素。因为每个元素的查找概率相等，所以ASL应该是所有元素位置的加和除以元素个数。比如有n个元素，每个的位置从1到n，所以总和是n(n+1)/2，然后除以n，得到(n+1)/2。不过具体这里的关键字有11个，所以应该是(11+1)/2=6？或者是不是需要考虑每个元素的位置？比如第一个元素查找一次，第二个两次，依此类推。然后总和是1+2+...+11=66，除以11就是6。所以第一题的答案应该是6。这个应该是对的。 接下来第二个问题是在二叉排序树（BST）中插入这些关键字后的平均查找长度。这里需要先构建这棵BST，然后计算每个节点的深度加1的和，再除以节点数。需要注意的是，插入顺序不同，树的形状也会不同，进而影响平均查找长度。题目里说是在空的BST中依次插入给定的关键字，所以要按照给出的顺序插入：32，10，24，17，31，30，46，47，40，63，49。 让我试着画出这棵树的结构： - 根节点是32。 - 插入10，比32小，作为左子。 - 插入24，比32小，往左子树，比10大，作为10的右子。 - 插入17，比32小，往左到10，然后往右到24，比24小，作为24的左子。 - 插入31，比32小，左子树到10，右到24，右到24的右子树？或者原24的右子是否已经有？原24插入的时候，24作为10的右子，之后插入17是24的左子。接下来插入31，应该从根开始，32左，到10的右子树24，然后比较31和24，31大，所以作为24的右子？ 是的，所以24的右子是31。 - 然后插入30，比32小，到10的右子24，再比24大，到24的右子31，30比31小，作为31的左子。 - 接下来插入46，比32大，作为32的右子。 - 插入47，比32大，到46，比46大，作为46的右子。 - 插入40，比32大，到46，再比46小，所以作为46的左子？因为原来的46右子已经是47了，那40应该是46的左子？ 是的。 - 插入63，比32大，到46的右子47，再比47大，作为47的右子63？ 或者原47的右子是否空着？是的，所以63作为47的右子。 - 最后插入49，比32大，到46，再比46大，到47，比47大，到63，然后49比63小，作为63的左子？ 这样构建出来的BST结构可能需要确认每个节点的位置是否正确，以及各节点的深度。 现在，计算每个节点的查找长度（即所在的层数，从1开始计算）。比如根节点32在第1层，查找长度是1。10在第二层，24在第三层，依此类推。然后总和所有节点的层数，除以11得到平均查找长度。 可能需要具体画出树的结构，然后计算每个节点的层数： 根节点：32（层1） 左子树： - 10（层2） - 右子24（层3） - 左子17（层4） - 右子31（层4） - 左子30（层5） 右子树： - 46（层2） - 右子47（层3） - 右子63（层4） - 左子49（层5） - 左子40（层3） 不过这里可能我之前插入40的时候是否正确？插入40是在插入46之后。插入46作为右子，之后插入47作为右子的右子。然后插入40的时候，应该从根开始，比32大，到46，40比46小，所以作为46的左子，也就是层3。对，没错。所以40在层3的位置。 同样，插入49的时候，是从根到32→46→47→63→左子49，所以层5？ 那每个节点的层数： 32（1） 10（2） 24（3） 17（4） 31（4） 30（5） 46（2） 40（3） 47（3） 63（4） 49（5） 计算每个节点的层数之和：1+2+3+4+4+5+2+3+3+4+5=1+2=3; +3=6; +4=10; +4=14; +5=19; +2=21; +3=24; +3=27; +4=31; +5=36。总和是36。平均是36/11≈3.27。所以第二题的ASL是36/11≈3.27，或者用分数的话是3又3/11。这应该是正确的吗？需要再检查一下每个节点的层数是否正确。 比如： 32层1 左子树： 10层2 右子24层3 左子17层4 右子31层4 左子30层5 右子树： 46层2 左子40层3 右子47层3 右子63层4 左子49层5 所以总和： 32（1） →1 10（2）→2 →累计3 24（3）→3 →累计6 17（4）→4 →累计10 31（4）→4 →累计14 30（5）→5 →累计19 46（2）→2 →累计21 40（3）→3 →累计24 47（3）→3 →累计27 63（4）→4 →累计31 49（5）→5 →累计36 没错，总和是36，平均36/11≈3.27。所以第二题的答案是36/11≈3.27。 第三个问题是关于散列表的处理，使用H(key)=key%17，线性探测法处理冲突，表长18。需要构造散列表，并计算查找成功和失败时的ASL。 首先，将每个关键字代入散列函数计算初始位置，然后处理冲突。 关键字列表：32，10，24，17，31，30，46，47，40，63，49。共11个元素。 计算每个关键字的H(key)=key%17： 32%17=32-17=15，余15 →地址15 10%17=10 →地址10 24%17=24-17=7 →地址7 17%17=0 →地址0 31%17=31-17=14 →地址14 30%17=30-17=13 →地址13 46%17=46-2*17=46-34=12 →地址12 47%17=47-2*17=47-34=13 →地址13 →冲突，探测下一个位置14，14被31占用了吗？初始位置13，冲突后探测地址14，如果14被占用，则继续探测15，依此类绕。或者这里的顺序是线性探测，即每次加1，直到找到空位，循环到表头吗？ 表长为18，所以地址是0到17。 现在逐个插入： 初始化散列表全部为空。 插入顺序是题目给出的顺序吗？原问题没有说明，所以可能需要假设按照给定的顺序插入：32，10，24，17，31，30，46，47，40，63，49。这个顺序会影响冲突处理的结果，因此必须严格按照插入顺序来处理。 现在逐个处理每个关键字的插入： 1. 插入32：H(32)=15 →地址15空，放这里。 表状态：15:32 2. 插入10：H(10)=10 →地址10空，放这里。 表状态：10:10, 15:32 3. 插入24：H(24)=7 →地址7空，放这里。 表状态：7:24, 10:10, 15:32 4. 插入17：H(17)=0 →地址0空，放这里。 表状态：0:17,7:24,10:10,15:32 5. 插入31：H(31)=14 →地址14空，放这里。 表状态：0:17,7:24,10:10,14:31,15:32 6. 插入30：H(30)=13 →地址13空，放这里。 表状态：13:30，其他同上。 7. 插入46：H(46)=12 →地址12空，放这里。 表状态：12:46, 13:30等。 8. 插入47：H(47)=47%17。计算一下：17*2=34，47-34=13 →余13。所以地址13已经被30占用了，冲突。需要线性探测，即下一个地址14，检查是否空。地址14有31，不空。下一个地址15（被32占），地址16，空吗？假设此时地址16是空的，所以插入到16？ 不，顺序是13→14→15→16→17→0→1…，因为表长是18，地址0到17。 所以插入47时，H(key)=13。地址13被占，探测下一个地址14，被占；地址15被占；地址16空吗？假设在插入47时，此时散列表中的情况： 在插入46之后，此时地址12是46，13是30，14是31，15是32，16和17尚未被占用？ 是的。所以在处理47时： 尝试13（被占）→14（被31占）→15（被32占）→16（空），所以插入到地址16。此时散列表16:47。 接下来第8个元素插入完毕。 9. 插入40：H(40)=40%17。17*2=34，40-34=6 →余6。地址6空，所以直接插入。 表状态：6:40，其他不变。 10. 插入63：H(63)=63%17。17*3=51，63-51=12 →余12。地址12被46占用了，冲突。线性探测下一个地址13→被占，地址14→被占，地址15→被占，地址16→被47占，地址17→空？是的，所以插入到17。 63放在地址17。 11. 插入49：H(49)=49%17。17*2=34，49-34=15 →余15。地址15被32占，冲突。探测下一个地址16→被47占，地址17→被63占，地址0→被17占，地址1→空，所以插入到地址1。 所以最终的散列表为： 0:17 1:49 6:40 7:24 10:10 12:46 13:30 14:31 15:32 16:47 17:63 是否正确？需要再次确认每个步骤： 当插入49时，H(49)=15。地址15被占，探测16→被占，17→被占，然后地址0→被占，地址1→空，所以插入到1。 是的。那散列表的地址分布如上述。 现在，计算查找成功的平均查找长度。对于每个关键字，查找次数等于插入时探测的次数加1（因为每次冲突探测的次数即为查找次数）。例如： 32：H=15，直接插入，探测1次 →查找次数1 10：H=10，直接插入，次数1 24：H=7，次数1 17：H=0，次数1 31：H=14，次数1 30：H=13，次数1 46：H=12，次数1 47：H=13 →冲突，探测13,14,15,16（成功），探测次数4 →查找次数4 40：H=6，次数1 63：H=12 →冲突，探测12,13,14,15,16,17（成功），探测次数6 →查找次数6 49：H=15 →冲突，探测15,16,17,0,1 →共探测5次，查找次数5+1=6？或者探测次数是5次，因为第一次是15，然后16、17、0、1，共5次探测，所以查找次数是5+1=6？或者更准确地说，每次探测都算一次比较，所以在成功查找时，查找次数等于探测次数+1吗？ 这里可能需要明确线性探测的查找次数计算方法。当插入时，每次冲突探测次数是找到空位所需的次数，而查找成功时的次数等于探测次数+1。比如，插入某个元素时，如果它需要探测t次才找到位置，那么查找成功时的次数就是t+1。或者，另一种理解是，当查找一个元素时，从H(key)的位置开始，依次比较，直到找到该元素，比较次数即为查找次数。例如，对于47，它被存在地址16。当查找47时，计算H(47)=13，检查地址13是否是47，不是（是30），然后检查14（是31），15（32），16（47），共4次比较。因此，查找次数是4次。同理，插入时探测的次数是3次（因为第一次在13冲突，然后探测14、15、16，共三次探测，最后放在16，所以探测次数是3次，但查找次数是4次？或者插入时的探测次数是3次冲突，所以需要探测次数是3次，而查找次数是3+1=4次？是的。例如，在插入47的时候，需要探测13（冲突）、14（冲突）、15（冲突）、16（空），所以探测次数是3次（从13开始检查，需要探测三次后找到空位），但查找的时候，要比较4次才能找到。所以查找成功次数为探测次数+1=3+1=4次？ 是的，所以每个元素的查找次数等于插入时的探测次数+1。或者，更准确的是，当插入元素时，探测次数是找到空位所需的次数，而查找时需要检查该元素的位置，直到找到为止，所以次数就是探测次数+1。 因此，每个关键字的查找次数如下： 32：插入时探测0次（直接放在15），查找次数1 10：0次探测，次数1 24：0次，次数1 17：0次，次数1 31：0次，次数1 30：0次，次数1 46：0次，次数1 47：插入时探测3次（13→14→15→16），所以查找次数3+1=4 40：0次，次数1 63：插入时探测次数：H=12冲突，探测12（被占）、13（被占）、14（被占）、15（被占）、16（被占）、17（空），所以探测次数5次，查找次数5+1=6？ 或者当插入63时，H=12，检查12是否可用，被占用了，然后探测13，被占，14被占，15被占，16被占，17可用。所以探测次数是5次（从12开始，探测了12到17，共5次探测），因此查找次数是5+1=6次？ 或者更仔细地说，每次探测都是地址+1，直到找到空位。比如： 对于63的插入： H=12 →检查地址12（被占），探测次数1 →地址13（被占），次数2 →地址14（被占），次数3 →地址15（被占），次数4 →地址16（被占），次数5 →地址17（空），次数6？或者探测次数是找到空位需要移动的次数？ 这个时候可能需要明确线性探测的探测次数的计算方式。例如，插入元素时，如果初始位置被占，则依次检查下一个位置，直到找到空位。每个检查的次数即为探测次数。例如，插入63时，初始位置12被占，探测13→被占（探测1次），14→被占（探测2次），15→被占（探测3次），16→被占（探测4次），17→空（探测5次）。所以总共有5次探测，加上初始位置的检查，总共探测次数是5次？或者初始位置算第0次？ 这里可能存在不同的定义方式，但通常探测次数指的是需要探测的次数，包括第一个位置。比如，当初始位置被占，则探测下一个位置，直到找到空位，次数为探测的次数。例如，在查找时，如果元素被存在初始位置后的第k个位置，则查找次数是k+1次。 对于插入63的情况： 初始位置12，被占，然后检查13（1次探测），被占；14（2次），被占；15（3次），被占；16（4次），被占；17（5次），空。所以探测次数是5次，因此查找时需要从12开始，检查到17，共6次比较（12、13、14、15、16、17）才能找到。因此查找次数是6次。所以插入时的探测次数为5次，查找次数为6次。 同理，插入49的时候： H=15，被占→探测16（被占），17（被占），0（被占），1（空）。探测次数是3次，查找次数是4次？ 或者探测次数是4次？因为初始地址15被占，探测16→被占（次数1），17→被占（次数2），0→被占（次数3），1→空（次数4）。所以探测次数是4次，查找次数是4+1=5次？ 这个时候可能需要明确线性探测的处理方式。例如，每次移动一个位置，直到找到空位，探测次数即移动的次数。例如，在插入时，初始位置被占，则探测次数等于移动的次数。 这里可能需要参考教材中的定义。通常，ASL成功时的计算是根据每个关键字的查找次数，即从散列地址开始，直到找到该关键字所需的比较次数。例如，对于47，H(key)=13，但存在地址16，所以需要比较13、14、15、16，共4次比较。所以ASL为各关键字的比较次数之和除以元素个数。 现在，针对每个关键字： 1. 32：H=15，位置15，比较1次 →1 2. 10：H=10，比较1次 →1 3. 24：H=7，比较1次 →1 4. 17：H=0，比较1次 →1 5. 31：H=14，比较1次 →1 6. 30：H=13，比较1次 →1 7. 46：H=12，比较1次 →1 8. 47：H=13，存在地址16，比较次数4 →13→14→15→16，共4次 9. 40：H=6，比较1次 →1 10.63：H=12，存在地址17，比较次数6 →12→13→14→15→16→17，共6次 11.49：H=15，存在地址1，比较次数5 →15→16→17→0→1，共5次 所以各关键字的比较次数： 32:1 10:1 24:1 17:1 31:1 30:1 46:1 47:4 40:1 63:6 49:5 总和是1+1+1+1+1+1+1+4+1+6+5= 1*7 +4+6+5=7+4=11+6=17+5=22 →总和22。平均ASL成功=22/11=2。 这个结果好像有问题，因为前面的计算中有几个关键字的比较次数超过1次。比如63需要比较6次，49需要5次，47需要4次。总和应该是： 各次数： 32,10,24,17,31,30,46,40各1次 →8个，总和8 47→4次 →8+4=12 63→6 →12+6=18 49→5 →18+5=23 所以总和是23，平均23/11≈2.09。可能哪里出错了？ 或者我刚才计算时出错了。让我重新统计： 每个关键字的比较次数： 32：1 →1 10：1 →2 24：1 →3 17：1 →4 31：1 →5 30：1 →6 46：1 →7 47：4 →11 40：1 →12 63：6 →18 49：5 →23 是的，总和是23，平均23/11≈2.09。所以查找成功的ASL是23/11≈2.09。 那之前的计算哪里出问题了？可能刚才误以为总和是22，但实际是23。 现在查找失败时的平均查找长度。这需要计算对于每个可能的散列地址H(key)，从该地址开始一直探测到遇到空位置为止的比较次数，然后取所有可能H(key)（即0到16，因为模17）的平均值。注意，表长是18，所以地址是0到17，但散列函数是%17，所以H(key)的可能值是0到16。对于每个H(key)值，假设查找一个不存在的关键字，其散列地址是k，那么需要从k开始探测，直到找到空位置，或者探测了所有位置（但表长是18，但这里可能处理为直到遇到空位置为止）。 例如，当计算查找失败时的ASL，每个散列地址k（0到16），计算从k开始探测需要多少次比较才能确定该关键字不在表中。 例如，假设散列表中的情况如之前构造的： 地址0:17 1:49 6:40 7:24 10:10 12:46 13:30 14:31 15:32 16:47 17:63 其余地址2、3、4、5、8、9、11、18？表长是18，所以地址到17。剩下的地址如2、3、4、5、8、9、11、以及地址18？不，地址是0到17。 所以，假设现在查找失败时，每个H(key)=k（0到16）需要计算从k开始，依次探测，直到遇到空位置，比较次数即为该k的查找失败次数。注意，即使后面的位置已经被占用，只要有一个空位出现，就停止。 例如，k=0： 从0开始探测： 地址0有元素，比较1次→继续探测地址1，有元素，比较2次→地址2空吗？假设地址2是空的。那么查找失败时的比较次数是2次？因为探测地址0和1，都是被占用的，然后地址2是空，停止。所以比较次数是2次？ 或者，是否需要探测到空位才停止，此时比较次数等于探测的次数？ 例如，k=0： 地址0被占→探测1次，地址1被占→探测2次，地址2空→停止，总比较次数是3次（比较0、1、2）？或者比较次数是指遇到空位时所需的探测次数？ 这里需要明确：查找失败时的比较次数是从H(key)开始，依次检查每个位置，直到找到空位置为止，所检查的位置数目。例如，如果H(key)=0，地址0被占，探测1→被占，地址2空，则比较次数是3次（0、1、2都被检查，直到地址2为空）。 但根据线性探测处理冲突的查找失败ASL计算方法，通常的公式是：对于每个散列地址k，查找失败时的探测次数是从k开始，直到遇到第一个空位置所需的探测次数（包括检查空位置的那次）。例如，假设H(key)=0，地址0被占，探测地址1，也被占，地址2空，所以需要探测3次（0、1、2），其中第三次发现地址2为空，停止，此时比较次数为3次。 不过这可能因教材而异，有的可能认为比较次数是探测到空位置的次数。例如，若H(key)=k，查找时检查k位置，如果被占且不是目标元素，则继续检查k+1，直到找到空位置为止。每个位置的检查都算一次比较，所以如果到空位置时停止，比较次数就是探测的次数，包括空位置的那一次吗？ 例如，在查找失败的情况下，当检查到某个地址为空时，说明元素不存在，此时比较次数等于已经检查过的位置数。例如： H(key)=0： 检查地址0（比较1次，被占）→地址1（比较2次，被占）→地址2（比较3次，空），停止。所以总比较次数是3次。 另一种说法是，当查找失败时，ASL是对于每个可能的H(key)值，计算需要探测多少次才能确定元素不存在，也就是直到遇到空位置，且每次探测都算一次比较，无论是否为空。例如： 对于H(key)=0： 探测0（非空，比较1次）→探测1（非空，比较2次）→探测2（空，比较3次）→停止，总比较次数3次。 所以对于每个散列地址k，从k开始，依次探测，直到找到空位，所需的比较次数为该地址的失败探测次数。然后将所有可能的k（0到16）的失败次数求和，除以散列函数的可能值数量（这里是17，因为模17），得到查找失败的平均查找长度。 现在需要针对每个k=0到16，计算其对应的失败探测次数。 根据之前的散列表： 已占用的地址是：0,1,6,7,10,12,13,14,15,16,17。 空地址是：2,3,4,5,8,9,11,17？哦，原表长是18，即地址0到17。但原插入的63放在地址17，所以地址17被占用了。所以空余的地址是2、3、4、5、8、9、11、以及可能其他的？ 原来的插入情况： 地址0:17 1:49 6:40 7:24 10:10 12:46 13:30 14:31 15:32 16:47 17:63 其他地址（2,3,4,5,8,9,11）是空的。 所以现在计算每个k=0到16的情况： k=0： 探测地址0（被占）→1（被占）→2（空）。比较次数3次。 k=1： 探测地址1（被占）→2（空）。比较次数2次。 k=2： 探测地址2（空）。比较次数1次。 k=3： 探测地址3（空）。比较次数1次。 k=4： 探测地址4（空）。1次。 k=5： 探测地址5（空）。1次。 k=6： 探测地址6（被占）→7（被占）→8（空）。比较次数3次？ 因为地址6被占，探测下一个地址7（被占），再下一个地址8（空），所以比较次数3次。 k=7： 地址7被占→8（空）。比较次数2次。 k=8： 地址8空。比较次数1次。 k=9： 地址9空。比较次数1次。 k=10： 地址10被占→11（空）。比较次数2次。 k=11： 地址11空。比较次数1次。 k=12： 地址12被占→13（被占）→14（被占）→15（被占）→16（被占）→17（被占）→0（被占）→1（被占）→2（空）。这需要循环探测吗？ 这里需要注意的是，线性探测通常是在表内顺序探测，直到回到起始点，但实际应用中，当表未满时，遇到空位就会停止。不过，根据线性探测处理冲突的方法，当查找失败时，必须探测到第一个空位为止，而不管是否绕回。例如，k=12： 地址12被占→13被占→14被占→15被占→16被占→17被占→此时下一个位置是0（因为表长是18，地址17之后是0？或者线性探测是向后移动，即地址17的下一个是0？或者表地址是0到17，当在地址17探测下一个时，是地址0？ 如果是循环的话，当k=12时，探测顺序是12→13→14→15→16→17→0→1→2→…直到找到空位。 根据这个散列表，地址12被占，接下来： 地址12被占→13被占→14被占→15被占→16被占→17被占→0被占→1被占→2空。所以比较次数是从12开始，依次检查12、13、14、15、16、17、0、1、2，其中地址2是空。所以比较次数是9次？ 这显然有问题，但根据实际的散列表，当k=12时，要探测到地址2才会找到空位，所以需要计算比较次数： 地址12（占）→13（占）→14（占）→15（占）→16（占）→17（占）→0（占）→1（占）→2（空）。共探测了9次，所以比较次数是9次？ 这似乎太高了，但根据散列表的实际存储情况，这是可能的。 同理，计算其他k值： k=12： 探测次数：从12开始，依次探测12→13→14→15→16→17→0→1→2（空），共9次比较。 k=13： 探测顺序：13（占）→14（占）→15（占）→16（占）→17（占）→0（占）→1（占）→2（空）。比较次数8次？ k=13的初始探测地址13被占，接着探测14、15、16、17、0、1、2，所以比较次数是8次？ k=14： 探测顺序：14（占）→15（占）→16（占）→17（占）→0（占）→1（占）→2（空）。比较次数7次。 k=15： 探测顺序：15（占）→16（占）→17（占）→0（占）→1（占）→2（空）。比较次数6次。 k=16： 探测顺序：16（占）→17（占）→0（占）→1（占）→2（空）。比较次数5次。 k=17： 注意H(key)的范围是0到16，所以k=17不是可能的散列值？因为H(key)=key%17，结果只能是0到16。所以k的取值是0到16，共17种可能。因此，k=17不在计算范围内。 所以继续处理k=12到k=16的情况： k=12：探测次数9次。 k=13：从13开始，探测次数8次。 k=14：7次。 k=15：6次。 k=16：从16开始探测，比较次数5次？ 现在，将每个k的探测次数统计如下： k=0 →3次 k=1 →2次 k=2 →1次 k=3 →1次 k=4 →1次 k=5 →1次 k=6 →3次（6→7→8） k=7 →2次（7→8） k=8 →1次 k=9 →1次 k=10→2次（10→11） k=11→1次 k=12→9次 k=13→8次 k=14→7次 k=15→6次 k=16→5次 现在，将这些次数相加： k=0:3 k=1:2 →5 k=2:1 →6 k=3:1 →7 k=4:1 →8 k=5:1 →9 k=6:3 →12 k=7:2 →14 k=8:1 →15 k=9:1 →16 k=10:2 →18 k=11:1 →19 k=12:9 →28 k=13:8 →36 k=14:7 →43 k=15:6 →49 k=16:5 →54 总次数是54次。平均查找失败时的ASL=54/17≈3.176。 所以查找失败的平均查找长度是54/17≈3.18。 总结： 第三题的散列表构造如上述各地址，查找成功的ASL是23/11≈2.09，查找失败的ASL是54/17≈3.18。 现在需要将这些结果整理出来，并确保正确性。 可能需要注意的地方： 1. 在计算查找失败时，每个k的探测次数是否正确？ 例如，k=12的探测次数是否为9次？ 是的，因为从12开始，探测到地址2才找到空位，路径是12→13→14→15→16→17→0→1→2，共9个地址，每个地址检查一次，所以比较次数是9次。 同样，k=13的探测次数是探测13到2，共8次。 确认这些计算是否正确。 另一个例子，k=16： 探测16→17→0→1→2，共5次比较（地址16、17、0、1、2），其中地址2是空。所以次数5次。 是的。 所以总和为54，除以17，得到约3.176，约3.18。 综上，三个问题的答案如下： （1）顺序查找的ASL为6； （2）二叉排序树的ASL为36/11≈3.27； （3）散列表的构造如上述，查找成功的ASL≈2.09，查找失败的ASL≈3.18。 现在需要将结果以清晰的结构呈现给用户，确保每个步骤正确，语法正确，使用中文。</think>### 解答： #### （1）顺序查找成功时的平均查找长度（ASL） 在顺序查找中，每个元素的查找概率相等。对于n个元素，成功查找的平均查找长度为： $$ ASL = \frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2} $$ 此处有11个关键字，因此： $$ ASL = \frac{11+1}{2} = 6 $$ **答案**：顺序查找成功时的平均查找长度为6。 --- #### （2）二叉排序树（BST）查找成功时的平均查找长度 按照给定顺序插入关键字：32，10，24，17，31，30，46，47，40，63，49，构建的BST如下： ``` 32 / \ 10 46 \ / \ 24 40 47 / \ \ 17 31 63 / / 30 49 ``` 每个关键字的查找长度（层数）为： - 32（1层） - 10（2层） - 24（3层） - 17（4层） - 31（4层） - 30（5层） - 46（2层） - 40（3层） - 47（3层） - 63（4层） - 49（5层） 总查找长度和为： $$1 + 2 + 3 + 4 + 4 + 5 + 2 + 3 + 3 + 4 + 5 = 36$$ 平均查找长度为： $$ ASL = \frac{36}{11} \approx 3.27 $$ **答案**：BST查找成功时的平均查找长度约为3.27。 --- #### （3）散列表构造及ASL计算 使用散列函数 \( H(key) = key \% 17 \)，表长为18，线性探测法处理冲突。 ##### 散列表构造 各关键字散列地址及最终位置如下： | 关键字 | 散列地址 | 最终位置 | 探测次数 | |--------|----------|----------|----------| | 32 | 15 | 15 | 1 | | 10 | 10 | 10 | 1 | | 24 | 7 | 7 | 1 | | 17 | 0 | 0 | 1 | | 31 | 14 | 14 | 1 | | 30 | 13 | 13 | 1 | | 46 | 12 | 12 | 1 | | 47 | 13 | 16 | 4 | | 40 | 6 | 6 | 1 | | 63 | 12 | 17 | 6 | | 49 | 15 | 1 | 5 | 散列表最终状态（部分地址为空）： ``` 0:17, 1:49, 6:40, 7:24, 10:10, 12:46, 13:30, 14:31, 15:32, 16:47, 17:63 ``` ##### 查找成功的ASL 每个关键字的查找次数和为： $$1+1+1+1+1+1+1+4+1+6+5 = 23$$ 平均查找长度为： $$ ASL_{\text{成功}} = \frac{23}{11} \approx 2.09 $$ ##### 查找失败的ASL 对每个可能的散列地址 \( k \in [0, 16] \)，计算从 \( k \) 开始探测到空位的次数： - \( k=0 \): 3次（0→1→2） - \( k=1 \): 2次（1→2） - \( k=2 \): 1次（2） - \( k=3 \): 1次（3） - \( k=4 \): 1次（4） - \( k=5 \): 1次（5） - \( k=6 \): 3次（6→7→8） - \( k=7 \): 2次（7→8） - \( k=8 \): 1次（8） - \( k=9 \): 1次（9） - \( k=10 \): 2次（10→11） - \( k=11 \): 1次（11） - \( k=12 \): 9次（12→13→14→15→16→17→0→1→2） - \( k=13 \): 8次（13→14→15→16→17→0→1→2） - \( k=14 \): 7次（14→15→16→17→0→1→2） - \( k=15 \): 6次（15→16→17→0→1→2） - \( k=16 \): 5次（16→17→0→1→2） 总次数和为54，平均查找长度为： $$ ASL_{\text{失败}} = \frac{54}{17} \approx 3.18 $$ **答案**： - 散列表构造如上表，查找成功的ASL≈2.09，查找失败的ASL≈3.18。