2024年4月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案含評(píng)分標(biāo)準(zhǔn)

絕密★啟用前

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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考

（課程代碼02142）

一、單項(xiàng)選擇題：本大題共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．時(shí)空性

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

三、應(yīng)用題：本大題共5小題，每小題6分，共30分。

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

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

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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第1頁（共4頁）

30．所設(shè)計(jì)的哈夫曼樹如答30圖所示。（4分）

答30圖

每個(gè)字符對(duì)應(yīng)的哈夫曼編碼分別為

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

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

31．圖G的鄰接表存儲(chǔ)結(jié)構(gòu)如答31圖所示。（圖中每行正確給1分，共6分）

答31圖

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第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分）

四、算法設(shè)計(jì)題：本大題共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)//（查最小值結(jié)點(diǎn)，2分）

q=p?>next;

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

}

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

}

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題答案及評(píng)分參考第3頁（共4頁）

35．intCountD2Node(BinTreebt)

{

intd;

if(!bt)return0;//（對(duì)于空樹，結(jié)點(diǎn)數(shù)為0，2分）

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

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

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

returnd+1;//（度為2的結(jié)點(diǎn)處理，1