第一部分：資料結構——線性結構(順序表、鍊錶、棧、佇列、陣列、串)
考點：1、時間複雜度
2、資料的邏輯結構與儲存結構相關知識——分類、與儲存結構之間的關係
3、順序表的知識——特點
4、鍊錶的知識——程式設計求單鏈表中結點的個數、插入、刪除。
5、棧與佇列知識——特點、迴圈佇列、基本術語、鏈佇列
6、陣列與矩陣——求元素的位址、稀疏矩陣
行優先儲存
下標從1開始:
loc(ai,j) = loc(a1,1)+[(i-1)*n+j-1]*b
下標從0開始:
loc(ai,j) = loc(a0,0)+(i*n+j)*b列優先儲存:
下標從1開始:
loc(ai,j) = loc(a1,1)+[(j-1)*m+i-1]*b
下標從0開始:
loc(ai,j) = loc(a0,0)+(j*m+i)*b
1. 設順序線性表中有n個資料元素，則第i個位置上插入乙個資料元素需要移動表中個資料元素；刪除第i個位置上的資料元素需要移動表中個元素。
2.資料的邏輯結構通常有集合、線性結構和四類結構。
3.若進棧序列為a、b、c ，且進棧和出棧可以穿插進行，則可能出現_________個不同的出棧序列。
4.在棧結構中，允許插入的一端稱為在佇列結構中，允許刪除的一端稱為
5. 下列程式段的時間複雜度為
s=0;
for(i=1;ifor(j=1;js+=i*j;
6. 假設某個帶頭結點的單鏈表的頭指標為head，則判定該錶為空表的條件（ ）
a、head= =null b、head->next= =null
c、head!=null d、head->next= =head
7. 棧是一種操作受限的線性結構，其操作的主要特點是（ ）
a、先進先出 b、後進先出 c、進優於出 d、出優於進
8. 假設以陣列a[n]存放迴圈佇列的元素，其頭、尾指標分別為front和rear。若設定尾指標指向佇列中的隊尾元素，頭指標指向佇列中隊頭元素的前乙個位置，則當前存於佇列中的元素個數為
9. 二維陣列a[4][5]按行優先順序儲存，若每個元素佔2個儲存單元，且第乙個元素a[0][0]的儲存位址為1000，則陣列元素a[3][2]的儲存位址為
10．設某資料結構的二元組形式表示為a=(d，r)，d=，r=，r=，則資料結構a是（ ）。
(a) 線性結構 (b) 樹型結構
(c) 物理結構 (d) 圖型結構
11．下面關於線性表的敘述錯誤的是（ ）。
(a) 線性表採用順序儲存必須占用一片連續的儲存空間
(b) 線性表採用鏈式儲存不必占用一片連續的儲存空間
(c) 線性表採用鏈式儲存便於插入和刪除操作的實現
(d) 線性表採用順序儲存便於插入和刪除操作的實現
12.通常從四個方面評價演算法的質量和
11-15為判斷題:
11.順序儲存方式的優點是儲存效率高，且插入元素和刪除元素效率高。
12.對於單迴圈鍊錶，從表中任一結點出發都能掃瞄表中全部結點
13.棧是一種對進棧、出棧操作總次數做了限制的線性表
14.無論是順序佇列還是鏈佇列，插入和刪除元素運算的時間複雜度都是o(1)。
15.稀疏矩陣的特點是矩陣中元素較少。
第二部分：資料結構——非線性結構(樹與二叉樹、圖) 考點：
1、二叉樹的基本術語和性質應用
2、二叉樹的遍歷——先序、中序、後序
3、完全二叉樹和滿二叉樹
4、二叉樹與樹之間的轉換、二叉樹與森林之間的轉換
5、哈夫曼樹——構造哈夫曼樹、wpl、哈夫曼編碼
6、採用二叉鍊錶儲存結構，實現二叉樹遞迴程式設計——遍歷、求二叉樹總結點數、求二叉樹葉子結點數、求二叉樹的深度
7、圖的基本術語
8、圖的儲存結構——鄰接矩陣表示法、鄰接鍊錶表示法
9、圖的遍歷——深度優先搜尋遍歷(dfs)、廣度優先搜尋遍歷(bfs)
10、圖的應用——最小生成樹（普里姆演算法）、拓撲排序
1.深度為k的二叉樹至多有個結點，最少有個結點。
2.設哈夫曼樹中共有99個結點，則該樹中有個葉子結點；若採用二叉鍊錶作為儲存結構，則該樹中有個空指標域。
3.設無向圖對應的鄰接矩陣為a，則a中第i行上非0元素的個數第i列上非0元素的個數（填等於，大於或小於）。
4.二叉樹就是度為2的樹
5.只要知道完全二叉樹中結點的先序序列，就可以唯一確定它的邏輯結構。
6.將一棵樹轉化成二叉樹後，該二叉樹根結點沒有左子樹
7.在有向圖中，各頂點的入度之和等於各頂點的出度之和
8.強連通圖不能進行拓撲排序
9. 高度為5的完全二叉樹中含有的結點數至少為
10. 一棵完全二叉樹上有1001個結點，其葉子結點的個數是
11. 在高度為h的完全二叉樹中，（ ）
a、度為0的結點都在第h層上
b、第i（1<=i<=h）層上結點都是度為2的結點
c、第i（1<=i<=h-1）層上有2i-1個結點
d、不存在度為1的結點
12. 有n個結點的無向圖的邊數最多為（ ）
a、n+1b、n(n-1)/2c、n(n+1) d、2n
13. 如圖所示有向圖的乙個拓撲序列是（ ）
a、abcdef b、fcbead
c、fedcba d、daebcf
14. 設圖的鄰接矩陣為，則該圖為( )
a、有向圖b、無向圖 c、強連通圖 d、完全圖
15. 已知一棵二叉樹的前序序列是abcdefg，中序序列是cbdaegf。請畫出該二叉樹，並給出該二叉樹的後序序列。
16.設無向圖g（如下圖所示），給出該圖的最小生成樹上邊的集合，並計算最小生成樹各邊上的權值之和。
17.以資料作為葉子結點的權值構造一棵哈夫曼樹，並計算出其帶權路徑長度。
18、以二叉鍊錶為儲存結構:
(1)寫出求二叉樹總結點數的演算法。
(2)寫出求二叉樹的深度的演算法。
(3)設計乙個求結點x在二叉樹中的雙親結點演算法.
要求：給出二叉鍊錶的c語言描述；採用遞迴的思想實現該演算法。
19、給出某個圖的鄰接矩陣或鄰接鍊錶，請畫出該圖，並給出dfs和bfs.
20．若一棵二叉樹的前序遍歷序列與後序遍歷序列相同，則該二叉樹可能的形狀是( )。
(a)樹中沒有度為2的結點 (b)樹中只有乙個根結點
(c)樹中非葉結點均只有左子樹
(d)樹中非葉結點均只有右子樹
21．設某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。
(a) n(n-1) (b) n+1 (c) n (d) n(n+1)
22．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（ ）個表頭結點。
(a) n-1 (b) n (c) n+1 (d) 2n-1
23.若用鍊錶儲存一棵二叉樹時，每個結點除資料域外，還有指向左孩子和右孩子的兩個指標。在這種儲存結構中，n個結點的二叉樹共有________個指標域，其中有________個指標域是存放了位址，有個指標是空指標。
24.深度為k的完全二叉樹中最少有_________個結點。
25.對於乙個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_______個和________個。
第三部分：資料結構——查詢與內部排序考點：
1、二分查詢（折半查詢）
2、雜湊查詢
雜湊函式:除留餘數法
解決衝突方法: 線性探測法、二次探測法
3、二叉排序樹
1. 對長度為15的有序順序表進行二分查詢，在各記錄的查詢概率均相等的情況下，查詢成功時所需進行的關鍵字比較次數的平均值為
a、39/15b、49/15
c、50/15d、55/15
5.根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為
9. 下面程式段的功能是實現二分查詢演算法，請在下劃線處填上正確的語句。
struct record;
資料結構複習題 2019
資料結構期末複習題1 0907 一 基本要求 1 資料結構基本概念 1 資料 資料物件和資料結構 邏輯 物理結構 基本操作 2 抽象資料型別 3 演算法的特徵及評價的標準 2 線形結構 1 順序表的特點及儲存結構 2 鍊錶的特點及儲存結構 3 棧的特點及基本操作 4 佇列的特點及基本操作 5 順序串...
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...