24.快速排序的樞軸有多種選擇方法，取首尾節點是較簡單的做法。
25.氣泡排序不但穩定，而且速度很快。
二、名詞解釋與問答
26.線性結構:
唯一的首節點，唯一的尾節點，除首尾外其它節點既有前驅也有後繼，首無前驅，尾無後繼。
27.線性結構中端操作受限的含義是什麼？
操作僅在指定的位置。棧在棧頂，佇列在隊頭和隊尾。
28.非線性結構
有樹、圖、集合等。可實現一對多、多對多、多對一的邏輯關係。是複雜的資料結構
29.鏈式儲存:
結點的結構為資料+指標，利用指標可定址找下乙個結點
30.連續位址儲存：
所有的節點儲存在一塊記憶體邏輯編號連續的記憶體中。起始的邏輯位址稱首位址。訪問通過首位址。
31.原子項：
資料元素中不可分解的項。
32.資料元素:
是資料結構的基本單位，有乙個或多個資料項（原子屬性）構成。
33.簡述雙向迴圈鍊錶的邏輯特點。雙向迴圈鍊錶與線性表有何異同？
雙向迴圈鍊錶中的節點含有兩個指標，乙個用於指向前驅節點，乙個用於指向後繼節點，可由表頭開始實現雙向訪問。線性鍊錶僅可以沿乙個方向訪問。
34.簡述雙向迴圈鍊錶的特點
雙向迴圈鍊錶中的結點含有兩個指標，乙個用於指向前驅結點，乙個用於指向後繼結點，可由表頭開始實現雙向訪問。
35.表頭節點的作用是什麼？
儲存表的相關資訊如表長、是否為空表。頭結點的資料域儲存指向第乙個結點的指標。
36.簡述環型佇列的特點。
將順序佇列臆想為乙個環狀空間，指標和佇列元素之間的關係不變。front= =rear無法判斷佇列是否為「空」還是「滿」
37.棧的top和bottom標誌：
棧的頂和底標誌， top指向頂， bottom指向底
38.稀疏矩陣：
矩陣中存在大量的零元素，當稀疏因子達到一定值時，就認為該矩陣為稀疏矩陣。
39.串
由零個或多個字元組成的有限序列
40.串的子串
串中任意個連續的字元組成的子串行稱為串的子串
41.串的長度
串中字元的數目稱為串的長度
42.主串
包含子串的串稱為主串
43.樹的結點:
包含乙個資料元素及若干指向其子樹的分支
44.樹結點的度（樹的度）
樹結點擁有的子樹數，稱為樹結點的度
45.樹的深度
樹中結點的最大層次稱為樹的深度
46.什麼是二叉樹？
二叉樹是樹形結構，它的特點是每個結點至多只有兩棵子樹，並且二叉樹的子樹有左右之分，其次序不能任意顛倒。
47.空二叉樹:
是一種特殊的bt。它沒有任何結點。
48.嚴格二叉樹：
深度為k，結點個數為2k-1個的bt
49.bt有幾種形態？逐一畫出圖形並作解釋。
五種。乙個根的bt；空bt；左傾斜bt；右傾斜bt；根+左子樹+右子樹。
50.圖的權:
圖的邊或弧相關的數叫做權
51.網
帶權的圖稱為網
52.連通圖
圖中任意兩個頂點都是連通的，則稱圖是連通的
53.圖的簡單路徑
序列中頂點不重複出現的路徑稱為簡單路徑
54.查詢
根據給定的某個值，在查詢表中確定乙個其關鍵字等於給定值的記錄或資料元素叫查詢。
55.查詢表:
由同一型別的資料元素構成的集合
56.關鍵值（關鍵字）:
是資料元素中某個資料項的值，用它可以識別乙個記錄
主關鍵字：可以唯一識別乙個記錄的關鍵字就是主關鍵字。
57.hash函式:
在記錄的儲存位置和它的關鍵字之間建立乙個確定的對應關係函式f，使得每個關鍵字和結構中乙個唯一的儲存位置相對應。這個函式f稱為雜湊（hash）函式
58.hash技術中的衝突是指什麼現象？如何解決？
對不同的關鍵字可能得到同乙個雜湊位址，這種現象稱為衝突。通常採用的解決衝突的方法有：開放定址法、再雜湊法、鏈位址法、建立乙個公共溢位區
59.簡述堆的特點，如何儲存堆結構資料。
n個元素的序列｛k1,k2,…kn｝當且僅當滿足以下關係時，稱為堆。
堆只需要乙個記錄大小的輔助空間。每個待排序的記錄僅占有乙個儲存空間。
60.排序中附加儲存空間的作用是什麼？
在基於比較和交換的排序技術中，若交換資料，必須有附加的儲存單元暫存待交換的資料，否則將導致部分資料丟失。附加空間是指記憶體。
61逆波蘭式xy+st-*表示的含義是什麼？畫出表示式樹，計算結果是多少？
（x+y）*(s-t)
62.多項式y=ax3+bx2+cx+d有多種計算方法，第一種直接計算y=a*x*x*x+b*x*x+c*x+d；第二種計算方法是：y=a； y=y*x+b； y=y*x+c； y=y*x+d； 哪種快？
為什麼？
第二種好。乘法和加法的次數不同。乘法和加法所需要的時間不同。
三、畫圖、讀圖
1.有bt如下圖，求先序、中序、後序遍歷。
先序 wm$#acd先根序hcmuxyt先根序v、r、t、d、x、p、f；
中序 $mwcad中根序cumxhyt中根序t、d、r、x、p、v、f；
後序$mcda#w後根序uxmctyh後根序d、t、p、x、r、f、v
先根序k、l、j、m、g、n； 先根序e、u、t、c、d、q、h；先根序w、m、k、f、z、v、h
中根序l、k、g、m、n、j； 中根序u、e、d、c、q、t、h；中根序k、m、z、f、v、w、h；
後根序l、g、n、m、j、k。後根序u、d、q、c、h、t、e。後根序k、z、v、f、m、h、w
2.有g、f、a、d、l、b資料，按題目所給定的次序逐步構建bst（按ascii碼值），構建完成後，再刪除l節點。
3.依次輸入鍵值47、38、69、27、53、72的資料，逐步構建bst。bst的基本功能是什麼？
bst是二叉排序樹，中序是公升序。
4.有鍵值為f、k、a、d、x、v、i的資料，按題目所給定的次序逐步構建bst（按ascii碼值）構建完成後，寫出中根序遍歷，再刪除v節點。
5.若有乙個棧，資料輸入的次序為u，v，w，寫出出棧序列。
6.若有乙個棧，資料輸入的次序為w，x，y，z，寫出輸出次序。
7.若有乙個棧，資料輸入的次序為x，y，z，給出出棧序列
8.有乙個棧（棧的規模=10），資料輸入的次序為a、b、c，寫出出棧序列。
9.有下圖，用kurskal法逐步求該圖的mst，需圖示說明。
依次挑選3、3、5、11邊
10.若有帶權無向圖（見下圖），指點起始頂點為g，用prim法求出該圖的mst。
11.如下圖，指定頂點c為起始頂點，用prim法求該樹的mst。
12.用二進位制系統傳輸電文seven-eleven，要求使用最少的位元量，畫出編碼樹，用你設計的方式傳輸該電文需用多少位元？v的二進位制編碼是什麼?
編碼樹如下，共需28位元， v的編碼可能不同，取決於huffman tree的形狀，因為此題有相同的權。
13.用二進位制系統傳輸電文thinning，要求使用最少的位元量，試畫編碼樹，用你設計的方式傳輸該電文最少需用多少位元？g的編碼是什麼?
編碼樹:
最少的位元量為:thinning=010011100000100011=18bit g的編碼是11
14.用二進位制系統傳輸電文cookbook，要求使用最少的位元量，試畫編碼樹，用你設計的方式傳輸該電文最少需用多少位元？k的編碼是什麼?
需用14位元（結果唯一），k的編碼是11（結果可能多樣，取決於哈夫曼數的形狀）
參考編碼：10000111010011=14bit k的編碼是11
15.用二進位制系統傳輸電文cctv***mov，要求使用最少的位元量，試畫編碼樹，用你設計的方式傳輸該電文最少需用多少位元？t的編碼是什麼?
10101101111001000001111=23bit t的編碼是110（視哈夫曼樹而定）
16.用二進位制系統傳輸電文antenna，要求使用最少的位元量，試畫編碼樹，用你設計的方式傳輸該電文最少需用多少位元？其中t的編碼是什麼?
最少的位元量為13，試畫編碼樹。
antenna＝0010100111100=13bit t的編碼是010（不唯一）
17.用二進位制系統傳輸電文yahoohook，要求使用最少的位元量，畫出編碼樹，用你設計的方式傳輸該電文需用多少位元？a的編碼是什麼？
最少需用19位元,
18若待排序的資料存放在陣列int a中，結點的鍵值為整型數n，試寫出插入排序演算法
//若待排序的資料存放在陣列中，節點的鍵值為整型數，試寫出插入排序演算法的偽碼。附加圖示說明。
insertsort(int a,int n)的偽碼。
void insertsort(int a, int n)
}19.若待排序的資料存放在陣列bubble[max]中，用類c語言寫出氣泡排序演算法的偽碼。
void bubble-sort(bubble,n)
int bubble[max]; int n;
n=j;
20.若bt採用「資料+指向左右孩子的指標」方式儲存，已知指向bt根結點的指標btree *bt，定義結點的結構，用偽碼描述求該bt有單孩子的結點個數int onechild(btree *bt)的演算法。
資料結構試題及答案
資料結構試卷 一 一 單選題 每題 2 分，共20分 1.棧和佇列的共同特點是 a a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列，在進行插入運算時 d a.僅修改頭指標b.頭 尾指標都要修改 c.僅修改尾指標d.頭 尾指標可能都要修改...
資料結構試題及答案
2 二維陣列是陣列元素為一維陣列的線性表，因此它是線性結構。3 順序錶用一維陣列作為儲存結構，因此順序表是一維陣列。4 通常使用兩個類來協同表示單鏈表，即鍊錶的結點類和鍊錶類。5 棧和佇列都是順序訪問的的線性表，但它們對訪問位置的限制不同。6 在使用字尾表表示實現計算器時用到乙個棧的例項，其作用是暫...
資料結構試題及答案
資料結構 自考複習思考試題 一 單選題 從選擇的答案中選出正確的答案，將其字母編號填入下列敘述中的括號內。每小題 3分，共24分 1 向乙個有127個元素原順序表中插入乙個新元素並儲存原來順序不變，平均要移動 個元素。a 8 b 63.5 c 63 d 7 2 設有乙個二維數a m n 假設a 0 ...