數(shù)據(jù)結(jié)構(gòu)期末考試試卷(通信14)-A答案及評(píng)分標(biāo)準(zhǔn)

1、 20152016學(xué)年第1學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法試卷答案及評(píng)分標(biāo)準(zhǔn) 專業(yè)班級(jí)通信1401-02 姓名 學(xué)號(hào) 開課系室計(jì)通學(xué)院軟件工程系 考試日期2015-11-08 題號(hào) 一 二 三 四 五 總分 得分 閱卷人 一、填空題（每空1分，共10分） 1尾首 2. 0（1）0（n） 3. 128208 4. abedc abcde 5. 2n n+1 二、單項(xiàng)選擇題（每題 2分，共20分） 1、C2、B3、D4、A 5、A 6、C7、A8、C9、C10、D 三、應(yīng)用題（每小題10分，共40分） 1、已知一棵二叉樹的前序遍歷的結(jié)果是 ABKCDFGHIJ,中序遍歷的結(jié) 果是KBCDAFHIGJ試畫出這棵

2、二叉樹，并保留中間過程。 當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時(shí)，逐步 形成二叉樹的過程如下圖所示： （評(píng)分說明：每個(gè)結(jié)點(diǎn)位置正確得1分） 2. 2.某帶權(quán)有向圖如下: 1）試畫出它的鄰接表表示法示意圖。 2）根據(jù)鄰接表表示法示意圖試寫出它的深度優(yōu)先搜索序列 （1）鄰接表表示法示意圖 （評(píng)分說明：數(shù)組正確得1分，每個(gè)鏈表0.5分）。 （2）深度優(yōu)先搜索序列：A，B，D，C，F(xiàn), E, G, H（3分） 3. 假定用于通信的電文僅由8個(gè)字母c1, c2, c3, c4, c5, c6, c7, c8組成，各字母在電文中出現(xiàn)的頻率分別為 5, 25, 3, 6, 10,

3、 11, 36, 4。 試為這8個(gè)字母設(shè)計(jì)不等長(zhǎng)Hufman編碼，并給出該電文的總長(zhǎng) 度。 已知字母集 1 :61 C5 next; q=p-next;(3 分) s=q-next; p-next=NULL; (3 分) while(s-next) q-next=p; p=q; q=s; s=s-next; /把 L 的元素逐個(gè)插入新表表頭 (6 分) q-next=p; L-next=q;(3 分) /LinkList_reverse 2、請(qǐng)寫出利用棧對(duì)二叉樹進(jìn)行中根遍歷的非遞歸算法。 typedef struct BiTNode / c 語言的結(jié)點(diǎn)結(jié)構(gòu) TElemType data; st

4、ruct BiTNode *l child, *r child; / 左右孩子指針 BiTNode, * BiTree; void PreOrder_No nrecursive(Bitree T)中序遍歷二叉樹的非遞歸算法 InitStack(S); Push(S,T); /根指針進(jìn)棧(4 分) while(!StackEmpty(S) while(Gettop(S,p) /向左走到盡頭(3 分) pop(S,p);(3 分) if(!StackEmpty(S) pop(S,p); visit(p-data); push(S,p-rchild); /向右一步 /while(5 分) /PreOrder_Nonrecursive 如果給 而 評(píng)分說明： 以上僅為參考評(píng)分標(biāo)準(zhǔn)， 評(píng)卷老師可