【正文】 15．畫出和下列已知序列對應(yīng)的樹T：二叉樹的層次訪問序列為：ABCDEFGHIJ；二叉樹的中序訪問次序?yàn)椋篋BGEHJACIF。波蘭式： + a * b – c d / e f 逆波蘭式：a b c d * + e f / 13．畫出和下列已知序列對應(yīng)的樹T：樹的先根次序訪問序列為：GFKDAIEBCHJ；樹的后根訪問次序?yàn)椋篋IAEKFCJHBG。 1, n111．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，問該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值和最小值。 1。9．已知一棵度為m的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)非終端結(jié)點(diǎn)？解：設(shè)樹中共有n個(gè)結(jié)點(diǎn)，n0個(gè)葉結(jié)點(diǎn)，那么n=n0+n1+…+nm (1)樹中除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)對應(yīng)著一個(gè)分支，而度為k的結(jié)點(diǎn)發(fā)出k個(gè)分支，所以： n=n1+2*n2+…+m*nm+1 (2)由(1)、(2)可知n0= n2+2*n3+3*n4+…+(m1)*nm+110．在具有n（n1）個(gè)結(jié)點(diǎn)的樹中，深度最小的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？深度最大的那棵樹其深度是多少？它共有多少葉子和非葉子結(jié)點(diǎn)？2。因?yàn)榍靶蛐蛄械牡谝粋€(gè)元素是根結(jié)點(diǎn)，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個(gè)元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個(gè)元素）是右子樹，若為空，則右子樹為空。8．證明：由二叉樹的前序序列和中序序列可以唯一地確定一棵二叉樹。7．證明：若哈夫曼樹中有n個(gè)葉結(jié)點(diǎn)，則樹中共有2n－1個(gè)結(jié)點(diǎn)。HGDE FBAC(題5圖)【解答】森林：ABHEGDCF6．證明：在結(jié)點(diǎn)數(shù)多于1的哈夫曼樹中不存在度為1的結(jié)點(diǎn)。DBCIG HAFE J(圖 3)【解答】HFGIJABCED在二叉樹中某結(jié)點(diǎn)所對應(yīng)的森林中結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是該結(jié)點(diǎn)在森林中既沒有孩子也沒有右兄弟結(jié)點(diǎn)?！窘獯稹浚?）順序存儲結(jié)構(gòu)示意圖：ABCDEF^^^G^^H（2）二叉鏈表存儲結(jié)構(gòu)示意圖： （3）三叉鏈表存儲結(jié)構(gòu)示意圖：ABC ^^ D ^ E ^^ F^ G ^^ H ^A ^BC ^^ D ^E ^^ F ^ G ^^ H ^IDEFGCBANMKJH(圖 2)3．對于圖2所示的樹，試給出：（1）雙親數(shù)組表示法示意圖；（2）孩子鏈表表示法示意圖；（3）孩子兄弟鏈表表示法示意圖。ADBGEHCF(圖 1)②二叉樹是有序樹，每個(gè)結(jié)點(diǎn)最多有兩棵子樹，樹是無序樹，且每個(gè)結(jié)點(diǎn)可以有多棵子樹。（）20．滿二叉樹一定是完全二叉樹，反之未必。（√）18．對一棵二叉樹進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。（）16．由先序序列和后序序列能唯一確定一棵二叉樹。（√）14．在哈夫曼編碼中，出現(xiàn)頻率相同的字符編碼長度也一定相同。（）12．在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結(jié)點(diǎn)的后繼。（√）10．先序遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)不一定跟在該結(jié)點(diǎn)之后。（√）8．若一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)。＋1。（√）6．對于有N個(gè)結(jié)點(diǎn)的二叉樹，其高度為235。（）4．先根遍歷森林和先序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。（√）2．由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。A．9 B．10 C．9至566之間 D．10至567之間16．給一個(gè)整數(shù)集合{3，5，6，7，9}，與該整數(shù)集合對應(yīng)的哈夫曼樹是（B）。A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一 14．設(shè)高度為h的二叉樹上只有度為０和度為２的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（B）。 A． gcefha B． gdbecfha C． bdgaechf D． gdbehfca12．一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（AB）。A．不發(fā)生改變 B． 發(fā)生改變 C． 不能確定 D． 以上都不對10．若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（D）。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（D）。A．n1 B． n C． n+1 D．n+2 7．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（B）。且有如下性質(zhì):T中任意結(jié)點(diǎn)v,其編號等于左子樹上的最小編號減１,而v的右子樹的結(jié)點(diǎn)中,其最小編號等于v左子樹上結(jié)點(diǎn)的最大編號加１，這是按（B）編號的。A．plchild=NULL B．pltag=1且prtag=1C．pltag=0 D．plchild=NULL 且pltag=14．如果結(jié)點(diǎn)A有3個(gè)兄弟,而且B是A的雙親,則B的度是（B）。A．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 B．二叉樹的度為2C．一棵二叉樹的度可小于2 D．任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為22．以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中（n0），空鏈域的個(gè)數(shù)為（C）。0 0 0 22 0 150 13 3 0 0 00 0 0 6 0 00 0 0 0 0 091 0 0 0 0 00 0 28 0 0 0【解答】（1）三元組表表示法:i j v12345671 4 221 6 152 2 132 3 33 4 65 1 916 3 28（2）十字鏈表法：012345^0123^455191^^233^346^^14226328^^1615^^2213^7．畫出下列廣義表的頭尾表示存儲結(jié)構(gòu)示意圖?！窘獯稹縰=ji+1v=j16．現(xiàn)有如下的稀疏矩陣A（如圖所示），要求畫出以下各種表示方法。當(dāng)i為奇數(shù)時(shí)，第i行的元素為：ai,i、ai,(i+1)，此時(shí)k=2*(i1)+ji=i+j2當(dāng)i為偶數(shù)時(shí)，第i行的元素為：ai,(i1)、ai,i，此時(shí)k=2*(i1)+jI+1=i+j1綜上所述，k=i+ji%21。問下列元素的存儲地址是什么？(1) a0000 (2)a1111 (3)a3125 (4)a8247【解答】(1) LOC( a0000)= 100 (2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776 (3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784 (4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=48164．假設(shè)一個(gè)準(zhǔn)對角矩陣：a11 a12a21 a22a33 a34a43 a44 …. aij a2m1,2m1 a2m1,2m a2m,2m1 a2m,2m 按以下方式存儲于一維數(shù)組B[4m]中（m為一個(gè)整數(shù)）：012345 6 … k … 4m1 4ma 11a 12a21a22a33a34a43…aij…a2m1,2ma2m,2m1a2m,2m寫出下標(biāo)轉(zhuǎn)換函數(shù)k=f(i,j)?！窘獯稹?（1）S的next與nextval值分別為012123456789和002002002009，p的next與nextval值分別為012123和002003。P=‘a(chǎn)abaac39。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)更為突出。（）7．所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（）5．若采用三元組存儲稀疏矩陣，把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算。（√）3．稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。A．二維數(shù)組和三維數(shù)組 B．三元組和散列C．三元組表和十字鏈表 D．散列和十字鏈表 判斷題1．串相等是指兩個(gè)串的長度相等。（1）A．90 B．180 C．240 D．540（2）A．108 B．114 C．54 D．60（3）A．M[8][5] B．M[3][10] C．M[5][8] D．M[0][9]5．?dāng)?shù)組A中，每個(gè)元素的存儲占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個(gè)數(shù)是（C），若該數(shù)組按行存放，元素A[8][5]的起始地址是（C），若該數(shù)組按列存放，元素A[8][5]的起始地址是（C）。A．串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù) D．串中所含非空格字符的個(gè)數(shù)3．已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（D）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321 課后習(xí)題解答 選擇題1．下面關(guān)于串的敘述錯(cuò)誤的是（C）。缺點(diǎn)是執(zhí)行中占內(nèi)存空間較多，運(yùn)行效率低。在實(shí)際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。3．什么是遞歸？遞歸程序有什么優(yōu)缺點(diǎn)？一個(gè)函數(shù)在結(jié)束本函數(shù)之前，直接或間接調(diào)用函數(shù)自身，稱為遞歸。2．棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)各有什么特點(diǎn)，什么情況下用到棧，什么情況下用到隊(duì)列？棧和隊(duì)列都是操作受限的線性表，棧的運(yùn)算規(guī)則是“后進(jìn)先出”，隊(duì)列的運(yùn)算規(guī)則是“先進(jìn)先出”?；騭qnum==maxsize。（） 簡答題1．循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？循環(huán)隊(duì)列的優(yōu)點(diǎn)是能夠克服“假溢滿”現(xiàn)象。（√）4．通常使用隊(duì)列來處理函數(shù)的調(diào)用。（√）2．任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。A．隊(duì)列 B．靜態(tài)鏈表 C．棧 D．順序表10．棧和隊(duì)都是（C）。8．用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時(shí)，在進(jìn)行刪除運(yùn)算時(shí)（D）。 D．snext=f。 C．snext=r。 B．rnext=s。A．fnext=r。A．top[2]top[1]|=0 B．top[1]+1=top[2]C．top[1]+top[2]=m D．top[1]=top[2]6．一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（C）。A．i B．ni C． ni+1 D．不確定4．表達(dá)式a*(b－c)＋d的后綴表達(dá)式是（B）。2．對于棧操作數(shù)據(jù)的原則是（B）。 D．pnext=Top。 C．pnext=Top。 B．pnext=Topnext。 /*返回找到的結(jié)點(diǎn)的地址*/} 課后習(xí)題解答 選擇題1．向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，其操作步驟為（C）。p=pprior。ppriorfreq=pfreq。pdata=k。ppriorfreqpfreq) /*調(diào)整結(jié)點(diǎn)的次序*/ {k=ppriordata。 /*修改p的freq域*/while(pprior!=Lamp。 /*查找值為x的結(jié)點(diǎn)，使p指向它*/if(!p) return(NULL)。amp。DlinkList Locate(DLinkList L, datatype x){p=Lnext。