49 49 49 83 47 41 47 59 83 59 43 47 41 43 83 43 59 41 41 41
47 43 49 47 43 83 59 59 49 83
(2)
59
43 43 43 47 59 47 49
47 41 49 83 83 49 41 83 59 41 47 59 49 59 49 47 83 43 41 43 41 83
2．
(1)初始序列
46，79，56，38，40，84 40，79，56，38，40，84
40，79，56，38，79，84 40，38，56，38，79，84 40，38，56，56，79，84 40，38，46，56，79，84 (2) 46 79 56
38 40 84 84 79 46
38 40 38 56 3．
(1)原序列16 15 20 53 64 7
15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 64 (2)
16
7 53
15 20 64
(3)平均查找长度=（1*1+2*2+3*3）/6=14/6
46 79 84 38 40 5684 79 56 40 46 4． (1)
5
2 14
4 6 3 7
(2)中序遍历
中序 2，3，4，5，6，7，14，16，18 5． 33 (1)
18
9 9 5 4
2 3
2 0000 3 0001 4 001 7 10 8 11 9 01
（2）2n-1个，因为非叶结点数比叶结点数少一个。 6．（1）dgbaechif （2）abdgcefhi （3）gdbeihfca
18 16 157 8 四、程序填空题 1． ?j<=n-1
?i<=n-j ?a[i]=a[i+1] ?a[i+1]=temp
?当某趟冒泡中没有出现交换则已排好序结束循环。
2． ?p
?q=p
?(NODE*)malloc(sizeof(NODE)) ?q->next ?p
3． ?printf(“%c”,BT->data);
?Preorder(BT->left); ? Preorder(BT->right);
4． ? Postorder(BT->left);
?Postorder(BT->right); ? printf(“%c”,BT->data);