一、 選擇題
1. 下面哪種排序法對***在空間和時間上最優( )
a. 快速排序 b. 氣泡排序
c. 插入排序 d. 堆排序
2. 2.就排序演算法所用的輔助空間而言，堆排序，快速排序，歸併排序的關係是（ ）
a．堆排序〈 快速排序〈歸併排序 b．堆排序〈 歸併排序〈 快速排序
c．堆排序〉 歸併排序 〉快速排序 d．堆排序 > 快速排序 > 歸併排序
e．以上答案都不對
3. 3.一株二叉樹的以某種遍歷方式的序列為a、b、c、d、e、f、g，.若該二叉樹的根結點為e,則它的一種可能的前序遍歷為____ ,相應的後序遍歷為____
a. ecbadfg, bdcafge b. ecbadfg, efacdbg
c. ecbadgf, eacbdgf d. eacbdgf, bdcafge
（常見題型，給出樹的前序遍歷和中序遍歷，中序和後續遍歷，推出二叉樹）
4. 關於圖和樹，下面說法正確的是________
a. 樹和圖都允許有環
b. 圖的深度遍歷和廣度遍歷結果可能一樣
c. 二叉樹是每個節點都有兩個孩子節點的樹
d. 二叉樹的前序遍歷和後序遍歷結果肯定不一樣
5. 完成在雙迴圈鍊錶結點p之後插入s的操作是（ ）
a．p->next=s ; s->priou=p; p->next->priou=s ; s->next=p->next;
b．p->next->priou=s; p->next=s; s->priou=p; s->next=p->next;
c．s->priou=p; s->next=p->next; p->next=s; p->next->priou=s ;
d．s->priou=p; s->next=p->next; p->next->priou=s ; p->next=s;
二、 填空題
1. 用鍊錶表示的資料的簡單選擇排序，結點的域為資料域data ，指標域 next ；鍊錶首指標為head ，鍊錶無頭結點。
selectsort(head)
p=head;
while (p(1
tmp=q->data; q->data=p->data; p->data=tmp; p= (6
}2. 二叉樹對稱序列為abcdefg, 後序序列為bdcafge,問前序序列為
3. 填空：要求用遞迴的方法實現二叉樹排序, 第二個引數s為要插入的新結點。
typedef struct inode b_tree;
b_tree *sort_b_tree(b_tree **tree, b_tree s)
else if (s->data < (*tree)->data) else if (s->data > (*tree)->data)
}三、 簡答題
1. 陣列和鍊錶的區別，請詳細解釋。
2. 排序演算法有哪些？< c語言總共有多少種排序法》
3. 怎麼理解雜湊表,雜湊表是什麼
4. 請寫出以下演算法的時間複雜度
氣泡排序法插入排序法堆排序法二叉樹排序法
快速排序法希爾排序法
5. 資料結構，二叉樹的相關知識，開銷量，為何使用二叉樹等。
四、 程式設計題
1. 編寫乙個程式，把乙個有序整數陣列放在二叉樹中。
2. 在二叉查詢樹中查詢某乙個值所在的位置。
3. 二叉樹，比父節點大的元素，都在右子樹，比父節點小的元素都在左子樹。也就是排序二叉樹，寫出插入乙個節點或者刪除乙個節點。
4. 實現單向鍊錶:建立鍊錶、插入鍊錶、查詢鍊錶、刪除特定序號鍊錶節點、遍歷剩餘鍊錶節點
5. 程式設計實現判斷乙個鍊錶是否是遞增的
6. 程式設計實現刪除鍊錶中的重複節點
7. 只遍歷一次鍊錶，實現鍊錶的倒序
8. 將兩個有序鍊錶a1,a2表合併為乙個有序鍊錶a3
9. 已知鍊錶節點
struct lnode ;
已建立乙個有序的鍊錶，從小到大排列。實現以下函式，將資料插入到鍊錶中，並且有序。請實現以下函式：
bool insertlink(linklist *p,int a){};
10. 寫乙個鍊錶，實現建立鍊錶，新增鍊錶節點，刪除鍊錶節點，查詢鍊錶節點，寫乙個main函式，建立乙個鍊錶，裡面新增20個學生節點（節點含有姓名和學號），再刪除其中任意乙個節點，輸出任意指定節點，輸出最後10名學生節點。
11. 將test.txt文中的整數按順序依次存入乙個鍊錶中，然後按順序輸出
12. 找出單鏈表的倒數第4個元素
13. 找出單鏈表的中間元素
14. 判斷單鏈表是否有環？如何找到環的「起始」點？如何知道環的長度？
15. 兩個單鏈表相交，計算相交點
16. 用兩個棧實現佇列
17. 用兩個佇列實現棧
18. 請實現乙個雙向迴圈鍊錶，包含新增，查詢，插入，刪除，銷毀等判斷是否為空，列印輸出等基本操作
19. 寫乙個函式，當兩個鍊錶中元素data相同時，刪除節點。
struct node 有兩個鍊錶struct node* heada, *headb。
20. 寫乙個雙向列表倒序的程式
21. 乙個雙向鍊錶，將兩個連續的節點交換
22. 怎樣編寫乙個程式，把乙個有序整數陣列放在二叉樹中
23. 在二叉查詢樹中查詢某乙個值所在的位置
24. 二叉樹，比父節點大的元素，都在右子樹，比父節點小的元素都在左子樹。也就是排序二叉樹，寫出插入乙個節點或者刪除乙個節點。
25. 如何判斷一棵二叉樹是否是平衡二叉樹
26. 實現冒泡（圖）
27. 找出字串中的最長子串，要求子串的所有字元相同
28. 遞迴演算法n！
29. 1 1 2 3 5 8 13 …… 任意語言程式設計求出第32位數是多少，遞迴實現
30. 請寫乙個公升序排序函式
31. 請寫出氣泡排序，選擇排序，快速排序
32. 給出洗牌的乙個演算法，並將洗好的牌儲存在乙個整形陣列裡
33. 乙個整數大於0,不用迴圈和本地變數,按照n、2n、4n、8n的順序遞增，當值大於5000時，把值按照指定順序輸出來。
資料結構期中筆試題答案
一 填空題 20分，每題2分 1.邏輯結構 儲存結構 2.便於插入和刪除操作 3.方便運算的實現 4.演算法執行過程中所需要的基本運算次數 5.儲存結構 7 遞迴演算法 8.抽象類或介面 二 選擇題 30分，每題2分 aacbb bddcb aacac 三 問答題 50分，每題10分 1.什麼是棧和...
資料結構上機題目
第二次 sqlist 順序表 2.11 設順序表va中的資料元素遞增有序。試寫一演算法，將x插入到順序表的適當位置上，以保持該錶的有序性。2.21 試寫一演算法，實現順序表的就地逆置，即利用原表的儲存空間將線性表 a1,a2,an 逆置為 an,an 1,a1 第三次 linklist 單鏈表 2....
資料結構題目說明
題目說明 1.運動會分數統計 限3人完成 任務 參加運動會有n個學校，學校編號為1 n。比賽分成m個男子專案，和w個女子專案。專案編號為男子1 m，女子m 1 m w。不同的專案取前五名或前三名積分 取前五名的積分分別為 7 5 3 2 1，前三名的積分分別為 5 3 2 哪些取前五名或前三名由學生...