2024年4月自考02142數(shù)據(jù)結構導論答案及評分參考

絕密★啟用前

2024年4月高等教育自學考試全國統(tǒng)一命題考試

數(shù)據(jù)結構導論試題答案及評分參考

（課程代碼02142）

一、單項選擇題：本大題共15小題，每小題2分，共30分。

1．B2．A3．B4．A5．D

6．B7．A8．C9．D10．B

11．C12．D13．D14．C15．C

二、填空題：本大題共13小題，每小題2分，共26分。

16．時空性

17．(n?1)/2

18．head?>next==head

19．24

20．2440

21．14

22．111

23．2(n?1)

24．12

25．18,32

26．7

27．24,39,72,98,45

28．24,39,45,98,72

三、應用題：本大題共5小題，每小題6分，共30分。

29．C，D，E，B，A；（2分）

C，D，B，E，A；（2分）

C，D，B，A，E。（2分）

數(shù)據(jù)結構導論試題答案及評分參考第1頁（共4頁）

30．所設計的哈夫曼樹如答30圖所示。（4分）

答30圖

每個字符對應的哈夫曼編碼分別為

A：0101B：11C：01111D：0110（1分）

E：00F：01110G：10H：0100（1分）

31．圖G的鄰接表存儲結構如答31圖所示。（圖中每行正確給1分，共6分）

答31圖

數(shù)據(jù)結構導論試題答案及評分參考第2頁（共4頁）

32．二叉排序樹如答32圖所示。（3分）

答32圖

后序遍歷序列為ACEDBHGF。（3分）

33．初始堆：5，23，16，58，94，72，61，87（2分）

第1趟：16，23，61，58，94，72，87，5（2分）

第2趟：23，58，61，87，94，72，16，5（2分）

四、算法設計題：本大題共2小題，每小題7分，共14分。

34．DataTypeminValue(LinkListL)

{

LinkListp,q;

p=L?>next;

q=p;//（初始化部分，2分）

while(p?>next!=NULL)//（循環(huán)語句及條件描述，1分）

{

if(p?>next?>data<q?>data)//（查最小值結點，2分）

q=p?>next;

p=p?>next;//（p指針后移，1分）

}

return(q?>data);//（返回最小值，1分）

}

數(shù)據(jù)結構導論試題答案及評分參考第3頁（共4頁）

35．intCountD2Node(BinTreebt)

{

intd;

if(!bt)return0;//（對于空樹，結點數(shù)為0，2分）

d=CountD2Node(bt?>lchild)+CountD2Node(bt?>rchild);

//（遞歸求左右子樹結點數(shù)，3分）

if(bt?>lchild&&bt?>rchild)

returnd+1;//（度為2的結點處理，1