數(shù)據(jù)結(jié)構(gòu)模擬試題4參考答案

1、數(shù)據(jù)結(jié)構(gòu)模擬試題4參考答案一、選擇題（20分）1-5 ACAB D6-10BB CA D二、填空題（20分）1n2只由空格字符組成的字符串空格字符的個(gè)數(shù)3534k(k+1)/253677128二叉樹(shù)無(wú)左子樹(shù)三、應(yīng)用題（30分）1參考答案如下： 523020686070502參考答案如下： 1）3456791082）9438107656894510376438 579103參考答案如下：HT的初態(tài) HT的終態(tài)30003800120001212007000710004000490020002800800081000110001111000005951000911480001512360002013

2、97000271321000047011124參考答案如下： 1） 2）始點(diǎn)終點(diǎn)最短路徑長(zhǎng)度CA無(wú)CB無(wú)CDC，D3CEC，D，F(xiàn)，E11CFC，D，F(xiàn)85參考答案如下： 1）哈希表a及其生成過(guò)程如下：19：524：310：3，417：3，4，5，615：138：3，4，5，6，718：4，5，6，7，840：5，6，7，8，9ASL=（1+1+2+4+1+5+5+5）/8=24/8=3 0 1 2 3 4 5 6 7 8 9 15 24 10 1 9 17 38 18 402）哈希表b及其生成過(guò)程如下：19：524：310：3，417：3，4，215：138：3，4，2，718：4，5，3，

3、840：5，6，4，9ASL= 0 1 2 3 4 5 6 7 8 9 15 17 24 10 19 38 18 406參考答案如下：EFABDCG四算法設(shè)計(jì)題（30分）1算法源代碼如下： void delete(link h) link q, p; p=h-next; while(p!=NULL) q=p; p=p-next; while(p-data=q-data) q-next=p-next; free(p); p=q-next; 2算法源代碼如下： void huffmancode(htnode *ht, int m, char *hc, int n) int i,start,c,p; char cdm; cdm-1=0; for(i=0;in;+i) start=m-1; c=i; p=hti.parent; while(p!=-1) if(htp.lchild=c) cd-start=0; else cd-start=1; c=p; p=htp.parent; strcpy(hci,&cdstart); 3算法源代碼如下： int idk(algraph graph, int k) arcptr p; int count=0, i