線性數(shù)學(xué)試題解答6(編輯修改稿)
2024-10-10 21:16 本頁面
【文章內(nèi)容簡介】 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é)點個數(shù)為 n (n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？ 【解答】結(jié)點個數(shù)為 n 時，高度最小的樹的高度為 1，有 2 層；它有 n1個葉結(jié)點， 1個分支結(jié)點；高度最大的樹的高度為 n1，有 n 層；它有 1 個葉結(jié)點， n1 個分支結(jié)點。 67 如果一棵樹有 n1 個度為 1的結(jié)點 , 有 n2 個度為 2 的結(jié)點 , … , nm 個度為 m 的結(jié)點 , 試問有多少個度為 0 的結(jié)點 ? 試推導(dǎo)之。 【解答】 總結(jié)點數(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é)點的二叉樹。 69 若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法： (1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。 (2) 以二叉樹為參數(shù)，交換每個結(jié)點的左子女和右子女。 【解答】 (1) 統(tǒng)計二叉樹中葉結(jié)點個數(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) 交換每個結(jié)點的左子女和右子女 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é)點都是葉結(jié)點 , 其余各層上每個結(jié)點都有 k 棵非空子樹 , 如果按層次自頂向下 , 同一層自左向右 , 順序從 1 開始對全部結(jié)點進行編號 , 試問 : (1) 各層的結(jié)點個數(shù)是多少 ? (2) 編號為 i 的結(jié)點的父結(jié)點 (若存在 )的編號是多少 ? (3) 編號為 i 的結(jié)點的第 m 個孩子結(jié)點 (若存在 )的編號是多少 ? (4) 編號為 i 的結(jié)點有右兄弟的條件是什么 ? 其右兄弟結(jié)點的編號是多少 ? 【解答】 (1) ki ( i = 0, 1, …… , h ) (2) i kk? ???? ???2 (3) ( i1)*k + m + 1 (4) ( i1 ) mod k ? 0 或 i ? ? ???? ???i kk k2 *時有右兄弟，右兄弟為 i + 1。 611 試用判定樹的方法給出在中序線索化二叉樹上： 【解答】 (1) 搜索指定結(jié)點的在中序下的后繼。 設(shè)指針 q 指示中序線索化二叉樹中的指定結(jié)點，指針 p 指示其后繼結(jié)點。 找 q 的右子樹中在中序下的第一個結(jié)點的程序為： p = qrightChild。 while ( pleftThread == 1 ) p = pleftChild。 // p 即為 q 的后繼 (2) 搜索指定結(jié)點的在前序下的后繼。
公司管理相關(guān)推薦
鄂ICP備17016276號-1