下面是范文網(wǎng)小編收集的年自學考試《數(shù)據(jù)結(jié)構(gòu)》各章復習要點總結(jié)3篇 數(shù)據(jù)結(jié)構(gòu)第一章知識點總結(jié)，以供借鑒。

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

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

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

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

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

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

　　地址的計算方法：

·按行優(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.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間;對零元素不分配空間。

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

　　稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠遠小于零元素的個數(shù)，則該矩陣稱為稀疏矩陣。

　　特殊矩陣的類型：

·對稱矩陣：滿足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.·對角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結(jié)點存放在一起，用這些結(jié)點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。

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

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

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

·其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。

　　廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。

　　廣義表與樹(形結(jié)構(gòu))相對應，這個廣義表就是純表。

　　如果一個廣義表的結(jié)點又可以被其他結(jié)點所共享，則這個表稱為再入表。

　　允許遞歸的表稱為遞歸表。

　　線性表∈純表(樹)∈再入表∈遞歸表。可見，廣義表是對線性表和樹的推廣。

　　廣義表有兩個特殊的基本運算：

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

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

　　第六章 樹

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

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

　　有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;

　　樹的四種不同表示方法：

·樹形表示法;

·嵌套集合表示法;

·凹入表示法;

·廣義表表示法。

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

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

　　二叉樹的4個重要性質(zhì)：

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

·深度為k的二叉樹至多有(2^k)-1個結(jié)點(k≥1);

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

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

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

　　樹的存儲結(jié)構(gòu)多用的是鏈式存儲。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點，加上一個指向根結(jié)點的BinTree型頭指針就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。

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

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

　　樹和森林及二叉樹的轉(zhuǎn)換是唯一對應的。

　　轉(zhuǎn)換方法：

·樹變二叉樹：兄弟相連，保留長子的連線。

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

·森林變二叉樹：樹變二叉樹，各個樹的根相連。

　　樹的存儲結(jié)構(gòu)：

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

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

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

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

　　樹的帶權路徑長度是樹中所有葉結(jié)點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優(yōu)二叉樹(即哈夫曼樹)。

　　在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。

　　哈夫曼樹有n個葉結(jié)點，共有2n-1個結(jié)點，沒有度為1的結(jié)點，這類樹又稱為嚴格二叉樹。

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

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

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

　　11-12-2數(shù)據(jù)結(jié)構(gòu)復習指導

　　第一章：

　　知識點：數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)元素關系的基本結(jié)構(gòu)類型；數(shù)據(jù)元素的不同存儲結(jié)構(gòu)；算法的重要特性；評價算法的重要指標； 如何由程序代碼估算算法的復雜度（大O描述）。

　　第二章：

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

　　第三章：

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

　　第四章：

　　知識點：串的相關定義與基本操作；模式匹配的定義與思想。

　　第五章：

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

　　第六章：

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

　　第七章：

　　知識點：（有向/無向/完全）圖的概念與其特點；（強）聯(lián)通圖的定義與特點；圖的不同存儲結(jié)構(gòu)及其操作；圖的不同方式的遍歷；最小生成樹的定義與其不同的求解方法；拓撲排序的定義與思想；關鍵（最短）路徑的定義與思想。

　　第九章：

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

　　第十章：

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

　　注：以上涉及到的復雜度分析，其推導過程不做要求。

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

　　2010年自學考試《數(shù)據(jù)結(jié)構(gòu)》各章復習要點總結(jié)(2)2010年自學考試《數(shù)據(jù)結(jié)構(gòu)》四至六章復習要點總結(jié)。

　　第四章 串

　　串是零個或多個字符組成的有限序列。

·空串：是指長度為零的串，也就是串中不包含任何字符(結(jié)點)。

·空白串：指串中包含一個或多個空格字符的串。

·在一個串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。

·子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置。

·空串是任意串的子串，任意串是自身的子串。

　　串分為兩種：

·串常量在程序中只能引用不能改變;

·串變量的值可以改變。

　　串的基本運算有：

·求串長strlen(char*s)

·串復制strcpy(char*to，char*from)

·串聯(lián)接strcat(char*to，char*from)

·串比較charcmp(char*s1，char*s2)

·字符定位strchr(char*s，charc)

。串是特殊的線性表(結(jié)點是字符)，所以串的存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。串的順序存儲結(jié)構(gòu)簡稱為順序串。

　　順序串又可按存儲分配的不同分為：

·靜態(tài)存儲分配：直接用定長的字符數(shù)組來定義。優(yōu)點是涉及串長的操作速度快，但不適合插入、鏈接操作。

·動態(tài)存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。

　　串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點數(shù)據(jù)域為單個字符。

　　為了解決“存儲密度”低的狀況，可以讓一個結(jié)點存儲多個字符，即結(jié)點的大小。

　　順序串上子串定位的運算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(串)，子串稱為模式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O((n-m+1)m)，假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運算位移是結(jié)點地址而不是整數(shù)。

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

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

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

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

　　地址的計算方法：

·按行優(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.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間;對零元素不分配空間。

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

　　稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠遠小于零元素的個數(shù)，則該矩陣稱為稀疏矩陣。

　　特殊矩陣的類型：

·對稱矩陣：滿足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.·對角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結(jié)點存放在一起，用這些結(jié)點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。

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

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

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

·其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。

　　廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。

　　廣義表與樹(形結(jié)構(gòu))相對應，這個廣義表就是純表。

　　如果一個廣義表的結(jié)點又可以被其他結(jié)點所共享，則這個表稱為再入表。

　　允許遞歸的表稱為遞歸表。

　　線性表∈純表(樹)∈再入表∈遞歸表?？梢?，廣義表是對線性表和樹的推廣。

　　廣義表有兩個特殊的基本運算：

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

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

　　第六章 樹

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

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

　　有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;

　　樹的四種不同表示方法：

·樹形表示法;

·嵌套集合表示法;

·凹入表示法;

·廣義表表示法。

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

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

　　二叉樹的4個重要性質(zhì)：

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

·深度為k的二叉樹至多有(2^k)-1個結(jié)點(k≥1);

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

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

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

　　樹的存儲結(jié)構(gòu)多用的是鏈式存儲。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點，加上一個指向根結(jié)點的BinTree型頭指針就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。

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

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

　　樹和森林及二叉樹的轉(zhuǎn)換是唯一對應的。

　　轉(zhuǎn)換方法：

·樹變二叉樹：兄弟相連，保留長子的連線。

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

·森林變二叉樹：樹變二叉樹，各個樹的根相連。

　　樹的存儲結(jié)構(gòu)：

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

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

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

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

　　樹的帶權路徑長度是樹中所有葉結(jié)點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優(yōu)二叉樹(即哈夫曼樹)。

　　在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。

　　哈夫曼樹有n個葉結(jié)點，共有2n-1個結(jié)點，沒有度為1的結(jié)點，這類樹又稱為嚴格二叉樹。

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

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

年自學考試《數(shù)據(jù)結(jié)構(gòu)》各章復習要點總結(jié)3篇 數(shù)據(jù)結(jié)構(gòu)第一章知識點總結(jié)相關文章：

★ 年自學考試《數(shù)據(jù)結(jié)構(gòu)》各章復習要點總結(jié)3篇(數(shù)據(jù)結(jié)構(gòu)第二章知識點總結(jié))