【正文】 折半查找時(shí)查找成功的平均查找長度。③ 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。答案： （4），依次執(zhí)行下列操作，畫出各步操作的結(jié)果。① 插入90 ② 插入25 ③ 插入45 ④ 刪除60 3階B樹 （5）設(shè)哈希表的地址范圍為0～17，哈希函數(shù)為：H（key）=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問題：① 畫出哈希表的示意圖；② 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？③ 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？④ 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。答案：①畫表如下：012345678910111213141516173217634924401030314647②查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63與31比較 ,不匹配。然后順移，與46,47,32,17,63相比，一共比較了6次?、鄄檎?0,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因?yàn)?2號單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。④對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋33+6）＝23/11（6）設(shè)有一組關(guān)鍵字（9，01，23，14，55，20，84，27），采用哈希函數(shù)：H（key）=key %7 ，表長為10，用開放地址法的二次探測法處理沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長度。答案：散列地址0123456789關(guān)鍵字14192384275520比較次數(shù)1112 3 412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%10=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4次。（7）設(shè)哈希函數(shù)H（K）=3 K mod 11，哈希地址空間為0～10，對關(guān)鍵字序列（32，13，49，24，38，21，4，12），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時(shí)和查找失敗時(shí)的平均查找長度ASLsucc和ASLunsucc。① 線性探測法；② 鏈地址法。答案：①散列地址012345678910關(guān)鍵字 4 12493813243221比較次數(shù) 11121212ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11 ②ASLsucc =（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11第8章 排序1．選擇題（1）從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。A．歸并排序 B．冒泡排序 C．插入排序 D．選擇排序 答案：C（2）從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（ ）。A．歸并排序 B．冒泡排序 C．插入排序 D．選擇排序 答案：D（3）對n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列（ ）情況下比較的次數(shù)最多。A．從小到大排列好的 B．從大到小排列好的 C．元素?zé)o序 D．元素基本有序答案：B解釋：對關(guān)鍵字進(jìn)行冒泡排序，關(guān)鍵字逆序時(shí)比較次數(shù)最多。（4）對n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)最多為（ ）。A．n+1 B．n C．n1 D．n(n1)/2答案：D解釋：比較次數(shù)最多時(shí)，第一次比較n1次，第二次比較n2次……最后一次比較1次，即(n1)+(n2)+…+1= n(n1)/2。（5）快速排序在下列（ ）情況下最易發(fā)揮其長處。A．被排序的數(shù)據(jù)中含有多個(gè)相同排序碼 B．被排序的數(shù)據(jù)已基本有序 C．被排序的數(shù)據(jù)完全無序 D．被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解釋：B選項(xiàng)是快速排序的最壞情況。（6）對n個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（ ）。A．O(n) B．O(n2) C．O(nlog2n) D．O(n3) 答案：B解釋：快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)，但在最壞情況下，即關(guān)鍵字基本排好序的情況下，時(shí)間復(fù)雜度為O(n2)。（7）若一組記錄的排序碼為（46, 79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。A．38，40，46，56，79，84 B．40，38，46，79，56，84C．40，38，46，56，79，84 D．40，38，46，84，56，79答案：C（8）下列關(guān)鍵字序列中，（ ）是堆。A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72答案：D解釋：D選項(xiàng)為小根堆（9）堆是一種（ ）排序。A．插入 B．選擇 C．交換 D．歸并答案：B（10）堆的形狀是一棵（ ）。A．二叉排序樹 B．滿二叉樹 C．完全二叉樹 D．平衡二叉樹答案：C（11）若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（ ）。A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38答案：B（12）下述幾種排序方法中，要求內(nèi)存最大的是（ ）。A．希爾排序 B．快速排序 C．歸并排序 D．堆排序答案：C解釋：堆排序、希爾排序的空間復(fù)雜度為O(1)，快速排序的空間復(fù)雜度為O(log2n)，歸并排序的空間復(fù)雜度為O(n)。（13）下述幾種排序方法中，（ ）是穩(wěn)定的排序方法。A．希爾排序 B．快速排序 C．歸并排序 D．堆排序答案：C解釋：不穩(wěn)定排序有希爾排序、簡單選擇排序、快速排序、堆排序；穩(wěn)定排序有直接插入排序、折半插入排序、冒泡排序、歸并排序、基數(shù)排序。（14）數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用( )算法最節(jié)省時(shí)間。A．冒泡排序 B．快速排序 C．簡單選擇排序 D．堆排序答案：D（15）下列排序算法中，（ ）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A．希爾排序 B．快速排序 C．冒泡排序 D．堆排序答案：A解釋：快速排序的每趟排序能將作為樞軸的元素放到最終位置；冒泡排序的每趟排序能將最大或最小的元素放到最終位置；堆排序的每趟排序能將最大或最小的元素放到最終位置。2．應(yīng)用題（1）設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。① 直接插入排序② 折半插入排序③ 希爾排序（增量選取5，3，1）④ 冒泡排序⑤ 快速排序⑥ 簡單選擇排序⑦ 堆排序⑧ 二路歸并排序答案：①直接插入排序[2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 12 16 28 30] 10 16* 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18 [2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30]② 折半插入排序 排序過程同①③ 希爾排序（增量選取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量選取5）6 2 12 10 18 16 16* 20 30 28 （增量選取3）2 6 10 12 16 16* 18 20 28 30 （增量選取1）④ 冒泡排序2 12 16 28 10 16* 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30] 2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16* [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16* 18 20 28 30] 2 6 10 [12 16 16* 18 20 28 30]2 6 10 12 16 16* 18 20 28 30] ⑤ 快速排序12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30左子序列遞歸深度為1，右子序列遞歸深度為3⑥ 簡單選擇排序2 [12 16 30 28 10 16* 20 6 18] 2 6 [16 30 28 10 16* 20 12 18] 2 6 10 [30 28 16 16* 20 12 18] 2 6 10 12 [28 16 16* 20 30 18] 2 6 10 12 16 [28 16* 20 30 18] 2 6 10 12 16 16* [28 20 30 18] 2 6 10 12 16 16* 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30]