程序二叉樹(shù)習(xí)題(answer)-wenkub
2023-04-09 06:41:02 本頁(yè)面
【正文】 序法，即按L N R次序）。答：當(dāng)k=1(單叉樹(shù))時(shí)應(yīng)該最深，深度＝n（層）；當(dāng)k=n1（n1叉樹(shù)）時(shí)應(yīng)該最淺，深度＝2（層），但不包括n=0或1時(shí)的特例情況。答：最快方法：用葉子數(shù)＝[n/2]＝350 5. 設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有 500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有 1 個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有 0 個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。 log2(n) 2. 一棵深度為6的滿二叉樹(shù)有 n1+n2=0+ n2= n01=31 個(gè)分支結(jié)點(diǎn)和 261 =32 個(gè)葉子。由于二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。 （ ）.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。 （ ）.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。一、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤（）（ ）. 若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n—1個(gè)非空指針域。 （ ）二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（應(yīng)2i1）（ ）用二叉鏈表法（linkrlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。）即有后繼鏈接的指針僅n1個(gè)。注：滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。+1= 235。答：最快方法：用葉子數(shù)＝[n/2]＝500 ，n2=n01=499。教材答案是“完全k叉樹(shù)”，未定量。這三種方法相互之間有關(guān)聯(lián)。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。 O(n) 。解：先構(gòu)造哈夫曼樹(shù)，得到各葉子的路徑長(zhǎng)度之后便可求出WPL＝（4＋5＋3）2＋（1＋2）3=33 (15)(9) (6) （注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應(yīng)排在葉子值之后）1 2（注：原題為選擇題：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15）三、單項(xiàng)選擇題（）（ C ）1． 不含任何結(jié)點(diǎn)的空樹(shù) 。 （Ｄ）既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是B，因?yàn)槟菚r(shí)樹(shù)的定義是n≥1（ C ）2．二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。 （Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 （ C ）(n0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 。 log2(n)log2(n)+1249。 x log2(n) +1其余的結(jié)點(diǎn)分成為m（m≥0）個(gè) B 的集合T1，T2，…，Tm，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有 B ，則它必定是葉結(jié)點(diǎn)。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。C算法如下：void traversal(struct node *root){if (root) {printf(“%c”, rootdata)。}}，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：（lchild,data,rchild）。如C，E，F(xiàn)，G等結(jié)點(diǎn)。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A2. （P60 427）把如圖所示的樹(shù)轉(zhuǎn)化成二叉樹(shù)。注：當(dāng)rtag＝1時(shí)說(shuō)明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。 直到LTag=1； 應(yīng)改為：while(!rLtag)r=rLchild。 //應(yīng)改為 while(!rLtag) r=rLchild。答：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。amp。 DLR(rootrchild)。amp。① 打印葉子結(jié)點(diǎn)值（并求總數(shù)）思路：先建樹(shù)，再?gòu)谋闅v過(guò)程中打印結(jié)點(diǎn)值并統(tǒng)計(jì)。}test。void insert_data(int x) /*如何生成二叉排序樹(shù)？參見(jiàn)教材P43C程序*/{ liuyu *p,*q,*s。srchild=NULL。 while(p) /*如何接入二叉排序樹(shù)的適當(dāng)位置*/ {q=p。 else p=prchild。amp。 DLR(rootrchild)。 root=NULL。x)。 } else insert_data(x)。，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。 int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/{int d,p。if(dp) p=d。return(p)。 if(Trchild) Get_Sub_Depth(Trchild,x)。 return (mn?m:n)+1。struct liuyu *lchild,*rchild。int m=sizeof(test)。slchild=NULL。}p=root。}else if(xpdata)p=plchild。}int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/{int d,p。if(dp) p=d。return(p)。 /*千萬(wàn)別忘了賦初值給root!*/do{printf(please input data%d:,i)。 /*從鍵盤采集數(shù)據(jù)，以9999表示輸入結(jié)束*/if(x==9999){ printf(\nNow output depth value=%d\n, depth (root)
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1