數據結構c語言版章節練習題(16章)(編輯修改稿)

　

【文章內容簡介】 _____，右孩子元素為________，雙親元素(i1)為________。15．假定一棵二叉樹順序存儲在一維數組a中，但讓編號為1的結點存入a[0]元素中，讓編號為2的結點存入a[1]元素中，其余類推，則編號為i結點的左孩子結點對應的存儲位置為________，若編號為i結點的存儲位置用j表示，則其左孩子結點對應的存儲位置為________。16．若對一棵二叉樹從0開始進行結點編號，并按此編號把它順序存儲到一維數組a中，即編號為0的結點存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i0)為________。17．對于一棵具有n個結點的二叉樹，對應二叉鏈表中指針總數為________個，其中________個用于指向孩子結點，________個指針空閑著。18．一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k))))，該樹的結點數為________個，深度為________。19．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，則對它進行的先序遍歷結果為____________，中序遍歷結果為____________，后序遍歷結果為____________，按層遍歷結果為____________。20．假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結果為____________，按層遍歷結果為___________。二、應用題1．已知一棵具有n個結點的完全二叉樹被順序存儲于一維數組的A[1]~A[n]元素中，試編寫一個算法打印出編號為i的結點的雙親和所有孩子。2．編寫一算法，求出一棵二叉樹中所有結點數和葉子結點數，假定分別用變參C1和C2統計所有結點數和葉子結點數，初值均為0。第六章 二叉樹的應用（二）一、單選題1. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為________。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)2. 向二叉搜索樹中插入一個元素時，其時間復雜度大致為________。 A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n)3. 根據n個元素建立一棵二叉搜索樹時，其時間復雜度大致為________。 A、 O(n) B、 O(log2n ) C、 O(n2) D、 O(nlog2n)4. 從堆中刪除一個元素的時間復雜度為________。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n)5. 向堆中插入一個元素的時間復雜度為________。 A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)6. 由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為________。 A、 24 B、 48 C、 72 D、 53二、填空題 1. 在一棵二叉搜索樹中，每個分支結點的左子樹上所有結點的值一定________該結點的值，右子樹上所有結點的值一定________該結點的值。2．對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個________。3．從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明_______，若元素的值小于根結點的值，則繼續向________查找，若元素的大于根結點的值，則繼續向________查找。4．在一個堆的順序存儲中，若一個元素的下標為i，則它的左孩子元素的下標為______，右孩子元素的下標為________。5. 在一個小根堆中，堆頂結點的值是所有結點中的________，在一個大根堆中，堆頂結點的值是所有結點中的________。6．當從一個小根堆中刪除一個元素時，需要把________元素填補到________位置，然后再按條件把它逐層________調整。三、應用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態。3. 已知一個堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態。4. 有七個帶權結點，其權值分別為3,7,8,2,6,10,14，試以它們為葉子結點構造一棵哈夫曼樹，并計算出帶權路徑長度WPL。數據結構期末復習練習題答案（僅供參考）第一章 緒 論一、單選題1. A 2. C 3. B 4. C 5. D 6. B 二、填空題1. 集合結構、線性結構、樹型結構、圖形結構 、鏈式 3. 1:1:N、M:N 、操作聲明 (或指針形參 ) ( 或 指針類型 ) 、值 、 、rand( ) %21 10. sizeof(a)、a+i*sizeof(a[0])、a+i11. 參數類型、數量、次序 12. 用戶自定義 13. = = 、ra 、rb 14. O(n)、O(m*n)15. n、n(n+1)/O(n2) 16. O(n)第二章 線性表 一、單選題1. B 2. A 3. C 4. B 5. D 6. C二、填空題、指針 2.( 38,56,25,60,42,74) 3. O(n)、O(1) 4.(1)、O(n) 、i+1pnext 、a[p].next 、后繼 、表頭 10．HLnext = = NULL 、HLnext = = HL三、應用題1.(1) ( 79 , 62 , 34 , 57 , 26 , 48 ) (2) ( 26 , 34 , 48 , 57 , 62 , 79 ) (3) ( 26, 34 , 39 , 48 , 57 , 62 )2．12，26，9，8，15，30，50）3．(1) ElemType DMValue( List amp。 L ) {if ( ListEmpty(L) ) { // 空線性表 cerr List is Empty!endl。 exit(1)。}ElemType x。 // x存放最小元素x = [0]。int k = 0。 // k存放最小元素的下標for ( int i = 1。 i。 i++ ) // 查找最小元素 if ( [i] x ) { x = [i] 。 k = i。 }[k] = []。 // 最后一個元素填補最小元素位置。 // 線性表長度減1return x。 // 返回最小元素 }2)ElemType Delete( List amp。 L, int i ) { if ( i1 || i )