數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版章節(jié)練習(xí)題(16章)(編輯修改稿)
2025-04-21 03:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 _____，右孩子元素為________，雙親元素(i1)為________。15．假定一棵二叉樹順序存儲(chǔ)在一維數(shù)組a中，但讓編號(hào)為1的結(jié)點(diǎn)存入a[0]元素中，讓編號(hào)為2的結(jié)點(diǎn)存入a[1]元素中，其余類推，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為________，若編號(hào)為i結(jié)點(diǎn)的存儲(chǔ)位置用j表示，則其左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為________。16．若對(duì)一棵二叉樹從0開始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組a中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i0)為________。17．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)應(yīng)二叉鏈表中指針總數(shù)為________個(gè)，其中________個(gè)用于指向孩子結(jié)點(diǎn)，________個(gè)指針空閑著。18．一棵二叉樹廣義表表示為a(b(d(,h)),c(e,f(g,i(k))))，該樹的結(jié)點(diǎn)數(shù)為________個(gè)，深度為________。19．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，則對(duì)它進(jìn)行的先序遍歷結(jié)果為____________，中序遍歷結(jié)果為____________，后序遍歷結(jié)果為____________，按層遍歷結(jié)果為____________。20．假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結(jié)果為____________，按層遍歷結(jié)果為___________。二、應(yīng)用題1．已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹被順序存儲(chǔ)于一維數(shù)組的A[1]~A[n]元素中，試編寫一個(gè)算法打印出編號(hào)為i的結(jié)點(diǎn)的雙親和所有孩子。2．編寫一算法，求出一棵二叉樹中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，假定分別用變參C1和C2統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，初值均為0。第六章 二叉樹的應(yīng)用（二）一、單選題1. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為________。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)2. 向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為________。 A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n)3. 根據(jù)n個(gè)元素建立一棵二叉搜索樹時(shí)，其時(shí)間復(fù)雜度大致為________。 A、 O(n) B、 O(log2n ) C、 O(n2) D、 O(nlog2n)4. 從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為________。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n)5. 向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為________。 A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)6. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為________。 A、 24 B、 48 C、 72 D、 53二、填空題 1. 在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定________該結(jié)點(diǎn)的值。2．對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)________。3．從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_______，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向________查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向________查找。4．在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為______，右孩子元素的下標(biāo)為________。5. 在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的________。6．當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把________元素填補(bǔ)到________位置，然后再按條件把它逐層________調(diào)整。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個(gè)元素，請(qǐng)以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。3. 已知一個(gè)堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個(gè)元素，請(qǐng)給出每刪除一個(gè)元素后堆的狀態(tài)。4. 有七個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL。數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)練習(xí)題答案（僅供參考）第一章 緒 論一、單選題1. A 2. C 3. B 4. C 5. D 6. B 二、填空題1. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu) 、鏈?zhǔn)? 3. 1:1:N、M:N 、操作聲明 (或指針形參 ) ( 或 指針類型 ) 、值 、 、rand( ) %21 10. sizeof(a)、a+i*sizeof(a[0])、a+i11. 參數(shù)類型、數(shù)量、次序 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三、應(yīng)用題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存放最小元素的下標(biāo)for ( int i = 1。 i。 i++ ) // 查找最小元素 if ( [i] x ) { x = [i] 。 k = i。 }[k] = []。 // 最后一個(gè)元素填補(bǔ)最小元素位置。 // 線性表長(zhǎng)度減1return x。 // 返回最小元素 }2)ElemType Delete( List amp。 L, int i ) { if ( i1 || i )
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1