一、 填空題
1. 資料結構是研究資料的__邏輯結構_和_物理結構，並在這種結構上定義相關的運算，設計實現這些運算的演算法，分析演算法的效率。演算法的效率包括時間和空間兩個方面，分別稱為___時間複雜度__和__空間複雜度___。
2. 資料的基本單位是__資料元素，資料的最小單位是__ 資料項。
3. 演算法是對特定問題求解___步驟____的一種描述，是指令的有限序列。
4. 乙個演算法的時間複雜度為(3n3+2n—7)，其數量級表示為 o（n3）。
5. 乙個演算法具有5個特性： 確定性 、 可行性 、 有窮性 、輸入和輸出。
6. 演算法效能的分析和度量，可以從演算法的時間複雜度和空間複雜度來評價演算法的優劣。
7. 資料的邏輯結構包括集合結構、 線性結構 、 樹形結構和圖型結構四種型別。
8. 通常象交通、道路問題的數學模型是一種稱為圖型結構的資料結構。
9. 資料結構在計算機中的表示稱為資料的物理結構 ，它可以採用___順序儲存___或_鏈式儲存__兩種儲存方法。
10. 線性表有兩種儲存結構，分別為順序儲存和鏈式儲存 。
11. 鏈式儲存的特點是利用指標來表示資料元素之間的邏輯關係。
12. 若頻繁地對線性表進行插入和刪除操作，該線性表宜採用_鏈式儲存____儲存結構。
13. 線性表中的資料元素之間具有一對一的線性關係，除第乙個和最後乙個元素外，其他資料元素有且只有乙個直接後繼和直接前趨。
14. 順序表中邏輯上相鄰的元素的物理位置_也相鄰____。
15. 在單鏈表l中，指標p所指結點有後繼結點的條件是__p->next!=null__。
16. 在順序儲存的線性表中插入或刪除乙個元素平均約移動表中__50%_（或一半）_的元素.
17. 在乙個單鏈表中p所指結點之後插入乙個s所指結點時，應執行s->next=_p->next__和p->next=__s____的操作。
18. 在乙個單鏈表中刪除p的後繼結點q時，應執行以下操作p->next= q->next 。
19. 對帶頭結點head的單鏈表，則判斷其為空的條件為 head->next=null 。
20. 對帶頭結點head的迴圈單鏈表尾結點(由p所指向)判非空的條件為 p->next=head 。
21. 在棧結構中，允許插入的一端稱為棧頂 ；在佇列結構中，允許插入的一端稱為隊尾 。
22. 棧是一種特殊的線性表，它允許在表的一端進行_插入和刪除___操作，棧中元素的進出原則為__先進後出__。
23. 佇列中元素的入隊和出隊應遵循 _先進先出___原則，資料元素1，2，3，4，5按照次序入隊後，第乙個出隊的是__ 1 ____。
24. 在迴圈佇列中，儲存空間為0～n-1。設隊頭指標front指向隊頭元素前乙個空閒元素，隊尾指標指向隊尾元素，那麼其隊空標誌為rear=front，隊滿標誌為 (rear+1)% n=front 。
25. 假定乙個順序佇列的對首和隊尾分別為f和r，則判斷隊空的條件為_f=r____。
26. 設順序表有19個元素，第乙個元素的位址為200，且每個元素佔3個位元組，則第14個元素的儲存位址為 239 。
27. 在乙個長度為n的順序表中刪除第i個元素（1≤i≤n），需向前移動 n-i 個元素。
28. 在乙個長度為n的順序表中第i個元素前（1≤i≤n），插入乙個元素，需向後移動 n-i+1 個元素。
29. 若線性表採用順序儲存結構，線性表的最大長度為1000，每個資料元素佔3個儲存單元，則要分配給該線性表____3000______儲存單元，若第乙個資料元素的儲存位址是2000，則第11個元素的儲存位址是_____2030_____。
30. 二維陣列有兩種儲存方式，第一種是以___行__為主序的儲存方式，第二種是以___列__為主序的儲存方式。現有乙個二維陣列a[6][7] ，按第一種方式儲存，a[0][0]的儲存位址是1000，每個元素佔5個位元組，則元素a[3][5]的儲存位址是___1115_ __。
1000+(3*7+5)*5
31. 設有乙個二維陣列a[5][4]，按行序優先儲存，a[0][0]的儲存位址是10，每個陣列元素佔2個位元組，則a[3][2]的儲存位址是_128(10+(3*4+2)*2_)__。
32. 現有乙個二維陣列a[6][8] ，若以行為主序順序儲存, a[0][0]的儲存位址是2000，每個元素佔2個位元組，則元素a[3][5]的儲存位址是____2046 _。若以列為主序順序儲存, 則元素a[3][5]的儲存位址是_ 2086 。
33. 兩個串相等的充分必要條件是:___串長相等___ 且 __對應的字元相等___。
34. 不含任何字元的串稱為空串其長度為 0 。
35. 對於稀疏矩陣的壓縮儲存，通常用乙個三元組表示非零元素的資訊，其中包括非零元素所在的行 、 列以及它的值。
36. 若二叉樹中有20個葉子結點，則該二叉樹有 19 個度為2的結點。
37. 若二叉樹中度為2的結點有15個，則該二叉樹有___16____個葉子結點。
38. 深度為h且有___2^h-1___個結點的二叉樹稱為滿二叉樹。
39. 深度為k的二叉樹最多有 2^k-1 個結點，最少有 k 個結點，第i 層上最多有___2^(i-1)__個結點。
40. 深度為5的滿二叉樹共有 31 個結點，其中有__16___個葉子節點。
41. 若深度為6的完全二叉樹的第6層有3個葉結點，則該二叉樹一共有 34 個結點。
42. 深度為15的滿二叉樹上，第11層有 1024 個結點。
43. 一棵具有100個結點的完全二叉樹，它的深度為 7 ，其中度為1的結點有1 個。
44. 某二叉樹的後根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為 dab 。
45. 哈夫曼樹是指對於一組帶有確定權值的葉子結點構造的具有最小帶權路徑長度的二叉樹。
46. 具有m個葉子結點的哈夫曼樹共有 2m-1 個結點。
47. 已知一棵哈夫曼樹含有60個葉子結點，則該樹中共有 59 個非葉子結點。
48. 由五個分別帶權值為9，2，3，5，14的葉子結點構成的一棵哈夫曼樹，該樹的帶權路徑長度
為_67__。
49. 在乙個具有n個頂點無向完全圖中，含有 n(n-1)/2 邊；在乙個具有n個頂點有向完全圖中，含有 n(n-1) 邊。乙個具有4個頂點的無向完全圖有 6 條邊。
50. 在乙個有向圖中，某個結點的度是指該結點的__出度___和___入度___之和。
51. 具有n個頂點的連通圖至少需有 n-1 條邊。
52. 乙個連通圖的生成樹是該圖的極小連通子圖。若這個連通圖有n個頂點，則它的生成樹有n-1 條邊。
53. 在有向圖的鄰接矩陣中，第i行中非零元素的個數正好是第i個頂點的出度 ；第i列中非零元素的個數正好是第i個頂點的入度 。
54. 在乙個圖中，所有頂點的度數之和等於所有邊數的 2 倍。
55. 在無向圖g的鄰接矩陣a中，若a［i］［j］等於1，則a［j］［i］等於 1 。
56. 設連通圖g有n個頂點，則g的生成樹一定有 n-1 邊。
57. 可以進行拓撲排序的有向圖一定是沒有環（迴路） ；在拓撲排序序列中第乙個頂點一定是入度為0的頂點。
58. dijkstra演算法是按路徑長度遞增的次序產生從乙個頂點到其餘各頂點最短路徑的演算法。
59. 對二叉排序樹進行中序遍歷，可以得到按關鍵字從小到大排列的結點序列。
60. 乙個有序表為，當折半查詢值為82的結點時，經過 4 次比較後查詢成功。
61. **性表中採用折半查詢法查詢乙個資料元素，線性表中元素應該按值有序，並且採用_順序儲存__儲存方法。
62. 若關鍵碼序列為(18,25,63,50,42,32,9)，雜湊函式為h(key)=key mod 9，與18發生衝突的元素有____2____個。
63. **性表的折半查詢法中要求線性表的儲存結構必須是採用_順序儲存__，且表中的元素必須是__有序___。
64. 在簡單選擇排序、堆排序、快速排列、歸併排序四種排序方法中，排序方法穩定的是_歸併排序_。
65. 氣泡排序是一種穩定的排序方法，對n個元素的序列進行氣泡排序時，最多需進行 n-1 趟。該排序方法的時間複雜度為 o(n2) 。
66. 給定序列，按堆的定義，則它一定大根堆。
67. 快速排序在平均情況下的時間複雜度為_o(nlog2 n)，在最環情況下的時間複雜度為__o(n2)_。
68. 資料結構是指資料及其相互之間的___一種或多種關係___。當結點之間存在m對n（m：n）的聯絡時，稱這種結構為___圖狀結構___。
69. 佇列的插入操作是在佇列的____隊尾_____進行，刪除操作是在佇列的__隊頭___進行。
70. 每次從無序表中順序取出乙個元素，把它插入到有序表中的適當位置，此種排序方法叫做___直接插入___排序；每次從無序表中挑選出乙個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做___ 簡單選擇___排序。
71. 二叉樹的前序遍歷序列為a，b，c，e，f，d，g，h，中序遍歷序列為a，e，c，f，b，g，d，h，其後序遍歷序列為_____e,f,c,g,h,d,b,a
72. 對於一棵具有n個結點的二叉樹，若乙個結點的編號為i(o＜i＜n—1)，則它的左孩子結點的編號為 2i ，右孩子結點的編號為 2i+1 ，雙親結點的編號為 i/2 。
73. 在乙個具有6個頂點的無向完全圖中，包含有 15 條邊，在乙個具有6個頂點的有向完全圖中，包含有 30 條邊。
74. 假設雜湊表的表長為11,雜湊函式為h(key)=key%7,若用線性探測處理衝突,則探查位址序列hi的計算公式為__hi=(hash(key)+di)mod m
75. 快速排序在平均情況下的時間複雜度為___o(nlog2n)__，在最壞情況下的時間複雜度為___o(n2)__。
資料結構總複習題
第一章概論 一 填空題 1 資料的儲存結構可用四種基本的儲存方法表示，分別是順序 鏈式 索引和雜湊。2 乙個演算法具有5個特性 有窮性 確定性 可行性，有零個或多個輸入 有乙個或多個輸出 3 資料結構包括資料的邏輯結構 儲存結構和運算 或基本操作 這三個方面的內容。4 資料結構中評價演算法的兩個重要...
資料結構複習題
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 分劃交換排...