数据结构复习题习题全六章含答案

8. 6

9. 2i、2i+1、? i/2? 10. 16 11. 5、18

12. a、f、空结点(即无右孩子结点) 13. 4、2、3

14. a[2*i]、a[2*i+1]、a[i/2] 15. 2i-1、2j+1

16. A[2*i+1]、a[2*i+2]、a[i/2] 17. 2n、n-1、n+1 18. 10、5

19. abcdef、cbaedf、cbefda、abdcef 20. abecfhijgd、abcdefghij 二、应用题

1．void Request( int A[] , int n , int i ) {

if ( i>n ) {

cerr <<”编号为”<

cout <<”当前结点为”<

int j = i/2; // 下标为j的结点是下标为i结点的双亲 if ( j>0 )

cout <<”双亲：”<

cout <<”树根没有双亲结点！”<

cout <<”左孩子：”<

else if ( 2*i == n ) {

cout <<”左孩子：”<

cout <<”无孩子！”<

．void Count( BTreeNode * BT , int & C1 , int & C2 ) {

if ( BT != NULL ) {

C1++; // 统计所有结点数

if ( BT->left == NULL && BT->right == NULL ) C2++; // 统计叶子结点数 Count( BT->left , C1 , C2 ); Count( BT->right , C1 , C2 ); }

}

2 }

3．(1) abecfgkdhilmj (2) abcdefghijklm (3)

第六章 二叉树的应用

一、 单选题

1. C 2. B 3. D 4. C 5. A 6. D 二、填空题

1. 小于、大于等于 2. 按升序排列的有序序列 3. 找到、左子树、右子树 4. 2i+1、2i+2 5. 最小值、最大值 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 四、算法设计

1．bool Find( BTreeNode * BST , ElemType & item )

{

while ( BST != NULL ) {

if ( item == BT->data ) { // 到

item = BST->data; return true;

}

else if (itemdata) BST=BST->left; // 找转