1、南昌大學20102011學年第一學期期末考試試卷 試卷編號：（A ）卷 課程編號： 課程名稱：數據結構考試形式：閉卷 適用班級： 姓名： 學號： 班級： 學院：專業：考試日期： 題號 -一- -二二 三 四 五 六 七 八 九 十 總分 累分人 題分 20 30 30 20 100 簽名 得分 考生注意事項：1、本試卷共8頁，請查看試卷中是否有缺頁或破損。如有立即舉手報告以便更換。 2、考試結束后，考生不得將試卷、答題紙和草稿紙帶出考場。 -、選擇題（每題1分，共20分） 得分 評閱人 1. 算法必須具備輸入、輸出和 。 A. 計算方法B.排序方法 C 解決問題的有限運算步驟D.程序設計方法

2、2. 設將整數1,2,3,4,5依次進棧，最后都出棧，出棧可以在任何時刻（只要棧不空）進 行，則出棧序列不可能是 。 3.用鏈表表示線性表的優點是 A.便于隨機存取 C.便于插入與刪除 A. 23415 B. 54132C. 23145D. 15432 0 B. 花費的存儲空間比順序表少 D.數據元素的物理順序與邏輯順序相同 4.若某線性表的常用操作是取第 i個元素及其前趨元素，則采用 存儲方 5.串是任意有限個0 式最節省時間 A.順序表 B.單鏈表C.雙鏈表 D.單向循環 A.符號構成的序列B.字符構成的序列C.符號構成的集合D.字符構成的集合 6. 設有一個對稱矩陣A，采用壓縮存儲方式，

3、以行序為主序存儲all為第一個元素, a85地址為 其存儲地址為1,每個元素占一個地址空間，則 D. 40 在 p結點之后插入s結點的正確 B. s-n ext=p; p=p D. p-n ext=s; s-n ext=p; A.23B.33C.18 7. 在一個單鏈表中，若p結點不是最后一結點 是。 A. s-n ext=p; p-n ext=s; C. s-n ext=p-n ext ; p-n ext=s; 8將含100個結點的完全二叉樹從根這一層開始，每層從左至右依次對結點編號，根 結點的編號為1。編號為47的結點X的雙親的編號為 A.24B.25C.23 D.無法確定 9. 在一棵二

4、叉樹中有30個葉子結點，僅有一個孩子的結點有 20個，則該二叉樹共有 個結點 A、79 B 、76 C 、56 D 、81 10. 深度為5的二叉樹至多有個結點。 A. 16 B. 32 C. 31D. 10 11. 對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加 同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是C A.直接選擇排序B.直接插入排序 C.快速排序D.起泡排序 12. 二分查找要求節點 A .有序、順序存儲B.有序、鏈接存儲 C.無序、順序存儲D.無序、鏈接存儲 13. 在一個無向圖中，所有頂點的度數之和等于圖的邊數的 倍 A. 1/2

5、B. 1C. 2D. 4 14. 已知用某種排序方法對關鍵字序列(51, 35，93, 24，13, 68，56，42，77)進 行排序時，前兩趟排序的結果為 (35,51,24,13,68, 56, 42, 77,93) (35,24,13,51,56, 42, 68, 77,93) 所采用的排序方法是 A.插入排序B.冒泡排序 C.快速排序D.歸并排序 15. 一棵二叉樹有67個結點，這些結點的度要么是 0,要么是2。這棵二叉樹中度為2 的結點有個 A. 33B. 34C. 32D. 30 16由五個分別帶權值為9, 2, 3, 5, 14的葉子結點構成的一棵哈夫曼樹，該樹的帶 權路徑長度

6、為。 A. 60B. 66C. 67D. 50 17.對一棵二叉排序樹進行 歷得到的結點序列是一個有序序列。 A.前序B.中序C.后序D.層序 18有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100當二分查找值82為的結點時, 比較后查找成功。 A. 1B. 2C. 4D. 8 19就平均查找速度而言，下列幾種查找速度從慢至快的關系是 。 A.順序折半哈希分塊B.順序分塊折半哈希 C.分塊折半哈希順序D.順序哈希分塊折半 20.設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最 好選用卡序法。 A.冒泡排序B.快速排序C.堆排序D.選

7、擇排序 二、填空題（每空2分，共30分） 得分 評閱人 1. 設r指向單鏈表最后一個結點，要在最后一個結點之后插入s所指的結點，需執行 的三條語句是r-next=s ; r=s; 【1 。 2. 數據的邏輯結構分為兩大類，它們是線性結構和【2 _。 3. 已知循環隊列用數組datan存儲元素值，用front,rear分別作為頭尾指針，則 當前元素個數為【3 。 4. 一棵二叉樹有30個葉子結點，僅有一個孩子的結點有20個，則該二叉樹共有 【4 個結點；若完全二叉樹共有100個結點，則其葉子結點數為【5。 5. 在帶頭結點單鏈表L中，表空的條件是 【6 。 6. 在一個長度為n的順序表中的第i個

8、元素（K i key=x; p-left=n ull; p-right=n ull; t=p; else if (xkey)search in sert(x,t-left) else【15】; 、應用題(每小題5分，共30分) 得分 評閱人 1.對于下面的稀疏矩陣，畫出其三元組法存儲表示（假設下標從0開始） 廠0 0 14 0 0 0 7 0 0 0 0 0 0 15 0 000= 0-6 0 0024 1800 000 2.已知一棵二叉樹的中序序列和后序序列分別如下，請畫出該二叉樹 中序序列：D I GJLKBAECHF 后序序列：I LKJ GDBEHFCA 3. 給定權值5,10,12,

9、15,30,40,構造相應的哈夫曼樹，并寫出他的帶權路徑長度 4. 已知一個無向圖的鄰接表為 V1 g 9 4 A V2 / 數據域 struct node *n ext;/ 指針域 2.采用順序結構存儲串，設計一個算法strcmp(s,t)實現串的比較，串的比較以詞典方 式進行，當s大于t時，返回1,當s等于t時，返回0,當s小于t時，返回-1,順 序串的類型定義如下： #defi ne Maxsize Typedef struct sqstring char chMaxsize;/ 存放串字符； int le n;存放串的實際長度； 答題卡 選擇題（每小題1分，共20分） 得分 評閱人 1

10、 C 2 B 3 C 4 A 5 B 6 B 7 C 8 C 9 A 10 C 11 C 12 A 13 C 14 B 15 A 16 C 17 B 18 C 19 B 20 C 填空題（每空2分，共30分） 得分 評閱人 【12】 【3】 【7】 【11】 【15】 【4】 【8】 倚窗遠眺，目光目光盡處必有一座山，那影影綽綽的黛綠色的 影，是 春天的顏色。周 遭流嵐升騰，沒露出那真實的面孔。面對那流轉的薄霧，我會幻想，那里 有一個世外桃源。在天階夜色涼如水的夏夜，我會靜靜地，靜靜地，等待一場流星雨的來臨 許下一個愿望，不乞求去實現，至少，曾經，有那么一刻，我那還未枯萎的，青春的，詩意 的心，在我最美的年華里，同星空做了一次靈魂的交流 秋