有序線性表既可以採用順序儲存結構，也可以採用鏈式儲存結構。
考點三：線性結構與非線性結構
根據資料結構中各資料元素之間前後件關係的複雜程度，一般將資料結構分為兩大型別：線性結構與非線性結構。
(1) 線性結構必須滿足的兩個兩個條件：
① 有且只有乙個根結點；
② 每乙個結點最多有乙個前件，也最多有乙個後件。則稱該資料結構為線性結構。
線性結構又稱線性表。在乙個線性結構中插入或刪除任何乙個結點後還應是線性結構。
(2) 棧、佇列、串等都線性結構。
非線性結構：資料結構不是線性結構，則稱之為非線性結構。
陣列、廣義表、樹和圖等資料結構都是非線性結構。
(3) 線性表的順序儲存結構具有以下兩個基本特點：
① 線性表中所有元素所佔的儲存空間是連續的；
② 線性表中各資料元素在儲存空間中是按邏輯順序依次存放的。
元素 ai 的儲存位址為：adr(ai)=adr(a1)+(i-1)k，adr(a1)為第乙個元素的位址，k 代表每個元素佔的位元組數。
線性表是由一組資料元素構成，資料元素的位置只取決於自己的序號，元素之間的相對位置是線性的。
在複雜線性表中，由若干項資料元素組成的資料元素稱為記錄，而由多個記錄構成的線性表又稱為檔案。
(4) 順序表的運算：查詢、插入、刪除。
考點四：棧和佇列
棧：形象的比喻小學課本上講烏鴉喝水用的杯子。
限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。
棧按照「先進後出」（filo）或「後進先出」（lifo）組織資料，棧具有記憶作用。
用top表示棧頂位置，用bottom表示棧底。
棧的基本運算：
(1) 插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給乙個指定的變數，此時指標無變化。
棧是支援子程式呼叫的資料結構。
佇列：形象比喻在食堂裡打飯時排的長隊，先來先服務
指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。
rear指標指向隊尾，front指標指向隊頭。當表中沒有元素時稱為空佇列。
佇列是「先進先出」（fifo）或「後進後出」（lilo）的線性表。
佇列運算包括：
(1) 入隊運算：從隊尾插入乙個元素；（2）退隊運算：從隊頭刪除乙個元素。
迴圈佇列：
佇列的頭指標指向佇列的尾指標，迴圈佇列是佇列的順序儲存結構。
考點五：鍊錶
在鏈式儲存方式中，要求每個結點由兩部分組成：
(1) 用於存放資料元素值，稱為資料域，
(2) 用於存放指標，稱為指標域。其中指標用於指向該結點的前乙個或後乙個結點（即前件或後件）。
鏈式儲存方式既可用於表示線性結構，也可用於表示非線性結構。
1) 線性鍊錶
線性表的鏈式儲存結構稱為線性鍊錶。
在某些應用中，對線性鍊錶中的每個結點設定兩個指標，乙個稱為左指標，用以指向其前件結點；另乙個稱為右指標，用以指向其後件結點。這樣的表稱為雙向鍊錶。
**性煉表中，各資料元素結點的儲存空間可以是不連續的，且各資料元素的儲存順序與邏輯順序可以不一致。**性煉表中進行插入與刪除，不需要移動鍊錶中的元素。
線性單鏈表中，head 稱為頭指標，head=null（或 0）稱為空表。
如果是雙向鍊錶的兩指標：左指標（llink）指向前件結點，右指標（rlink）指向後件結點。
線性鍊錶的基本運算：查詢、插入、刪除。
2) 帶鏈的棧
棧也是線性表，也可以採用鏈式儲存結構。帶鏈的棧可以用來收集計算機儲存空間中所有空閒的儲存結點，這種帶鏈的棧稱為可利用棧。
考點六：二叉樹及其基本性質
1）二叉樹及其基本概念
樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。具有以下兩個特點：
①非空二叉樹只有乙個根結點；
②每乙個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
度：結點的左右子樹的個數，每乙個結點的度最大為 2，即所有子樹（左子樹或右子樹）也均為二叉樹，在二叉樹中，乙個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。樹的度即為二叉樹中最大的度的數。
葉子結點：既沒有左子樹也沒有右子樹的結點。
例如，乙個家族中的族譜關係如圖 1-1 所示：
a 有後代 b，c；
b 有後代 d，e；c 有後代 f；
典型的二叉樹如圖 1-1 所示：
1) 二叉樹基本性質
二叉樹具有以下幾個性質：
性質 1：在二叉樹的第 k 層上，最多有 2k-1（k≥1）個結點；
性質 2：深度為 m 的二叉樹最多有 2m-1 個結點；
性質 3：在任意一棵二叉樹中，度為 0 的結點（即葉子結點）總是比度為 2 的結點多乙個。
性質 4：具有 n 個結點的二叉樹，其深度至少為［log2n］+1，其中［log2n］表示取 log2n 的整數部分。
1） 滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
2） 二叉樹的遍歷
二叉樹的遍歷：
(1) 前序遍歷（dlr），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
例如，對圖 1-1 中的二叉樹進行前序遍歷的結果（或稱為該二叉樹的前序序列）為：a，b，d，e，c，f。
(2) 中序遍歷（ldr），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
例如，對圖 1-1 中的二叉樹進行中序遍歷的結果（或稱為該二叉樹的中序序列）為：d，b，e，a，c，f。
(3) 後序遍歷（lrd）首先遍歷左子樹，然後訪問遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
例如，對圖 1-1 中的二叉樹進行後序遍歷的結果（或稱為該二叉樹的後序序列）為：d，e，b，f，c，a。
考點七：順序查詢
查詢是指在乙個給定的資料結構中查詢某個指定的元素。從線性表的第乙個元素開始，依次將線性表中的元素與被查詢的元素相比較，若相等則表示查詢成功；若線性表中所有的元素都與被查詢元素進行了比較但都不相等，則表示查詢失敗。
例如，在一維陣列[21，46，24，99，57，77，86]中，查詢資料元素 98，首先從第 1 個元素 21 開始進行比較，與要查詢的資料不相等，接著與第 2 個元素 46 進行比較，以此類推，當進行到與第 4 個元素比較時，它們相等，所以查詢成功。如果查詢資料元素 100，則整個線性表掃瞄完畢，仍未找到與 100 相等的元素，表示線性表中沒有要查詢的元素。
在下列兩種情況下也只能採用順序查詢：
(1) 如果線性表為無序表，則不管是順序儲存結構還是鏈式儲存結構，只能用順序查詢。
(2) 即使是有序線性表，如果採用鏈式儲存結構，也只能用順序查詢。(有序表，儲存的資料從小到大有規律存放)
考點八：二分法查詢
二分法查詢，也稱拆半查詢，是一種高效的查詢方法。能使用二分法查詢的線性表必須滿足兩個條件：用順序儲存結構；線性表是有序表。
二分法查詢只適用於順序儲存的有序表。
例如，長度為 8 的線性表關鍵碼序列為：[6，13，27，30，38，46，47，70]，被查元素為 38，首先將與線性表的中間項比較，即與第 4 個資料元素 30 相比較，38 大於中間項 30 的值，則**性表[38，46，47，70]繼續查詢；接著與中間項比較，即與第 2 個元素 46 相比較，38 小於 46，則**性表[38]繼續查詢，最後一次比較相等，查詢成功。
順序查詢法每一次比較，只將查詢範圍減少 1，而二分法查詢，每比較一次，可將查詢範圍減少為原來的一半，效率大大提高。
對於長度為n的有序線性表，在最壞情況下，二分法查詢只需比較log2n次，而順序查詢需要比較n次。
考點九：排序技術
(1) 交換類排序法
①氣泡排序法
首先，從表頭開始往後掃瞄線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。然後，從後到前掃瞄剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。對剩下的線性表重複上述過程，直到剩下的線性表變空為止，此時已經排好序。
在最壞的情況下，氣泡排序需要比較次數為n(n-1)/2。
②快速排序法
任取待排序序列中的某個元素作為基準（一般取第乙個元素），通過一趟排序，將待排元素分為左右兩個子串行，左子串行元素的排序碼均小於或等於基準元素的排序碼，右子串行的排序碼則大於基準元素的排序碼，然後分別對兩個子串行繼續進行排序，直至整個序列有序。
(2) 插入類排序法
①簡單插入排序法，最壞情況需要 n(n-1)/2 次比較；
②希爾排序法，最壞情況需要 o(n1.5)次比較。
(3) 選擇類排序法
①簡單選擇排序法，最壞情況需要 n(n-1)/2 次比較；
②堆排序法，最壞情況需要 o(nlog2n)次比較。
2023年自學考試《資料結構》各章複習要點總結
第四章串 串是零個或多個字元組成的有限序列。空串 是指長度為零的串，也就是串中不包含任何字元 結點 空白串 指串中包含乙個或多個空格字元的串。在乙個串中任意個連續字元組成的子串行稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現的位置。空串是任意串的子串，任意串是自...
2023年自學考試《資料結構》各章複習要點總結
第十章檔案 檔案是性質相同的記錄的集合。記錄是檔案中訪問的基本單位，資料項是檔案可使用的最小單位，資料項有時稱欄位或者屬性。檔案 邏輯結構是一種線性結構。操作有 檢索和維護。並有實時和批量處理兩種處理方式。檔案 儲存結構是指檔案在外存上的組織方式。基本的組織方式有 順序組織 索引組織 雜湊組織和鏈組...
自學考試資料結構試題
課程 02331 請考生按規定用筆將所有試題的答案塗 寫在答題紙上。選擇題部分 注意事項 1.答題前，考生務必將自己的考試課程名稱 姓名 准考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。2.每小題選出答案後，用2b鉛筆把答題紙上對應題目的答案標號塗黑。如需改動，用橡皮擦乾淨後，再選塗其他答...