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

PAGEPAGE1石家莊鐵道大學(xué)2013-2014學(xué)年第1學(xué)期2012級本科期末考試答案（A）12345678910CACBBCBDDB1．（15分）（酌情給分）（1）赫夫曼樹（7分）0.4110.4110.590.200.210.290.300.090.120.130.160.050.080.020.03ADCFEGBH01010101010101（2）每個字母的赫夫曼編碼（3分）A:010B:101C:00D:011E:10001F:10000G:1001H:1（3）赫夫曼樹存儲結(jié)構(gòu)的終態(tài)（5分）結(jié)點iweightparentlchildrchild10.09110020.16120030.20130040.12110050.0390060.0290070.08100080.30140090.051065100.131297110.211314120.2914102130.4115311140.5915128151013142．（10分）（酌情給分）（1）構(gòu)造Hash表（8分）下標0123456789101112131415數(shù)據(jù)26133426933923115138比較次數(shù)12122111112（2）ASLsucc=（1/11）（1*7+2*4）=1.36（2分）3．（10分）（酌情給分）（1）鄰接矩陣。（5分）（2）最小生成樹（給出簡要的構(gòu)造過程）（5分）123123456239461234562112345623第1步第2步121234562346123456234第3步第4步112345623946第5步4．（10分）（酌情給分）（1）采用快速排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（5分）下標 0 1 2 3 4 5 6 7 8 9 10初始序列 {39 1 28 12 6 24 51 70 19 45}第1趟排序結(jié)果 39 {19 1 28 12 6 24} 39 {70 51 45}第2趟排序結(jié)果 19{6 1 12} 19 {28 24} 39 {70 51 45}第3趟排序結(jié)果 6 {1} 6{12} 19 {28 24} 39 {70 51 45}第4趟排序結(jié)果 28 1 6 12 19 {24} 28 39 {70 51 45}第5趟排序結(jié)果 70 1 6 12 19 24 28 39 {45 51} 70第6趟排序結(jié)果451 6 12 19 24 28 39 45{51} 70（2）采用二路歸并排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（5分）初始序列 [39] [1] [28] [12] [6] [24] [51] [70] [19] [45第1趟排序結(jié)果 [1 39] [12 28] [6 24] [51 70] [19 45]第2趟排序結(jié)果 [1 12 28 39] [6 24 51 70] [19 45]第3趟排序結(jié)果 [1 6 12 24 28 39 51 70] [19 45]第4趟排序結(jié)果 [1 6 12 19 24 28 39 45 51 70] （1）二叉樹（分析寫出過程）（6分）分析過程：前序遍歷序列：ABDHEICFJGK中序遍歷序列：DHBIEAJFCKGA的左子樹的前序遍歷序列：BDHEIA的右子樹的前序遍歷序列：CFJGKA的左子樹的中序遍歷序列：DHBIEA的右子樹的中序遍歷序列：JFCKGB的左子樹的前序遍歷序列：DHC的左子樹的前序遍歷序列：FJB的左子樹的中序遍歷序列：DHC的左子樹的中序遍歷序列：JFB的右子樹的前序遍歷序列：EIC的右子樹的前序遍歷序列：GKB的右子樹的中序遍歷序列：IEC的右子樹的中序遍歷序列：KG（2）后序遍歷序列：HDIEBJFKGCA（4分）（3）森林：（5分）1.單鏈表問題答案(答案不惟一)TypedefstructNode{delete(q);}elsep=p->next;delete(q);}elsep=p->next;}2.二叉樹問題(答案不惟一)TypedefstructBitNode{intdata;StructBitNode*lchild,*rchild;}BitNode,*BiTree;intcount(BiTreet,inta){ if(t)//或條件為t==NULLreturn0; elsereturncount(t->lchild)+count(t->rchild)+(t->data<a);}structnode*next;}Node,*LinkList;//沒有頭結(jié)點的代碼實現(xiàn)voiddelete_node