資料結構與演算法a卷答案
一、 選擇題（本題共20小題，每題2分，共40分）
二、分析運算題（本題共6小題，每題6分，共36分）
(1) 如果輸入序列為6 5 4 3 2 1,試問能否通過棧結構得到以下兩個序列3 4 6 5 2 1和2 3 4 1 5 6;請說明為什麼不能或如何才能得到
輸出序列2 3 4 1 5 6可以得到（2分）
輸出序列3 4 6 5 2 1不能得到（2分），
其理由是，輸出序列中間兩元素是6 5，前面2個元素（3 4）得到後，棧中元素剩6 5，且5在棧頂，不可能棧底元素6在棧頂元素5之前出棧(2分)。
(2) 請寫出圖中二叉樹的前序(先序)和中序遍歷序列。
①前序(先序)：abdcef （3分）
②中序：dbaecf （3分）
(3) 算術表示式如下：a*(b+c)-d
① 用二叉樹表示算術表示式
② 寫出後序（字尾）表示式
3分）②後序（字尾）表示式：abc+*d-（3分）
(4) 請寫出無向圖中頂點a-f的度
a:3（1分）
b:2（1分）
c:1（1分）
d:2（1分）
e:4（1分）
f:2（1分）
(5) 給定元素序列：（50，25，80，20，76，93），畫出按照該序列構造的二叉排序樹(必須畫出二叉排序樹的建樹過程)。
每個結點1分
(6) 下面的鄰接表表示乙個給定的無向圖
① 請根據鄰接表畫出無向圖
② 給出從頂點v1開始, 根據鄰接表對圖用深度優先搜尋法進行遍歷時的頂點序列；
③ 給出從頂點v1開始, 根據鄰接表對圖用廣度優先搜尋法進行遍歷時的頂點序列。
（2分）
②深度序列：v1 v2 v5 v3 v4 v6 （2分）
③廣度序列：v1 v2 v3 v4 v5 v6 （2分）
三、程式填空題（本題共5空，每空2分，共10分）
①p->next（2分）
②malloc（2分）
③data（2分）
④s->next = p->next（2分）
⑤p->next = s（2分）
四、演算法設計題（本題共1小題，每題14分，共14分）
1. 如果通訊字元a，b，c，d出現頻度分別為7，5，2，4
①某同學設計了如下程式，請根據程式畫出對應的二叉樹，計算所畫出的二叉樹的帶權路徑長度（必須寫出計算過程，否則不給分）；
②請畫出赫夫曼（哈弗曼）樹(必須畫出赫夫曼樹的建樹過程)；
③計算它的帶權路徑長度（必須寫出計算過程，否則不給分）
④根據赫夫曼樹，用if-else語句修改①中的程式，寫出最佳判定演算法。
①（2分）
wpl = 7*3 + 5*3 + 4*2 + 2*1 = 46 （2分）
②（3分）
③ wpl = 2*3 + 4*3 + 5*2 + 7*1 = 35 （3分）
④if(input==』a』)
printf("%c",』a1分）
else if(input==』b』)
printf("%c",』b1分）
else if(input==』c』)
printf("%c",』c1分）
else
printf("%c",』d1分）
廈門理工學院C語言課程設計報告
c語言程式設計 課程設計報告 2012 2013學年第 2 學期 專業班級 姓名學號 指導教師 成績電腦科學與技術系 報告正文部分的格式 要求 正文部分一律用五號字，宋體，單倍行距。一級大標題靠左，四號，宋體，加粗。二級大標題靠左，小四，宋體，不加粗。課程設計的內容如下 c語言是一種程式設計靈活，特...
廈門理工學院12級資料結構期末試卷與答案
資料結構與演算法a卷答案 12 13學年第一學期 一 選擇題 本題共20小題，每題2分，共40分 1 5 aabdc 6 10 dddbc 11 15 cbcdd 16 20 abcab 二 分析運算題 本題共6小題，每題5分，共30 分 1 如果輸入序列為1 2 3,先進入棧結構後進入佇列結構，試...
廈門理工學院課表規範
時間早晨 第1節星期一 星期二星期三 星期四大學英語 10建築學周四第1,2節陳彩蒂1 101美術 二周四第3,4節陳曉娟 黃漢潔建工系美術教室218 實6 218健身與健周四第5,6,7 星期五星期六星期日建築設計基礎 下周五第1,2節林蓉 趙華萍 何苗建築學教室2 104 第2節大學英語2 口語...