【正文】 k，low，high）//在長(zhǎng)為n的有序表中查找關(guān)鍵字k，若查找成功，返回k所在位置，查找失敗返回0。{if（low≤high） //low和high分別是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].keyk）return （BinSrch（r,k，mid+1，high））。 else return （BinSrch（r,k，low，mid1））。 } else return （0）；//查找失敗。}//算法結(jié)束（2）試寫一個(gè)判別給定二叉樹(shù)是否為二叉排序樹(shù)的算法。[題目分析] 根據(jù)二叉排序樹(shù)中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre（初值為null）和全局變量flag，初值為true。若非二叉排序樹(shù)，則置flag為false。[算法描述]define true 1define false 0typedef struct node{datatype data。 struct node *lchild,*rchild。} *BTree。void JudgeBST（BTree T,int flag）// 判斷二叉樹(shù)是否是二叉排序樹(shù)，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。{ if（T!=null amp。amp。 flag） { Judgebst（Tlchild,flag）；// 中序遍歷左子樹(shù) if（pre==null）pre=T；// 中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷 else if（predataTdata）pre=T；//前驅(qū)指針指向當(dāng)前結(jié)點(diǎn) else{flag=flase；} //不是完全二叉樹(shù) Judgebst （Trchild,flag）；// 中序遍歷右子樹(shù)}//JudgeBST算法結(jié)束第8章 排序1．選擇題（1）從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。A．歸并排序 B．冒泡排序 C．插入排序 D．選擇排序 答案：C（2）從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（ ）。A．歸并排序 B．冒泡排序 C．插入排序 D．選擇排序 答案：D（3）對(duì)n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列（ ）情況下比較的次數(shù)最多。A．從小到大排列好的 B．從大到小排列好的 C．元素?zé)o序 D．元素基本有序答案：B解釋：對(duì)關(guān)鍵字進(jìn)行冒泡排序，關(guān)鍵字逆序時(shí)比較次數(shù)最多。（4）對(duì)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ā)揮其長(zhǎng)處。A．被排序的數(shù)據(jù)中含有多個(gè)相同排序碼 B．被排序的數(shù)據(jù)已基本有序 C．被排序的數(shù)據(jù)完全無(wú)序 D．被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解釋：B選項(xiàng)是快速排序的最壞情況。（6）對(duì)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．二叉排序樹(shù) B．滿二叉樹(shù) C．完全二叉樹(shù) D．平衡二叉樹(shù)答案：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)定排序有希爾排序、簡(jiǎn)單選擇排序、快速排序、堆排序；穩(wěn)定排序有直接插入排序、折半插入排序、冒泡排序、歸并排序、基數(shù)排序。（14）數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用( )算法最節(jié)省時(shí)間。A．冒泡排序 B．快速排序 C．簡(jiǎn)單選擇排序 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)。① 直接插入排序④ 冒泡排序⑤ 快速排序⑥ 簡(jiǎn)單選擇排序⑦ 堆排序①直接插入排序[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]④ 冒泡排序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⑥ 簡(jiǎn)單選擇排序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] 2 6 10 12 16 16* 18 20 28 [30]（5）借助于快速排序的算法思想，在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..n]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“not find”信息。請(qǐng)簡(jiǎn)要說(shuō)明算法思想并編寫算法。[題目分析]把待查記錄看作樞軸，先由后向前依次比較，若小于樞軸，則從前向后，直到查找成功返回其位置或失敗返回0為止。int index (RecType R[],int l,h,datatype key){int i=l,j=h。 while (ij) { while (i=j amp。amp。 R[j].keykey) j。 if (R[j].key==key) return j。 while (i=j amp。amp。 R[i].keykey) i++。 if (R[i].key==key) return i。 } cout“Not find”。 return 0。 }//index27