程序二叉樹(shù)習(xí)題(answer)(已修改)
2025-04-06 06:41 本頁(yè)面
【正文】 一、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤（）（ ）. 若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n—1個(gè)非空指針域。（ ）.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1。 （ ）.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。 （ ）.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。 （ ）二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn)）（ ）.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k11，其中k是樹(shù)的深度。（應(yīng)2i1） （ ）.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子樹(shù)。 （ ）.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i—1個(gè)結(jié)點(diǎn)。（應(yīng)2i1）（ ）用二叉鏈表法（linkrlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。）即有后繼鏈接的指針僅n1個(gè)。（ √ ）。最快方法：用葉子數(shù)＝[n/2]＝6，再求n2=n01=5 二、填空（）1． 由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有 5 種形態(tài)。 2. 一棵深度為6的滿二叉樹(shù)有 n1+n2=0+ n2= n01=31 個(gè)分支結(jié)點(diǎn)和 261 =32 個(gè)葉子。注：滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3． 一棵具有２５７個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為 9 。（ 注：用235。 log2(n) +1= 235。 +1=94. 設(shè)一棵完全二叉樹(shù)有700個(gè)結(jié)點(diǎn)，則共有 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(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ù)。答：最快方法：用葉子數(shù)＝[n/2]＝500 ，n2=n01=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)＝0.6. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，可能達(dá)到的最大深度為 n ，最小深度為 2 。答：當(dāng)k=1(單叉樹(shù))時(shí)應(yīng)該最深，深度＝n（層）；當(dāng)k=n1（n1叉樹(shù)）時(shí)應(yīng)該最淺，深度＝2（層），但不包括n=0或1時(shí)的特例情況。教材答案是“完全k叉樹(shù)”，未定量。)7. 二叉樹(shù)的基本組成部分是：根（N）、左子樹(shù)（L）和右子樹(shù)（R）。因而二叉樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 L R N 次序）和中序法（也稱對(duì)稱序法，即按L N R次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 F E G H D C B 。
解：法1：先由已知條件畫(huà)圖，再后序遍歷得到結(jié)果；法2：不畫(huà)圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹(shù)。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹(shù)上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹(shù)同樣處理，則問(wèn)題得解。 O(n) 。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹(shù)的深度k+1，包括葉子的空域也遞歸了一次。9. 用5個(gè)權(quán)值{3, 2, 4, 5, 1}構(gòu)造的哈夫曼（Huffman）樹(shù)的帶權(quán)路徑長(zhǎng)度是 33 。解：先構(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ù)。 （Ｃ）是一棵樹(shù)也是一棵二叉樹(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)存儲(chǔ)。 （Ｂ）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)。 （Ｃ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)。 （Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 （ C ）(n0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 。(Ａ) 233。log2(n)249。 (Ｂ) 235。 log2(n) (Ｃ) 235。 log2(n) +1 (Ｄ) 233。log2(n)+1249。注1：233。x 249。表示不小于x的最小整數(shù)；235。 x表示不大于x的最大整數(shù)，它們與[ ]含義不同！注2：選（A）是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)冪時(shí)就會(huì)少算一層。似乎235。 log2(n) +1是對(duì)的？（ A ）4．把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是 。（Ａ）唯一的 （Ｂ）有多種（Ｃ）有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子 （Ｄ）有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子5. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m≥0）個(gè) B 的集合T1，T2
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1