《数据结构教学资料》数据结构a参考答案

《《数据结构教学资料》数据结构a参考答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构(A)试卷参考答案一.判断题：(每小题2分，共20分)1.X2・J3・X4・X5・X6.J7・X8・J9.V10.V二选择题：(每小题2分，共10分)1.(1)2.(2)3・(4)4.(3)5・(3)三.填空题：(每空2分，共10分)1.0(1),O(N)2.12233344442.313.N-1四.应用题：(每小题6分，共30分)1・(6分)2.（6分）3.(6分)构造哈夫曼树:（3分）7恥44卩哈夫曼编码为：（3分）5：10107：10119：10016：0018：0123：114.直接插入排序过程：(3分)初始序列：(18)311622513024i=2

2、:(1831)1622513024i=3:(161831)22513024i=4:(16182231)513024i=5:(1618223151)30246:(161822303151)24i=7:(16182224303151)堆排序过程：(3分)16p18p16心18p堆排序的结果为：161822243031515.图：（3分）最小生成树：（3分）算法设计:五.（每小题10分，共20分）1•intcountleaf(BiTreeT){if(!T)return0;2分elseif(!T—>lchild)&&(!T—>rchild)return1;2分elseretu

3、rn(countleaf(T—>lchild)+countleaf(T—>rchild));6分}2.voidzhengxu(Sqlist&L,intn){L.r[0]=L.r[low];2分low=l;high=n;while(low

4、low]=L.r[0];}算法的时间复杂度为

5、0(11)。3.、voidreverse_merge(Linklist&A,Linklist&B,Linklist&C){pa=A->next;pb=B->next;pre=NULL;2分while(pa

6、

7、pb)6分{if(pa->data<=pb->data

8、

9、!pb){pc=pa;q=pa->next;pa->next=pre;pa=q;}else{pc二pb;q=pb->next;pb->next二pre;pb=q;}pre=pc;}C=A;A->next=pc;2分}//reverse_merge