下面是范文網(wǎng)小編收集的年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3篇(數(shù)據(jù)結(jié)構(gòu)第二章知識(shí)點(diǎn)總結(jié))，供大家閱讀。

年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)1

　　2010年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)(5)龍耒為你整理：

　　第九章 查找

　　查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱(chēng)之為動(dòng)態(tài)查找表，否則稱(chēng)之為靜態(tài)查找表。

　　衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度ASL)。

　　線(xiàn)性表查找的方法：

·順序查找：逐個(gè)查找，ASL=(n+1)/2;

·二分查找：取中點(diǎn)int(n/2)比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹(shù)表示。ASL=(∑(每層結(jié)點(diǎn)數(shù)*層數(shù)))/N;·分塊查找：要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。

　　二叉排序樹(shù)(BST)定義是二叉排序樹(shù)是空樹(shù)或者滿(mǎn)足如下性質(zhì)的二叉樹(shù)：

·若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值;

·若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;

·左、右子樹(shù)本身又是一棵二叉排序樹(shù)。

　　二叉排序樹(shù)的插入、建立、刪除的算法平均時(shí)間性能是O(nlog2n)。

　　二叉排序樹(shù)的刪除操作可分三種情況進(jìn)行處理：

·*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。

·*P只有一個(gè)孩子*child，此時(shí)只需將*child和*p的雙親直接連接就可刪去*p。

·*p有兩個(gè)孩子，則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。

　　關(guān)于B-樹(shù)(多路平衡查找樹(shù))。它適合在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過(guò)程稱(chēng)為散列。

　　散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。

　　常見(jiàn)的散列函數(shù)構(gòu)的造方法：

·平方取中法：hash=int((x^2)0)

·除余法：表長(zhǎng)為m，hash=x%m

·相乘取整法：hash=int(m*(x*A-int(x*A));A=

·隨機(jī)數(shù)法：hash=random(x)。

　　處理沖突的方法：

　　開(kāi)放定址法： 一般形式為hi=(h(key)+di)%m1≤i≤m-1，開(kāi)放定址法要求散列表的裝填因子α≤1。

·開(kāi)放定址法類(lèi)型：

·線(xiàn)性探查法：address=(hash(x)+i)%m;·二次探查法：address=(hash(x)+i^2)%m;

·雙重散列法：address=(hash(x)+i*hash(y))%m;

·拉鏈法： 是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。

·拉鏈法的優(yōu)點(diǎn)：

·拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象;

·鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無(wú)法確定表長(zhǎng)的情況;

·拉鏈法中α可以大于1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間;

·拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。

·拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間，還是開(kāi)放定址法省空間。

　　第十章 文件

　　文件是性質(zhì)相同的記錄的集合。記錄是文件中存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位，數(shù)據(jù)項(xiàng)有時(shí)稱(chēng)字段或者屬性。

　　文件

·邏輯結(jié)構(gòu)是一種線(xiàn)性結(jié)構(gòu)。

·操作有：檢索和維護(hù)。并有實(shí)時(shí)和批量處理兩種處理方式。

　　文件

·存儲(chǔ)結(jié)構(gòu)是指文件在外存上的組織方式。

·基本的組織方式有：順序組織、索引組織、散列組織和鏈組織。

·常用的文件組織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件。

　　評(píng)價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作所花費(fèi)的時(shí)間和文件組織所需的存儲(chǔ)空間。

　　檢索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標(biāo)志。

　　順序文件是指按記錄進(jìn)入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關(guān)鍵字有序稱(chēng)順序有序文件，否則稱(chēng)順序無(wú)序文件。

　　一切存儲(chǔ)在順序存儲(chǔ)器(如磁帶)上的文件都只能順序文件，只能按順序查找法存取。順序文件的插入、刪除和修改只能通過(guò)復(fù)制整個(gè)文件實(shí)現(xiàn)。

　　索引文件的組織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對(duì)應(yīng)的關(guān)系，它和主文件一起構(gòu)成索引文件。

　　索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引。

　　若記錄很大使得索引表也很大時(shí)，可對(duì)索引表再建立索引，稱(chēng)為查找表。是一種靜態(tài)索引。

　　索引順序文件常用的有兩種：

·ISAM索引順序存取方法：是專(zhuān)為磁盤(pán)存取文件設(shè)計(jì)的，采用靜態(tài)索引結(jié)構(gòu)。

·VSAM虛擬存儲(chǔ)存取方法：采用B+樹(shù)作為動(dòng)態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成。

　　散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱(chēng)為直接存取文件。

　　散列文件

·優(yōu)點(diǎn)是：文件隨機(jī)存放，記錄不需要排序;插入刪除方便;存取速度快;不需要索引區(qū)，節(jié)省存儲(chǔ)空間。

·缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢(xún)問(wèn)方式限地簡(jiǎn)單詢(xún)問(wèn)，需要重新組織文件。

　　多重表文件：對(duì)需要查詢(xún)的次關(guān)鍵字建立相應(yīng)的索引，對(duì)相同次關(guān)鍵字的記錄建一個(gè)鏈表并將鏈表頭指針、長(zhǎng)度、次關(guān)鍵字作為索引表的索引項(xiàng)。

　　倒排表：次關(guān)鍵字索引表稱(chēng)倒排表，主文件和倒排表構(gòu)成倒排文件。

年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)2

　　2010年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)(3)龍耒為你整理：

　　第五章 多維數(shù)組和廣義表

　　數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有：

·行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C

·列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN

　　地址的計(jì)算方法：

·按行優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。

　　特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。

　　稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱(chēng)為稀疏矩陣。

　　特殊矩陣的類(lèi)型：

·對(duì)稱(chēng)矩陣：滿(mǎn)足a(ij)=a(ji)。元素總數(shù)n(n+1)/=max(i，j)，J=min(i，j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣：

·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d.·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d.·對(duì)角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線(xiàn)性表來(lái)表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。

　　廣義表是n(n≥0)個(gè)元素的有限序列，其中的元素是原子或者是一個(gè)廣義表。

　　廣義表表頭和表尾的概念：

·若廣義表LS非空(n≥1)，則這個(gè)廣義表的第一個(gè)元素就是表頭。

·其余的元素組成的表稱(chēng)為L(zhǎng)S的表尾，所以表尾必是一個(gè)子表。

　　廣義表有兩種表示法，一種是括號(hào)表示法，一種是圖形表示法。

　　廣義表與樹(shù)(形結(jié)構(gòu))相對(duì)應(yīng)，這個(gè)廣義表就是純表。

　　如果一個(gè)廣義表的結(jié)點(diǎn)又可以被其他結(jié)點(diǎn)所共享，則這個(gè)表稱(chēng)為再入表。

　　允許遞歸的表稱(chēng)為遞歸表。

　　線(xiàn)性表∈純表(樹(shù))∈再入表∈遞歸表。可見(jiàn)，廣義表是對(duì)線(xiàn)性表和樹(shù)的推廣。

　　廣義表有兩個(gè)特殊的基本運(yùn)算：

·取表頭head(LS)：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。

·取表尾tail(LS);取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。

　　第六章 樹(shù)

　　樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿(mǎn)足：只有一個(gè)稱(chēng)為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱(chēng)根的子樹(shù)。

　　根是開(kāi)始結(jié)點(diǎn);結(jié)點(diǎn)的子樹(shù)數(shù)稱(chēng)度;度為0的結(jié)點(diǎn)稱(chēng)葉子(終端結(jié)點(diǎn));度不為0的結(jié)點(diǎn)稱(chēng)分支結(jié)點(diǎn)(非終端結(jié)點(diǎn));除根外的分支結(jié)點(diǎn)稱(chēng)內(nèi)部結(jié)點(diǎn);

　　有序樹(shù)是子樹(shù)有左，右之分的樹(shù);無(wú)序樹(shù)是子樹(shù)沒(méi)有左，右之分的樹(shù);森林是m個(gè)互不相交的樹(shù)的集合;

　　樹(shù)的四種不同表示方法：

·樹(shù)形表示法;

·嵌套集合表示法;

·凹入表示法;

·廣義表表示法。

　　二叉樹(shù)的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱(chēng)作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

　　二叉樹(shù)不是樹(shù)的特殊情形，與度數(shù)為2的有序樹(shù)不同。

　　二叉樹(shù)的4個(gè)重要性質(zhì)：

·二叉樹(shù)上第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1)(i≥1);

·深度為k的二叉樹(shù)至多有(2^k)-1個(gè)結(jié)點(diǎn)(k≥1);

·在任意一棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1;

·具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int(log2n)+1。滿(mǎn)二叉樹(shù)是一棵深度為k，結(jié)點(diǎn)數(shù)為(2^k)-1的二叉樹(shù);完全二叉樹(shù)是滿(mǎn)二叉樹(shù)在最下層自右向左去處部分結(jié)點(diǎn);

　　二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹(shù)的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。(存儲(chǔ)前先將其畫(huà)成完全二叉樹(shù))

　　樹(shù)的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類(lèi)型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱(chēng)為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。

　　根據(jù)訪問(wèn)結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n)。

　　利用二叉鏈表中的n+1個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱(chēng)為“線(xiàn)索”，加上線(xiàn)索的二叉鏈表就稱(chēng)為線(xiàn)索鏈表。線(xiàn)索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒(méi)有什么作用。

　　樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。

　　轉(zhuǎn)換方法：

·樹(shù)變二叉樹(shù)：兄弟相連，保留長(zhǎng)子的連線(xiàn)。

·二叉樹(shù)變樹(shù)：結(jié)點(diǎn)的右孩子與其雙親連。

·森林變二叉樹(shù)：樹(shù)變二叉樹(shù)，各個(gè)樹(shù)的根相連。

　　樹(shù)的存儲(chǔ)結(jié)構(gòu)：

·有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。

·孩子鏈表表示法：為樹(shù)中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。

·雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。

·孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹(shù)的前序遍歷與相對(duì)應(yīng)的二叉樹(shù)的前序遍歷一致;樹(shù)的后序遍歷與相對(duì)應(yīng)的二叉樹(shù)的中序遍歷一致。

　　樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱(chēng)為最優(yōu)二叉樹(shù)(即哈夫曼樹(shù))。

　　在葉子的權(quán)值相同的二叉樹(shù)中，完全二叉樹(shù)的路徑長(zhǎng)度最短。

　　哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒(méi)有度為1的結(jié)點(diǎn)，這類(lèi)樹(shù)又稱(chēng)為嚴(yán)格二叉樹(shù)。

　　變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱(chēng)為前綴碼(其實(shí)是非前綴碼)。

　　哈夫曼樹(shù)的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫(huà)好了哈夫曼樹(shù)，按分支情況在左路徑上寫(xiě)代碼0，右路徑上寫(xiě)代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。

年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3

　　11-12-2數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指導(dǎo)

　　第一章：

　　知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)元素關(guān)系的基本結(jié)構(gòu)類(lèi)型；數(shù)據(jù)元素的不同存儲(chǔ)結(jié)構(gòu)；算法的重要特性；評(píng)價(jià)算法的重要指標(biāo)； 如何由程序代碼估算算法的復(fù)雜度（大O描述）。

　　第二章：

　　知識(shí)點(diǎn)：線(xiàn)性表不同的存儲(chǔ)方式及其各自特點(diǎn)；順序表及鏈表的基本操作（插入、刪除等）與其具體代碼實(shí)現(xiàn)。

　　第三章：

　　知識(shí)點(diǎn)：棧和隊(duì)列的結(jié)構(gòu)特點(diǎn)；二者基本操作的思想；鏈隊(duì)列和循環(huán)隊(duì)列的基本操作；循環(huán)隊(duì)列如何判空和判滿(mǎn)。

　　第四章：

　　知識(shí)點(diǎn)：串的相關(guān)定義與基本操作；模式匹配的定義與思想。

　　第五章：

　　知識(shí)點(diǎn)：數(shù)組的定義與順序?qū)崿F(xiàn)方式；數(shù)組順序存儲(chǔ)中元素地址的計(jì)算；稀疏矩陣的壓縮存儲(chǔ)方式與元素地址的特點(diǎn)；廣義表的定義與基本操作（表頭，表尾，判長(zhǎng)度、深度）。

　　第六章：

　　知識(shí)點(diǎn)：樹(shù)的基本術(shù)語(yǔ)；（滿(mǎn)/完全）二叉樹(shù)的定義與各種性質(zhì)特點(diǎn)；二叉樹(shù)不同的存儲(chǔ)與遍歷方式；一般樹(shù)的存儲(chǔ)結(jié)構(gòu)；樹(shù)與森林的遍歷方式；赫夫曼樹(shù)與編碼的求法。

　　第七章：

　　知識(shí)點(diǎn)：（有向/無(wú)向/完全）圖的概念與其特點(diǎn)；（強(qiáng)）聯(lián)通圖的定義與特點(diǎn)；圖的不同存儲(chǔ)結(jié)構(gòu)及其操作；圖的不同方式的遍歷；最小生成樹(shù)的定義與其不同的求解方法；拓?fù)渑判虻亩x與思想；關(guān)鍵（最短）路徑的定義與思想。

　　第九章：

　　知識(shí)點(diǎn)：順序查找、折半查找的思想及其具體代碼實(shí)現(xiàn)和復(fù)雜度分析；索引查找的思想；二叉排序樹(shù)的思想及操作；平衡二叉樹(shù)的定義與操作；B-樹(shù)的定義與特點(diǎn)；哈希表（函數(shù)）的定義；哈希函數(shù)的構(gòu)造方法與處理沖突的方法。

　　第十章：

　　知識(shí)點(diǎn)：各種排序方法的思想與其復(fù)雜度、穩(wěn)定性分析。

　　注：以上涉及到的復(fù)雜度分析，其推導(dǎo)過(guò)程不做要求。

年自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》各章復(fù)習(xí)要點(diǎn)總結(jié)3篇(數(shù)據(jù)結(jié)構(gòu)第二章知識(shí)點(diǎn)總結(jié))相關(guān)文章：