算法與數(shù)據(jù)結(jié)構(gòu)-參考答案-A卷

石家莊鐵道大學(xué)2013-2014學(xué)年第1學(xué)期

2012級本科期末考試答案（A）

12345678910

CACBBCBDDB

（15分）（酌情給分）

（1）赫夫曼樹（7分）

FE

（2）每個字母的赫夫曼編碼（3分）

A:010B:101C:00D:011E:10001F:10000G:1001H:1

（3）赫夫曼樹存儲結(jié)構(gòu)的終態(tài)（5分）

結(jié)點iweightparentIchildrchild

10.091100

20.161200

30.201300

40.121100

50.03900

60.02900

70.081000

80.301400

90.051065

100.131297

110.211314

120.2914102

130.4115311

140.5915128

15101314

2.（10分）（酌情給分）

（1）構(gòu)造Hash表（8分）

下標0123456789101112131415

數(shù)據(jù)26133426933923115138

比較12122111112

次數(shù)

(2)ASLsucc=(1/11)(1*7+2*4)=1.36(2分)

3.（10分）（酌情給分）

（1）鄰接矩陣。（5分）

0023000000

2000000915

3000011006

00001100004

00900000000

0015640000

（2）最小生成樹（給出簡要的構(gòu)造過程）（5分）

構(gòu)造過程:

第1步第2步

第5步

4.40分）（酌情給分）

（1）采用快速排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（5分）

下標012345678910

初始序列{391281262451701945}

第1趟排序結(jié)果39(1912812624}39{705145}

第2趟排序結(jié)果19{6112}19{2824}39{705145}

第3趟排序結(jié)果6{1}6{12)19{2824)39{705145}

第4趟排序結(jié)果28161219{24}2839{705145)

第5趟排序結(jié)果70161219242839{4551}70

第6趟排序結(jié)果4516121924283945{51)70

（2）采用二路歸并排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（5分）

初始序列139J[1J[28][12][6J124][51J[70][19J[45

第1趟排序結(jié)果[139][1228][624][5170][1945]

第2趟排序結(jié)果[1122839][6245170][1945]

第3趟排序結(jié)果[16122428395170][1945]

第4趟排序結(jié)果[161219242839455170J

（1）二叉樹（分析寫出過程）（6分）

A

分析過程：

前序遍歷序列：ABDHEICFJGK

中序遍歷序列：DHB1EAJFCKG

A的左子樹的前序遍歷序列：BDHEIA的右子樹的前序遍歷序列：CFJGK

A的左子樹的中序遍歷序列：DHBIEA的右子樹的中序遍歷序列：JFCKG

B的左子樹的前序遍歷序列：DHC的左子樹的前序遍歷序列：FJ

B的左子樹的中序遍歷序列：DHC的左子樹的中序遍歷序列：JF

B的右子樹的前序遍歷序列：EIC的右子樹的前序遍歷序列：GK

B的右子樹的中序遍歷序列：IEC的右子樹的中序遍歷序列：KG

(2)后序遍歷序列：HDIEBJFKGCA(4分)

(3)森林：(5分)

1.單鏈表問題答案(答案不惟一)

TypedefstructNode{

chardata;

delete(q);

structnode*next;

}Node,*LinkList;)

elsep=p->next;

〃沒有頭結(jié)點的代碼實現(xiàn)

)

voiddelete_node(LinkListL)

(

2.二叉樹問題(答案不惟一)

LinkListp,q;

TypedefstructBitNode)

P=L;

intdata;

while(p->next!=NULL)

StructBitNode*lchild,*rchild;

(

}BitNode,*BiTree;

q=p->next;

intcount(BiTreet,inta)

if(q->data>