中南財經(jīng)政法大學自考《數(shù)據(jù)結構》復習指導

第一章：緒論
　　一、概念：
　　數(shù)據(jù)結構：是一門研究程序設計中計算機操作的對象以及它們之間的關系和運算的一門學科。
　　數(shù)據(jù)：是描述額觀事物的數(shù)、字符以及所有能輸入到計算機中被計算機程序加工處理的信息的集合。
　　數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（一個數(shù)據(jù)項或多個數(shù)據(jù)項（域）。數(shù)據(jù)項是數(shù)據(jù)的最小單位。結點、頂點、記錄。
　　數(shù)據(jù)對象：是性質相同的數(shù)據(jù)元素的集合。
　　數(shù)據(jù)結構：研究是是數(shù)據(jù)元素之間抽象化的相互關系和這種關系在計算機中的存貯表示，并對每種結構定義各自的運算，設計出相應的算法，而且經(jīng)過運算后所得的新結構一般仍然是原來的結構類型。
　　數(shù)據(jù)類型：是指程序設計語言中各變量可取的數(shù)據(jù)種類。
　　算法：是執(zhí)行特定計算的有窮過程。特點：
　　·動態(tài)有窮·確定性·輸入·輸出·可行性。
　　第二章 線性表和數(shù)組
　　概念：
　　一、線性表：是N個元素構成的有限序列。
　　順序存貯結構：地址計算，插入、刪除。
　　鏈式存貯結構：單鏈表，查找、插入、刪除。
　　循環(huán)鏈表：
　　雙向鏈表：
　　二、數(shù)組：
　　以行為主；
　　以列為主；計算地址：
　　三、棧：是一種特殊的線性表，這種表只能在固定的一端進行插入與刪除運算。
　　隊列：是另一種特殊的線性表，刪除運算限定在表的一端進行，而插入運算在另一端進行。
　　第三章：串
　　概念：是由N個字符組成的有限序列。
　　存貯結構：
　　順序表示法：
　　1、緊縮格式 2、非緊縮格式 3、以單字節(jié)為單位的存貯方式
　　鏈式表示法：
　　串名的存貯映象：
　　第四章：樹
　　一、概念：
　　樹：是一個或多個結點的有窮集合T，且滿足以下條件：
　　1、有且僅有一個指定的稱作樹根的結點；
　　2、除根以外的其余結點被分成m個不相交的集合，這些集合的每一個又都是樹，并且稱為根的子樹。
　　結點的度：結點N的子樹數(shù)稱為結點的度。
　　樹的度：樹T中各結點的度的最大值稱的樹T的度。
　　葉子：樹中度為0的結點稱為葉子（終端結點）。
　　分枝結點：樹中度不為0的結點稱為分枝結點（非終端結點）。
　　雙親和孩子：若樹中結點P的一棵子樹的根是結點C，則我們稱P是C的雙親或父母，反之稱C是P的孩子。
　　結點的層數(shù)：樹的層數(shù)為1，其余任一結點的層數(shù)等于它的雙親的層數(shù)加
　　樹的深度：樹中各結點的層數(shù)的最大值稱為T的深度（高度）。
　　兄弟和堂兄弟：同一雙親的孩子之間互稱為兄弟，其雙親在同一層的結點互為堂兄弟。
　　祖先和子孫：一個點的祖先是指從樹的根到該結點所經(jīng)分枝上的所有結點。一個結點的子樹的所有結點都稱為該結點的子孫。
　　有序樹和無序樹：如果樹中結點各棵子樹規(guī)定從左至右是有次序的，則稱樹為有序樹，否則為無序樹。
　　森林：N棵互不相交的樹的集合稱為森林。
　　二、樹的存貯表示：
　　1、雙親數(shù)組表示：記錄型一維數(shù)組：data，
　　2、孩子鏈表表示法：
　　·多重鏈表表示法： data，degree，link1，link2…
　　·單鏈表表示法：data，
　　3、左孩子右兄弟鏈表示法：lchild，data，
　　三、二叉樹：
　　1、概念：是有限個結點的集合，它或者為空集，或者是由一個根結點以及兩棵互不相交的且分別稱為根的左子樹和右子樹的二叉樹組成。五種形態(tài)：空，根，左，右，左右 2、性質：
　　·位于二叉樹第I層上的結點，最多為2I-1；（I）
　　·深度為K的二叉樹的結點總數(shù)，最多為2K-1（K）
　　·
　　滿二叉樹：一棵深度為K的具有2K-1個結點的二叉樹
　　完全二叉樹：在一棵二叉樹中，若所有結點的度為0或為2的二叉樹
　　順序二叉樹：如果深度為K的具有N個結點的二叉樹，它的每一個結點都與深度為K的滿二叉樹中順序編號是1到N的結點相對應的二叉樹。
　　三、二叉樹的存貯表示：
　　1、順序存貯：
　　2、鏈表表示：lchild，data，
　　3、遍歷：
　　·前序：根—左—右
　　·中序：左—根—右
　　·后序：左—右—根
　　四、線索二叉樹：
　　五、樹的二叉樹表示，森林與二叉樹的轉換。
　　六、路徑長度：樹中一個結點到另一個結點之關的路徑由這兩個結點之間的分枝所構成，路徑上的分枝數(shù)目稱為它的路徑長度。
　　哈夫曼樹：WPL，哈夫曼碼第五章：圖
　　概念：一個圖G由兩個集合V和E組成，V是有限的非空頂點集，E是用頂點對表示的邊集。
　　無向圖，有向圖；
　　鄰接，關聯(lián)，鄰接到（于），關聯(lián)于，孤立頂點。
　　頂點的度：圖G中關聯(lián)于頂點V的邊的數(shù)目稱為V的度。
　　所有頂點的度等于邊的兩倍。
　　子圖
　　完全圖：每對頂點之間都有一條邊相連的圖。在有向圖中，每對頂點之間都有兩條有向邊相互關聯(lián)的圖。
　　在無向完全圖中，邊的總數(shù)為Cn2=n（n-1）
　　在有向完全圖中，邊的總數(shù)為Pn2=n（n-1）
　　路徑：由邊組成。
　　回路
　　連通圖：對于無向圖，如果圖中任何兩頂點都是可達的，則稱此圖為連能圖。
　　對于有向圖，如果圖中任何兩個頂點都是相互可達的，則此有向圖是強連通的，如果圖中任何兩頂點至少有一個頂點另一個頂點可達，則稱此有向圖是單向連通的。
　　強連通分量：有向圖的最大強連通子圖稱為它的強連通分量。 樹圖：其本質特征是連通性和無圈性，把不含圈的無向連通圖稱為樹圖。
　　網(wǎng)絡：是每條邊上帶有數(shù)量指標的連通圖。
　　鄰接矩陣，鄰接表
　　第六章 查找
　　查找：就是確定一個已給的數(shù)據(jù)是否出現(xiàn)在某個數(shù)據(jù)表中。
　　域（字段）：組成記錄的每個數(shù)據(jù)項。
　　關鍵字：通常記錄中總存在某個或某組數(shù)據(jù)項，它們的值能唯一標識一個記錄，這個（組）數(shù)據(jù)項稱為關鍵字。
　　方法：順序
　　二分
　　線性插值
　　分區(qū)
　　二叉排序樹：如果將記錄的鍵碼按二叉樹的結構來組織，并且假定樹中任意非葉子結點的鍵碼大于其左子樹所有結點的鍵碼（若左子樹存在的話），而小于其右子樹所有結點的鍵碼（如右子樹存在的話），這樣的二叉樹叫二叉排序樹（二叉查找樹）。 哈 希查找：
　　哈希函數(shù)：能把關鍵字映射成記錄存貯地址的函數(shù)。
　　哈希表：假定數(shù)組HT[0··m-1]為存貯記錄的地址空間，哈希函數(shù)H以每個記錄的關鍵字值K作為輸入，產生一個落在[0··m-1]內的整數(shù)H（K），并以它作為K所標識的記錄在表HT中的地址或索引號，這樣產生的記錄表H（K）叫做 ··
　　構造哈希函數(shù)的方法：
　　直接定址法
　　除留余數(shù)法
　　平方取中法
　　折疊法與移位法
　　數(shù)字分析法
　　沖突處理：
　　開放定址法： 1、線性探測法 2、偽隨機探測法
　　鏈地址法
　　第七章：排序
　　內部排序：
　　外部排序：
　　內部：冒泡 選擇 插入 歸并 堆排序 快速排序 基數(shù)
　　堆：每個非終端結點的關鍵字大于等于它的孩子結點的關鍵字

有意報考本校的學生，可直接電話聯(lián)系： QQ聯(lián)系：1621695467

中南財經(jīng)政法大學自考網(wǎng)站：

http://www.zlcjzsb.org/

中南財經(jīng)政法大學自考招生簡章:

http://trillionsbussines.com/baoming/20090909121448.html