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

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

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

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

http://www.zlcjzsb.org/

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

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