數(shù)據(jù)結(jié)構(gòu)c版王紅梅版課后答案khdaw-資料下載頁(yè)

　　

【正文】 序遍歷序列 b1b2b3… bk bk+1 可唯一確定一棵二叉 樹(shù)。在前序遍歷序列中第一個(gè)訪問(wèn)的一定是根結(jié)點(diǎn)，即二叉樹(shù)的根結(jié)點(diǎn)是 a1，在中序遍歷序列中查找值為 a1 的結(jié)點(diǎn)，假設(shè)為 bi，則 a1=bi 且 b1b2… bi1 是對(duì)根結(jié)點(diǎn) a1 的左子樹(shù)進(jìn)行中序遍歷的結(jié)果，前序遍歷序列 a2a3… ai 是對(duì)根結(jié)點(diǎn) a1 的左子樹(shù)進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列 a2a3… ai 和中序遍歷 序列 b1b2… bi1 唯一確定了根結(jié)點(diǎn)的左子樹(shù)，同樣可證前序遍歷序列 ai+1ai+2… ak+1 和中序遍歷序列 bi+1bi+2… bk+1 唯一確定了根結(jié)點(diǎn)的右子樹(shù)。6．已知一棵度為 m 的樹(shù)中有：n1 個(gè)度為 1 的結(jié)點(diǎn)，n2 個(gè)度為 2 的結(jié)點(diǎn)，……，nm 個(gè)度為 m 的結(jié)點(diǎn)，問(wèn) 該樹(shù)中共有多少個(gè)葉子結(jié)點(diǎn)？【解答】設(shè)該樹(shù)的總結(jié)點(diǎn)數(shù)為 n，則n=n0+n1+n2+……+nm 又： n=分枝數(shù)+1=0n0+1n1+2n2+……+mnm+1 由上述兩式可得：n0= n2+2n3+……+(m1)nm+17．已知二叉樹(shù)的中序和后序序列分別為 CBEDAFIGH 和 CEDBIFHGA，試構(gòu)造該二叉樹(shù)。【解答】二叉樹(shù)的構(gòu)造過(guò)程如圖 512 所示。8．對(duì)給定的一組權(quán)值 W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。【解答】構(gòu)造的哈夫曼樹(shù)如圖 513 所示。樹(shù)的帶權(quán)路徑長(zhǎng)度為：WPL=24+34+53+73+83+92+112=1209．已知某字符串 S 中共有 8 種字符，各種字符分別出現(xiàn) 2 次、1 次、4 次、5 次、7 次、3 次、4 次和 9 次， 對(duì)該字符串用[0，1]進(jìn)行前綴編碼，問(wèn)該字符串的編碼至少有多少位。【解答】以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹(shù)如圖 514 所示。其帶權(quán)路徑長(zhǎng)度=25+15+34+53+92+43+43+72=98，所以，該字符串的編碼長(zhǎng)度至少為 98 位。10．算法設(shè)計(jì)⑴ 設(shè)計(jì)算法求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)。【解答】本算法不是要打印每個(gè)結(jié)點(diǎn)的值，而是求出結(jié)點(diǎn)的個(gè)數(shù)。所以可將遍歷算法中的“訪問(wèn)”操作改為“計(jì) 數(shù)操作”，將結(jié)點(diǎn)的數(shù)目累加到一個(gè)全局變量中，每個(gè)結(jié)點(diǎn)累加一次即完成了結(jié)點(diǎn)個(gè)數(shù)的求解。具體算法如下：⑵ 設(shè)計(jì)算法按前序次序打印二叉樹(shù)中的葉子結(jié)點(diǎn)。【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不 同之處是此處不是打印每個(gè)結(jié)點(diǎn)的值，而是打印出其中的葉子結(jié)點(diǎn)，即為有條件打印。為此，將前序遍歷算法中的訪問(wèn)操作改為條件打印即可。算法如下：⑶ 設(shè)計(jì)算法求二叉樹(shù)的深度。【解答】當(dāng)二叉樹(shù)為空時(shí)，深度為 0；若二叉樹(shù)不為空，深度應(yīng)是其左右子樹(shù)深度的最大值加 1，而其左右 子樹(shù)深度的求解又可通過(guò)遞歸調(diào)用本算法來(lái)完成。具體算法如下：⑷ 編寫(xiě)算法，要求輸出二叉樹(shù)后序遍歷序列的逆序。【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問(wèn)根結(jié)點(diǎn)，再遍歷根結(jié)點(diǎn)的右 子樹(shù)，最后遍歷根結(jié)點(diǎn)的左子樹(shù)。注意和前序遍歷的區(qū)別，具體算法如下：⑸ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法求二叉樹(shù)中結(jié)點(diǎn) x 的雙親。【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過(guò)程中查找結(jié)點(diǎn) x 并記載其雙親。具體算法如下：⑹ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)中刪除以值 x 為根結(jié)點(diǎn)的子樹(shù)。【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過(guò)程中查找結(jié)點(diǎn) x 并記載其雙親，然后將結(jié)點(diǎn) x 的雙親結(jié)點(diǎn)中指 向結(jié)點(diǎn) x 的指針置空。具體算法如下：⑺ 一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法對(duì)該二叉樹(shù)進(jìn)行前序遍歷。【解答】按照題目要求，設(shè)置一個(gè)工作棧以完成對(duì)該樹(shù)的非遞歸算法，思路如下：① 每訪問(wèn)一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓棧，查看此結(jié)點(diǎn)是否有左子樹(shù)，若有，訪問(wèn)左子樹(shù)，重復(fù)執(zhí)行該過(guò)程直到 左子樹(shù)為空。② 從棧彈出一個(gè)結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹(shù)，訪問(wèn)右子樹(shù)執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。 具體算法如下：⑻ 編寫(xiě)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左右子樹(shù)。【解答】對(duì)二叉樹(shù)進(jìn)行后序遍歷，在遍歷過(guò)程中訪問(wèn)某結(jié)點(diǎn)時(shí)交換該結(jié)點(diǎn)的左右子樹(shù)。 具體算法如下：⑼ 以孩子兄弟表示法做存儲(chǔ)結(jié)構(gòu)，求樹(shù)中結(jié)點(diǎn) x 的第 i 個(gè)孩子。【解答】先在鏈表中進(jìn)行遍歷，在遍歷過(guò)程中查找值等于 x 的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域 firstchild 找到值為 x 結(jié)點(diǎn)的第一個(gè)孩子，再沿右兄弟域 rightsib 找到值為 x 結(jié)點(diǎn)的第 i 個(gè)孩子并返回指向這個(gè)孩子的 指針。樹(shù)的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如下：template struct TNode{T data。TNode *firstchild, *rightsib。}。具體算法如下：學(xué)習(xí)自測(cè)及答案1．前序遍歷和中序遍歷結(jié)果相同的二叉樹(shù)是（ ）。A 根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)B 根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)C 所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)D 所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)【解答】D2．由權(quán)值為{3, 8, 6, 2, 5}的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，其帶權(quán)路徑長(zhǎng)度為（ ）。A 24 B 48 C 53 D 72【解答】C3．用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組 A[1] ~ A[n]中，結(jié)點(diǎn) A[i]若有左子樹(shù)， 則左子樹(shù)的根結(jié)點(diǎn)是（ ）。A A[2i1] B A[2i+1] C A[i/2] D A[2i]【解答】D4．對(duì)任何一棵二叉樹(shù) T，如果其終端結(jié)點(diǎn)的個(gè)數(shù)為 n0，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 n2，則（ ）。A n0=n21 B n0=n2 C n0=n2+1 D 沒(méi)有規(guī)律【解答】C5．一棵滿二叉樹(shù)中共有 n 個(gè)結(jié)點(diǎn)，其中有 m 個(gè)葉子結(jié)點(diǎn)，深度為 h，則（ ）。A n=h+m B h+m=2n C m=h1 D n=2h1【解答】D6．對(duì)于完全二叉樹(shù)中的任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為 h，則其左分支下的子孫的最大層次 為（ ）。A h B h+1 C h 或 h+1 D 任意【解答】C7．假定一棵度為 3 的樹(shù)中結(jié)點(diǎn)數(shù)為 50，則其最小高度應(yīng)為 。A 3 B 4 C 5 D 6【解答】C8．在線索二叉樹(shù)中，一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)的充要條件為（ ）。A 左線索標(biāo)志為 0，右線索標(biāo)志為 1 B 左線索標(biāo)志為 1，右線索標(biāo)志為 0C 左、右線索標(biāo)志均為 0 D 左、右線索標(biāo)志均為 1【解答】C9．對(duì)于一棵具有 n 個(gè)結(jié)點(diǎn)的樹(shù)，其所有結(jié)點(diǎn)的度之和為（ ）。【解答】n110．在順序存儲(chǔ)的二叉樹(shù)中，編號(hào)為 i 和 j 的兩個(gè)結(jié)點(diǎn)處在同一層的條件是（ ）。【解答】11．現(xiàn)有按前序遍歷二叉樹(shù)的結(jié)果 ABC，問(wèn)有哪幾種不同的二叉樹(shù)可以得到這一結(jié)果？【解答】共有 5 種二叉樹(shù)可以得到這一結(jié)果，如圖 515 所示。12．試找出分別滿足下列條件的所有二叉樹(shù)：⑴ 前序序列和中序序列相同。⑵ 中序序列和后序序列相同。⑶ 前序序列和后序序列相同。【解答】 ⑴ 空二叉樹(shù)、只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)和右斜樹(shù)。⑵ 空二叉樹(shù)、只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)和左斜樹(shù)。⑶ 空二叉樹(shù)、只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)13．將下面圖 516 所示的樹(shù)轉(zhuǎn)換為二叉樹(shù)，圖 517 所示的二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林。【解答】圖 516 所示樹(shù)轉(zhuǎn)換的二叉樹(shù)如圖 518 所示，圖 517 所示二叉樹(shù)轉(zhuǎn)換的森林如圖 519 所示。14．以孩子兄弟表示法作為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法求樹(shù)的深度。【解答】采用遞歸算法實(shí)現(xiàn)。若樹(shù)為空樹(shù)，則其深度為 0，否則其深度等于第一棵子樹(shù)的深度+1 和兄弟子 樹(shù)的深度中的較大者。具體算法如下：15．設(shè)計(jì)算法，判斷一棵二叉樹(shù)是否為完全二叉樹(shù)。【解答】根據(jù)完全二叉樹(shù)的定義可知，對(duì)完全二叉樹(shù)按照從上到下、從左到右的次序（即層序）遍歷應(yīng)該 滿足：⑴ 若某結(jié)點(diǎn)沒(méi)有左孩子，則其一定沒(méi)有右孩子；⑵ 若某結(jié)點(diǎn)無(wú)右孩子，則其所有后繼結(jié)點(diǎn)一定無(wú)孩子。 若有一結(jié)點(diǎn)不滿足其中任意一條，則該二叉樹(shù)就一定不是完全二叉樹(shù)。因此可采用按層次遍歷二叉樹(shù)的方 法依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行判斷是否滿足上述兩個(gè)條件。為此，需設(shè)兩個(gè)標(biāo)志變量 BJ 和 CM，其中 BJ 表示已掃 描過(guò)的結(jié)點(diǎn)是否均有左右孩子，CM 存放局部判斷結(jié)果及最后的結(jié)果。具體算法如下：第 6 章 圖課后習(xí)題講解1. 填空題⑴ 設(shè)無(wú)向圖 G 中頂點(diǎn)數(shù)為 n，則圖 G 至少有（ ）條邊，至多有（ ）條邊；若 G 為有向圖，則至少有（ ） 條邊，至多有（ ）條邊。【解答】0，n(n1)/2，0，n(n1)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱(chēng)為完全圖，在完全圖中， 任意兩個(gè)頂點(diǎn)之間都存在邊。⑵ 任何連通圖的連通分量只有一個(gè)，即是（ ）。【解答】其自身⑶ 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（ ）和（ ）。【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲(chǔ)結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷ 已知無(wú)向圖 G 的頂點(diǎn)數(shù)為 n，邊數(shù)為 e，其鄰接表表示的空間復(fù)雜度為（ ）。【解答】Ｏ(n+e)【分析】在無(wú)向圖的鄰接表中，頂點(diǎn)表有 n 個(gè)結(jié)點(diǎn)，邊表有 2e 個(gè)結(jié)點(diǎn)，共有 n+2e 個(gè)結(jié)點(diǎn)，其空間復(fù)雜度 為Ｏ(n+2e)=Ｏ(n+e)。⑸ 已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第 j 個(gè)頂點(diǎn)的入度的方法是（ ）。【解答】求第 j 列的所有元素之和⑹ 有向圖 G 用鄰接矩陣 A[n][n]存儲(chǔ)，其第 i 行的所有元素之和等于頂點(diǎn) i 的（ ）。【解答】出度⑺ 圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的（ ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（ ）；圖的廣度優(yōu)先遍歷類(lèi)似于樹(shù)的（ ）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。【解答】前序，棧，層序，隊(duì)列⑻ 對(duì)于含有 n 個(gè)頂點(diǎn) e 條邊的連通圖，利用 Prim 算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（ ），利用 Kruskal算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（ ）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim 算法采用鄰接矩陣做存儲(chǔ)結(jié)構(gòu)，適合于求稠密圖的最小生成樹(shù)；Kruskal 算法采用邊集數(shù)組 做存儲(chǔ)結(jié)構(gòu)，適合于求稀疏圖的最小生成樹(shù)。⑼ 如果一個(gè)有向圖不存在（ ），則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄小！窘獯稹炕芈罚?0） 在一個(gè)有向圖中，若存在弧、則在其拓?fù)湫蛄兄校旤c(diǎn) vi, vj, vk 的相對(duì)次序?yàn)椋?）。【解答】vi, vj, vk【分析】對(duì)由頂點(diǎn) vi, vj, vk 組成的圖進(jìn)行拓?fù)渑判颉?. 選擇題⑴ 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。A 1/2 B 1 C 2 D 4【解答】C【分析】設(shè)無(wú)向圖中含有 n 個(gè)頂點(diǎn) e 條邊，則 。⑵ n 個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（ ）條邊，其形狀是（ ）。A n B n+1 C n1 D n(n1)E 無(wú)回路 F 有回路 G 環(huán)狀 H 樹(shù)狀【解答】A，G⑶ 含 n 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（ ）。A 1 B n/2 C n1 D n【解答】C【分析】若超過(guò) n1，則路徑中必存在重復(fù)的頂點(diǎn)。⑷ 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（ ）。A n B (n1)2 C n1 D n2【解答】D⑸ 圖的生成樹(shù)（ ），n 個(gè)頂點(diǎn)的生成樹(shù)有（ ）條邊。A 唯一 B 不唯一 C 唯一性不能確定 D n E n +1 F n1【解答】C，F(xiàn)⑹ 設(shè)無(wú)向圖 G=(V, E)和 G39。 =(V39。, E39。 )，如果 G39。 是 G 的生成樹(shù)，則下面的說(shuō)法中錯(cuò)誤的是（ ）。A G39。 為 G 的子圖 B G39。 為 G 的連通分量C G39。 為 G 的極小連通子圖且 V = V39。 D G39。 是 G 的一個(gè)無(wú)環(huán)子圖【解答】B【分析】連通分量是無(wú)向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊都加上， 所以，連通分量中可能存在回路。⑺ G 是一個(gè)非連通無(wú)向圖，共有 28 條邊，則該圖至少有（ ）個(gè)頂點(diǎn)。A 6 B 7 C 8 D 9【解答】D【分析】n 個(gè)頂點(diǎn)的無(wú)向圖中，邊數(shù) e≤n(n1)/2，將 e=28 代入，有 n≥8，現(xiàn)已知無(wú)向圖非連通，則 n=9。⑻ 最小生成樹(shù)指的是（ ） 。A 由連通網(wǎng)所得到的邊數(shù)最少的生成樹(shù) B 由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)C 連通網(wǎng)中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù) D 連通網(wǎng)的極小連通子圖【解答】C⑼ 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以用（ ）。A 求關(guān)鍵路徑的方法 B 求最短路徑的方法C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法【解答】D【分析】當(dāng)有向圖中無(wú)回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序（退出