期末考試形式：閉卷試卷
總評成績：試卷70%+平時30%
試卷題型：1.選擇題（20分） ，2.應用題（30分）3.程式填空題（30分）4.演算法設計題（20分）
每章複習要點：
第1章：概念理解：資料結構，時間複雜度
程式段：
i=1;
while(i<=n)
i=i*2;
第2章：表的順序儲存結構，鏈式儲存結構（單鏈表、迴圈鍊錶、雙向鍊錶），表的基本操作與應用，本章所佔分值在15分左右，會考表的演算法。
(1)順序儲存結構
1、下面關於線性表的敘述中，錯誤的是哪乙個？（ ）
a．線性表採用順序儲存，必須占用一片連續的儲存單元。
b．線性表採用順序儲存，便於進行插入和刪除操作。
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元。
d．線性表採用鏈結儲存，便於插入和刪除操作。
2、對於順序表的優缺點，以下說法錯誤的是：（）
a、無需為表示節點間的邏輯關係而增加額外的儲存空間；
b、可以方便地隨機訪問表中的任一節點；
c、插入和刪除運算較方便；
d、由於順序表要求占用連續的空間，儲存分配智慧型預先進行。
(2) 鏈式儲存結構
1、鍊錶不具備的特點是？（ ）
a．可隨機訪問任一節點。
b．插入刪除不需要移動元素。
c．不必事先估計儲存空間。
d．所需空間與其長度成正比。
2、（1) 靜態鍊錶既有順序儲存的優點，又有動態鍊錶的優點。所以，它訪問表中第i個元素的時間與i無關。(2) 靜態鍊錶中能容納的元素個數的最大數在表定義時就確定了，以後不能增加。
(3) 靜態鍊錶與動態鍊錶在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ ）。
a．（1）（2） b．（1） c．（1）（2）(3) d．（2）
3、對於乙個頭指標為head的帶頭結點的單鏈表，判定該錶為空表的條件是
a、head==null b、head→next==null c、head→next==head d、head!=null
4、如果對線性表的運算只有兩種，即刪除第乙個元素，在最後乙個元素後面插入新元素，最好使用（）
a、只有表頭指標而沒有表尾指標的迴圈單鏈表
b、只有表尾指標而沒有表頭指標的迴圈單鏈表
c、非迴圈雙鏈表
d、迴圈雙鏈表
5、線性表（ a1,a2,…,an）以鏈結方式儲存時，訪問第i位置元素的時間複雜性為（ ）
a．o（i） b．o（1） c．o（n） d．o（i-1）
第3章：棧的實現，棧的應用（數制轉換，括號匹配），hanoi塔不考，佇列的實現（其中迴圈佇列重點）。本章所佔分值在10分左右，可能會考演算法。
（1）棧
1、乙個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。
a. 2 3 4 1 5 b. 5 4 1 3 2 c. 2 3 1 4 5 d. 1 5 4 3 2
2、輸入序列為abc，輸出為abc時（假設元素出棧則輸出），經過的棧操作為（ ）。
a．push,pop,push,pop,push,pop b．push,push,push,pop,pop,pop
c．push,push,pop,pop,push,pop d．push,pop,push,push,pop,pop
（2）佇列
1、迴圈佇列用陣列a【0…maxsize】存放其元素值，頭尾指標是front和rear，則佇列中元素個數是（）
a、（rear-front-1）%maxsize
b、rear-front
c、（rear-front+1）%maxsize
d、（rear-front+maxsize）%maxsize
2、乙個佇列的入隊序列是1，2，3，4，則佇列的輸出序列是（ ）。
a. 4，3，2，1 b. 1，2，3，4 c.1，4，3，2 d. 3，2，1，4
3、用乙個大小為6的陣列來實現迴圈佇列，且當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear 和front 的值分別為多少？( )。
a. 1 和 5 b. 2 和 4 c. 4 和2 d. 5 和1
第4章：只考計算模式串的next值,不考演算法，本章所佔分值在5分左右
1、串"ababaaababaa"的next陣列為（ ）。
a．012345678999 b．012121111212
c．011234223456 d．012301232234
第5章：陣列的儲存位置計算，壓縮矩陣的儲存（不考演算法）本章所佔分值在5分左右
1、n階對稱矩陣a,將其上三角的元按列優先順序壓縮存放在一維陣列b[1…n(n+1)/2]中，第乙個元素a1，1存於b[1]中，則應存放到b[k]中的元素ai,j(1 <= i <= n,i <= j <= n)的下標i，j與k的對應關係是k=（ ）。
a. i(i+1)/2 + jb. i(i-1)/2 + j
c. j(j+1)/2 + id. j(j-1)/2 + i
2、設有陣列a[i,j]，陣列的每個元素長度為3位元組，i的值為1到8，j的值為1到10，陣列從記憶體首位址ba開始順序存放，當用以列為主存放時，元素a[5，8]的儲存位址為( )。
a. ba+141 b. ba+180 c. ba+222 d. ba+225
第6章：二叉樹的二叉鍊錶儲存，二叉樹的遍歷，霍夫曼樹，本章肯定會考二叉樹相關演算法本章所佔分值在20分左右
1、一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（ ）。
a．250 b．500 c．505 d．501
2、已知一棵二叉樹的前序遍歷結果為abcdef，中序遍歷結果為cbaedf，則後序遍歷的結果為（ ）。
a．cbefda b．fedcba c．cbedfa d．不定
3、已知一棵二叉樹的先序遍歷序列為abd#e##fg###c#h##，#表示空樹，請畫出對應的二叉樹。
4、 已知下列字元a、b、c、d、e、f、g 的權值分別為3、12、7、4、2、8、11，試填寫出其對應哈夫曼樹ht儲存結構的終態，即把下表填充完整。（生成的哈夫曼樹權值左孩子小右孩子大，權值相等時編號小的先取）
5、寫出求二叉樹高度的演算法。
6、一顆度為7的樹有8個度為1的結點、7個度為2的結點、6個度為3的結點、5個度為4的結點、4個度為5的結點、3個度為6的結點、2個度為7的結點，該樹有（）個葉子結點。
7、 已知一棵二叉樹的先序、中序和後序序列如下，其中空缺了部分，請畫出該二叉樹。
先序: _bc_efg_ijk_
中序：cbed_gaj_h_l
後序：_e_fd_j_l_ha
第7章：圖的四種儲存結構，圖的遍歷，最小生成樹，拓撲排序，關鍵路徑與最短路徑，本章所佔分值在15分左右，可能會考演算法，但演算法主要考察圖的遍歷演算法，其他演算法不考。
1、已知無向帶權連通圖g(v, e)的鄰接表如下所示，請畫出該圖，並使用prim或kruskal演算法求出該圖的最小生成樹。
其中邊結點的3個域為：
2、如g3有向圖中，頂點表示課程，弧表示課程間的先後關係。如果每人每學期中學一門課程，則應當如何安排課程學習？給出三種方案。
第9章：順序查詢表，折半查詢表，二叉排序樹（重點），平衡二叉樹，雜湊表，本章所佔分值在15分左右，會考表的演算法（順序查詢，折半，二叉排序樹相關演算法）。
1、對長度為8的有序表，給出折半查詢的判定樹，給出等概率情況下的平均查詢長度。
2、輸入乙個正整數序列，建立一顆二叉排序樹。
3、依次把結點插入到初始狀態為空的平衡二叉樹中,使得在每次插入後保持該樹仍然是平衡二叉樹。依次畫出每次插入後所形成的平衡二叉樹。
4、使用雜湊函式h(key)=key % 9，把乙個整數值轉換成雜湊表下標，現要把資料1，13，12，34，38，33，27，22插入到雜湊表中（表長為9）。
1）使用線性探測法構造雜湊表。
2) 使用鏈位址法構造雜湊表。
第10章：所有的排序方法，本章所佔分值在15分左右，會考演算法（所有的排序方法）。
1. 已知待排序的序列為（503，87，512，61，908，170，897，275，653，462），將待排序的序列公升序排序，請用二叉樹的形式畫出初建堆的過程（只給出建初始堆的過程）。
2. 一組記錄的關鍵字為（22，5，37，14，12），利用快速排序的方法，以第乙個記錄為基準，畫出一次劃分的過程（6分）。
3. 將資料序列(28,76,54,39,87,14,46,25,78,62)按shell排序法進行排序,增量序列為5，3，1，請寫出每倘排序完成之後的序列狀態。
4. 將資料序列(986,321,123,432,500,654,018,765,987,210)進行基數排序,請寫出每趟分配、收集排序過程。
5. 將資料序列(46,35,78,12,62,38,80,29)進行歸併排序,請寫出每趟排序過程。
一．單項選擇題，每小題2分，共80分。
1.為解決計算機與印表機之間速度不匹配的問題，通常設定乙個列印資料緩衝區，主機將要輸出的資料依次寫入該緩衝區，而印表機則依次從該緩衝區中取出資料。該緩衝區的邏輯結構應該是
a.棧b.佇列c.樹d.圖
2.設棧s和佇列q的初始狀態均為空，元素abcdefg依次進入棧s。若每個元素出棧後立即進入佇列q，且7個元素出隊的順序是bdcfeag，則棧s的容量至少是a．1b.
2c.3d.4
3.給定二叉樹圖所示。設n代表二叉樹的根，l代表根結點的左子樹，r代表根結點的右子樹。若遍歷後的結點序列為3，1，7，5，6，2，4，則其遍歷方式是a．
資料結構期末複習提要
電大理工部計算機教研室 資料結構是 電大計算機應用專業一門統設必修課和專業基礎課，它主要研究資料的各種邏輯結構，在計算機中的儲存結構，對資料進行的插入 查詢 刪除 排序 遍歷等運算，這些運算在儲存結構上具體實現的演算法。學習好該課程將為學好整個計算機專業打下堅實的基礎。第一部分各章複習要求 下面按照...
2019春季期末資料結構複習答案
2011春季資料結構期末複習 1.答 樹 2.答 無向圖 3.答 二叉樹 4.答 無向圖 45 6 8 295.答 有向圖 二 10 分別寫出下列二叉樹的先序 中序和後序遍歷序列答 先序遍歷序列是 abdfgche 中序遍歷序列是 fdgbahce 後序遍歷序列是 fgdbheca 三 10 設葉子...
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束，這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...