數據結構c語言版章節練習題(16章)-資料下載頁

　　

【正文】 2),(6,4,6) )1 2 2 3 4 5 5 62 4 7 1 4 2 6 44 3 1 8 5 7 2 6 (2) (3) ((1,3,8),(2,1,4),(2,5,7),(4,2,3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1))1 2 2 4 4 4 6 73 1 5 2 4 6 5 28 4 7 3 5 6 2 12．(1) A：長度：1 深度：2 (2) B：長度：3 深度：1 (3) C：長度：2 深度：3 (4) D：長度：2 深度：2 (5) E：長度：3 深度：3 (6) F：長度：1 深度：4第四章 棧和隊列 一、單選題1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D二、填空題、隊首 (LIFO)、先進先出(FIFO) 、存儲 、棧頂指針5. front = = rear 、(rear+1)%QueueMaxSize = = front 6. 1 、StackMaxSize17. 棧空、空隊、隊列只有一個元素 、棧頂指針 9. 指針域、棧頂指針 、存儲 = = 0 next = HS 、HS = p 13. HS = HSnext14. ( front = = rear ) amp。amp。 ( front NULL ) 15. 3 4 25 6 15 + / 8 * +16. (24+8)*3/(4*(107)) 、8三、應用題 12 15 5 30 18四、編程題遞歸算法：long Fib( int n ) {if ( n==1 || n=2 ) // 終止遞歸條件 return 1。else return Fib(n1)+Fib(n2)。}非遞歸算法：long Fib( int n ) {int a , b , c。 // c代表當前項，a和b分別代表當前項前面的第2項和第1項a = b = 1。if ( n == 1 || n == 2 ) return 1。else for ( int i = 3 。 i=n 。 i++ ) { c = a+b。 // 求當前項 a = b。 // 產生第2項 b = c。 // 產生第1項 }return c。 // 返回所求的第n項} 遞歸算法的時間復雜度為 O(2n)，空間復雜度為 O(n)；非遞歸算法的時間復雜度為 O(n)，空間復雜度為 O(1)。第五章 樹和二叉樹一、填空題 、50 3. 6 、21 、3 、6 、I和J 9. 2i、2i+? i/2? 、18 、f、空結點(即無右孩子結點) 13. 314. a[2*i]、a[2*i+1]、a[i/2] 15. 2i2j+1 16. A[2*i+1]、a[2*i+2]、a[i/2] 、nn+1 、5 19. abcdef、cbaedf、cbefda、abdcef 20. abecfhijgd、abcdefghij二、應用題1．void Request( int A[] , int n , int i ) {if ( in ) { cerr 編號為i的結點不存在！endl。 exit(1)。}cout 當前結點為A[i]endl。int j = i/2。 // 下標為j的結點是下標為i結點的雙親if ( j0 ) cout 雙親：A[j]endl。else cout 樹根沒有雙親結點！endl。if ( 2*i n ) { cout 左孩子：A[2*i]endl。 cout 右孩子：A[2*i+1]endl。}else if ( 2*i == n ) { cout 左孩子：A[2*i]endl。 cout 無右孩子！endl。}else cout 無孩子！endl。 } 2．void Count( BTreeNode * BT , int amp。 C1 , int amp。 C2 ) {if ( BT != NULL ) { C1++。 // 統計所有結點數 if ( BTleft == NULL amp。amp。 BTright == NULL ) C2++。 // 統計葉子結點數 Count( BTleft , C1 , C2 )。 Count( BTright , C1 , C2 )。} } 3．(1) abecfgkdhilmj (2) abcdefghijklm (3) 第六章 二叉樹的應用一、單選題1. C 2. B 3. D 4. C 5. A 6. D二、填空題1. 小于、大于等于2. 按升序排列的有序序列3. 找到、左子樹、右子樹4. 2i+2i+25. 最小值、最大值6. 堆尾、堆頂、向下三、應用題 1. 2. 初態：空堆 ( ) 插入38后：( 38 ) 插入64后：( 38 , 64 ) 插入52后：( 38 , 64 , 52 ) 插入15后：( 15 , 38 , 52 , 64 ) 插入73后：( 15 , 38 , 52 , 64 , 73 ) 插入40后：( 15 , 38 , 40 , 64 , 73 , 52 ) 插入48后：( 15 , 38 , 40 , 64 , 73 , 52 , 48 ) 插入55后：( 15 , 38 , 40 , 55 , 73 ,52 , 48 , 64 ) 插入26后：( 15 , 26 , 40 , 38 , 73 ,52 , 48 , 64 , 55 ) 插入12后：( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 , 55 ,73 ) 3. 初態堆：( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 ) 刪除第1個元素后堆：( 15 , 26 , 40 , 38 , 64 , 52 , 48 ) 刪除第2個元素后堆：( 26 , 38 , 40 , 48 , 64 , 52 ) 刪除第3個元素后堆：( 38 , 48 , 40 , 52 , 64 ) 刪除第4個元素后堆：( 40 , 48 , 64 , 52 ) 4. 哈夫曼樹： WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131