一、判斷題（正確在括號內填√，錯誤在括號內填×，每題1分，共15分）
（ ）1．線性表採用順序儲存，必須占用一片連續的儲存單元。
（ ）2．棧和佇列的共同點是只允許在端點處插入和刪除元。
（ ）3．資料結構包括資料間的邏輯結構、資料的儲存方式和資料的運算三個方面。。
（ ）4．一棵哈夫曼樹中不存在度為1的結點。
（ ）5．雜湊法是一種對關鍵字進行運算的查詢方法和儲存方法。
（ ）6．乙個佇列的入隊序列是1,2,3,4,則佇列的出隊序列是4,3,2,1。
（ ）7．資料元素是資料的最小單位。
（ ）8．演算法的五個特性為：有窮性、輸入、輸出、完成性和確定性
（ ）9．線性表採用鏈式儲存結構時，其位址必須是連續的。
（ ）10．二叉樹中任何乙個結點的度都是2。
（ ）11．直接插入排序是穩定的排序。
（ ）12．n個頂點的無向圖最多有n*(n-1)條邊。
（ ）13．乙個有向圖的鄰接矩陣一定是乙個非對稱矩陣。
（ ）14．用二分查詢法對乙個順序表進行查詢，這個順序表可以是按各鍵值排好序的，也可以是沒有按鍵值排好序的。
（ ）15．設高度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為2h-1。
二、單項選擇（在備選答案中選出乙個正確答案，並將正確答案的序號填在題乾後的括號內。每題1分，共15分）
1. 下列演算法的時間複雜度為
x=n;// n>1
while(x>=(y+1)*(y+1)) y++;
a．o(n1/2) b．o(n2) c． o(log2n) d．o(n)
2. n個頂點的無向連通圖的最小生成樹包含( )條邊 。
3. 深度為6（根的層次為1）的二叉樹最多有（ ）個結點。
a．64b．32c． 63d．31
4. 乙個線性表第乙個元素的儲存位址是100,每個元素的長度為2,則第5個元素的位址是( ) 。
a. 110b. 120 c. 100 d. 108
5. 在乙個單鏈表中，若刪除p所指結點的後續結點，則執行（ ）
a．p->next=p->next->next ; b．p=p->next;
c．p->next=p->nextd．p =p->next->next;
6 . 稀疏矩陣一般的壓縮儲存方法有兩種,即（ ）。
a．二維陣列和三維陣列 b．三元組和十字鍊錶 c．雜湊和十字鍊錶 d．三元組和雜湊
7. 按照二叉樹的定義,具有3個結點的二叉樹有（ ）種。
a．3b．4 c．5d．6
8. 具有4個頂點的無向完全圖有（ ）條邊。
a. 6b. 20c. 16d. 12
9. 經過以下棧運算後，x的值是
initstack(s); push(s, a); push(s, b); pop(s, x) ; gettop(s, x);
a. ab. bc. 1d. 0
10. 在乙個長度為n的順序表中，刪除第i個元素，需向前移動元素的個數
n-ic. n-i+1
11. 最大容量為n的迴圈佇列，隊尾指標是rear，隊頭是front，則隊滿的條件是 （ ）。
a. rear+1=frontb. rear=front
c．(rear+1) mod n=frontd. (rear-l) mod n=front
12. 具有6個頂點的無向圖至少應有（ ）條邊才能確保是乙個連通圖。
a. 6b. 7c. 8d. 5
13. 採用順序查詢方法查詢長度為n的線性表時,每個元素的平均查詢長度為（ ）
ａ . (n+1)/2 ｂ. n/2 ｃ. nn-1)/2
14. 無向圖的鄰接矩陣是乙個（ ）。
a. 零矩陣 b. 對稱矩陣 c. 上三角矩陣 d. 對角矩陣
15. 有乙個有序表,當用二分查詢法查詢鍵值為4的結點時，經（ ）比較後查詢成功。
a. 2b. 4c. 3d. 12
三、簡答與應用題（第1題5分，2—6每題7分，共40分）
1. 畫出5種不同型態的二叉樹。
2. 對於給定的5個實數w=，試構造huffman樹，並求出該樹的最小帶權路徑長度wpl。
3. 對下面的資料序列，寫出採用氣泡排序演算法排序的每一趟排序的結果。
（50，72，31，80，60，20，96，14）
4. 設雜湊表長度為11，雜湊函式h（k）=k%11，採用線性探測法處理衝突，若輸入序列為（100，90，120，60，78，35，42，31，15，88），要求構造出雜湊表。
5. 已知一棵二叉樹的順序儲存結構如下圖所示。
（1）畫出此棵二叉樹。(3分)
（2）寫出該二叉樹的中根遍歷和後根遍歷的序列。(4分)
6. 已知某帶權無向圖,如下圖所示。
(1)請用鄰接矩陣法表示該圖。(3分)
(2)從頂點0出發，採用prim演算法畫示最小生成樹的過程。(4分)
四、演算法設計題（每題10分，共30分）
1. 寫出二叉樹的前序遍歷遞迴演算法。
2. 在帶頭結點單鏈表head中，若p結點存在，試編寫刪除某一結點p的演算法。
3．編寫直接插入排序演算法。
學生資訊管理系統資料結構課程設計
華中科技大學文華學院 資料結構 課程設計報告 題目 學生資訊管理系統 專業 計算機應用與技術 學號 姓名 指導老師 時間 一 總體框架圖 1 題目 學生資訊管理系統 2 設計內容及要求 內容 完成簡單的學生資訊管理系統 要求 1 學生資訊包括 學號 姓名 數學成績 英語成績 數構成績 2 用鍊錶存放...
資料結構試卷 A
密封線密封線 考生姓名准考證號原所在單位 嘉應學院考試卷 a 電腦科學與技術專業資料結構試題 題號得分評卷人 二 判斷題 本大題共10小題，每小題1.5分，共15分，正確的在答題框內打上 t 錯誤的在答題框內打上 f 題號答案12 3456 78910 得分一二三 四五六七 總分複核人 一 單選題 ...
資訊專業資料結構上機實驗題目
第三章佇列 第十四周 1 定義乙個迴圈佇列實現下列操作 1 增加n個元素 2 刪除n個元素 3 判隊空，判隊滿 4 佇列中查詢元素 2 定義乙個鏈佇列，實現上述相同操作。第六章二叉樹 第十五周 1 定義二叉樹的儲存結構 2 實現如下操作 1 建立乙個具有n個結點的，給定形狀的二叉樹2 用遞迴演算法求...