計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第4章

PAGE10第4章 不基于比較的排序不用Sterling公式，而用第2章中對(2.6)式證明的方法證明lgn!=(nlgn)。證明：首先，我們有l(wèi)gn!=lg1+lg2+…+lgn=k=1nlgkk=1nlgn=nlgn=O(n再有l(wèi)gn!=k=1nlgkk=n/2nlgkk=n/2nlgn2n2lgn2所以有l(wèi)gn!=(nlgn)。假設(shè)序列A[1..n]含有n個(gè)不同的數(shù)并已從小到大排好，即A[1]<A[2]<…<A[n]。為方便起見，還假定A[0]=-￥和A[n+1]=￥?？紤]在這個(gè)序列中搜索一個(gè)給定數(shù)字x。如果有某個(gè)序號i存在使得x=A[i](1in)，則報(bào)告成功并輸出序號i。否則，找出兩個(gè)相鄰序號，i和i+1，滿足A[i]<x<A[i+1]。證明，如果用比較的方法搜索的話，任何算法在最壞情況下需要至少élg(n+1)ù次比較。這題的結(jié)果和第2章習(xí)題5的結(jié)果證明二元搜索算法(例2.1)是最優(yōu)的。證明： 顯然，x和序列A中任何一個(gè)數(shù)最多只須比較一次。所以，這樣的搜索算法可以用一個(gè)決策樹來描述。這是一個(gè)完全二叉樹，其中每個(gè)內(nèi)結(jié)點(diǎn)對應(yīng)一個(gè)序列中數(shù)。假定第一次比較是在x和序列中某個(gè)數(shù)A[i]進(jìn)行，那么樹的根結(jié)點(diǎn)對應(yīng)A[i]。我們有三種比較結(jié)果：x=A[i]。這時(shí)搜索停止在這個(gè)結(jié)點(diǎn)并報(bào)告成功。x<A[i]。這種情形發(fā)生時(shí)，這以后算法進(jìn)行的所有的比較用一個(gè)左子樹描述。這時(shí)，如果這以后算法不再比較，則算法中止，左子樹為一葉結(jié)點(diǎn)。x>A[i]。這種情況發(fā)生時(shí)，這以后算法進(jìn)行的所有的比較用一個(gè)右子樹描述。這時(shí)，如果這以后算法不再比較，則算法中止，右子樹為一葉結(jié)點(diǎn)。顯然，一個(gè)算法必須正確地報(bào)告各種情況。對一個(gè)有n個(gè)數(shù)的序列，一共有2n+1種可能的情況，它們是x=A[i](1in)，和A[i]<x<A[i+1]，0in。因此，這個(gè)二叉樹必須有至少2n+1個(gè)結(jié)點(diǎn)，包括內(nèi)結(jié)點(diǎn)和外結(jié)點(diǎn)。假設(shè)這個(gè)樹的高為h，那么它含有的結(jié)點(diǎn)數(shù)最多為：1+2+4+…+2h=2h+1-1。因此我們有2h+1-132n+1，即2h3n+1。由此得h3élg(n+1)ù。因?yàn)樯疃葹閔的結(jié)點(diǎn)必定是個(gè)葉結(jié)奌并代表算法要進(jìn)行h次比較的情況。因此在最壞情況下，任何算法需要至少élg(n+1)ù次比較。假設(shè)在需要排序的6個(gè)數(shù)a1,a2,a3,a4,a5,a6中，已知a1<a3<a5，但此外不知道其他數(shù)字之間的任何關(guān)系。證明任何基於比較的排序算法在最壞情況下需要至少7次比較才能把這6個(gè)數(shù)排好序。證明：在已知a1<a3<a5的情況下，這6個(gè)數(shù)可能有的不同的排列數(shù)是4′5′6=120。所以任一個(gè)基於比較的排序算法對應(yīng)的決策樹必須有至少120個(gè)葉子。設(shè)該樹的高度為h，那么，下面關(guān)系必須滿足：2h3120。因此有h37。這也就是說，某個(gè)葉子的深度至少為7。那么，當(dāng)算法在這個(gè)葉子結(jié)束時(shí)必定經(jīng)過了至少7次比較。所以任何基於比較的排序算法在最壞情況下需要至少7次比較。對任意一個(gè)有n個(gè)內(nèi)結(jié)點(diǎn)的完全二叉樹T，其外路徑總長EPL(T)和內(nèi)路經(jīng)總長IPL(T)滿足以下關(guān)系:EPL(T)=IPL(T)+2n。證明：我們對n進(jìn)行歸納證明。歸納基礎(chǔ)：當(dāng)n=1時(shí)，顯然有EPL(T)=2和IPL(T)=0。所以等式EPL(T)=IPL(T)+2n成立。歸納步驟：假設(shè)當(dāng)內(nèi)結(jié)點(diǎn)數(shù)為n=1，2，…，k-1(k2)時(shí)，均有EPL(T)=IPL(T)+2n。我們證明在n=k時(shí)，該等式仍成立。假設(shè)完全二叉樹T有k個(gè)內(nèi)結(jié)點(diǎn)。如下圖(a)所示，我們總可以找到一個(gè)內(nèi)結(jié)點(diǎn)x，它的兩個(gè)兒子都是葉子，標(biāo)為a和b。如圖(b)所示，如果我們把a(bǔ)和b從樹中刪去，我們可得到另一個(gè)完全二叉樹T’。這個(gè)完全二叉樹T’有k-1個(gè)內(nèi)結(jié)點(diǎn)。xxabx點(diǎn)x的兩個(gè)兒子a和b都是葉子把點(diǎn)x的兩個(gè)兒子a和b都刪去后的二叉樹T’由歸納假設(shè)，我們有EPL(T’)=IPL(T’)+2(k-1)。從樹T和T’的關(guān)系，我們有以下關(guān)系：EPL(T)=EPL(T’)–depth(x)+depth(a)+depth(b) (1)IPL(T)=IPL(T’)+depth(x) (2)由(1)–(2)，以及depth(a)=depth(b)，得到EPL(T)-IPL(T)=EPL(T’)-IPL(T’)-2depth(x)+2depth(a)=2(k-1)+2(depth(a)–depth(x))=2(k-1)+2=2k。所以有EPL(T)=IPL(T)+2k，歸納成功?？炫判虬褦?shù)組A[p..r]中的數(shù)進(jìn)行排序的過程可以用一個(gè)二叉樹來描述。假設(shè)算法的第一次劃分以后，數(shù)字k是中心點(diǎn)，位置在A[q]，左邊部分存放在A[p..q-1]中，而右邊部分存放在A[q+1..r]中。我們用二叉樹的根來代表數(shù)字k。然后，它的左子樹可遞歸地從算法對A[p..q-1]的操作來構(gòu)造，而它的右子樹可遞歸地從算法對A[q+1..r]的操作來構(gòu)造。當(dāng)序列為空時(shí)，其對應(yīng)的二叉樹為一個(gè)葉子。當(dāng)序列只含一個(gè)數(shù)時(shí)，其對應(yīng)的二叉樹只含一個(gè)內(nèi)結(jié)點(diǎn)而它的左右子樹均為葉子。下面圖例顯示快排序?qū)π蛄?，6，2，10，8的操作過程是如何用一個(gè)二叉樹表示的。容易看出，以內(nèi)結(jié)點(diǎn)x為中心點(diǎn)的劃分所需要的比較次數(shù)就等于它下面子樹中內(nèi)結(jié)點(diǎn)的個(gè)數(shù)(不包括x本身)。作為例子，上面圖(c)中我們把各次劃分所用比較次數(shù)標(biāo)在相應(yīng)結(jié)點(diǎn)邊上。當(dāng)某個(gè)內(nèi)結(jié)點(diǎn)下面子樹不含內(nèi)結(jié)點(diǎn)而只含葉子時(shí)，它不對應(yīng)一個(gè)劃分，或者說，它需要0次比較。(a)證明快排序完成對數(shù)組A[p..r]排序所用的比較次數(shù)就等於它所對應(yīng)的二叉樹的內(nèi)路徑總長。(b)用（a）的結(jié)果證明快排序最好情況復(fù)雜度是(nlgn)。證明：設(shè)快排序?qū)?yīng)的二叉樹是T。設(shè)I為內(nèi)結(jié)點(diǎn)的集合。由它的構(gòu)造知道，快排序所用的比較次數(shù)是N(T)=v∈I(以v為根的子樹中內(nèi)結(jié)點(diǎn)的個(gè)數(shù)(不含v本身))。這也就是說，兩個(gè)數(shù)字a和b在快排序中作了比較當(dāng)且僅當(dāng)在樹T中a是b的祖先或b是a的祖先。因此，我們可以換一種方式統(tǒng)計(jì)。我們注意到，有數(shù)字a參與的比較次數(shù)等于它的所有祖先的個(gè)數(shù)，即depth(a)。所以，當(dāng)b是a的祖先時(shí)，它們之間的比較被統(tǒng)計(jì)了一次，統(tǒng)計(jì)在depth(a)中。而當(dāng)a是b的祖先時(shí)，它們之間的比較也正好被統(tǒng)計(jì)了一次，統(tǒng)計(jì)在depth(b)中。因此，快排序一共進(jìn)行的比較次數(shù)是N((b)由第3題作業(yè)知，IPL(T)=EPL(T)-2n，這里n是內(nèi)結(jié)點(diǎn)數(shù)。在快排序?qū)?yīng)的二叉樹中，n也是數(shù)組A中元素的個(gè)數(shù)。因?yàn)檫@個(gè)二叉樹有(n+1)個(gè)葉子，由定理4.5知，EPL(T)=(nlgn)。所以有IPL(T)=EPL(T)-2n=(nlgn)–2n=(nlgn)。這也就是說，任何一次快排序的過程都需要(nlgn)次比較，包括最好情況。請解釋為什么計(jì)數(shù)排序是穩(wěn)定排序。解：計(jì)數(shù)排序先對0到k之間的每一個(gè)值u，統(tǒng)計(jì)出被排序列A[1..n]中有幾個(gè)數(shù)字是小于等于u的。這個(gè)值記在數(shù)組C[u]中。然后，計(jì)數(shù)算法是從右向左，逐個(gè)安排序列A中的數(shù)。假設(shè)有幾個(gè)數(shù)都等于u，C[u]=j。那么最右邊一個(gè)u將被安排在數(shù)組B的第j個(gè)位置，并把C[u]值減一。這樣，下一個(gè)u就會被安排在數(shù)組B的第j-1個(gè)位置。以后，每安排一個(gè)u，C[u]值減一。這樣就保證在安排下一個(gè)u時(shí)，原序列中它右邊的u已在其右邊安排好了。所以計(jì)數(shù)排序是穩(wěn)定排序。利用計(jì)數(shù)排序，設(shè)計(jì)一個(gè)復(fù)雜度為O(n)的算法把取值在0到n2-1內(nèi)的n個(gè)整數(shù)排序。 解：把輸入的每一個(gè)整數(shù)x除以n后會得一個(gè)商a和一個(gè)余數(shù)b，即x=an+b。這里，a和b的值均在0到n-1之間。因此，每一個(gè)整數(shù)x可視為以n為基底的兩位數(shù)ab，其中a為高位數(shù)而b為低位數(shù)。所以，我們可以用基數(shù)排序?qū)澾@n個(gè)數(shù)排序。因每位數(shù)的取值范圍為[0,n-1]，其復(fù)雜度為O(2n)=O(n)。(尋找缺失整數(shù)問題) 數(shù)組A[1..n]含有除了一個(gè)整數(shù)之外的所有從0到n的整數(shù)。我們希望把這一缺失的整數(shù)在O(n)時(shí)間內(nèi)找到。這個(gè)本應(yīng)簡單的問題變得復(fù)雜起來是因?yàn)?這個(gè)問題中每個(gè)數(shù)是以二進(jìn)制存放而我們每次只能訪問一個(gè)比特。也就是說，你不能把一個(gè)整數(shù)一次取出。為簡單起見，你可以假定n=2k-1，而每個(gè)數(shù)是一個(gè)k位的二進(jìn)制數(shù)。解：我們注意到，如果從0到n的整數(shù)都全的話，那么在每一位上0和1的個(gè)數(shù)必定相等，都出現(xiàn)2k-1次。因此，只要在每一位上數(shù)一下是0缺失還是1缺失即可找到所缺失整數(shù)的每一個(gè)比特。但是這樣做需要kn=nlgn次操作，不滿足復(fù)雜度要求。我們進(jìn)一步觀察到，如果我們對最低位作了統(tǒng)計(jì)后發(fā)現(xiàn)比特1缺失的話，那么所有最低位為0的整數(shù)全部包含在數(shù)組A中。這樣的整數(shù)一共有2k-1個(gè)。這些數(shù)字在任何一位都會提供一半的0和一半的1。因此，我們在檢查其他位時(shí)，不用訪問這些數(shù)字也可得知缺失的是0還是1。這樣，當(dāng)我們確定了最低位缺失的比特(比如1)后，下面我們只須檢查最低位與缺失比特(比如1)相同的整數(shù)。這些整數(shù)一共有n-2k-1=2k-1-1個(gè)。這些數(shù)的最低位相同(比如1)，而前面(k-1)位包含了除一個(gè)整數(shù)以外的所有(k-1)位的整數(shù)。這樣一來，我們就面臨了同樣的問題但k的值減1。因此，我們可以設(shè)計(jì)一個(gè)遞歸的算法，其復(fù)雜度滿足遞推關(guān)系T(k)=T(k-1)+O(2k)=O(2k)=O(n)。下面給出該算法的偽碼。我們假定在檢查第k位時(shí)，需要訪問的數(shù)組A中的數(shù)字的序號順序存放在另一數(shù)組B[1..2k-1]中。例如B[1]=3，B[2]=8，那么頭兩個(gè)要訪問的數(shù)為A[3]和A[8]。一開始，B[i]=i，即每個(gè)數(shù)組A中的數(shù)字都會訪問到，但在遞歸過程中，只有數(shù)組A的一個(gè)子序列需要搜索，我們用數(shù)組B來標(biāo)明這個(gè)子序列。我們用A[j,k]表示A[j]的第k位的值。Finding-Missing-Integer(k,B[1..2k-1],M[1..k]) //M[1..k]是缺失的數(shù)，M[k]是最低位ifk=1 //數(shù)組B只含一個(gè)數(shù) then j?B[1] ifA[j,1]=0 thenM[1]?1 //比特1在第1位缺失 elseM[1]?0 //比特0在第1位缺失 endif returnendif //否則做以下操作。u?0v?0 //u和v用于統(tǒng)計(jì)比特0的個(gè)數(shù)和1的個(gè)數(shù)。fori?1to2k-1 j?B[i] ifA[j,k]=0 then u?u+1 //B一分為二，u記錄第k位為0的個(gè)數(shù) C[u]?j //B一分為二，C記錄第k位為0的序號j else v?v+1 //v記錄第k位為1的個(gè)數(shù) D[v]?j //D記錄第k位為1的序號j endifendfor ifu=2k-1-1 //少一個(gè)第k位為0的整數(shù) then M[k]?0 //缺失的整數(shù)第k位為0 B[1..2k-1-1]C[1..2k-1-1] else M[k]?1 B[1..2k-1-1]D[1..2k-1-1] endifFinding-Missing-Integer(k-1，B[1..2k-1-1]，M[1..k-1])End調(diào)用上面遞歸算法的主程序的偽碼如下：Missing-Integer(k,A[1..2k-1]) //n=2k-1fori1to2k-1 B[i]iendforFinding-Missing-Integer(k,B[1..2k-1],M[1..k])returnM[1..k]End(檢查n個(gè)皇后問題) 在一個(gè)n′n的棋盤里如何放置互不攻擊的n個(gè)皇后是個(gè)有名的問題。我們用坐標(biāo)(i,j)(1i,jn）來表示一個(gè)皇后被置于棋盤的第i行和第j列的交叉點(diǎn)上。一個(gè)在坐標(biāo)(i,j)上的皇后和一個(gè)在坐標(biāo)(u,v)上的皇后會互相攻擊當(dāng)且僅當(dāng)它們在同一行，或者同一列，或者同一對角線上，也就是(i=u)或(j=v)或|i-u|=|j-v|。現(xiàn)在假設(shè)有n個(gè)皇后，他們的位置是(a1,b1)，(a2,b2)，…，(an,bn)，請?jiān)O(shè)計(jì)一個(gè)O(n)的算法來檢查他們是否可以相安無事。解：將他們按行號用O(n)時(shí)間的整數(shù)排序后很容易檢查是否有兩個(gè)皇后在同一行。同樣可以在O(n)時(shí)間內(nèi)查出是否有在同一列的皇后。兩個(gè)在坐標(biāo)(i,j)和(u,v)上的皇后如果在對角線上互相攻擊，那么必有|i-u|=|j-v|，也就是i-u=j-v，或者i-u=v–j。這也就是說必有i-j=u–v，或者i+j=u+v。這兩種情況同樣可以用計(jì)數(shù)排序在O(n)時(shí)間內(nèi)檢查。下面是偽碼。Checking-N-Queen(A[1..n],B[1..n]) //第k個(gè)皇后坐標(biāo)為(A[k],B[k])Counting-sort(A[1..n],C[1..n],n) //A[1..n]排序后為C[1]C[2]…C[n]fori=1to(n-1) ifC[i]=C[i+1] thenreturn(Twoqueensareatthesamerow) //兩皇后在同一行 endifendforCounting-sort(B[1..n],C[1..n]，n) //B[1..n]排序后為C[1]C[2]…C[n]fori=1to(n-1) ifC[i]=C[i+1] thenreturn(Twoqueensareatthesamecolumn) //兩皇后在同一列 endifendforD[1..n](A[1..n]-B[1..n]) //使得D[k]=A[k]–B[k]Counting-sort(D[1..n],C[1..n]，n) //D[1..n]排序后為C[1]C[2]…C[n]fori=1to(n-1) ifC[i]=C[i+1] thenreturn(Twoqueensareatthesamediagonal)//兩皇后共45度對角線 endifendforD[1..n](A[1..n]+B[1..n]) //使C[k]=A[k]+B[k]Counting-sort(D[1..n],C[1..n]，n) //D[1..n]排序后為C[1]C[2]…C[n]fori=1to(n-1) ifC[i]=C[i+1] thenreturn(Twoqueensareatthesamediagonal)//兩皇后共135度對角線 endifendforReturn(Thesenqueenswillnotattackeachother) //這n個(gè)皇后不互相攻擊End 第3章的習(xí)題2(b)要求設(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的算法把數(shù)組A[1..n]中出現(xiàn)奇數(shù)次的數(shù)字挑選出來。請證明，任何基于比較的算法，在最壞情況時(shí)，需要至少lg(n!)次比較才能解決這個(gè)問題。證明： 假設(shè)有這樣的一個(gè)基于比較的算法。我們討論在最壞情況時(shí)，它需要作多少次比較。讓我們輸入給這個(gè)算法一個(gè)n個(gè)數(shù)都不同的數(shù)組A[1..n]，那么算法必定會把所有n個(gè)數(shù)字全部挑選出來，因?yàn)槊總€(gè)數(shù)只出現(xiàn)一次。假設(shè)這n個(gè)數(shù)的集合是S={a1，a2，…，an}。設(shè)a1和a2是數(shù)組中最小的兩個(gè)數(shù)，a1<a2。那么，我們可以斷定，這個(gè)算法一定比較了a1和a2。我們可用反證法證明如下。如果這個(gè)算法沒有比較a1和a2，卻判定數(shù)組中所有數(shù)字都出現(xiàn)奇數(shù)次，那么我們可以把數(shù)組A[1..n]中的a2改動一下，我們讓a2等于a1，a2=a1，其余數(shù)不變。然后把這改動后的數(shù)組A[1..n]再讓這個(gè)算法去判定。顯然，這個(gè)改動不會改變?nèi)魏蝺蓚€(gè)數(shù)，ai和aj(1i<jn)的比較結(jié)果，除非i=1，j=2。因?yàn)檫@個(gè)算法先前沒有比較a1和a2，所以算法這一次會重復(fù)所有先前的比較，而察覺不到我們的改動。因此，這個(gè)算法仍然會判定數(shù)組中所有數(shù)字都出現(xiàn)奇數(shù)次。顯然，這就錯(cuò)了，因?yàn)檫@次數(shù)組中，a1和a2是相同的數(shù)字，a1出現(xiàn)了兩次。同理，如果a3是第3小的數(shù)，那么這個(gè)算法必定要比較a2和a3。以此類推，如果這n個(gè)數(shù)可排序?yàn)閍1<a2<…<an，那么這個(gè)算法必定需要比較每兩個(gè)相鄰的數(shù)字。這就意味著，根據(jù)這個(gè)算法的比較結(jié)果，我們可以把這n個(gè)不同數(shù)字排序。因?yàn)榛诒容^的排序至少需要nlgn次比較，所以這個(gè)算法也需要至少nlgn次比較。在一個(gè)有n（=2k+1）個(gè)數(shù)的序列A[1..n]中，有一個(gè)與其他數(shù)都不同的數(shù)x，而其他的數(shù)則成對出現(xiàn)，一共有k對數(shù)字。每對中兩個(gè)數(shù)有相同的值，但不同的對子有不同的數(shù)值。(a) 請?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(nlgn)的基于比較的算法找出這個(gè)與其他數(shù)都不同的數(shù)x。(b) 用決策樹證明，任何基于比較的算法，在最壞情況時(shí)，需要(nlgn)次比較才能找出這個(gè)與其他數(shù)都不同的數(shù)x。解：(a)算法把序列排序后逐個(gè)檢查即可。偽碼如下。Distinct-number(A[1..n])SortthearraysuchthatA[1]≤A[2]≤…≤A[n]foundfalsei1single1 //A[1]還沒有配對whilefound=falseandi<n ii+1 ifA[i]=A[i-1] then ifsingle=i–1 thensingle0 elsereturn(error,thereare3numbersidentical.) endif else ifsingle=i–1 then foundtrue return(A[i–1]isthedistinctnumber) else single=i endif endifendwhilereturn(A[n]isthedistinctnumber)End(b) 證明：因?yàn)楸容^兩個(gè)數(shù)只能告訴你哪個(gè)數(shù)大或相等，所以任何算法在找到數(shù)x后，一定要知道每一個(gè)其他的數(shù)A[i]≠x,是哪個(gè)數(shù)A[j]與A[i]配對。否則不可以確定解是x還是A[i]。也就是說，算法必須知道所有的配對。那么，一共有多少個(gè)可能的解呢？我們可如下計(jì)算：數(shù)x可能出現(xiàn)在A[1..n]中任一個(gè)位置，即有2k+11個(gè)數(shù)x在A[1..n]中位置定下后，第一對數(shù)的位置有2k2個(gè)第二對數(shù)的位置有2k-22……依此類推，第k對數(shù)的位置有22因?yàn)槿我饨粨Q和排列這k個(gè)對子得到同一個(gè)解，所以，不同解的個(gè)數(shù)是：N=2k+112k22k-222k-4 =(2k+1)2k(2k-1)2(2k-2)(2k-3)2(2k-4)(2k-5) =(2k+1)2k!2這就是說，算法對應(yīng)的決策樹至少有(2k+1)2k!2 h≥lgN=lg(2k+1)+lg((2k)!)–k–lgk! =(2klg2k–klgk) =(klg2k) =(nlgn) //因?yàn)閗=(n)。所以，任何算法需要(nlgn)次比較找出A[1..n]中這個(gè)與其他數(shù)都不同的數(shù)x。*我們知道，將數(shù)組A[1..n]合并排序的過程可以用一棵完全二叉樹T來表示。第3章的圖3.2給出了以下的例子。證明這棵樹T的所有葉子在最底下兩層，樹高為h=lgn。為簡單起見，假設(shè)合并一個(gè)有p個(gè)數(shù)字的序列和一個(gè)有q個(gè)數(shù)字的序列需要p+q次比較。證明將數(shù)組A[1..n]合并排序需要的比較次數(shù)等于這棵樹的外路徑總長，即EPL(T)。用(b)的結(jié)果證明，合并排序需要的比較次數(shù)小于等于nlgn-(n-1)。這里，我們假設(shè)合并一個(gè)有p個(gè)數(shù)字的序列和一個(gè)有q個(gè)數(shù)字的序列需要最多p+q-1次比較。證明： (a)我們對數(shù)組A[1..n]的規(guī)模n進(jìn)行歸納證明。歸納基礎(chǔ)： 下面的圖(a)，(b)，(c)，(d)分別是n=1，2，3，4時(shí)合并排序?qū)?yīng)的二叉樹。顯然，每棵樹中的所有葉子在最底下兩層，樹高為h=lgn。 88A[1](a)62A[1]A[2]A[1..2]542A[1]A[2]A[1..2]A[3]A[1..3]42A[1]A[2]A[1..2]A[3]A[1..4]62A[4]A[3..4](b)(c)(d)歸納步驟： 假設(shè)當(dāng)n=1，2，…，k-1(k5)時(shí)，合并排序?qū)?yīng)的二叉樹中的所有葉子在最底下兩層，樹高為h=lgn。我們證明，當(dāng)n=k時(shí)，合并排序?qū)?yīng)的二叉樹中的n個(gè)葉子也都在最底下兩層，樹高為h=lgn。 由合并排序知，當(dāng)n=k時(shí)，合并排序?qū)?yīng)的二叉樹中，根的左右子樹分別有n/2和n/2個(gè)葉子。因?yàn)閚/2<n=k，所以，由歸納假設(shè)，左右子樹中的所有葉子也在最底兩層。又因?yàn)閚/2n/2+1，左右子樹中的結(jié)點(diǎn)個(gè)數(shù)要么相等，要么差一個(gè)。因?yàn)楹喜⑴判驅(qū)?yīng)的二叉樹是完全二叉樹，所以它們的高度相等，h左=h右。（否則至少相差兩個(gè)結(jié)點(diǎn)。）所以，合并排序?qū)?yīng)的二叉樹中所有葉子也在最底下兩層。 由歸納假設(shè)，h左=lgn/2。如果n是偶數(shù)，那么h左=lgn/2=lg(n/2)=lgn-1=lgn-1。如果n是奇數(shù)，那么h左=lgn/2=lg(n+1)/2)=lg(n+1)-1=lg(n+1)-1=lgn-1。所以，我們總有h左=lgn-