数据结构（本）期末综合练习（2013年6月）

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

(3)平均查找长度=（1*1+2*2+3*3）/6=14/6

2．（1）

16 42 32

52 82 67 57

102

图8

（2）102，52，42，82，16，67，32，57 3． (1) 5 2 14 4 6 18

3 7 16 33

图9

(2)中序遍历

中序 2，3，4，5，6，7，14，16，18 4．

(1)原序列16 15 20 53 64 7

15 16 20 53 7 64 15 16 20 7 53 64 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

图10

(3)平均查找长度=（1*1+2*2+3*3）/6=14/6 5．（1）答

18

11 7

6 5 3 4

3 3 2 1 34

wpl1=45

图11

（2）答 18

7 11

3 4 6 5

2 1 3 3 wpl2=45

图12

6．（1） 50 38 82 16 64 110 13 图13 （2）三次；四次

四、程序填空题 1． （1）&a

（2）d?next=NULL （3）p->data （4）p=p->next （5）p!=NULL 2．（1）malloc(sizeof (struct node))

35

（2）rear->next=p （3）p

3．

（1）Postorder(BT->left) （2）Postorder(BT->right) （3） printf(“%c”,BT->data) 4．（1）j

（2）q=q->next （3）q->next （4）q->next （5）p 36