8. 設指標變數p指向單鏈表結點a，則刪除結點a的後繼結點b需要的操作為( )。
√a）p->next=p->next->nextb） p=p->next
c）p=p->next->nextd） p->next=p
9. ( )又稱為fifo表；( )又稱為filo表。
√a）佇列 b）雜湊表c）棧 d）雜湊表
10. 對於棧運算元據的原則是（ ）。
a） 先進先出√b） 後進先出 c） 後進後出 d） 不分順序
11. 用不帶頭結點的單鏈表儲存佇列時，其隊頭指標指向隊頭結點，其隊尾指標指向隊尾結點，則在進行刪除操作時( )。
√a）僅修改隊頭指標b） 僅修改隊尾指標
c） 隊頭、隊尾指標都要修改 d） 隊頭、隊尾指標都可能要修改
12. 假設以陣列a[m]存放迴圈佇列的元素，其頭尾指標分別為front和rear，則當前佇列中的元素個數為（ ）。
√a）(rear-front+m)%m b）rear-front+1 c）(front-rear+m)%m d）(rear-front)%m
13. 棧和佇列的共同點是（ ）。
a） 都是先進先出b） 都是先進後出
√c） 只允許在端點處插入和刪除元素 d） 沒有共同點
14. 設棧s和佇列q的初始狀態為空，元素e1，e2，e3，e4,e5和e6依次通過棧s，乙個元素出棧後即進佇列q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧s的容量至少應該是( )。
a） 6 b） 4 √c） 3 d） 2
15. 設有乙個10階的對稱矩陣a，採用壓縮儲存方式，以行序為主儲存，a11為第一元素，其儲存位址為1，每個元素佔乙個位址空間，則a85的位址為（ ）。
a） 12b） 33 c） 18 d） 40
16. 由3 個結點可以構造出多少種不同的二叉樹？( )
a）2 b）3 c）4 √d）5
17. 二叉樹中第i(i≥1)層上的結點數最多有( )個。
a） 2i b） 2i √c） 2i-1 d） 2i-1
18. 在有n個葉子結點的哈夫曼樹中，其結點總數為( )。
a）不確定 b）2n c）2n+1 √d）2n-1
19. 一棵二叉樹高度為h，所有結點的度或為0、或為2，則這棵二叉樹最少有( )結點。
a）2hb）2h-1 c）2h+1 d）h+1
20. 若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是( )。
a）9b）11 c）15 d）不確定
21. 樹的後根遍歷序列等同於該樹對應的二叉樹的( )。
a） 先序序列√b） 中序序列 c） 後序序列 d）層序序列
22. 在二叉樹結點的先序序列，中序序列和後序序列中，所有葉子結點的先後順序( )。
a）都不相同b）完全相同
c）先序和中序相同，而與後序不同d）中序和後序相同，而與先序不同
23. 下列哪一種圖的鄰接矩陣是對稱矩陣？( )
a）有向圖√b）無向圖 c）aov網 d）aoe網
24. 在乙個無向圖中，所有頂點的度數之和等於所有邊數(2 )倍，在乙個有向圖中，所有頂點的入度之和等於所有頂點出度之和的(1 )倍。
a）1/2b）2c）1 d）4
25. 乙個有n個頂點的無向圖最多有( )條邊。由n個頂點組成的有向圖，最多可以有( )條邊。
a）n*n b）2nc）n(n-1d）n(n-1)/2
26. 下列說法不正確的是( )。
a）圖的遍歷是從給定的源點出發每乙個頂點僅被訪問一次
b）遍歷的基本演算法有兩種：深度遍歷和廣度遍歷
√c）圖的深度遍歷不適用於有向圖
d）圖的深度遍歷是乙個遞迴過程
27. 下面哪一方法可以判斷出乙個有向圖是否有環(迴路) ( )。
a）深度優先遍歷 √b） 拓撲排序 c） 求最短路徑 d） 求關鍵路徑
28. 下列演算法中，( )演算法用來求圖中每對頂點之間的最短路徑。
a）dijkstra √b）floyed c）prim d）kruskal
29. 關鍵路徑是事件結點網路中( )。
√a）從源點到匯點的最長路徑 b）從源點到匯點的最短路徑
c）最長迴路 d）最短迴路
30. 若查詢每個記錄的概率均等，則在具有n個記錄的連續順序檔案中採用順序查詢法查詢乙個記錄，其平均查詢長度asl為( )。
a） (n-1)/2 b） n/2c） (n+1)/2 d） n
31. 下面關於二分查詢的敘述正確的是 ( ) 。
a） 表必須有序，表可以順序方式儲存，也可以鍊錶方式儲存
b） 表必須有序，而且只能從小到大排列
c 表必須有序且表中資料必須是整型，實型或字元型
√d） 表必須有序，且表只能以順序方式儲存
32. 折半查詢的時間複雜性為( ) 。
a） o(n2b） o(nc） o(nlognd）o(logn)
33. 當採用分快查詢時，資料的組織方式為 ( ) 。
a）資料分成若干塊，每塊內資料有序
√b）資料分成若干塊，每塊內資料不必有序，但塊間必須有序，每塊內最大(或最小)的資料組成索引塊
c） 資料分成若干塊，每塊內資料有序，每塊內最大(或最小)的資料組成索引塊
d） 資料分成若干塊，每塊(除最後一塊外)中資料個數需相同
34. 下面關於雜湊(hash，雜湊)查詢的說法正確的是( )。
a）雜湊函式構造的越複雜越好，因為這樣隨機性好，衝突小
b）除留餘數法是所有雜湊函式中最好的
√c）不存在特別好與壞的雜湊函式，要視情況而定
d）若需在雜湊表中刪去乙個元素，不管用何種方法解決衝突都只要簡單的將該元素刪去即可
35. 下面給出的四種排序法中( )排序法是不穩定性排序法。
a） 插入 b） 冒泡 c） 二路歸併√d） 堆
36. 穩定的排序方法是( ) 。
a）直接插入排序和快速排序 √b）折半插入排序和起泡排序
c）簡單選擇排序和四路歸併排序 d）樹形選擇排序和shell排序
37. 有一組資料(15，9，7，8，20，-1，7，4) 用快速排序的劃分方法進行一趟劃分後資料的排序為 ( )(按遞增序)。
√a）下面的b，c，d都不對。 b）9，7，8，4，-1，7，15，20
c）20，15，8，9，7，-1，4，7 d）9，4，7，8，7，-1，15，20
38. 設有乙個檔案有200個記錄，按分塊查詢法查詢記錄，如分成10塊，每塊20個記錄，用二分查詢法查索引表，用順序查詢法查塊內記錄，則平均查詢長度為( )。
a）8）4b）10）5c）13）4d）16
39. 快速排序在最壞情況下的時間複雜性為( )。
a）o(nlog2nb）o(n2c）o(n) d）o(nlogn)
二、填空
1. 乙個演算法的效率可分為時間效率和空間效率。
2. 線性表l=（a1,a2,…,an）用陣列表示，假定插入、刪除表中任一元素的概率相同，則插入、刪除乙個元素平均需要移動元素的個數是 n/2和 (n-1)/2 。
3. 對於乙個具有n個結點的單鏈表，在已知的結點*p後插入乙個新結點的時間複雜度為 o(1) ，在給定值為x的結點後插入乙個新結點的時間複雜度為 o(n) 。
4. 順序儲存結構是通過元素在計算機內「物理位置相鄰」 表示元素之間的邏輯關係的，鏈式儲存結構是通過指標表示元素之間的邏輯關係的。
5. 帶頭結點的雙迴圈鍊錶l為空表的條件是： p-next=head 。
6. 當兩個棧共享一儲存區時，棧利用一維陣列stack(1,n)表示，兩棧頂指標為top1與top2，則當棧1空時，top1為 1 ，棧2空時 ，top2為 n ，棧滿時為 top1+top2==n 。
7. 順序棧s用data[1））n]儲存資料，棧頂指標是top，則值為x的元素入棧的操作是 *s）top++=x 。
8. 已知鏈佇列q的頭尾指標分別是f和r，則將值x入隊的操作序列是 p->data=e;p->next=null;q）r->next=p;q）r=p; 。
9. 稀疏矩陣的儲存策略是只儲存非零元素。
10. 稀疏矩陣的儲存方法主要有兩個：乙個是三元組 ，另乙個是十字鏈表示法。
11. 二叉樹由根 ， 左子樹右子樹三個基本單元組成。
12. 一棵有n個結點的滿二叉樹有 n1=0 個度為1的結點、有 (n-1)/2, (n1+2n2)個分支 (非終端)結點和 (n=n0+n1+n2, n0= n2+1), (n+1)/2 個葉子，該滿二叉樹的深度為log2(n+1) 。
13. 設f是由t1,t2,t3三棵樹組成的森林，與f對應的二叉樹為b，已知t1,t2,t3的結點數分別為n1，n2和n3則二叉樹b的左子樹中有 n1-1 個結點，右子樹中有 n2+n3 個結點。
14. 線索二叉樹的左線索指向其前驅右線索指向其後繼 。
15. 設一棵huffman樹有6個葉結點，權值分別為3、4、7、14、15、20，則根節點的權值是 63 。
當初始記錄序列按關鍵字有序或基本有序時，快速排序演算法的時間複雜性為o(n2)。
資料結構複習總結答案
第一章緒論 一 填空題 1 資料是描述客觀事物的數 字元以及所有能輸入到計算機且能夠被電腦程式加工處理的符號集合是資料的基本單位是資料的最小單位。通常被計算機加工處理的資料不是孤立無關的，而是彼此之間存在著某種聯絡，將這種資料間的聯絡稱為 2 資料結構進行形式化定義時，可以從邏輯上認為資料結構ds是...
資料結構答案
1 有乙個帶頭指標的單鏈表，寫出在值為x的結點之後插入m個結點的演算法 int insertm linklist l,int x,int m p next q連線斷點 3 假設乙個長度大於1的單迴圈鍊錶既無頭結點也無頭指標，s為指向鍊錶中某個結點的指標，試設計刪除結點s的直接前驅結點的演算法 voi...
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束，這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...