【正文】 叉樹中刪除以值x為根結(jié)點的子樹?！窘獯稹繉Χ骀湵磉M行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親?！窘獯稹恳氲玫胶笮虻哪嫘?，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點，再遍歷根結(jié)點的右子樹，最后遍歷根結(jié)點的左子樹。具體算法如下：⑶ 設(shè)計算法求二叉樹的深度。為此，將前序遍歷算法中的訪問操作改為條件打印即可?！窘獯稹勘舅惴ǖ囊笈c前序遍歷算法既有相同之處，又有不同之處。所以可將遍歷算法中的“訪問”操作改為“計數(shù)操作”，將結(jié)點的數(shù)目累加到一個全局變量中，每個結(jié)點累加一次即完成了結(jié)點個數(shù)的求解。10．算法設(shè)計⑴ 設(shè)計算法求二叉樹的結(jié)點個數(shù)。其帶權(quán)路徑長度=25+15+34+53+92+43+43+72=98，所以，該字符串的編碼長度至少為98位。樹的帶權(quán)路徑長度為：WPL=24+34+53+73+83+92+112=1209．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用[0，1]進行前綴編碼，問該字符串的編碼至少有多少位。8．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。6．已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？ 【解答】設(shè)該樹的總結(jié)點數(shù)為n，則n=n0+n1+n2+……+nm 又：n=分枝數(shù)+1=0n0+1n1+2n2+……+mnm+1由上述兩式可得：n0= n2+2n3+……+(m1)nm+17．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(jié)點，所以，a1= b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n=k時，前序遍歷序列a1a2a3… ak和中序遍歷序列b1b2b3… bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3… akak+1和中序遍歷序列b1b2b3… bk bk+1可唯一確定一棵二叉樹。【解答】證明采用歸納法。4．證明：對任一滿二叉樹，其分枝數(shù)B＝2(n01) ?！窘獯稹垮e。因為根結(jié)點無兄弟結(jié)點。⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。【解答】錯。由前序遍歷的操作定義可知。⑵ 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。【解答】錯。⑽ 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。A 前序 B 中序 C 后序 D 層序【解答】A，B⑼ 設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為nnnn4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（ ）個結(jié)點，根結(jié)點的左子樹上有（ ）個結(jié)點。 中結(jié)點的（ ）序列，T中結(jié)點的后序序列就是 T39。⑻ 如果T39。⑺ 任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（ ）。⑹ 一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（ ?。┏闪?。⑸ 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）。⑷ 線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（ 　?。?。⑶ 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A 1 B 2 C 3 D 4【解答】D⑵ 設(shè)二叉樹有n個結(jié)點，則其深度為（ ）。【解答】n，n1【分析】n1個分支結(jié)點是經(jīng)過n1次合并后得到的。⑼ 在具有n個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的。⑻ 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）。則該樹中有（ ）個葉子結(jié)點?！窘獯稹?0【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子?！窘獯稹?k1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多?！窘獯稹?h 1，2h1【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點?！窘獯稹?i1，(n+1)/2，(n1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n1)/2。【解答】有且僅有一個，互不相交⑵ 樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（ ），子樹的根結(jié)點稱為該結(jié)點的（ ），該結(jié)點稱為其子樹根結(jié)點的（ ）。注意矩陣元素的表示方法。⑵ 因為k和i, j之間是一一對應(yīng)的關(guān)系，k+1是當(dāng)前非零元素的個數(shù)，整除即為其所在行號，取余表示當(dāng)前行中第幾個非零元素，加上前面零元素所在列數(shù)就是當(dāng)前列號，即：7．已知兩個nn的對稱矩陣按壓縮存儲方法存儲在已維數(shù)組A和B中，編寫算法計算對稱矩陣的乘積?！窘獯稹竣?要求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲了多少個非零元素，這些非零元素的個數(shù)就是k的值?！窘獯稹縃ead(Head(Tail(Tail(LS))))5．廣義表(a, b, (c, (d)))的表尾是（ ）?！窘獯稹縩(n+1)/23．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲，則A[i][j]在數(shù)組S中的存儲位置是（ ）。若按行優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ），若按列優(yōu)先方式存儲，元素M[7][5]的起始地址為（　　 ）。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個for循環(huán)執(zhí)行m次，第二個for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時間復(fù)雜度為Ｏ(mn+n2)。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度?！窘獯稹竣?ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST))))=獎金⑵ 工資表ST的頭尾表示法如圖47所示。6．設(shè)某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣” 。如果采用三元組順序表進行壓縮存儲，假設(shè)矩陣中有t個非零元素，其空間復(fù)雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復(fù)雜度亦為Ｏ(t)。5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲結(jié)構(gòu)完成求 運算的優(yōu)缺點。4．一個稀疏矩陣如圖44所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示?！窘獯稹垮e?！窘獯稹繉?。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。⑶ 稀疏矩陣壓縮存儲后，必會失去隨機存取功能?！窘獯稹繉Α＠缍S數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。3. 判斷題⑴ 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。B 對角矩陣只須存放非零元素即可。A 對角矩陣 B 三角矩陣 C 稀疏矩陣 D 對稱矩陣 【解答】C⑹ 若廣義表A滿足Head(A)=Tail(A)，則A為（ ）A ( ) B (( )) C (( ),( )) D(( ),( ),( ))【解答】B⑺ 下面的說法中，不正確的是（　　?。〢 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu)C 廣義表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。⑷ 對特殊矩陣采用壓縮存儲的目的主要是為了（　　?。〢 表達變得簡單 B 對矩陣元素的存取變得簡單C 去掉矩陣中的多余元素 D 減少不必要的存儲空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9]【解答】D，E，K【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要906=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+810+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j9+i=d+85，解此方程，得i=4，j=9?！窘獯稹?，4，(a)，((((b),c)),(d))⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是（ ）。⑷ 稀疏矩陣一般壓縮存儲方法有兩種，分別是（ ）和（ ）。⑶ 設(shè)有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（ ）。⑵ 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（ ）。【解答】存取，修改，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。【解答】PA321, P3A21, P32A1, P321A, AP321=I_ am_ a_ teacther，其長度為（ ）。 top=topnext。 x=topdata。 B x=topdata。A x=top?！窘獯稹緾2．一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。 C top=top1?！窘獯稹繉W(xué)習(xí)自測及答案 1．在一個具有n個單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時，top的變化為（ ）?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率?！窘獯稹肯扰袛啻甋中要刪除的內(nèi)容是否存在，若存在，則將第i+j1之后的字符前移j個位置?！窘獯稹坎僮鞑襟E為：① 將所有元素出棧并入隊；② 依次將隊列元素出隊，如果是偶數(shù)結(jié)點，則再入隊，如果是奇數(shù)結(jié)點，則入棧；③ 將奇數(shù)結(jié)點出棧并入隊；④ 將偶數(shù)結(jié)點出隊并入棧；⑤ 將所有元素出棧并入隊；⑥ 將所有元素出隊并入棧即為所求。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。試設(shè)計相應(yīng)的入隊和出隊的算法?？沾诖幚碇锌勺鳛槿我獯淖哟?。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。其執(zhí)行過程如圖38所示。7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊）。）【解答】棧頂元素為6，棧底元素為1。【解答】假設(shè)有一個順序隊列，如圖36所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產(chǎn)生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數(shù)組中還有2個存儲單元空閑，其下標(biāo)分別為0和1。⑵可以，設(shè)Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。4. 設(shè)有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。【解答】錯。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。⑷ 在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear。⑶ 在棧滿的情況下不能做進棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉?。應(yīng)該有 種。A 連接 B 模式匹配 C 求子串 D 求串長【解答】B3. 判斷題⑴ 有n個元素依次進棧，則出棧序列有(n1)/2種。A S1的棧底位置為0，S2的棧底位置為n1B S1的棧底位置為0，S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應(yīng)該分別指向兩個棧中的第一個元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。⑻ 設(shè)數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當(dāng)S[n]全滿時才不能進行進棧操作。⑺ 棧和隊列的主要區(qū)別在于（ ）。⑹ 一個隊列的入隊順序是1，2，3，4，則隊列的輸出順序是（ ）。⑸ 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號）的兩個元素。A 6　　　　 B 4　　　　 C 3　　　　 D 2【解答】C【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設(shè)，即出棧的順序也是eeeeee1。A 不確定 B ni C ni1 D ni+1【解答