0.緒論
一、填空題
1、資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類
2、資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法
二、選擇題
1、乙個演算法必須在執行有窮步之後結束，這是演算法的（ ）。
a、正確性 b、有窮性
c、確定性 d、可行性
2、演算法的每一步必須有確切的定義，也就是說，對於每步需要執行的動作必須嚴格、清楚地給出規定，這是演算法的（ ）。
a、正確性 b、有窮性
c、確定性 d、可行性
3、演算法原則上都是能夠有機器或人所完成的。整個演算法好象是乙個解決問題的「工作序列」，其中的每一步都是我們力所能及的乙個動作，這是演算法的（）
a、正確性 b、有窮性 c、確定性 d、可行性
三、簡單題
1、什麼是資料結構？什麼是演算法？兩者有什麼關係？
2、什麼時間複雜度和空間複雜度？
3、資料的邏輯結構分幾種？儲存結構又有哪幾種？
線性表1、乙個線性表第乙個元素的儲存位址是 100，每個元素的長度
為 2， 則第 5 個元素的位址是 ( b)。
（a）110 （b）108（c）100 （d）120
2、向乙個有 127 個元素的順序表中插入乙個新元素並保持原來
順序不變，平均要移動（ c）個元素。
（a）64（b）63 （c）63.5 （d）7
2、線性表採用鏈式儲存結構時，其位址 ( d)。
(a) 必須是連續的b) 部分位址必須是連續的
(c) 一定是不連續的d) 連續與否均可以
3、在乙個單鏈表中，若 p 所指結點不是最後結點，在 p 之後插
入 s 所指結點，則執行 (b )。
（a）s->next=p;p->next=s; （b） s->next=p->next;p->next=s;
（c）s->next=p->next;p=s; （d）p->next=s;s->next=p;
4、在乙個單鏈表中，若刪除 p 所指結點的後續結點，則執行 (a )
（a）p->next=p->next->next;
（b）p=p->next; p->next=p->next->next;
（c）p->next=p->next;
（d）p =p->next->next;
5.在長度為n的順序表的第i(1≤i≤n+1)個位置上插入乙個
元素，元素的移動次數為 a_，刪除第i個位置元素，元素
的移動次數為 b 。
a. n-i+1 b. n-i c. i d. i-1
6. 演算法分析的兩個主要方面是_a___。
a. 空間複雜性和時間複雜性 b. 正確性和簡明性
c. 可讀性和文件性 d. 資料複雜性和程式複雜性
7.寫出順序表插入、刪除及就地逆置演算法（見實驗）
8、寫出單鏈表插入、刪除、求表長及逆置演算法（見教材p32頁演算法2.19）
排序1.下列排序演算法中，時間複雜度不受資料初始狀態影響，恒為o(log2n)的是____。
a. 堆排序b. 氣泡排序
c. 直接選擇排序d. 快速排序
2.若表r在排序前已按鍵值遞增順序排列，則____演算法的比較次數最少。
a. 直接插入排序b. 快速排序
c. 堆排序d.選擇排序
3.已知一組關鍵字，請分別寫出按插入排序、氣泡排序、直接選擇排序和快速排序方法排序過程，每一趟排序結束時的關鍵字的狀態。
4.寫出簡單排序演算法和一場快速排序演算法等等
棧的基礎知識
1、若入棧序列是 a, b, c, d, e，則不可能的出棧序列是（c）。
（a） edcba（b）decba（c）dceab （d）abcde
2、判定乙個棧 st(最多元素為m0) 為空的條件是（b）。
（a） != -1 （b） = -1
（c） != m0 -1 （d） = m0-1
3、判定乙個棧 st(最多元素為m0) 為滿的條件是（d）。
（a） != 0b） = 0
（c） != m0 -1 （d） = m0-1
4.在n(n>0)個元素的順序棧中插入1個元素的時間複雜度為(c)。
a. o(nlog2n) b. oc. o(1) d. o(n)
5.在n(n>0)個元素的順序棧中刪除1個元素的時間複雜度為(d)。
a. o(n) b. oc. o(nlog2n) d. o(1)
填空題部分
1、棧的特點是後進先出（或lifo），佇列的特點是先進先出（或fifo ）。
2、線性表、棧和佇列都是線性結構，可以**性表的任何位置插入和刪除元素，棧只能在表尾插入和刪除元素， 佇列只能在表尾插入元素和表首刪除元素。
3、若佇列的入隊序列是 1, 2, 3, 4，則出隊序列是（b）。
（a）4,3,2,1（b）1,2,3,4（c）1,4,3,2（d）3,2,4,1
佇列基礎知識
1、迴圈佇列用陣列 a[0, m-1] 存放其元素值，已知其頭尾指
針分別是 front 和 rear 則當前佇列中的元素個數是（a）。
(a) (rear-front+m)%m (b) rear-front+1
(c) rear-front-1d) rear-front
2、以陣列 q[0… m－1] 存放迴圈佇列中的元素，變數 rear
和 qulen 分別指示迴圈佇列中隊尾元素的實際位置和當前
佇列中元素的個數，佇列第乙個元素的實際位置是（d）。
(a) rear－qulen (b) rear－qulen＋m
(c) m－qulend) 1＋(rear＋m－qulen) % m
3.設迴圈佇列中陣列的下標範圍是1～n，其頭尾指標分別為f和r，
則判斷迴圈佇列滿的條件為(b)
a. r=fb. f=(r+1) % n
c. r=(f+1) % (n+1d. r=f+1
練習一、填空題
1、線性表、棧和佇列都是____ 結構，線性表可以在＿ 位置插入和刪除元素；對於棧只能在＿ 插入和刪除元素；對於佇列只能在＿ 插入和刪除元素。
2、棧是一種特殊的線性表，允許插入和刪除運算的一端稱為＿ ，不允許插入和刪除運算的一端稱為＿ 。
3、 ＿ 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。
4、向棧中壓入元素的操作是先＿ ，後＿ 。
5、在操作序列push(1),push(2),pop(),push(5),push(7),pop(),push(6)之後，棧頂元素是＿ ，棧底元素是＿ 。
6、用單鏈表表示的鏈式佇列的隊頭是在鍊錶的 ＿ 位置。
二叉樹和樹
1.二叉樹的前序遍歷序列中，任意乙個結點均處在其子女結點的前面，這種說法（ aa）正確 （b）錯誤
2.由於二叉樹中每個結點的度最大為 2，所以二叉樹是一種特殊的樹，這種說法（ ba）正確 （b）錯誤
3.已知某二叉樹的後序遍歷序列是 dabec。中序遍歷序列是 debac，它的前序遍歷序列是（ d ）。
（a）acbed （b）decab（c）deabc （d）cedba
4.某二叉樹的前序遍歷結點訪問順序是 abdgcefh，中序遍歷的結點訪問順序是 dgbaechf，則其後序遍歷的結點訪問順序是（ d ）。
（a）bdgcefha （b）gdbecfha （c）bdgaechf （d）gdbehfca
5．在一非空二叉樹的中序遍歷序列中，根結點的右邊（a）
（a）只有右子樹上的所有結點 （b）只有右子樹上的部分結點
（c）只有左子樹上的部分結點 （d）只有左子樹上的所有結點
6.任一二叉樹的葉子結點在先、中和後序遍歷序列中的相對次序 ( a ) 。
（a）不發生改變 （b）發生改變 （c）不能確定 （d）以上都不對
7.對二叉樹從1開始進行連續編號，要求每個結點的編號大於其左右孩子的編號，同乙個結點的左右孩子中，其左孩子的編號小於其右孩子的編號，則可採用__c__遍歷實現編號。
a. 無序 b. 中序 c. 後序 d. 從根開始的層次遍歷
8.深度為k的二叉樹的結點總數，最多為 c 個。
ａ)２k-1 ｂ) log2k ｃ) ２k－１ ｄ)２k
9. 深度為9的二叉樹中至少有個結點。
ａ)２9 ｂ)２89－1
10．二叉樹有n個葉子，沒有度為1的結點，共有 2n-1 個結點
分析：度為2的結點有n-1個，所以共2n-1個結點。
11.設一棵完全二叉樹具有1000個結點，則它有500 個葉子結點，有499個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。
12.一棵深度為6的滿二叉樹有個葉子和個分支結點。
13、n個葉子結點的二叉樹最少有 2n-1 結點。
1、一棵哈夫曼樹有 19 個結點，則其葉子結點的個數是(10 )。
2、有七個帶權結點，其權值分別為 3, 7, 8, 2, 6, 10, 14，試以它們為葉結點構造一棵哈夫曼樹（請按照每個結點的左子樹根結點的權小於等於右子樹根結點的權的次序構造），並計算出帶權路徑長度wpl及該樹的結點總數。
3、有一電文共使用五種字元 a, b, c, d, e，其出現頻率依次為 4, 7, 5, 2, 9。
(1)、試畫出對應的編碼哈夫曼樹（要求左子樹根結點的權小於等於右子樹根結點的權）。
(2)、求出每個字元的哈夫曼編碼
資料結構複習
1.以niklus wirth的觀點，程式等於什麼?2.演算法的重要特性。3.好演算法的標準。4.線性結構的特點。5.線性結構與非線性結構的區別。6.列出所學過的線性結構與非線性結構。7.頭指標 頭結點 首元結點的區別。8.帶頭結點和不帶頭結點的線性鍊錶的區別。9.單鏈表 雙鏈表 迴圈鍊錶的區別及各...
資料結構複習
2 掌握圖的兩種儲存結構，鄰接矩陣及鄰接表 重點掌握圖的鄰接矩陣表示方法。掌握給定乙個圖，採用鄰接矩陣或鄰接表表示法，對圖中邊 頂點的度 任意兩點是否有邊相連的確定方法 3 最小生成樹，重點掌握採用普里姆演算法及克魯斯卡爾演算法如何求最小生成樹 4 重點掌握圖的深度優先遍歷及廣度優先遍歷 重點掌握圖...
《資料結構》複習
第一章緒論 一 基本概念 資料 資料元素 資料項 資料結構 邏輯結構 物理結構 線性結構 非線性結構 順序儲存結構 鏈式儲存結構 雜湊儲存結構 索引儲存結構 資料型別 抽象資料型別。演算法 語句的頻度 演算法的時間複雜度 演算法的漸進複雜度 空間複雜度 二 資料結構概念 資料結構包括資料的邏輯結構 ...