自學考試《資料結構》複習指導
第一章：緒論
一、概念：
資料結構：是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。
資料：是描述額觀事物的數、字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。
資料元素：資料元素是資料的基本單位。（乙個資料項或多個資料項（域）。資料項是資料的最小單位。結點、頂點、記錄。
資料物件：是性質相同的資料元素的集合。
資料結構：研究是是資料元素之間抽象化的相互關係和這種關係在計算機中的存貯表示，並對每種結構定義各自的運算，設計出相應的演算法，而且經過運算後所得的新結構一般仍然是原來的結構型別。
資料型別：是指程式語言中各變數可取的資料種類。
演算法：是執行特定計算的有窮過程。特點：
·動態有窮·確定性·輸入·輸出·可行性。
第二章線性
表和陣列
概念：一、線性表：是n個元素構成的有限序列。
順序存貯結構：位址計算，插入、刪除。
鏈式存貯結構：單鏈表，查詢、插入、刪除。
迴圈鍊錶：
雙向鍊錶：
二、陣列：
以行為主；
以列為主；計算位址：
三、棧：是一種特殊的線性表，這種表只能在固定的一端進行插入與刪除運算。
佇列：是另一種特殊的線性表，刪除運算限定在表的一端進行，而插入運算在另一端進行。
第三章：串
概念：是由n個字元組成的有限序列。
存貯結構：
順序表示法：
1、緊縮格式 2、非緊縮格式 3、以單位元組為單位的存貯方式
鏈式表示法：
串名的存貯映象：
第四章：樹
一、概念：
樹：是乙個或多個結點的有窮集合t，且滿足以下條件：
1、有且僅有乙個指定的稱作樹根的結點；
2、除根以外的其餘結點被分成m個不相交的集合，這些集合的每乙個又都是樹，並且稱為根的子樹。
結點的度：結點n的子樹數稱為結點的度。
樹的度：樹t中各結點的度的最大值稱的樹t的度。
葉子：樹中度為0的結點稱為葉子（終端結點）。
分枝結點：樹中度不為0的結點稱為分枝結點（非終端結點）。
雙親和孩子：若樹中結點p的一棵子樹的根是結點c，則我們稱p是c的雙親或父母，反之稱c是p的孩子。
結點的層數：樹的層數為1，其餘任一結點的層數等於它的雙親的層數加1.
樹的深度：樹中各結點的層數的最大值稱為t的深度（高度）。
兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟，其雙親在同一層的結點互為堂兄弟。
祖先和子孫：乙個點的祖先是指從樹的根到該結點所經分枝上的所有結點。乙個結點的子樹的所有結點都稱為該結點的子孫。
有序樹和無序樹：如果樹中結點各棵子樹規定從左至右是有次序的，則稱樹為有序樹，否則為無序樹。
森林：n棵互不相交的樹的集合稱為森林。
二、樹的存貯表示：
1、雙親陣列表示：記錄型一維陣列：data，parent
2、孩子鍊錶表示法：
·多重鍊錶表示法： data，degree，link1，link2…
·單鏈表表示法：data，likn
3、左孩子右兄弟鏈表示法：lchild，data，rsibling
三、二叉樹：
1、概念：是有限個結點的集合，它或者為空集，或者是由乙個根結點以及兩棵互不相交的且分別稱為根的左子樹和右子樹的二叉樹組成。五種形態：空，根，左，右，左右 2、性質：
·位於二叉樹第i層上的結點，最多為2i-1；（i）=1
·深度為k的二叉樹的結點總數，最多為2k-1（k）=1
·n0=n2+1
滿二叉樹：一棵深度為k的具有2k-1個結點的二叉樹
完全二叉樹：在一棵二叉樹中，若所有結點的度為0或為2的二叉樹
順序二叉樹：如果深度為k的具有n個結點的二叉樹，它的每乙個結點都與深度為k的滿二叉樹中順序編號是1到n的結點相對應的二叉樹。
三、二叉樹的存貯表示：
1、順序存貯：
2、鍊錶表示：lchild，data，rchlid
3、遍歷：
·前序：根—左—右
·中序：左—根—右
·後序：左—右—根
四、線索二叉樹：
五、樹的二叉樹表示，森林與二叉樹的轉換。
六、路徑長度：樹中乙個結點到另乙個結點之關的路徑由這兩個結點之間的分枝所構成，路徑上的分枝數目稱為它的路徑長度。
哈夫曼樹：wpl，哈夫曼碼
第五章：圖
概念：乙個圖g由兩個集合v和e組成，v是有限的非空頂點集，e是用頂點對表示的邊集。
無向圖，有向圖；
鄰接，關聯，鄰接到（於），關聯於，孤立頂點。
頂點的度：圖g中關聯於頂點v的邊的數目稱為v的度。
所有頂點的度等於邊的兩倍。
子圖完全圖：每對頂點之間都有一條邊相連的圖。在有向圖中，每對頂點之間都有兩條有向邊相互關聯的圖。
在無向完全圖中，邊的總數為cn2=n（n-1）/2
在有向完全圖中，邊的總數為pn2=n（n-1）
路徑：由邊組成。
迴路連通圖：對於無向圖，如果圖中任何兩頂點都是可達的，則稱此圖為連能圖。
對於有向圖，如果圖中任何兩個頂點都是相互可達的，則此有向圖是強連通的，如果圖中任何兩頂點至少有乙個頂點另乙個頂點可達，則稱此有向圖是單向連通的。
強連通分量：有向圖的最大強連通子圖稱為它的強連通分量。 樹圖：其本質特徵是連通性和無圈性，把不含圈的無向連通圖稱為樹圖。
網路：是每條邊上帶有數量指標的連通圖。
鄰接矩陣，鄰接表
第六章查詢
查詢：就是確定乙個已給的資料是否出現在某個資料表中。
域（字段）：組成記錄的每個資料項。
關鍵字：通常記錄中總存在某個或某組資料項，它們的值能唯一標識乙個記錄，這個（組）資料項稱為關鍵字。
方法：順序
二分線性插值
分割槽二叉排序樹：如果將記錄的鍵碼按二叉樹的結構來組織，並且假定樹中任意非葉子結點的鍵碼大於其左子樹所有結點的鍵碼（若左子樹存在的話），而小於其右子樹所有結點的鍵碼（如右子樹存在的話），這樣的二叉樹叫二叉排序樹（二叉查詢樹）。 雜湊查詢：
雜湊函式：能把關鍵字對映成記錄存貯位址的函式。
雜湊表：假定陣列ht[0··m-1]為存貯記錄的位址空間，雜湊函式h以每個記錄的關鍵字值k作為輸入，產生乙個落在[0··m-1]內的整數h（k），並以它作為k所標識的記錄在表ht中的位址或索引號，這樣產生的記錄表h（k）叫做 ··]
構造雜湊函式的方法：
直接定址法
除留餘數法
平方取中法
摺疊法與移位法
數字分析法
衝突處理：
開放定址法： 1、線性探測法 2、偽隨機探測法
鏈位址法
第七章：排序
內部排序：
外部排序：
內部：冒泡選擇插入歸併堆排序快速排序基數
堆：每個非終端結點的關鍵字大於等於它的孩子結點的關鍵字
第八章：檔案
基本概念
以上資料由百度貼吧：
自考樂園俱樂部楊尚傑為你精心編輯
資料結構複習指導
1.資料結構是指 a a.資料元素的組織形式 b.資料型別 c.資料儲存結構d.資料定義 2.資料在計算機儲存器內表示時，實體地址與邏輯位址不相同的，稱之為 c a.儲存結構b.邏輯結構 c.鏈式儲存結構d.順序儲存結構 3.樹形結構是資料元素之間存在一種 d a.一對一關係 b.多對多關係 c.多...
資料結構複習指導
elemtype data struct btnode lchild,rchild,parent btnode,bintree 例 用二叉鍊錶儲存n個結點的二叉樹 n 0 共有 n 1 個空指標域 採用三叉鍊錶儲存，共有 n 2 個空指標域。空樹 bt null 左右子樹均空 bt lchild n...
2019資料結構複習指導
考試題型 選擇題 24 填空題 20 解析題 10 運算題 10 簡答題 10 演算法填空 10 演算法設計 14 第一章緒論 1 資料結構的凡個方面，什麼是邏輯結構，什麼是儲存結構。常見的運算有哪些。答 資料元素之間的邏輯關係，即資料的邏輯結構。資料元素及其關係在計算機儲存器中的儲存方式，即資料的...