北航第六次数据结构与程序设计作业（查找与排序）选填题
一、
顺序查找的平均查找长度ASL=（1 + 2 + …… + n）/ n = (n + 1）/ 2
二、
这半查找法的平均查找次数和判定树的深度有关系。若查找一个不存在的元素，说明进行了深度次比较。
注意，判定树不是满二叉树，因此深度和结点个数之间并不存在必然的数学关系。
但是我们可以根据满二叉树h=log（n+1）大概估计一下，如果是三层的满二叉树，那么n为7，如果是4层的满二叉树，则n为15。因此，本题的判定树一定是5层，因此最多比较五次。
判定树具体形态为：
三、
ASL=每i层结点个数*i （累积和）/ 长度
判定树形态为：
则总的长度为：（1 * 1 + 2 * 2 + 4 * 3 + 2 * 4）=(1 + 4 + 12 + 8）=25
四、
判定树形态：
要小心：题目中说了，是访问元素的下标，因此，访问路径的元素为10,16,12，下标为4,7,5
五、
①显然不对，没有考虑到叶子结点
②对
③对
④只有当插入数据导致结点分裂，而且分裂至根结点的数据个数也超过m-1个的时候，树才长高一层
六、
19%13=6，84%13=6
14%13=1，1%13=1，27%13=1，79%13=1
23%13=10，10%13=10
68%13=3，55%13=3
20%13=7
11%13=11
因此，余数为1的有4个，也就是散列地址为1的链中有4个记录
七、
原大堆为：
插入18后：
注意注意，看看题目问的是：比较的次数，而不是18交换的次数，18先和10比较，发现18比10大。那就18和10交换位置，然后再和25比较，发现25比18大，因此不交换。
八、
选择排序每次选一个最小的放在当前序列的最左边，位置确定。
冒泡先把最大的冒到最后，再把次大的冒到倒数第二，位置也是确定的。
归并大家先想一个这个情景：考试的时候，1班的第一名一定是全年级第一名吗？未必对吧？归并排序和这个情况一样，你是你子序列中的最值，但是和相邻子序列归并之后就未必是了
堆排序每次都把最大的元素即堆顶和当前堆的最后一个元素交换，因此位置也确定。
九、
我们发现，每次都是当前序列的最小元素和当前未排序序列第一个元素交换，很明显的选择排序
十、
冒泡的话，前两趟跑完之后，最大和次大，即23和13应该排在最后
插入排序，第i趟排序结束以后，前i+1个元素是有序的，此题满足
选择排序肯定先把最小的放到前面俩
归并肯定也不是，因为第三第四的大小关系不对，第七第八也不对
十一、
选择排序，选最小的，放第一个，13和49交换，明显A
十二、
你猜猜qsort函数第一个参数为啥是数组名
十三、
考试问你时间复杂度，你就看ppt就行了。。。反正开卷
十四、
第一次，16和6交换：
30和10交换：
28和4交换：
4和key12交换
明显，选C
十五、
找找，那一组里，没有两个元素，左边都比他小，右边都比他大
A.2的左边都比他大，9的左边都比他小，可以
B.同A
C.9到时可以，但找不出另一个
D.5的左边都比他小，右边都比他大；9的左边都比他小
十六、
由题可知，前6个元素已经排好序，那么排好序的结果应该是：
13 38 49 65 76 97 47 50
第一次和49比，第二次和38比，第三次和13比
十七、
查找每个元素，这个元素都要被比较，那就只能是判定树的根节点了
（1+99）/ 2 =50
十八、
看好了，是在序列中的位置，不是下标，位置从1开始，下标从0开始
判定树的根结点为第(1+12)/2=6,根结点右子树的根结点的位置为（7+12）/ 2=9。
十九、
发生冲突，说明余数一致，说明能整除，放眼观去，63,9,45都能整除，因此3个和18冲突
二十、
从arr[1]到arr[n-1]，如果本身就递增，那么每个元素只跟自己的直接前驱元素比较一次就行，那么比较了n-1次。