自考資料結構筆記(詳盡版)
感謝熱心自考人：liuii322
筆記特點：圖例豐富，超級詳細，幾乎涵蓋本課程所有要求掌握的知識點，。。。用於複習和做小條
概論- 學習資料結構的意義 5
概論- 演算法的描述和分析(一) 5
線性表 - 鏈式儲存結構- 單鏈表的運算（一） 14
三棧和佇列 - 棧 - 棧的定義及基本運算 22
三棧和佇列 - 佇列 - 佇列的定義及基本運算 25
三棧和佇列 - 佇列 - 順序佇列 25
棧和佇列 - 佇列 - 鏈佇列 26
三棧和佇列 - 棧和佇列的應用例項 - 棧的應用例項（一） 27
四—串的基本概念（一） 30
圖 - 圖的概念（一） 63
圖 - 圖的儲存結構 - 鄰接矩陣表示法 67
圖 - 圖的遍歷 - 深度優先遍歷（一） 72
圖 - 圖的遍歷 - 廣度優先遍歷 （一） 75
圖 - 生成樹和最小生成樹 - 生成樹 77
圖 - 生成樹和最小生成樹 - 最小生成樹（一） 79
圖 - 最短路徑 （一） 82
圖 - 拓撲排序 （一） 84
排序 - 排序基本概念 （一） 86
排序 - 插入排序 - 直接插入排序（一） 87
排序 - 插入排序 - 直接插入排序（二） 88
排序 - 插入排序 - 希爾排序 89
排序 - 交換排序 - 氣泡排序（一） 90
排序 - 交換排序 - 快速排序 （一） 92
排序 - 選擇排序 - 堆排序（一） 96
排序 - 歸併排序（一） 98
排序 - 分配排序 - 基數排序 101
排序 - 各種內部排序方法的比較和選擇（一） 102
查詢 - 查詢的基本概念 103
查詢-線性表的查詢-順序查詢 104
查詢 - 線性表的查詢 - 二分查詢（一） 105
查詢 - 線性表的查詢 - 分塊查詢 107
查詢 - 樹上的查詢 - 二叉排序樹（一） 109
查詢 - 樹上的查詢 - ｂ－樹 114
查詢 - 雜湊技術 - 雜湊表的概念 121
查詢 - 雜湊技術 - 雜湊函式的構造方法 122
檔案 - 檔案的基本概念（一） 123
檔案 - 順序檔案 125
檔案 - 索引檔案（一） 126
檔案 - 索引順序檔案 - isam檔案（一） 127
檔案 - 索引順序檔案 - vsam檔案 （一） 130
檔案 - 雜湊檔案 131
檔案 - 多關鍵字檔案 - 多重表檔案 132
檔案 - 多關鍵字檔案 - 倒排檔案 133
概論--基本概念和術語
資料：資料：指能夠被計算機識別、儲存和加工處理的資訊載體。
資料元素：就是資料的基本單位，在某些情況下，資料元素也稱為元素、結點、頂點、記錄。資料元素有時可以由若干資料項組成。
資料結構：指的是資料之間的相互關係，即資料的組織形式。
1．資料結構一般包括以下三方面內容：
① 資料元素之間的邏輯關係，也稱資料的邏輯結構；
資料的邏輯結構是從邏輯關係上描述資料，與資料的儲存無關，是獨立於計算機的。資料的邏輯結構可以看作是從具體問題抽象出來的數學模型。② 資料元素及其關係在計算機儲存器內的表示稱資料的儲存結構；③ 資料的運算，即對資料施加的操作。
資料的運算定義在資料的邏輯結構上，每種邏輯結構都有乙個運算的集合。最常用的檢索、插入、刪除、更新、排序等運算實際上只是在抽象的資料上所施加的一系列抽象的操作。
（1）邏輯結構：表中每一行是乙個資料元素(或記錄、結點)，由學號、姓名等資料項組成。資料元素之間的邏輯關係是：對錶中任乙個結點，與它相鄰且在它前面的結點稱直接前趨最多只有乙個；
（2）儲存結構：該錶的儲存結構是指用計算機語言如何表示結點之間的這種關係，即表中的結點是順序鄰接地儲存在一片連續的單元之中，還是用指標將這些結點鏈結在一起？
2．資料的邏輯結構分類：邏輯結構簡稱為資料結構。
（1）線性結構：邏輯特徵是：若結構是非空集，則有且僅有乙個開始結點和乙個終端結點，並且所有結點都最多只有乙個直接前趨和乙個直接後繼。 線性表,棧,佇列,串等都是線性結構。
（2）非線性結構：邏輯特徵是：乙個結點可能有多個直接前趨和直接後繼。陣列、廣義表、樹和圖等資料結構都是非線性結構。
3．資料的四種基本儲存方法
（1）順序儲存方法：該方法把邏輯上相鄰的結點儲存在物理位置上相鄰的儲存單元裡，結點間的邏輯關係由儲存單元的鄰接關係來體現。由此得到的儲存表示稱為順序儲存結構，通常借助程式語言的陣列描述。
該方法主要應用於線性的資料結構。非線性的資料結構也可通過某種線性化的方法實現順序儲存。（如陣列）
（2）鏈結儲存方法：該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關係由附加的指標字段表示。由此得到的儲存表示稱鏈式儲存結構,通常借助於程式語言的指標型別描述。
（3）索引儲存方法：該方法通常在儲存結點資訊的同時，還建立附加的索引表。 索引表由若干索引項組成。
若每個結點在索引表中都有乙個索引項，則該索引表稱之為稠密索引。若一組結點在索引表中只對應乙個索引項，則該索引表稱為稀疏索引。索引項的一般形式是：
(關鍵字、位址)關鍵字是能唯一標識乙個結點的那些資料項。稠密索引中索引項的位址指示結點所在的儲存位置；稀疏索引中索引項的位址指示一組結點的起始儲存位置。
（4）雜湊儲存方法：根據結點關鍵字直接計算出該結點儲存位址。
四種儲存方法可單獨使用也可組合起來對資料結構進行儲存映像。
同一邏輯結構採用不同的儲存方法，可以得到不同的儲存結構。
4．資料結構三方面的關係：資料的邏輯結構、儲存結構及資料的運算這三方面是乙個整體。儲存結構是資料結構不可缺少的乙個方面：同一邏輯結構的不同儲存結構可冠不同資料結構名稱來標識。
【例】線性表是一種邏輯結構，用順序方法的儲存表示，稱其為順序表；用鏈式儲存方法，稱為鍊錶；用雜湊儲存方法，稱為雜湊表。
資料的運算也是資料結構不可分割的乙個方面。在給定了資料的邏輯結構和儲存結構之後，按定義的運算集合及其運算的性質不同，也可能導致完全不同的資料結構。
資料型別：是乙個值的集合以及在這些值上定義的一組操作的總稱。通常資料型別可以看作是程式語言中已實現的資料結構。
按"值"是否可分解，可將資料型別劃分為兩類：
①原子型別：其值不可分解。通常是由語言直接提供。
②結構型別：其值可分解為若干個成分（或稱為分量）。
抽象資料型別（簡稱adt）：是指抽象資料的組織和與之相關的操作。可以看作是資料的邏輯結構及其在邏輯結構上定義的操作。
抽象資料型別可以看作是描述問題的模型，它獨立於具體實現。它的優點是將資料和操作封裝在一起，使得使用者程式只能通過在adt裡定義的某些操作來訪問其中的資料，從而實現資訊隱藏。
adt和類的概念實際上反映了程式或軟體設計的兩層抽象：adt相當於是在概念層（或稱為抽象層）上描述問題，而類相當於是在實現層上描述問題。不採用adt的形式來描述資料結構
概論- 學習資料結構的意義
1． 計算機處理問題的分類
（1）數值計算問題 （2）非數值性問題
2．非數值問題求解
瑞士計算機科學家沃思教授曾提出： 演算法+資料結構=程式
資料結構是資料的邏輯結構和儲存結構，演算法是對資料運算的描述
概論- 演算法的描述和分析(一)
資料的運算通過演算法(algorithm)描述
1．演算法 ：非形式地說，演算法是任意乙個良定義的計算過程。它以乙個或多個值作為輸入，並產生乙個或多個值作為輸出。
（1）乙個演算法可以被認為是用來解決乙個計算問題的工具。
「資料結構」串講筆記
課程 21049 適用專業 計算機應用 計算機網路 串講教師 北京航空航天大學唐髮根 考試題型 第一部分選擇題 一 單項選擇題 每小題2分，共20分 第二部分非選擇題 二 填空題 每空2分，共20分 三 簡答題 15分 四 問題求解題 每小題10分，共20分 五 演算法填空題 25分 第一章緒論 主...
2331資料結構自考大綱
第1章概論 一 課程內容 1.1 引言 1.2 資料 邏輯結構和運算 1.3 儲存實現和運算實現 二 學習的目的與要求 本章集中介紹貫穿和應用與資料結構課程始終的基本概念和主要工具，概括反映了後繼各章的基本問題，為進入具體內容的學習提供了必要的引導。本章總的要求是 理解資料 資料元素和資料項的概念及...
自考資料結構真題
絕密 考試結束前 全國2013年10月高等教育自學考試 資料結構試題 課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把...