中南財(cái)經(jīng)政法大學(xué)自考《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)指導(dǎo)

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

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

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

http://www.zlcjzsb.org/

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

http://www.heywebguys.com/baoming/20090909121448.html