北航第六次数据结构与程序设计作业（查找与排序）选填题

一、

顺序查找的平均查找长度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次。