線性數(shù)學(xué)試題解答6(參考版)
2024-09-08 21:16本頁面
【正文】 02 03 14 15 09 05 11 06 20 29 16 17 33 49 (Ⅵ ) 02 03 15 09 05 11 06 20 29 16 17 33 49 14 (Ⅶ ) 100 61 39 36 25 22 17 7 10 11 11 4 3 6 5 C3 C8 C5 C6 C1 C4 C2 C7 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 70 11 15 23 26 33 39 45 52 58 66 58 66 82 169 15 23 26 18 33 39 45 52 375 0 0 70 11 。 仿照霍夫曼樹的構(gòu)造方法來構(gòu)造擴(kuò)充 4 叉樹，每次合并 4 個(gè)結(jié)點(diǎn)。由于在本題中 n0 = 11≠ 3 * n4 +1，需要補(bǔ) 2 個(gè)權(quán)值為0 的外結(jié)點(diǎn)。這棵擴(kuò)充 4 叉樹的帶權(quán)外部路徑長度是多少 ? 【解答】權(quán)值個(gè)數(shù) n = 11，擴(kuò)充 4 叉樹的內(nèi)結(jié)點(diǎn)的度都為 4，而外結(jié)點(diǎn)的度都為 0。試為這 8 個(gè)字母設(shè)計(jì)不等長 Huffman 編碼 , 并給出該電文的總碼數(shù)。 【解答】 EBCD FHIGJ A A B E F CD HIGJ A B E F C D G J HI A B E F C D G J H I 15 03 14 02 06 09 16 17 F： 02 03 15 14 06 09 16 17 05 02 03 15 14 06 09 16 17 05 11 (Ⅰ ) (Ⅱ ) (Ⅲ ) 02 03 15 14 09 16 17 05 11 06 20 (Ⅳ ) 02 03 14 15 09 16 17 05 11 06 20 29 02 03 14 15 09 16 17 05 11 06 20 29 33 (Ⅴ ) 82 此樹的帶權(quán)路徑長度 WPL = 229。 【解答】 因?yàn)榻o出二叉樹的前序遍歷序列和中序遍歷序列能夠唯一地確定這棵二叉樹， 能夠唯一地確定一棵樹。 【解答】 當(dāng)前序序列為 ABECDFGHIJ，中序序列為 EBCDAFHIGJ 時(shí)，逐步形成二叉樹的過程如 下圖所示： 620 已知一棵樹的先根次序遍歷的結(jié)果與其對應(yīng)二叉樹表示 (長子 兄弟表示 )的前序遍歷結(jié)果相同 , 樹的后根次序遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同。 Double_order ( currentrightChild )。 cout currentdata 39。 39。試寫出執(zhí)行這種雙序遍歷的算法。 ( i )。 break。 case 1 : switch ( U[i].rtag ) { case 0 : V[i].llink = i + 1。 break。 case 1 : V[i].llink = 1。 V[k].rlink = i + 1。 if ( ( ) == 0 ) { k = ( )。 i CurrentSize。 int k。 U = new DoublyTagNode Type [Maxsz]。 //存儲(chǔ)雙標(biāo)記表的向量 int MaxSize, CurrentSize。 //結(jié)點(diǎn)的左子女、右兄弟標(biāo)記 1 對應(yīng)二叉樹 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 A B C D E F G H K J I A B C D E F G H I K J 對應(yīng)二叉樹 llink data rlink 0 1 2 3 4 5 6 7 8 9 10 1 1 1 4 1 6 1 8 9 1 1 A B C D E F G H I K J 5 2 3 1 1 7 1 1 10 1 1 森林的左子女 右兄弟表示的靜態(tài)二叉鏈表 ltag data rtag 0 1 2 3 4 5 6 7 8 9 10 1 0 0 1 0 1 0 1 1 0 0 A B C D E F G H I K J 1 1 1 0 0 1 0 0 1 0 0 森林的雙標(biāo)記表示 public: DoublyTagNode ( ) : ltag(0), rtag(0) { } DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) { } } template class Type class staticlinkList //靜態(tài)鏈表類定義 : public LchRsibNodeType, public DoublyTagNode Type{ private: LchRsibNodeType *V。 //結(jié)點(diǎn)的左子女、右兄弟指針 public: LchRsibNode ( ) : llink(NULL), rlink(NULL) { } LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) { } } template class Type class DoublyTagNode { //雙標(biāo)記表結(jié)點(diǎn)類的 定義 protected: Type data。 【解答】 (1) 結(jié)構(gòu)定義 template class Type class LchRsibNode { //左子女 右兄弟鏈表結(jié)點(diǎn)類的定義 protected: Type data。并設(shè)定若 ltag = 0，則該結(jié)點(diǎn)沒有子女，若 ltag ? 0，則該結(jié)點(diǎn)有子女；若 rtag = 0，則該結(jié)點(diǎn)沒有下一個(gè)兄弟，若 rtag ? 0，則該結(jié)點(diǎn)有下一個(gè)兄弟。 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 5 2 8 3 4 6 5 2 8 3 4 6 10 5 2 8 3 4 6 10 14 【解答】 617 在森林的二叉樹表示中，用 llink 存儲(chǔ)指向結(jié)點(diǎn)第一個(gè)子女的指針，用 rlink 存儲(chǔ)指向結(jié)點(diǎn)下一個(gè)兄弟的指針，用 data 存儲(chǔ)結(jié)點(diǎn)的值。 } } 614 寫出向堆中加入數(shù)據(jù) 4, 2, 5, 8, 3, 6, 10, 14 時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。 //建立根結(jié)點(diǎn) ConstructTree ( T, n, 2*i+1, ptrleftChild )。 if ( i = n ) ptr =
公司管理相關(guān)推薦
鄂ICP備17016276號-1