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