習(xí)題參考答案習(xí)題1參考答案一、單項選擇題1~5BACD(C,D)6~10DACAC11~15ACCCB二、指出如下程序段的基本語句，并分析時間復(fù)雜度。1.基本語句是“m=m+1;”，時間復(fù)雜度是O(n2)。2.基本語句是“x++;”，時間復(fù)雜度是O(n2)。3.基本語句是“a[i][j]=0;”，時間復(fù)雜度是O(m×n)。4.基本語句是“y=y+1;”，時間復(fù)雜度是O(n1/2)。5.基本語句是“x++;”，時間復(fù)雜度是O(n3)。6.基本語句是“y=y+i*j;”，時間復(fù)雜度是O(n2)。三、解答下列問題1.（1）屬于集合；（2）屬于線性結(jié)構(gòu)；（3）屬于樹結(jié)構(gòu)；（4）屬于圖結(jié)構(gòu)。2.復(fù)數(shù)的抽象數(shù)據(jù)類型定義如下：ADTComplexDataModelD={e1,e2|e1和e2均是實數(shù)}，R={<e1,e2>|e1和e2分別是實數(shù)的實部和虛部}OperationCreat輸入：兩個實數(shù)x和y功能：構(gòu)造一個復(fù)數(shù)，實部是x虛部是y輸出：復(fù)數(shù)CGetReal輸入：復(fù)數(shù)C功能：取復(fù)數(shù)C的實部輸出：復(fù)數(shù)C的實部值GetImag輸入：復(fù)數(shù)C功能：取復(fù)數(shù)C的虛部輸出：復(fù)數(shù)C的虛部值A(chǔ)dd輸入：兩個復(fù)數(shù)C1和C2功能：將復(fù)數(shù)C1和C2相加輸出：兩個復(fù)數(shù)C1和C2的和Subi輸入：兩個復(fù)數(shù)C1和C2功能：將復(fù)數(shù)C1和C2相減輸出：兩個復(fù)數(shù)C1和C2的差Equal輸入：兩個復(fù)數(shù)C1和C2功能：判斷復(fù)數(shù)C1和C2是否相等輸出：如果復(fù)數(shù)C1等于C2，返回1，否則返回0endADT3.第二種算法的時間性能要好些。第一種算法需要執(zhí)行(n+n-1+…+2+1)=n(n+1)/2次乘法運算、n次加法運算，第二種算法進(jìn)行了優(yōu)化，需要執(zhí)行n次乘法運算和n次加法運算。四、算法設(shè)計題，要求分別用偽代碼和程序語言描述算法，并分析時間復(fù)雜度。1.設(shè)變量m和n分別表示真分?jǐn)?shù)的分母和分子，首先采用歐幾里得算法求m和n的最大公約數(shù)，再將m和n同時除以這個最大公約數(shù)，時間復(fù)雜度為O(logmin(m,n))。算法用偽代碼描述如下，很容易將偽代碼轉(zhuǎn)換為程序語言描述。1.1.tempm=m;tempn=n;2.r=m%n;3.重復(fù)下述操作直到r等于03.1m=n;n=r;3.2r=m%n;4.輸出tempm/n和tempn/n;2.設(shè)字符數(shù)組str[n]存儲字符串，變量i和j分別指向字符串的首部和尾部，i從前向后，j從后向前，依次取出字符進(jìn)行比較，直到i和j相遇，如果在匹配過程中對應(yīng)字符不相等，則說明不是回文串。算法只有一層循環(huán)，時間復(fù)雜度T(n)=O(n)。假設(shè)字符串長度為n，算法用偽代碼描述如下，很容易將偽代碼轉(zhuǎn)換為程序語言描述。1.1.初始化：i=0;j=n-1;2.重復(fù)執(zhí)行下述操作，直到i等于j2.1如果str[i]等于str[j]，則i++;j--;2.2否則str不是回文串，返回0;3.str是回文串，返回1;3.提示：設(shè)變量i和j從數(shù)組的兩端向中間進(jìn)行比較，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i]與A[j]交換。算法將數(shù)組掃描一遍，時間復(fù)雜度為Ｏ(n)。4.提示：從頭開始掃描數(shù)組，對于值等于x的元素，用變量k記載出現(xiàn)的次數(shù)；對于值不等于x的元素，將其前移k個位置。該算法只掃描了一遍數(shù)組，因此時間復(fù)雜度為O(n)。算法只設(shè)置了兩個簡單變量，因此空間復(fù)雜度為O(1)。5.提示：設(shè)數(shù)組r[n]存儲R、G和B三種元素，設(shè)三個變量i、j、k，其中i之前的元素（不包括r[i]）全部為R，k之后的元素（不包括r[k]）全部為B，i和j之間的元素（不包括r[j]）全部為G，j指向當(dāng)前正在處理的元素。首先將變量i初始化為0，k初始化為n-1，j初始化為0。然后j從前向后掃描，在掃描過程中根據(jù)r[j]的顏色，將其交換到序列的前面或后面，直到j(luò)等于k。由于下標(biāo)j和k整體將數(shù)組掃描一遍，因此時間復(fù)雜度為O(n)。五、算法設(shè)計題，分析最好、最壞和平均情況下的時間復(fù)雜度。1.設(shè)變量max和min分別存儲最大值和最小值，算法如下：voidvoidMaxMin(intr[],intn,int&max,int&min){max=r[0];min=r[0];for(inti=1;i<n;i++){if(r[i]>max)max=r[i];elseif(r[i]<min)min=r[i];}}最好情況下，數(shù)組r[n]遞增有序，元素的比較次數(shù)是n-1次；最壞情況下，數(shù)組r[n]遞減有序，元素的比較次數(shù)是2(n-1)次；平均情況下，n-1次循環(huán)中，第一個if語句執(zhí)行n-1次，elseif語句執(zhí)行(n-1)/2次，元素的比較次數(shù)是3(n-1)/2。綜上，最好、最壞、平均情況下的時間復(fù)雜度均是O(n)。2.設(shè)變量max和nmax分別存儲最大值和次最大值，首先將數(shù)組的前兩個元素進(jìn)行比較初始化max和nmax，然后對數(shù)組掃描一遍，對每一個數(shù)組元素的取值確定是否更新max和nmax。算法分析同第1題。習(xí)題2參考答案一、單項選擇題1~5ADA(B,C)D6~10CBDBA11~15ADBBC16~20CBBDA二、解答下列問題1.順序表的優(yōu)缺點略。（1）選用順序存儲結(jié)構(gòu)。從時間性能角度考慮，順序表可以進(jìn)行隨機存取，單鏈表只能進(jìn)行順序存取。由于很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲結(jié)構(gòu)。（2）選用鏈接存儲結(jié)構(gòu)。從空間性能角度考慮，鏈表容易實現(xiàn)容量的擴充，適合線性表的長度動態(tài)發(fā)生變化。順序表不僅容量難以擴充，多個順序表并存還會造成存儲空間的碎片。2.鏈表為空的判斷條件分別是：first->next=NULL，first=NULL，示意圖略。3.加上頭結(jié)點之后，所有元素結(jié)點的存儲地址都存放在其前驅(qū)結(jié)點的指針域中，而且無論單鏈表是否為空，頭指針始終指向頭結(jié)點，統(tǒng)一了空表和非空表的處理。在帶頭結(jié)點的單鏈表中執(zhí)行插入和刪除等操作，在表頭與在其他位置的操作語句是一致的，不用特殊處理。如果單鏈表不帶頭結(jié)點，則需要特殊處理在表頭的情況。4.不能顛倒這兩條語句。如果先執(zhí)行p->next=s，則斷開了p->next和后繼結(jié)點b的鏈接關(guān)系，沿著p->next將無法獲得結(jié)點p的后繼結(jié)點b。5.在各種存儲結(jié)構(gòu)下，線性表基本操作的時間復(fù)雜度如下表所示。（1）（2）（3）（4）（5）（6）①O(1)O(n)O(n)O(1)O(n)O(1)②O(n)O(n)O(1)O(n)O(1)O(n)③O(n)O(n)O(1)O(n)O(1)O(n)④O(n)O(n)O(1)O(1)O(1)O(n)⑤O(n)O(n)O(1)O(n)O(1)O(n)⑥O(n)O(n)O(1)O(1)O(1)O(1)6.由于要求根據(jù)下標(biāo)隨機存取每個元素，所以，必須采用數(shù)組存儲。但是數(shù)組中的元素要求具有相同的數(shù)據(jù)類型，因此，可以使用指針數(shù)組ptr[MaxSize]（即間接尋址方法），ptr[i]指向線性表的第i+1（0≤i≤n-1）個元素。7.所需存儲空間為ED。8.如果單鏈表帶頭結(jié)點，則共需要(n+1)(P+E)個存儲單元。9.（1）i=1n+1pin-i+1三、算法設(shè)計題1.提示：可以從有序表的尾部開始依次取元素與x進(jìn)行比較，若大于x，將該元素后移一個位置，再取前一個元素重復(fù)上述操作；否則，找到插入位置。2.提示：不失一般性，假設(shè)a≤b≤c，由D=|a-b|+|b-c|+|c-a|可知，決定D大小的關(guān)鍵是|c-a|的值，對于一個確定的c值，問題的關(guān)鍵是找到最接近c的a值。設(shè)dist=|S1i-S2j|+|S2j-S3k|+|S3k-S1i|。3.提示：設(shè)工作指針p指向當(dāng)前結(jié)點，設(shè)指針q指向結(jié)點p的后繼（如果后繼結(jié)點存在），在掃描的過程中判斷結(jié)點p的值是否小于結(jié)點q的值。4.提示：設(shè)工作指針p指向當(dāng)前結(jié)點，若結(jié)點p的元素值與后繼結(jié)點的元素值不相等，則后移指針p；否則刪除該后繼結(jié)點。5.提示：利用單鏈表的有序性，在單鏈表中查找第一個大于mink的結(jié)點和第一個小于maxk的結(jié)點，將二者間的所有結(jié)點刪除。6.提示：通過指針s找到其前驅(qū)結(jié)點q以及q的前驅(qū)結(jié)點p，然后將結(jié)點q刪除。由于循環(huán)單鏈表的長度大于1，因此結(jié)點q一定存在。7.提示：設(shè)工作指針p指向單鏈表的開始結(jié)點，在遍歷過程中復(fù)制結(jié)點p并插入到結(jié)點p的后面。8.提示：設(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，從鏈表的兩端向中間進(jìn)行元素比較。9.提示：用尾插法，設(shè)指針p和q分別為表la和lb的工作指針，指針r指向結(jié)果鏈表當(dāng)前的尾結(jié)點，將p->data和q->data的較小結(jié)點插在結(jié)點r的后面。10.提示：首先構(gòu)造一個空的循環(huán)單鏈表L2，然后設(shè)工作指針p遍歷單鏈表L1，對于奇數(shù)號結(jié)點保留在L1中，對于偶數(shù)號結(jié)點用頭插法插入L2中。習(xí)題3參考答案一、單項選擇題1~5CDCBC6~10DDBBA11~15CDBCD16~20DCCDB二、解答下列問題1.棧頂元素為6，棧底元素為1，執(zhí)行過程略。2.隊頭元素為5，隊尾元素為9，執(zhí)行過程略。3.（1）不能，第2個出棧元素不可能是1。（2）可以，操作串是IOIIOOIO。4.在入棧出棧操作序列的任一位置，入棧次數(shù)（即“I”的個數(shù)）都必須大于等于出棧次數(shù)（即“O”的個數(shù)），否則在形式上視作非法序列。由于棧的初態(tài)和終態(tài)都為空，則整個序列的入棧次數(shù)必須等于出棧次數(shù)，否則在形式上視為非法序列。5.當(dāng)前rear和front的值分別為0和3，則隊列中有3個元素。刪除一個元素，front的值為4，增加兩個元素，rear的值為2。示意圖略。6.設(shè)變量front存儲隊頭元素的前一個位置，變量count存儲隊列的元素個數(shù)，可以通過隊頭位置和隊列長度計算出隊尾元素的位置，存儲結(jié)構(gòu)定義如下：#defineQueueSize100/*定義數(shù)組的最大長度*/typedefintDataType;/*定義隊列元素的數(shù)據(jù)類型，假設(shè)為int型*/typedefstruct{DataTypedata[QueueSize];/*存放隊列元素的數(shù)組*/intfront,count;/*隊頭位置和隊列長度*/}CirQueue;7.在隊列中插入元素時，用棧S1存放已經(jīng)入隊的元素，即通過向棧S1執(zhí)行入棧操作來實現(xiàn)。在隊列中刪除元素時，將棧S1的元素全部送入到棧S2中，再從棧S2中刪除棧頂元素，最后將棧S2的元素全部送入到棧S1中。判斷隊空的條件是棧S1和S2同時為空。8.設(shè)棧OPND存儲運算對象，棧OPTR存儲優(yōu)先級較低的運算符，在計算表達(dá)式的過程中，棧OPND和OPTR的變化過程如下表所示。步驟棧OPND棧OPTR算術(shù)表達(dá)式（下劃線為當(dāng)前掃描的字符）初始#A-B*C/D#1A#A-B*C/D#2A#--B*C/D#3AB#-B*C/D#4AB#-**C/D#5ABC#-*C/D#6AT1（T1=B*C）#-//D#7AT1D#-/D#8AT2（T2=T1/D）#-#9T3（T3=A-T2）##9.設(shè)二元組（data,count）存儲元素值及該值的元素個數(shù)。例如，數(shù)組r[]={1,1,1,5,5,3,3,3,3,3,3,3,3,9}，對應(yīng)的壓縮存儲為B[]={{1,3},{5,2},{3,8},{9,1}}。顯然，值相同的元素越多，采用這種壓縮存儲方法越節(jié)省存儲空間。10.注意到數(shù)組B的下標(biāo)從0開始，則k=i2+i+j-n+1。11.假設(shè)矩陣B的行列下標(biāo)均從1開始，注意到數(shù)組A的下標(biāo)從0開始，元素b15,16在數(shù)組A中的存儲位置（即下標(biāo)）是70。12.存儲示意圖略。三、算法設(shè)計題1.根據(jù)棧和隊列的操作特性，算法的操作步驟如下：（1）將所有元素依次出棧并入隊；（2）將隊列元素依次出隊，將偶數(shù)號元素入隊，將奇數(shù)號元素入棧；（3）將奇數(shù)號元素依次出棧并入隊；（4）將偶數(shù)號元素依次出隊并入棧；（5）將偶數(shù)號元素依次出棧并入隊；（6）將所有元素依次出隊并入棧。2.提示：入隊操作在循環(huán)單鏈表的尾部進(jìn)行，出隊操作在循環(huán)單鏈表的頭部進(jìn)行，由于循環(huán)單鏈表不帶頭結(jié)點，需要處理空表的特殊情況。3.提示：假設(shè)采用順序棧作為存儲轉(zhuǎn)換后結(jié)果，將每一次計算得到的余數(shù)存儲到順序棧中，再逆序輸出。4.提示：設(shè)字符數(shù)組A存儲算術(shù)表達(dá)式，對于左括號，執(zhí)行入棧操作，對于右括號，如果棧頂元素是匹配的左括號，則執(zhí)行出棧操作，否則匹配失敗，結(jié)束掃描。5.提示：當(dāng)有元素入隊時，隊列非空，將flag置1。當(dāng)有元素出隊時，隊列不滿，將flag置0。6.提示：設(shè)數(shù)組S[n]表示順序棧，設(shè)數(shù)組in[n]存儲輸入的字符序列，數(shù)組out[n]表示要判斷的出棧序列，設(shè)變量i和j分別指示正在處理的入棧和出棧字符。7.提示：設(shè)left指向隊列左端第一個元素（可以看成是左端的隊頭）的前一個位置，right指向右端第一個元素（可以看成是右端的隊頭）的位置。8.提示：設(shè)變量count累計鞍點個數(shù)，變量k記載某行最小值的列下標(biāo)。先計算每一行最小值，再考查該值是否是k列的最大值。時間復(fù)雜度為Ｏ(n2+mn)。9.提示：要求時間復(fù)雜度為O(m+n)，因此不能采用常規(guī)的二層循環(huán)進(jìn)行查找?？梢詮挠疑辖情_始，將元素A[i][j]與x進(jìn)行比較，有以下三種情況：（1）A[i][j]>x，向左繼續(xù)查找；（2）A[i][j]<x，向下繼續(xù)查找；（3）A[i][j]=x，查找成功。如果下標(biāo)超出矩陣范圍，則查找失敗。時間復(fù)雜度是O(m+n)。習(xí)題4參考答案一、單項選擇題1~5CBBBB6~10DDBDB11~15BDAAA16~20(A,D)BDDC21~25CBCDC二、解答下列問題1.（1）樹的根結(jié)點是A；（2）樹的葉子結(jié)點是B、E、G、D；（3）結(jié)點C的雙親結(jié)點是A，結(jié)點C的孩子結(jié)點是E和F；（4）樹的深度是4，結(jié)點C位于第2層；（5）樹的度是2，結(jié)點C的度是2。2.略。abefcdabefcdgh圖A-1對應(yīng)的二叉樹4.lchild和rchild是用數(shù)組下標(biāo)模擬指向該結(jié)點左右孩子的指針，因此是二叉鏈表的靜態(tài)鏈表形式，對應(yīng)的二叉樹如圖A-1所示。5.因為在滿二叉樹中沒有度為1的結(jié)點，所以有：n=n0+n2設(shè)B為樹的分枝數(shù)，則有：n=B+1所以，B=n0+n2-1再由二叉樹性質(zhì)：n0=n2+1，代入上式有：B=n0+n0-1-1=2(n0-1)6.提示：設(shè)二叉樹的前序遍歷序列為a1a2a3…an，中序遍歷序列為b1b2b3…bn，采用歸納法證明。7.設(shè)該樹的結(jié)點數(shù)為n，則有：n=n0+n1+n2+……+nm又：n=分枝數(shù)+1=0×n0+1×n1+2×n2+……+m×nm+1由上述兩式可得：n0=n2+2n3+……+(m-1)nm+18.共有5種二叉樹的前序遍歷序列為ABC，如圖A-2所示。AABC圖A-2前序序列為ABC的二叉樹ABCABCABCABC9.提示：首先由前序序列確定二叉樹的根結(jié)點，再到中序序列確定左右子樹的結(jié)點；分別確定左右子樹的根結(jié)點；遞歸確定每一個結(jié)點的位置。10.提示：首先由后序序列確定二叉樹的根結(jié)點，再到中序序列確定左右子樹的結(jié)點；分別確定左右子樹的根結(jié)點；遞歸確定每一個結(jié)點的位置。11.首先由層序序列確定二叉樹的根結(jié)點，再到中序序列確定左右子樹的結(jié)點；由于根結(jié)點的左右子樹均不空，則層序序列的第2、3個結(jié)點分別是根結(jié)點的左右孩子；遞歸確定每一個結(jié)點的位置。12.對于二叉樹結(jié)構(gòu)，雙親和右孩子在對應(yīng)樹（或森林）中是兄弟關(guān)系，據(jù)此在二叉樹中增加連線；去掉所有雙親和右孩子的連線，再進(jìn)行層次調(diào)整，轉(zhuǎn)換為三棵樹組成的森林。對于樹結(jié)構(gòu)，兄弟結(jié)點在對應(yīng)二叉樹中是雙親和右孩子的關(guān)系，據(jù)此在樹中增加連線；對每個雙親結(jié)點，只保留與長子的關(guān)系，去掉與其他孩子的連線，再進(jìn)行層次調(diào)整。13.森林的前序序列和后序序列對應(yīng)二叉樹的前序序列和中序序列，據(jù)此構(gòu)造二叉樹，再將二叉樹轉(zhuǎn)換為森林，結(jié)果如圖A-3所示。AABFGDKNLHEIJMOC圖A-3由前序序列和后序序列確定的森林14.提示：設(shè)權(quán)值集合W={31,16,10,8,11,20,4}，構(gòu)造哈夫曼樹，得到哈夫曼編碼為：{a:01,b:001,c:100,d:0001,e:101,f:11,g:0000}（編碼不唯一）。7個字符的等長編碼至少需要3位二進(jìn)制數(shù)。假設(shè)電文的總長度為100，采用等長編碼需要300位二進(jìn)制數(shù)，采用哈夫曼編碼需要(31×2+16×3+10×3+8×4+11×3+20×2+4×4)=261位二進(jìn)制數(shù)，壓縮比是(300-261)/300=13%。15.提示：合并長度為m和n的兩個有序表最多需要比較O(m+n)次。將表A和B合并成表C，如果表C還需要與另一個表合并，則表A和B的元素需要再做一次比較，因此，應(yīng)該先合并表長較小的兩個有序表。采用哈夫曼算法，將表的長度作為權(quán)值構(gòu)造哈夫曼樹。以數(shù)列{10,30,40,50,50,60,90}構(gòu)造的哈夫曼樹，這棵哈夫曼樹的構(gòu)造過程決定了合并的順序。16.將哈夫曼算法進(jìn)行擴展，構(gòu)造擴展的哈夫曼樹，如圖A-4所示。電文編碼總長度為11×2+23×2+2×4+2×4+3×3+5×3+7×2+8×2+9×2+35×1=191。464624105J:35E:7A:8G:9H:11F:2312C:34B:5D:2I:2圖A-4度為3的哈夫曼樹三、算法設(shè)計1.提示：設(shè)數(shù)組T[n]作為二叉樹的順序存儲，對二叉鏈表進(jìn)行前序遍歷，在訪問結(jié)點時執(zhí)行下述操作：將結(jié)點的數(shù)據(jù)信息存儲到T[i]；遞歸轉(zhuǎn)換左子樹；遞歸轉(zhuǎn)換左子樹。簡單起見，將數(shù)組T[n]設(shè)為全局變量。2.提示：可以將遍歷算法的訪問改為計數(shù)，為此設(shè)累加器sum為全局變量，在訪問結(jié)點時將sum增1，每個結(jié)點累加一次即完成結(jié)點個數(shù)的計數(shù)。3.提示：在前序遍歷過程中的訪問操作改為條件輸出。4.提示：當(dāng)二叉樹為空時，深度為0；若二叉樹不為空，深度是根結(jié)點左右子樹深度的最大值加1，而左右子樹深度的求解可以通過遞歸調(diào)用來完成。5.提示：設(shè)棧S保存已經(jīng)訪問的結(jié)點，模擬遞歸遍歷的執(zhí)行過程。假設(shè)二叉樹的元素類型為char，存儲在數(shù)組T[n]中。6.提示：利用完全二叉樹雙親結(jié)點與孩子結(jié)點編號間的關(guān)系，分別求下標(biāo)為i和j的結(jié)點的雙親、雙親的雙親，……，直至找到最近的公共祖先。7.提示：對二叉鏈表遍歷的過程中查找結(jié)點x并記載其雙親，為此，需要設(shè)全局變量par表示正在訪問結(jié)點的雙親。8.提示：對二叉鏈表遍歷的過程中查找結(jié)點x并記載其雙親par，然后將結(jié)點par中指向結(jié)點x的指針置空。9.提示：在對二叉鏈表進(jìn)行遍歷的過程中查找值等于x的結(jié)點，然后由此結(jié)點的最左孩子域firstchild找到結(jié)點x的第一個孩子，再沿右兄弟域rightsib找到結(jié)點x的第i個孩子。10.提示：設(shè)變量leaf存儲葉子結(jié)點個數(shù)，level存儲層數(shù)。對二叉樹進(jìn)行層序遍歷的過程中，為了對指定層的結(jié)點進(jìn)行處理，設(shè)變量last記載當(dāng)前訪問結(jié)點所在層次。根據(jù)層序遍歷的特點，將last指向該層最右結(jié)點，當(dāng)last結(jié)點處理完則進(jìn)入下一層。11.提示：對完全二叉樹按照層序遍歷應(yīng)該滿足：（1）如果某結(jié)點沒有左孩子，則一定沒有右孩子；（2）如果某結(jié)點無右孩子，則其所有后繼結(jié)點一定無孩子。如果有一個結(jié)點不滿足上述任意一條，則該二叉樹就一定不是完全二叉樹。設(shè)標(biāo)志變量flag表示已掃描過的結(jié)點是否有左孩子或右孩子。習(xí)題5參考答案一、單項選擇題1~5BACBA6~10DDBCC11~15DBDAA16~20ACACA21~25D(C,C,F)DAB二、解答下列問題1.鄰接矩陣共需要4n2+2n個字節(jié)。鄰接表共需要6n+20e個字節(jié)。2.如果采用鄰接矩陣存儲，只需判斷元素edge[i][j]（或edge[j][i]）是否等于1，時間復(fù)雜度是O(1)。如果采用鄰接表存儲，需要判斷第i個邊表中是否含有結(jié)點j，這需要遍歷第i個邊表，時間復(fù)雜度是O(e/n)。3.如果采用鄰接矩陣存儲，需要將第i行和第i列的所有元素置0，時間復(fù)雜度是O(n)。如果采用鄰接表存儲，首先需要刪除該頂點出邊表中的所有結(jié)點，然后遍歷所有邊表，刪除邊表中鄰接點域為該頂點的所有結(jié)點，時間復(fù)雜度是O(n+e)。4.用反證法證明。設(shè)v1,v2,…,vk是生成樹的一條最長路徑，其中，v1為起點，vk為終點。若vk的度為2，取vk的另一個鄰接點v，由于生成樹中無回路，所以，v在最長路徑上，顯然v1,v2,…,vk,v的路徑最長，與假設(shè)矛盾。同理可證起點v1的度不能大于1，只能為1。所以生成樹中最長路徑的起點和終點的度均為1。5.任意n個結(jié)點的有向無環(huán)圖都可以得到一個拓?fù)湫蛄?。設(shè)拓?fù)湫蛄袨関0v1v2…vn-1，下面證明此時的鄰接矩陣為上三角矩陣。證明采用反證法。假設(shè)此時的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i＞j），使得edge[i][j]不等于零，即圖中存在從vi到vj的有向邊。由拓?fù)湫蛄械亩x可知，在任意拓?fù)湫蛄兄?，頂點vi的位置一定在vj之前，而在拓?fù)湫蛄衯0v1v2…vn-1中，由于i＞j，即頂點vi的位置在vj之后，導(dǎo)致矛盾。因此命題正確。6.略。7.深度優(yōu)先遍歷序列為：v1v2v3v5v4v6，廣度優(yōu)先遍歷序列為：v1v2v4v6v3v5。8.深度優(yōu)先遍歷序列為：123456，對應(yīng)的生成樹如圖A-5所示。廣度優(yōu)先遍歷序列為：124356，對應(yīng)的生成樹如圖A-6所示。1123645圖A-5深度優(yōu)先生成樹圖A-6廣度優(yōu)先生成樹123645669.Prim算法依次加入最小生成樹的邊是(a,c)3、(a,b)6、(b,d)1、(b,f)5、(f,e)2。Kruskal算法依次加入最小生成樹的邊是(b,d)1、(e,f)2、(a,c)3、(b,f)5、(a,b)6。由于不是基于圖的存儲結(jié)構(gòu)執(zhí)行算法，因此答案不唯一。10.采用Dijkstra算法求解最短路徑的過程如下表所示。數(shù)組元素集合Sv2v3v4v5v6v7dist[2]path[2]dist[3]path[3]dist[4]path[4]dist[5]path[5]dist[6]path[6]dist[7]path[7]{v1}∞""∞""∞""11v1v5∞""7v1v7{v1v7}22v1v7v2∞""13v1v7v411v1v5∞""{v1v7v5}22v1v7v2∞""13v1v7v421v1v5v6{v1v7v5v4}22v1v7v2∞""16v1v7v4v6{v1v7v5v4v6}22v1v7v225v1v7v4v6v3{v1v7v5v4v6v2}25v1v7v4v6v311.拓?fù)湫蛄屑词强尚械墓ば蛐蛄惺牵?52364、512364、152634、512634。12.各事件（頂點）的最早開始時間和最遲開始時間分別是v1(0,0)，v2(6,0)，v3(4,5)，v4(13,13)，v5(22,22)，v6(24,24)。各活動（邊）的最早開始時間和最遲開始時間分別是a1(0,0)，a2(0,1)，a3(4,5)，a4(6,6)，a5(4,13)，a6(13,13)，a7(13,13)，a8(22,22)。關(guān)鍵活動是a1、a4、a6、a7和a8，構(gòu)成兩條關(guān)鍵路徑。13.提示：用Prim算法或Kruskal算法求最小生成樹時每次選取權(quán)值最大的邊，求得最大生成樹，利潤（即生成樹的代價）是17。CADBE465436圖A-7第14題的解答14.該方法求得的路徑不一定是最短路徑。例如，對于圖A-7所示的帶權(quán)圖，如果按照上述方法，從頂點CADBE465436圖A-7第14題的解答15.提示：該問題即是確定圖的中心點，該中心點與其他各頂點之間的往返路徑長度之和為最小。求解步驟如下：（1）為有向圖建立鄰接矩陣；（2）采用Floyd算法求出任意兩個頂點間的最短路徑長度；（3）依次計算每個頂點與其他各頂點的往返代價之和；（4）計算往返代價之和最小的頂點即是圖的中心點?？梢钥闯觯t(yī)院建在結(jié)點D時總的往返代價最小。三、算法設(shè)計題1.提示：在鄰接矩陣上查找值不為零的元素，在鄰接表的邊表中插入相應(yīng)的結(jié)點。2.提示：在鄰接表上依次取每個邊表中的結(jié)點，將鄰接矩陣中對應(yīng)位置的元素值置為1。3.提示：掃描所有出邊表，統(tǒng)計出邊表中頂點i出現(xiàn)的次數(shù)。設(shè)累加器數(shù)組indegree[n]，數(shù)組下標(biāo)為頂點的編號。4.提示：設(shè)變量count累加出度為零的頂點個數(shù)，掃描鄰接矩陣的每一行，如果矩陣元素不等于0，則提前跳出循環(huán)。5.提示：拓?fù)渑判蚩梢耘袛嘤邢驁D是否有回路。設(shè)數(shù)組indegree[n]存放各頂點的入度，并用值為0的數(shù)組元素作為棧。6.提示：假設(shè)數(shù)組visited[n]已初始化為0，從頂點i出發(fā)進(jìn)行深度優(yōu)先遍歷，如果可以訪問到頂點j，說明由頂點vi到頂點vj存在路徑。習(xí)題6參考答案一、單項選擇題1~5BCCDD6~10A(A,D)ACC11~15CBBDA16~20BACCD21~25DACBC二、解答下列問題1.（1）順序查找判定樹是一棵斜樹。（2）在成功情況下的平均查找長度：i=1nci2.（1）折半查找判定樹是一棵二叉搜索樹。（2）在成功情況下的平均查找長度：i=1nc3.長度為2k-1的有序表對應(yīng)判定樹為深度為k的滿二叉樹，在查找成功的情況下，最多需要比較k次。該有序表對應(yīng)的判定樹在k+1層有2k個外結(jié)點對應(yīng)查找失敗的情況，查找失敗的比較次數(shù)是k次。4.按照集合的元素順序構(gòu)造二叉搜索樹，查找成功的平均查找長度=1×1+2×2+3×2+4×3=23/8。15102010152010201520151020101520102015201510(a)形狀1(b)形狀2(c)形狀3(d)形狀4(e)形狀5圖A-8可能構(gòu)成的二叉搜索樹2010156.略?！摹摹摹?49925∧12∧37∧26∧15∧52∧43∧7082∧11∧0∧∧∧∧849925∧12∧37∧26∧15∧52∧43∧7082∧11∧01234567891011圖A-9構(gòu)造的開散列表8.提示：T1T3是否相同取決于在刪除v后，平衡二叉樹是否失衡。（1）正確。（2）和（3）錯。9.設(shè)含有Fk個結(jié)點的平衡二叉樹的最大深度為k，則Fk=Fk-2+Fk-1+1。顯然，F(xiàn)1=1，F(xiàn)2=2。含有12個結(jié)點的平衡二叉樹的最大深度為5。10.略。11.構(gòu)造的開散列表如圖A-9所示，平均查找長度為：ASL=(8×1+4×2)/12=16/12=4/3。12.構(gòu)造的閉散列表和關(guān)鍵碼比較次數(shù)如圖A-10所示。查找成功的平均比較次數(shù)為：(1×7+2×2+5×1)/10=1.6。散列地址01234567891011121314關(guān)鍵碼53177046646187891225比較次數(shù)1111512112圖圖A-10構(gòu)造的閉散列表13.根據(jù)裝填因子的定義求出表長為：9/0.6=15。設(shè)散列函數(shù)為：H(key)=keymod13，構(gòu)造的散列表如圖A-11所示。圖A-11裝填因子為0.6的散列表14.略。15.略。16.next[7]={-1,0,1,0,1,2,3}。17.KMP算法的匹配過程執(zhí)行4趟。第1趟匹配：i=4,j=4失敗，i不動，j回溯到next[4]，即j=1。第2趟匹配：i=4,j=1失敗，i不動，j回溯到next[3]，即j=0。第3趟匹配：i=4,j=0失敗。第5趟匹配：i=10,j=5，T中全部字符都比較完畢，匹配成功。18.用拉鏈法構(gòu)造的開散列表不會產(chǎn)生堆積，因而平均查找長度較短；拉鏈法屬于動態(tài)存儲分配，更適合處理無法確定表長的情況；在拉鏈法構(gòu)造的開散列表上執(zhí)行刪除操作不用考慮截斷查找路徑問題，因而更加易于實現(xiàn)；拉鏈法構(gòu)造的開散列表可以存儲的記錄個數(shù)不受散列表長度的限制。三、算法設(shè)計題1.提示：將哨兵存儲在r[0]，從下標(biāo)n開始查找，退出循環(huán)后不用進(jìn)行判斷。2.提示：采用折半查找技術(shù)分別查找元素x和y，再順序輸出x和y之間的所有元素。3.提示：設(shè)計遞歸算法，從根結(jié)點root開始查找結(jié)點p，有以下三種情況：（1）結(jié)點p是根結(jié)點：深度為1；（2）p->data<root->data：深度加1，然后到左子樹上查找；（3）p->data>root->data：深度加1，然后到右子樹上查找。4.提示：根據(jù)二叉搜索樹的特性，比較結(jié)點p、q和根結(jié)點root的值，有如下情況：（1）結(jié)點p為根結(jié)點：結(jié)點p（即root）為公共祖先；（2）結(jié)點q為根結(jié)點：結(jié)點q（即root）為公共祖先；（3）p->data<root->data且root->data<q->data：結(jié)點root為公共祖先；（4）p->data<root->data且q->data<root->data：到左子樹查找；（4）p->data>root->data且q->data>root->data：到右子樹查找。5.提示：二叉查找樹的中序遍歷序列是一個遞增序列，設(shè)全局變量predata保存當(dāng)前結(jié)點的前驅(qū)結(jié)點元素值。6.提示：在二叉樹進(jìn)行后序遍歷過程中求各結(jié)點的平衡因子。7.提示：設(shè)散列表為ht[m]，刪除值為x的記錄，假設(shè)查找集合為整數(shù)，在閉散列表中刪除值為x的關(guān)鍵碼時，用一個特殊值（SpecVal）代替。8.提示：在工作指針后移的過程中判斷p的后繼結(jié)點的數(shù)據(jù)域是否等于待刪元素，注意要處理表頭的特殊情況。9.提示：對于next[j]，從長度為j-1的子串開始進(jìn)行比較，直至找到相等的真前綴和真后綴，如果查找失敗，則next[j]=0。習(xí)題7參考答案一、單項選擇題1~5CCCBB6~10AACCA11~15DDBCD16~20CCBBD二、解答下列問題1.略。2.由于是按兩個關(guān)鍵碼進(jìn)行排序，越重要的關(guān)鍵碼越在后面進(jìn)行排序。由于堆排序是不穩(wěn)定的，先采用堆排序按關(guān)鍵碼k2進(jìn)行升序排列，再采用直接插入排序按關(guān)鍵碼k1進(jìn)行升序排列。3.最好情況：41326578。注意到，每次劃分進(jìn)行的關(guān)鍵碼比較次數(shù)為序列長度減1，因此，可通過判定樹計算比較次數(shù)。如圖A-12所示，結(jié)點的值表示子序列中所含記錄個數(shù)，比較次數(shù)為：7+2+3+1=13。最壞情況：12345678，比較次數(shù)為：7+…+2+1=28。5445722338609683圖A-13遞歸調(diào)用樹1545445722338609683圖A-13遞歸調(diào)用A-12最好情況的判定樹5.提示：二叉搜索樹是結(jié)點之間滿足一定次序關(guān)系的二叉樹，堆是結(jié)點之間滿足一定次序關(guān)系的完全二叉樹。6.采用基數(shù)排序。因為英文單詞都很短，可以將每個位置的字母看作一個關(guān)鍵碼（不足可以在前面補空格），設(shè)n個英文單詞中最長的單詞有m個字母，采用基數(shù)排序的時間復(fù)雜度為O(m(n+26m))，由于m<<n，則O(m(n+26m))=O(n)。基于比較的排序方法，平均時間復(fù)雜