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

1、 20152016學(xué)年第1學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法試卷答案及評分標(biāo)準 專業(yè)班級通信1401-02 姓名 學(xué)號 開課系室計通學(xué)院軟件工程系 考試日期2015-11-08 題號 一 二 三 四 五 總分 得分 閱卷人 一、填空題（每空1分，共10分） 1尾首 2. 0（1）0（n） 3. 128208 4. abedc abcde 5. 2n n+1 二、單項選擇題（每題 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時，逐步 形成二叉樹的過程如下圖所示： （評分說明：每個結(jié)點位置正確得1分） 2. 2.某帶權(quán)有向圖如下: 1）試畫出它的鄰接表表示法示意圖。 2）根據(jù)鄰接表表示法示意圖試寫出它的深度優(yōu)先搜索序列 （1）鄰接表表示法示意圖 （評分說明：數(shù)組正確得1分，每個鏈表0.5分）。 （2）深度優(yōu)先搜索序列：A，B，D，C，F(xiàn), E, G, H（3分） 3. 假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, c7, c8組成，各字母在電文中出現(xiàn)的頻率分別為 5, 25, 3, 6, 10,

3、 11, 36, 4。 試為這8個字母設(shè)計不等長Hufman編碼，并給出該電文的總長 度。 已知字母集 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 的元素逐個插入新表表頭 (6 分) q-next=p; L-next=q;(3 分) /LinkList_reverse 2、請寫出利用棧對二叉樹進行中根遍歷的非遞歸算法。 typedef struct BiTNode / c 語言的結(jié)點結(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); /根指針進棧(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 如果給 而 評分說明： 以上僅為參考評分標(biāo)準， 評卷老師可