第1章緒論（已校對無誤）
1．資料結構包括資料的邏輯結構 、 資料的儲存結構和資料的運算三方面的內容。2．程式包括兩個內容： 資料結構和演算法 。
3. 資料結構的形式定義為：資料結構是乙個二元組： data structure =（d，s） 。
4. 資料的邏輯結構在計算機儲存器內的表示，稱為資料的儲存結構 。
5. 資料的邏輯結構可以分類為線性結構和非線性結構兩大類。
6. 在圖狀結構中，每個結點的前驅結點數和後繼結點數可以有多個 。
7. 在樹形結構中，資料元素之間存在一對多的關係。
8. 資料的物理結構，指資料元素在計算機中的標識（映象），也即儲存結構 。
9. 資料的邏輯結構包括線性結構 、 樹形結構和圖形結構 3種型別，樹型結構和有向圖結構合稱為非線性結構 。
10. 順序儲存結構是把邏輯上相鄰的結點儲存在物理上連續的儲存單元裡，結點之間的邏輯關係由儲存單元位置的鄰接關係來體現。
11. 鏈式儲存結構是把邏輯上相鄰的結點儲存在物理上任意的儲存單元裡，節點之間的邏輯關係由附加的指標域來體現。
12. 資料的儲存結構可用4種基本的儲存方法表示，它們分別是順序儲存 、 鏈式儲存 、 索引儲存和雜湊儲存 。
13. 線性結構反映結點間的邏輯關係是一對一的，非線性結構反映結點間的邏輯關係是一對多或多對多 。
14. 資料結構在物理上可分為順序儲存結構和鏈式儲存結構。
15. 我們把每種資料結構均視為抽象型別，它不但定義了資料的表示方式，還給出了處理資料的實現方法 。
16. 資料元素可由若干個資料項組成。
17. 演算法分析的兩個主要方面是時間複雜度和空間複雜度。
18. 乙個演算法的時間複雜度是用該演算法所消耗的時間的多少來度量的，乙個演算法的空間複雜度是用該演算法在執行過程中所占用的儲存空間的大小來度量的。
19. 演算法具有如下特點： 有窮性 、確定性、 可行性 、輸入、輸出。
20. 對於某一類特定的問題，演算法給出了解決問題的一系列操作，每一操作都有它的確切的定義，並在有窮時間內計算出結果。
21. 下面程式段的時間複雜度為 ㏒3n 。
i=1；
while(i<=n)
i= i﹡3；
第2章線性表（已校對無誤）
1. 一線性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每個ai代表乙個資料元素（或結點） 。
a1稱為起始結點，an稱為終端結點，i稱為ai**性表中的位置（或序號） 。對任意一對相鄰結點ai，ai+1，（1≤i≤n），ai稱為ai+1的直接前驅 ，ai+1稱為ai的直接後繼 。
2. 對乙個長度為n的線性表，要刪除第i個元素，則在順序表示的情況下，計算複雜性為 o(n) ，在鏈式表示的情況下，計算複雜性為 o(1) 。
3. 在乙個長度為n的順序表中，向第i個元素（1≤i≤n）之前插入乙個新元素時，需向後移動 n－i＋1 個元素。
4. 順序表中邏輯上相鄰的元素在物理位置上一定相連。
5. 在n個結點的順序表中插入乙個結點需平均移動 n/2 個結點，具體的移動次數取決於表長n和插入位置i 。
6. 在順序表中訪問任意乙個結點的時間複雜度均為 o(1) ，因此，順序表也稱為隨機訪問的資料結構。
7. 順序表相對於鍊錶的優點有隨機訪問和空間利用率高 。
8. 在長度為n的順序表中插入乙個元素的時間複雜度為 o(n) 。
9. 在帶有頭結點的單鏈表l中，若要刪除第乙個結點，則須執行下列三條語句： u＝l->next ；l->next=u->next；free（u）。
10. 鍊錶相對於順序表的優點有插入和刪除操作方便。
11. 在單鏈表中除首結點外，任意結點的儲存位置都由直接前驅結點中的指標指示。
12. 在n個結點的單鏈表中要刪除已知結點*p，需找到它的直接前驅結點的位址 ，其時間複雜度為 o(n) 。
13．單鏈表中設定頭結點的作用是簡化操作，減少邊界條件的判斷 。
14．在帶表頭結點的單鏈表中，當刪除某一指定結點時，必須找到該結點的前驅結點。
15. 在雙鏈表中，每個結點有兩個指標域，乙個指向前驅結點 ，另乙個指向後續結點 。
16. 帶頭結點的單鏈表l為空的判定條件是 l->next==null ，不帶頭結點的單鏈表l為空的判定條件是 l==null 。
17. 在單鏈表中，指標p所指結點為最後乙個結點的條件是 p->next==null 。
18. 迴圈鍊錶的最大優點是從表中任意結點出發都可訪問到表中每乙個元素（或從表中任意結點出發都可遍歷整個鍊錶） 。
19. 設rear是指向非空、帶頭結點的迴圈單鏈表的尾指標，則該鍊錶首結點的儲存位置是 rear->next->next 。
20. 帶頭結點的雙向迴圈表l為空表的條件是 l->prior== l->next 。
21. 在迴圈鍊錶中，可根據任一結點的位址遍歷整個鍊錶，而單鏈表中需知道頭指標才能遍歷整個鍊錶。
22. 將兩個各有n個元素的有序表歸併成乙個有序表，其最少的比較次數是 1 。
第3章棧和佇列（已校對無誤）
1. 棧又稱為後進先出表，佇列又稱為先進先出表。
2. 向乙個順序棧插入乙個元素時，首先使棧頂指標後移乙個位置，然後把待插入元素寫入（或插入） 到這個位置上。
3. 從乙個棧刪除元素時，需要前移一位棧頂指標 。
4. 在乙個順序棧中，若棧頂指標等於 －1 ，則為空棧；
若棧頂指標等於 maxsize－1 ，則為滿棧。
5. 在乙個鏈式棧中，若棧頂指標等於null，則為空棧 ；在乙個鏈式佇列中，若隊頭指標與隊尾指標的值相同，則表示該隊列為空或該佇列只含有乙個結點 。
6. 向乙個鏈式棧插入乙個新結點時，首先把棧頂指標的值賦給新結點的指標域 ，然後把新結點的儲存位置賦給棧頂指標 。
7．在求表示式值的算符優先演算法中使用的主要資料結構是棧 。
8．設有乙個順序棧s，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的出棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 3 。
9. 設有乙個空棧，現輸入序列為1，2，3，4，5。經過push，push，pop，push，pop，push，pop，push後，輸出序列是 2 3 4 。
10. 在按算符優先法求解表示式3－1＋5*2時，最先執行的運算是 * ，最後執行的運算是 － 。
11. 在棧的adt定義中，除初始化操作外，其他基本操作的初始條件都要求棧存在 。
12. 僅允許在同一端進行插入和刪除的線性表稱為棧 。
13. 在順序棧s中，棧為空的條件是 ，棧為滿的條件是 。
14. 設有算術表示式x＋a*（y－b）－c/d，該表示式的字首表示為 －＋x*a－yb/cd 。
字尾表示為 xayb－*＋cd/－ 。
15. 用s表示入棧操作，x表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應的s、x操作串為 sxssxsxx 。
16. 向乙個棧頂指標為top的鏈式棧中插入乙個新結點*p時，應執行 p->link＝top 和 top＝p 操作。
17. 從乙個棧頂指標為top的非空鏈式棧中刪除結點並不需要返回棧頂結點的值和**結點時，應執行 top＝top->link 操作。
18. 設有乙個空棧，棧頂指標為1000h（十六進製制。現有輸入序列為1，2，3，4，5，經過push，push，pop，push，pop，push，push之後，輸出序列是 2，3 ，而棧頂指標是 100c h。
設棧為順序棧，每個元素佔4個位元組。
19. 在作入棧運算時應先判別棧是否滿 ；在作出棧運算時應先判別棧是否空 。
10. 用乙個大小為1000的陣列來實現迴圈佇列，當前rear和front的值分別為0和994，若要達到隊滿的條件，還需要繼續入隊的元素個數是 993 。
20. 佇列的插入操作在隊尾進行，刪除操作在隊頭進行。
21. 在乙個迴圈佇列q中，判斷隊空的條件為 ，判斷隊滿的條件為 ( 。
22. 向乙個迴圈佇列中插入元素時，需要首先移動隊尾指標 ，然後再向所指位置寫入（或插入） 新插入的元素。
23. 當用長度為n的陣列順序儲存乙個棧時，若用top==n表示棧空，則表示棧滿的條件為 top==0 。
24. 迴圈佇列的引入，目的是為了克服假溢位時大量移動資料元素 。
第4章串（已校對無誤）
1. 兩個串相等的充分必要條件是兩個串的長度相等且對應位置的字元相同 。
2. 空格串是由乙個或多個空格字元組成的串 ，其長度等於其包含的空格個數 。
3. 模式串′abaabade′的next函式值為 01122341
補充：1. 串的兩種最基本的儲存方式是順序儲存方式和鏈結儲存方式 。
2. 空串是零個字元的串 ，其長度等於零 。
3. 組成串的資料元素只能是字元 。
4. 串是一種特殊的線性表，其特殊性表現在其資料元素都是字元 。
第5章陣列（已校對無誤）
1. 將下三角矩陣a[1..8，1..8]的下三角部分逐行地儲存到起始位址為1000的記憶體單元中，已知每個元素佔4個單元，則元素a[7，5]的位址為 1100 。
2. 二維陣列a[0…9，0…19]採用列序為主方式儲存，每個元素佔乙個儲存單元，並且元素a[0，0]的儲存位址是200，則元素a[6，12]的位址是 332 。
資料結構填空題
3 填空題 1.資料有 邏輯結構 和 儲存結構 兩種結構。2.資料邏輯結構除了集合以外，還包括 線性結構 樹形結構和圖形結構 3.資料結構按邏輯結構可分為兩大類，它們是 線性結構和非線性結構 4.樹形結構和圖形結構 合稱為非線性結構。5.在樹形結構中，除了樹根結點以外，其餘每個結點只有 1 個前驅結...
資料結構作業答案
第一章單選題1 下列關於演算法的基本特徵，說法不正確的是 能行性是演算法中的每乙個步驟必須能夠實現且能達到預期的目的。演算法的確定性是指演算法中的每乙個步驟必須是有明確的定義，不允許模稜兩可。演算法的有窮性是指演算法必須能在有限的時間內做完。演算法與提供情報無關。d 教師批改 d 2 演算法的時間複...
資料結構填空題題庫
1.線性結構中元素之間存在著 一對一 關係，樹型結構中元素之間存在著 一對多 關係。2.評價資料結構的兩條基本標準是 儲存需要量 和 運算的時間效率 3.演算法的五個特性是指 有窮性 確定性 可行性 輸入和輸出 4.資料的邏輯結構是從邏輯關係上描述資料，它與資料的 儲存結構 無關，是獨立於計算機的。...