《資料結構》試卷及答案
1．演算法分析的目的是( c )。
a.找出資料結構的合理性b.研究演算法中輸入和輸出的關係
c.分析演算法的效率以求改進 d.分析演算法的易懂性和文件性
2．（ b ）是具有相同特性資料元素的集合，是資料的子集。
a.資料符號 b.資料物件 c.資料d.資料結構
3．用鍊錶表示線性表的優點是 ( c )。
a.便於隨機訪問b.花費的儲存空間比順序表少
c.便於插入與刪除d.資料元素的物理順序與邏輯順序相同
4．輸入序列為（a,b,c,d）不可能的輸出有（ d ）。
a.(a,b,c,db. (d,c,b,a) c. (a,c,d,b) d . (c,a,b,d)
5．在陣列表示的迴圈佇列中，front、rear分別為佇列的頭、尾指標，maxsize為陣列的最大長度，隊滿的條件是( b )。
a. front=maxsizeb. (rear+1)%maxsize=front
c. rear=maxsized. rear=front
6．設有串t='i am a good student '，那麼substr(t,6,6)=（ d ）。
a. studentb. a good s c. goodd. a good
7．設有乙個對稱矩陣a，採用壓縮儲存方式，以行序為主序儲存a11為第乙個元素，其儲存位址為1，每個元素佔乙個位址空間，則 a85位址為（ b ）。
a.23b.33c.18d. 40
8．已知廣義表 ls=(a,(b,c,d),e)運用head和tail函式，取出ls中原子b的運算（c ）。
a. gethead(gethead(lsb. gettail(gethead(ls))
c. gethead(gethead(gettail(ls))) d. gethead(gettail(ls))
9．若已知一棵二叉樹先序序列為abcdefg，中序序列為cbdaegf，則其後序序列為( a ) 。
a. cdbgfeab. cdbfgea
c. cdbagfed. bcdagfe
10．下列儲存形式中，(c ) 不是樹的儲存形式。
a.雙親表示法b.左子女右兄弟表示法
c.廣義表表示法d.順序表示法
11．對待排序的元素序列進行劃分，將其分為左、右兩個子串行，再對兩個子串行施加同樣的排序操作，直到子串行為空或只剩乙個元素為止。這樣的排序方法是 (c )。
a.直接選擇排序b.直接插入排序
c.快速排序d.起泡排序
12．採用折半查詢方法進行查詢，資料檔案應為（ a），且限於（ ）。
a.有序表順序儲存結構b.有序表鏈式儲存結構
c.隨機表順序儲存結構d.隨機表鏈式儲存結構
13．就平均查詢速度而言，下列幾種查詢速度從慢至快的關係是（ b ）
a.順序折半雜湊分塊b.順序分塊折半雜湊
c.分塊折半雜湊順序d.順序雜湊分塊折半
14．執行下面程式段時，執行s語句的次數為（d ）
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
s; a. n2 b. n2/2 c. n(n+1) d. n(n+1)/2
15．串是一種特殊的線性表，其特殊性體現在（b ）
a.可以順序儲存b.資料元素是乙個字元
c.可以鏈結儲存d.資料元素可以是多個字元
16．樹的基本遍歷策略分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。結論(a )是正確的。
a.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同
b.樹的後根遍歷序列與其對應的二叉樹的先序遍歷序列相同
c.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同
d.以上都不對
17．由五個分別帶權值為9，2，3，5，14的葉子結點構成的一棵哈夫曼樹，該樹的帶權路徑長度為(c )。
a. 60 b. 66c. 67d. 50
18．一棵二叉樹有67個結點，這些結點的度要麼是0，要麼是2。這棵二叉樹中度為2的結點有( a)個
a. 33 b. 34c. 32d. 30
19．有乙個有序表為,當二分查詢值82為的結點時，（ c）次比較後查詢成功。
a. 1 b. 2c. 4d. 8
20．若有檔案的關鍵字序列為：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下為二路歸併排序過程。第二趟為:
da.[265 301] [129 751] [863 937] [694 742] [076 438]
b.[076 129 265 301 438 694 742 751 863 937]
c.[129 265 301 694 742 751 863 937] [076 438]
d.[129 265 301 751] [694 742 863 937] [076 438]
二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內）
1 演算法是指令的有限序列，其中每一條指令表示乙個或多個操作，此外，乙個演算法還具有五個重要特性，它們分別是 __有窮性確定性可行性-,
有零或多個輸入和有一或多個輸出。
2 演算法優劣的五個標準是正確性、可使用性、-可讀性健壯性效率
3 有n個球隊參加的足球聯賽按主客場制進行比賽，共需進行n(n-1)場比賽。4 設有串t='i am a student '，s='good'，那麼concat(t,s)= 'i am a student good'，substr(t,8,7)= 'student'
5 在解決計算機主機與印表機之間速度不匹配時通常設定乙個列印資料緩衝區，主機將要輸出的資料依次寫入該緩衝區，而印表機從該緩衝區中取出資料列印。該緩衝區應該是乙個佇列結構，其主要特點是先進先出。
6 廣義表((a),a)的表頭是(a)，表尾是(a)。
三、判斷題（對的打「√」，錯的打「×」。每小題1分，共10分;答案填在下表內）
t1資料的邏輯結構與資料元素本身的內容和形式無關 。
f2 三個結點的二叉樹和三個結點的樹一樣，都具有三種不同的形態。
t3中序序列和後序序列相同的二叉樹為：空樹和缺右子樹的單支樹 。
t4對於兩棵具有相同關鍵字集合而形狀不同的二叉排序樹，中序遍歷後得到的關鍵字排列順序相同。
f5 序列是堆 。
f6 對於無向圖的生成樹，從同一頂點出發所得的生成樹相同 。
t7 若設雜湊表長m=14，雜湊函式h(key)=key%11，表中已有4個結點。 addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其餘位址為空，如用二次探測再雜湊處理衝突，關鍵字為49的結點的位址是9。
t8乙個深度為k的，具有最少結點數的完全二叉樹按層次，(同層次從左向右)用自然數依此對結點編號則，則編號最小的葉子的序號是2k-2+1 ；編號是i的結點所在的層次號是「log2 i|+1。（「log2 i|表示向上取整」（根所在的層次號規定為1層）。
f9在一棵7階b樹中，乙個結點中最多有6棵子樹，最少有3棵子樹。
t10演算法可以沒有輸入，但是必須有輸出 。
四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分）
五、要求題（本大題共2小題，共12分）
設關鍵字的輸入序列為
1．（8分）從空樹開始構造平衡二叉樹，畫出每加入乙個新結點時二叉樹的形態，若發生不平衡，指明需做的平衡旋轉型別及平衡旋轉的結果。
2． （4分）上面的資料作為待排序的資料，寫出用快速排序進行一趟劃分後的資料序列
六、按要求做題（本大題共2小題，共12分）
1畫出無向圖g的鄰接表儲存結構，根據鄰接表儲存結構寫出深度優先和廣度優先遍歷序列。（7分）
2 用prim演算法求下圖的最小生成樹，寫出最小生成樹的生成過程。（5分）
七、演算法分析設計題（本大題共5小題，共30分）
1．寫出程式段的功能,並給出乙個測試用例（乙個輸入資料和乙個輸出結果）(5分)。
void conversion()
while(!stackempty(s))
河北工業大學陡河電廠實習報告
大唐國際陡河發電廠實習報告 河北工業大學高舉 工學並舉 偉大旗幟歷經百餘年一路走來，如今終於把口號付諸於實踐。經過熱能專業三年的學習，專業課程已將要結束，在理論知識積累快要完畢時為了加深我們對所學專業的認識，提高專業素養，培養專業熱情，為以後的就業學習做準備，學院特意精心為我們安排了到唐山陡河電廠進...
附1 塗卡要求河北工業大學
附1 塗卡要求。影象資訊採集卡填塗說明 1 所在院校名稱及院校 本一 河北工業大學10080 本三 河北工業大學城市學院 13584。1 院 系 從左向右，只填頭兩個空格 2 姓名及區位碼 從左向右依次填寫，中間不得空格，如出現編碼本內查詢不到的漢字，請將區位碼內的四個數字一律填塗 0 並請在漢字旁...
河北工業大學數值分析實驗報告
電器數值分析實驗報告 姓名班級學號 1 電磁體設計 請將計算結果填在相應位置 磁通量等勢線 沿z軸的磁感應強度分布曲線 磁感應強度分布雲圖 2 同軸線電感分析 請將計算結果填在相應位置 電感值 1.66733e 007 畫出相應的場量雲圖 3 微波積體電路中的微帶線分析 請將計算結果填在相應位置 等...