数据结构练习题及参考答案

14. ( front = = rear ) && ( front <>NULL ) 15. 3 4 25 6 15 + - / 8 * + 16. (24+8)*3/(4*(10-7)) 、8 三、应用题

12 15 5 30 18 四、编程题

递归算法：

long Fib( int n ) {

if ( n==1 || n=2 ) A 2. B 二、填空题

1. 行号、列号、元素值 2. 行号、列号 3. 引用 (或指针) 4. 等于 5. 4 、5

6. 列号、行号 7. 单、表 8. 括号 9. 3

10. 元素值、子表指针 11. true、NULL 三、应用题

1．(1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) ) (2) 1 2 2 3 4 5 5 6

2 4 7 1 4 2 6 4

4 -3 1 8 5 -7 2 6

(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 7

3 1 5 2 4 6 5 2

8 4 -7 -3 5 6 2 1

2． (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. n-1 2. 5 、 50 3. 6

4. 31、21 5. 10、4、3 6. 2、1、1、6 7. B、I和J 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; 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 ) { ey )

return mid; ey )

return Binsch( A , low , mid-1 , K ); ey ) return mid; ey ) high = mid-1; tn<

QuickSort( A,s,j-1)

QuickSort( A,j+1,t)