一、

順序查找的平均查找長度ASL=（1 + 2 + …… + n）/ n = (n + 1）/ 2

---

二、

這半查找法的平均查找次數(shù)和判定樹的深度有關(guān)系。若查找一個不存在的元素，說明進行了深度次比較。

注意，判定樹不是滿二叉樹，因此深度和結(jié)點個數(shù)之間并不存在必然的數(shù)學(xué)關(guān)系。
但是我們可以根據(jù)滿二叉樹h=log（n+1）大概估計一下，如果是三層的滿二叉樹，那么n為7，如果是4層的滿二叉樹，則n為15。因此，本題的判定樹一定是5層，因此最多比較五次。

判定樹具體形態(tài)為：

---

三、
ASL=每i層結(jié)點個數(shù)*i （累積和）/ 長度
判定樹形態(tài)為：

則總的長度為：（1 * 1 + 2 * 2 + 4 * 3 + 2 * 4）=(1 + 4 + 12 + 8）=25

---

四、

判定樹形態(tài)：
要小心：題目中說了，是訪問元素的下標，因此，訪問路徑的元素為10,16,12，下標為4,7,5

---

五、
①顯然不對，沒有考慮到葉子結(jié)點
②對
③對
④只有當插入數(shù)據(jù)導(dǎo)致結(jié)點分裂，而且分裂至根結(jié)點的數(shù)據(jù)個數(shù)也超過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

因此，余數(shù)為1的有4個，也就是散列地址為1的鏈中有4個記錄

---

七、
原大堆為：
插入18后：

注意注意，看看題目問的是：比較的次數(shù)，而不是18交換的次數(shù)，18先和10比較，發(fā)現(xiàn)18比10大。那就18和10交換位置，然后再和25比較，發(fā)現(xiàn)25比18大，因此不交換。

---

八、
選擇排序每次選一個最小的放在當前序列的最左邊，位置確定。

冒泡先把最大的冒到最后，再把次大的冒到倒數(shù)第二，位置也是確定的。

歸并大家先想一個這個情景：考試的時候，1班的第一名一定是全年級第一名嗎？未必對吧？歸并排序和這個情況一樣，你是你子序列中的最值，但是和相鄰子序列歸并之后就未必是了

堆排序每次都把最大的元素即堆頂和當前堆的最后一個元素交換，因此位置也確定。

---

九、

我們發(fā)現(xiàn)，每次都是當前序列的最小元素和當前未排序序列第一個元素交換，很明顯的選擇排序

---

十、

冒泡的話，前兩趟跑完之后，最大和次大，即23和13應(yīng)該排在最后

插入排序，第i趟排序結(jié)束以后，前i+1個元素是有序的，此題滿足

選擇排序肯定先把最小的放到前面?zhèn)z

歸并肯定也不是，因為第三第四的大小關(guān)系不對，第七第八也不對

---

十一、
選擇排序，選最小的，放第一個，13和49交換，明顯A

---

十二、

你猜猜qsort函數(shù)第一個參數(shù)為啥是數(shù)組名

---

十三、

考試問你時間復(fù)雜度，你就看ppt就行了。。。反正開卷

---

十四、
第一次，16和6交換：

30和10交換：
28和4交換：
4和key12交換
明顯，選C

---

十五、
找找，那一組里，沒有兩個元素，左邊都比他小，右邊都比他大
A.2的左邊都比他大，9的左邊都比他小，可以
B.同A
C.9到時可以，但找不出另一個
D.5的左邊都比他小，右邊都比他大；9的左邊都比他小

---

十六、
由題可知，前6個元素已經(jīng)排好序，那么排好序的結(jié)果應(yīng)該是：
13 38 49 65 76 97 47 50
第一次和49比，第二次和38比，第三次和13比

---

十七、
查找每個元素，這個元素都要被比較，那就只能是判定樹的根節(jié)點了
（1+99）/ 2 =50

---

十八、

看好了，是在序列中的位置，不是下標，位置從1開始，下標從0開始
判定樹的根結(jié)點為第(1+12)/2=6,根結(jié)點右子樹的根結(jié)點的位置為（7+12）/ 2=9。

---

十九、

發(fā)生沖突，說明余數(shù)一致，說明能整除，放眼觀去，63,9,45都能整除，因此3個和18沖突

---

二十、

從arr[1]到arr[n-1]，如果本身就遞增，那么每個元素只跟自己的直接前驅(qū)元素比較一次就行，那么比較了n-1次。