數(shù)據(jù)結(jié)構(gòu)作業(yè)題-文庫(kù)吧
2025-03-10 03:01 本頁(yè)面
【正文】 ange) (2) L2((apple, pear), (banana, orange)) (3) L3(((apple), (pear), (banana), (orange)))55 畫(huà)出廣義表L的存儲(chǔ)結(jié)構(gòu)圖并求出它的深度： L=( (( )), a,((b,c),( ),d),(((e))) ) 第六章 61 在結(jié)點(diǎn)個(gè)數(shù)為n (n1)的各棵樹(shù)中，深度最小的樹(shù)的深度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？深度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？ 62 如果一棵度為k的樹(shù)有n1個(gè)度為1的結(jié)點(diǎn), 有n2個(gè)度為2的結(jié)點(diǎn), … , nk個(gè)度為k的結(jié)點(diǎn), 試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）? 試推導(dǎo)之。63 如果一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。試問(wèn)該樹(shù)葉子結(jié)點(diǎn)的數(shù)目。64 使用 (1) 順序表示和 (2) 二叉鏈表表示法，分別畫(huà)出下圖所示二叉樹(shù)的存儲(chǔ)表示。（3）分別求出該二叉樹(shù)的先序、中序、后序遍歷序列。65 試分別找出滿足以下條件的所有二叉樹(shù):(1) 二叉樹(shù)的前序序列與中序序列相同。(2) 二叉樹(shù)的中序序列與后序序列相同。(3) 二叉樹(shù)的前序序列與后序序列相同。66 請(qǐng)畫(huà)出右圖所示的森林所對(duì)應(yīng)的二叉樹(shù),并分別按以下說(shuō)明進(jìn)行線索化。（1）先序全線索化 （2）中序全線索化 （3）后續(xù)后繼線索化121131411921054315768 67 已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫(huà)出這棵二叉樹(shù)?！窘獯稹慨?dāng)前序序列為ABECDFGHIJ，中序序列為EBCDAFHIGJ時(shí)，逐步形成二叉樹(shù)的過(guò)程如下圖所示： AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD68畫(huà)出和下列已知序列對(duì)應(yīng)的樹(shù)T:樹(shù)的先根次序訪問(wèn)序列為：GFKDAIEBCHJ；樹(shù)的后根次序訪問(wèn)序列為：DIAEKFCJHBG。69畫(huà)出和下列已知序列對(duì)應(yīng)的森林F: 森林的先序訪問(wèn)序列為：ABCDEFGHIJKL；森林的中序訪問(wèn)序列為：CBEFDGAJIKLH。610 假定用于通信的電文僅由8個(gè)字母c1, c2, c3, c4, c5, c6, c7, c8組成, , , , , , , 。試為這8個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼, 并給出該電文的總碼數(shù)。使用 0~7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。101001019214002030710628051106173260 10C5C7C2100110 C8C410C1C6C3帶權(quán)路徑長(zhǎng)度WPL=(+)*5+(++)*4+(++)*2=，是最優(yōu)方案。若等長(zhǎng)C1至C8編碼分別為000~111，平均長(zhǎng)度為3。 c1 c2 c3 c4 c5 c6 c7 c8 0010 10 00000 0001 01 00001 11 0011 二、算法設(shè)計(jì)題： 編寫(xiě)遞歸算法，將二叉樹(shù)（用二叉鏈表作為二叉樹(shù)的存儲(chǔ)表示）中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換。 編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)（用二叉鏈表存儲(chǔ)表示）中葉子結(jié)點(diǎn)的數(shù)目。 編寫(xiě)按層次遍歷二叉樹(shù)的算法。第7章 圖71在n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊的條數(shù)為（n(n1)/2 ）。畫(huà)出4個(gè)頂點(diǎn)的無(wú)向完全圖。12345672 下面判斷下面的有向圖是強(qiáng)連通圖嗎？若不是強(qiáng)連通圖，有幾個(gè)強(qiáng)連通分量？ABCDEFABCDEF G1 G2 G3G1不是強(qiáng)連通圖，有6個(gè)強(qiáng)連通分量（每個(gè)頂點(diǎn)分別是1個(gè)強(qiáng)連通分量）G2是強(qiáng)連通圖 (只有1個(gè)強(qiáng)連通分量，就是G2本身)56G3不是強(qiáng)連通圖，有3個(gè)強(qiáng)連通分量.：123473 給出上圖G3的鄰接矩陣、鄰接表、逆鄰接表。DA(給出圖G1的鄰接矩陣、鄰接表、逆鄰接表、鄰接多重表（十字鏈表）大家自己畫(huà)G3)(1) 鄰接矩陣EBFC∧310 A1 B2 C3 D4 E5 F(2) 鄰接表∧42∧5∧41∧∧4∧0 A1 B2 C3 D4 E5 F（逆鄰接表）∧30∧1∧0∧531∧2data fin fout (3) 鄰接多重表（十字鏈表）i j ilink jlink0 1 (A, B)∧0 A1 B2 C3 D4 E5 F∧∧0 3 (A, D)∧∧1 2 (B, C)1 4 (B, E)∧∧∧2 5 (C, F)3 1 (D, B)3 4 (D, E)5 4 (F, E)∧∧74 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？用鄰接矩陣表示圖，矩陣元素的個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的平方(即n個(gè)頂點(diǎn)，矩陣是nn)，與邊的條數(shù)無(wú)關(guān)。矩陣中非零元素的個(gè)數(shù)與邊的條數(shù)有關(guān)（無(wú)向圖非零元素的個(gè)數(shù)是邊數(shù)的2倍；有向圖非零元素的個(gè)數(shù)等于邊數(shù)）?！窘獯稹?5 有n（n1）個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說(shuō)明。n個(gè)頂點(diǎn)的無(wú)向連通圖至少有n1條邊，n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊。例如：
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1