線性數(shù)學(xué)試題解答6(編輯修改稿)
2024-10-10 21:16 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 inaryTree ( Type value ) : RefValue ( value ), root ( NULL ){ } ~BinaryTree ( ) { destroy (root)。 } BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) { } BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) { } Typeamp。 GetData ( ) const { return data。 } BinTreeNodeType* GetLeft ( ) const { return leftChild。 } BinTreeNodeType* GetRight ( ) const { return rightChild。 } void SetData ( const Typeamp。 item ){ data = item。 } void SetLeft ( BinTreeNodeType *L ) { leftChild = L。 } void SetRight ( BinTreeNodeType *R ){ RightChild =R。 } int IsEmpty ( ) { return root == NULL ? 1 : 0。 } BinTreeNodeType *Parent ( BinTreeNodeType *current ) { return root == NULL || root == current ? NULL : Parent ( root, current )。 } BinTreeNodeType * LeftChild ( BinTreeNodeType *current ) { return current != NULL ? currentleftChild : NULL。 } BinTreeNodeType * RighttChild ( BinTreeNodeType *current ) { return current != NULL ? currentrightChild : NULL。 } int Insert ( const Typeamp。 item )。 BinTreeNodeType * Find ( const Typeamp。 item )。 BinTreeNodeType * GetRoot ( ) const { return root。 } friend istreamamp。 operator ( istreamamp。 in, BinaryTreeTypeamp。 Tree )。 //輸入二叉樹 friend ostreamamp。 operator ( ostreamamp。 out, BinaryTreeTypeamp。 Tree )。 //輸出二叉樹 } 65 在結(jié)點(diǎn)個(gè)數(shù)為 n (n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？ 【解答】結(jié)點(diǎn)個(gè)數(shù)為 n 時(shí)，高度最小的樹的高度為 1，有 2 層；它有 n1個(gè)葉結(jié)點(diǎn)， 1個(gè)分支結(jié)點(diǎn)；高度最大的樹的高度為 n1，有 n 層；它有 1 個(gè)葉結(jié)點(diǎn)， n1 個(gè)分支結(jié)點(diǎn)。 67 如果一棵樹有 n1 個(gè)度為 1的結(jié)點(diǎn) , 有 n2 個(gè)度為 2 的結(jié)點(diǎn) , … , nm 個(gè)度為 m 的結(jié)點(diǎn) , 試問(wèn)有多少個(gè)度為 0 的結(jié)點(diǎn) ? 試推導(dǎo)之。 【解答】 總結(jié)點(diǎn)數(shù) n = n0 + n1 + n2 + … + nm 總分支數(shù) e = n1 = n0 + n1 + n2 + … + nm1 = m*nm + (m1)*nm1 + … + 2*n2 + n1 則有 1)1(20 ??????? ?? ??mi inin 68 試分別找出滿足以下條件的所有二叉樹 : (1) 二叉樹的前序序列與中序序列相同 。 (2) 二叉樹的中序序列與后序序列相同 。 (3) 二叉樹的前序序列與后序序列相同。 【解答】 (1) 二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹； (2) 二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹； (3) 二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。 69 若用二叉鏈表作為二叉樹的存儲(chǔ)表示，試針對(duì)以下問(wèn)題編寫遞歸算法： (1) 統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。 (2) 以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女。 【解答】 (1) 統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)個(gè)數(shù) int BinaryTreeType :: leaf ( BinTreeNodeType * ptr ) { if ( ptr == NULL ) return 0。 else if ( ptrleftChild == NULL amp。amp。 ptrrightChild == NULL ) return 1。 else return leaf ( ptrleftChild ) + leaf ( ptrrightChild )。 } (2) 交換每個(gè)結(jié)點(diǎn)的左子女和右子女 void BinaryTreeType :: exchange ( BinTreeNodeType * ptr ) { BinTreeNodeType * temp。 if ( ptrleftChild != NULL || ptrrightChild != NULL ) { temp = ptrleftChild。 ptrleftChild = ptrrightChild。 ptrrightChild = temp。 exchange ( ptrleftChild )。 exchange ( ptrrightChild )。 } } 610 一棵高度為 h 的滿 k 叉樹有如下性質(zhì) : 第 h 層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn) , 其余各層上每個(gè)結(jié)點(diǎn)都有 k 棵非空子樹 , 如果按層次自頂向下 , 同一層自左向右 , 順序從 1 開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào) , 試問(wèn) : (1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少 ? (2) 編號(hào)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) (若存在 )的編號(hào)是多少 ? (3) 編號(hào)為 i 的結(jié)點(diǎn)的第 m 個(gè)孩子結(jié)點(diǎn) (若存在 )的編號(hào)是多少 ? (4) 編號(hào)為 i 的結(jié)點(diǎn)有右兄弟的條件是什么 ? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少 ? 【解答】 (1) ki ( i = 0, 1, …… , h ) (2) i kk? ???? ???2 (3) ( i1)*k + m + 1 (4) ( i1 ) mod k ? 0 或 i ? ? ???? ???i kk k2 *時(shí)有右兄弟，右兄弟為 i + 1。 611 試用判定樹的方法給出在中序線索化二叉樹上： 【解答】 (1) 搜索指定結(jié)點(diǎn)的在中序下的后繼。 設(shè)指針 q 指示中序線索化二叉樹中的指定結(jié)點(diǎn)，指針 p 指示其后繼結(jié)點(diǎn)。 找 q 的右子樹中在中序下的第一個(gè)結(jié)點(diǎn)的程序?yàn)椋? p = qrightChild。 while ( pleftThread == 1 ) p = pleftChild。 // p 即為 q 的后繼 (2) 搜索指定結(jié)點(diǎn)的在前序下的后繼。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1