算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)一、第2章程序性能1、給出一個(gè)程序段，會(huì)寫出該程序段的時(shí)間復(fù)雜度；二、第3章線性表1、順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)表中元素可以隨機(jī)訪問；非表尾的插入和刪除操作需要移動(dòng)元素；表空間無法動(dòng)態(tài)擴(kuò)充，需預(yù)先按最大空間分配，存儲(chǔ)空間利用率低；相鄰元素的物理位置相鄰無需為維護(hù)表中元素的邏輯關(guān)系增加額外的存儲(chǔ)空間2、若用數(shù)組實(shí)現(xiàn)表，設(shè)表元素總數(shù)為n，在第k個(gè)元素后插入一個(gè)新元素，需 要后移的元素?cái)?shù)目為n-k。設(shè)在表的任何合法位置上插入元素的概率均等，則 插入操作所需要的元素移動(dòng)平均次數(shù)為n/2。3、若用數(shù)組實(shí)現(xiàn)表，設(shè)表元素總數(shù)為n，刪除第k個(gè)元素，需要前移的元素?cái)?shù) 目為n-k。設(shè)刪除表的任何元素

2、的概率均等，則刪除操作所需要的元素移動(dòng)平 均次數(shù)為（n-1）/2。4、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)表元素分散存放，物理位置不一定相鄰；每個(gè)結(jié)點(diǎn)包含指向下一結(jié)點(diǎn)的指針域；只能順序搜索，不能隨機(jī)訪問；插入和刪除操作只需要通過修改指針實(shí)現(xiàn)，效率較高不需為表預(yù)留空間，存儲(chǔ)空間利用率高，表容量可動(dòng)態(tài)擴(kuò)充每個(gè)結(jié)點(diǎn)中的指針域需占用額外空間5、在帶哨兵結(jié)點(diǎn)的單循環(huán)鏈表中，設(shè)置尾指針last指向鏈尾結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中 的后繼指針域?yàn)閚ext，則判斷表空的表達(dá)式為last-next=last；在帶哨兵結(jié) 點(diǎn)的雙循環(huán)鏈表中，設(shè)置指針header指向哨兵結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中的后繼指針 域?yàn)閚ext,前驅(qū)指針域?yàn)閜rior，則判斷表空

3、的表達(dá)式為header-next=header 或 header-prior=header。6、在帶哨兵結(jié)點(diǎn)的單鏈表的插入和刪除操作中，鏈指針的修改7、理解靜態(tài)鏈表靜態(tài)鏈表中的指針域又稱為游標(biāo)或模擬指針，存放下一元素在數(shù)組中的下標(biāo)多條靜態(tài)鏈表可共用一個(gè)數(shù)組空間在數(shù)組空間中，靜態(tài)鏈表中的元素可以分散存放，即相鄰元素的下標(biāo)不一定 相鄰靜態(tài)鏈表的擴(kuò)充受到數(shù)組空間容量的限制三、第4章棧1、棧的操作原則為先進(jìn)后出或后進(jìn)先出，插入和刪除操作均在棧頂方向上進(jìn)行。2、用數(shù)組實(shí)現(xiàn)棧的入棧和出棧函數(shù)；3、用數(shù)組實(shí)現(xiàn)棧的優(yōu)缺點(diǎn)：棧上的基本操作都能在常量時(shí)間內(nèi)完成，效率較高；為避免棧發(fā)生溢出，通常需要預(yù)置一個(gè)較大?？?/p>

4、間，存儲(chǔ)空間利用率較低； 為提高空間利用率，可讓多棧共享數(shù)組空間；4、用鏈表實(shí)現(xiàn)棧的特點(diǎn)：鏈?？臻g可以動(dòng)態(tài)擴(kuò)充四、第5章隊(duì)列1、隊(duì)列的操作原則是先進(jìn)先出或后進(jìn)后出，插入操作在隊(duì)尾進(jìn)行，刪除操作在 隊(duì)頭進(jìn)行2、若用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列，設(shè)置front指向隊(duì)頭元素前一單元，rear指向隊(duì)尾元 素，并采用總剩一個(gè)單元不利用的方法區(qū)分滿空狀態(tài)，則當(dāng)front和rear滿足 什么關(guān)系時(shí)隊(duì)列為空，滿足什么關(guān)系時(shí)隊(duì)列為滿？3、用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列的入隊(duì)和出隊(duì)函數(shù)。五、第6章樹1、樹的基本概念，包括樹的度、葉結(jié)點(diǎn)或終端結(jié)點(diǎn)、分支結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)、兄 弟、堂兄弟、祖先、子孫、樹的高度、有序樹、無序樹。2、樹的表示法父結(jié)

5、點(diǎn)數(shù)組表示法可以快速找到結(jié)點(diǎn)的父結(jié)點(diǎn)，但查詢兒子結(jié)點(diǎn)和兄弟結(jié)點(diǎn) 可能要遍歷整個(gè)數(shù)組；在兒子表示法中，若采用定長(zhǎng)結(jié)點(diǎn)的多重鏈表結(jié)構(gòu)，則表示一棵有n個(gè)結(jié)點(diǎn) 度為d的樹必有nd-(n-1 )個(gè)空鏈域兒子鏈表表示法適合于查找子結(jié)點(diǎn)，但不適合于查找父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)帶雙親的兒子鏈表表示法適合于查找子結(jié)點(diǎn)、父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)左兒子右兄弟表示法方便查找子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)，但不方便查找父結(jié)點(diǎn)給出一棵樹，會(huì)用父結(jié)點(diǎn)數(shù)組表示法、兒子鏈表表示法、左兒子右兄弟表示 法表示它。3、二叉樹的概念二叉樹是有序樹度為2的樹不一定是二叉樹度為2的有序樹不一定是二叉樹子樹有嚴(yán)格左右次序之分，且度2的樹是二叉樹4、具有3個(gè)結(jié)點(diǎn)的樹有5種

6、形態(tài)，具有3個(gè)結(jié)點(diǎn)的二叉樹有3種形態(tài)。5、滿二叉樹的特點(diǎn)：所有葉結(jié)點(diǎn)都集中在最底層不存在度為1的結(jié)點(diǎn)每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值所有分支結(jié)點(diǎn)都存在左子樹和右子樹例題：高度為8的滿二叉樹的結(jié)點(diǎn)總數(shù)為255。6、完全二叉樹的特點(diǎn)：葉結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)最下層的葉結(jié)點(diǎn)一定集中在該層的左端度小于2的結(jié)點(diǎn)只可能位于最下兩層除最下層外，其余各層均滿度為1的結(jié)點(diǎn)只可能出現(xiàn)在倒數(shù)第二層對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫最大層次為s，則其左分支下的子孫的最 大層次必為s或s+17、二叉樹的性質(zhì)具有n個(gè)結(jié)點(diǎn)的非空二叉樹共有n-1個(gè)分支非空二叉樹的第i層上至多有2i-i個(gè)結(jié)點(diǎn)（i1）高度為h的非空二叉樹至多

7、有2h-1個(gè)結(jié)點(diǎn)高度為h的完全二叉樹至多有2h-1個(gè)結(jié)點(diǎn)，至少有2h-i個(gè)結(jié)點(diǎn)若非空二叉樹有no個(gè)葉結(jié)點(diǎn)，氣個(gè)度為2的結(jié)點(diǎn)，則氣二具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為h= |log2n +1。具有n個(gè)結(jié)點(diǎn)的二叉樹的最小高度為L(zhǎng)log2n_| +1，最大高度為n。若對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按照層次從上到下，每層從左到右的順序進(jìn) 行編號(hào)，則編號(hào)為i的結(jié)點(diǎn)具有下列性質(zhì)：i如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無父結(jié)點(diǎn)；否則父結(jié)點(diǎn)是i/2ii如果2in，則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉結(jié)點(diǎn)）；否則左孩子編號(hào)為2iiii如果2i+1n，則結(jié)點(diǎn)i無右孩子；否則右孩子為結(jié)點(diǎn)2i+1例題：（以下題均設(shè)僅含一個(gè)結(jié)點(diǎn)的二叉

8、樹的高度為1）具有74個(gè)結(jié)點(diǎn)的完全二叉樹，高度為 7，葉結(jié)點(diǎn)有37 個(gè)。（設(shè)僅含一個(gè)結(jié)點(diǎn)的二叉樹的高度為1）已知二叉樹中葉子數(shù)為40，僅一個(gè)孩子的結(jié)點(diǎn)數(shù)為20，則總結(jié)點(diǎn)數(shù)_。在含30個(gè)結(jié)點(diǎn)的完全二叉樹中，對(duì)所有結(jié)點(diǎn)按層序從1開始編號(hào)（從上層到下層，每層從左到右），則編號(hào)為10的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為20 ，右子 結(jié)點(diǎn)編號(hào)為21 ，父結(jié)點(diǎn)編號(hào)為 5。高度為11的完全二叉樹至多有2047個(gè)結(jié)點(diǎn)，至少有1024個(gè)結(jié)點(diǎn)。具有70個(gè)結(jié)點(diǎn)的完全二叉樹的高度為_1。具有43個(gè)結(jié)點(diǎn)的二叉樹的最小高度為6 ，最大高度為 43。設(shè)在高度為h的二叉樹（設(shè)僅有一個(gè)結(jié)點(diǎn)的二叉樹高度為1）中只有葉結(jié)點(diǎn) 和度為2的結(jié)點(diǎn)（沒有

9、度為1的結(jié)點(diǎn)），則該二叉樹至多有2h-1個(gè)結(jié)點(diǎn)， 至少有2h-1個(gè)結(jié)點(diǎn)。8、二叉樹的存儲(chǔ)結(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，含有n個(gè)結(jié)點(diǎn)的二叉鏈表有n+1個(gè)空鏈域，含 有n個(gè)結(jié)點(diǎn)的三叉鏈表有n+2個(gè)空鏈域。9、二叉樹的前序、中序、后序遍歷給定一棵二叉樹，能寫出它的前序、中序、后序遍歷序列；給定一棵二叉樹的前序和中序序列，能畫出該二叉樹并寫出它的后序序列； 或給定一棵二叉樹的后序和中序序列，能畫出該二叉樹并寫出它的前序序列；10、線索二叉樹線索二叉樹結(jié)點(diǎn)的Ichild、ltag、rchild、rtag各域的含義如何利用中序線索鏈表進(jìn)行二叉樹的中序遍歷？如何利用后序線索鏈表進(jìn)行 二叉樹的后序遍歷？如何利

10、用前序線索鏈表進(jìn)行二叉樹的前序遍歷？11、樹、二叉樹、森林的相互轉(zhuǎn)換中的幾個(gè)結(jié)論前序遍歷樹與前序遍歷與該樹對(duì)應(yīng)的二叉樹具有相同的遍歷結(jié)果后序遍歷樹與中序遍歷與該樹對(duì)應(yīng)的二叉樹具有相同的遍歷結(jié)果前序遍歷森林與前序遍歷與該森林對(duì)應(yīng)的二叉樹具有相同的遍歷結(jié)果后序遍歷森林與中序遍歷與該森林對(duì)應(yīng)的二叉樹具有相同的遍歷結(jié)果六、第7章優(yōu)先隊(duì)列1、最大堆和最小堆的定義（理解）2、初始建堆操作的建堆過程；堆的插入操作中堆的調(diào)整過程；刪除堆頂元素后 堆的調(diào)整過程3、堆排序的時(shí)間復(fù)雜度為O（nlogn）4、堆排序的方法；堆排序是一種不穩(wěn)定的排序方法5、左偏高樹的左子樹高度不一定大于右子樹高度6、具有m個(gè)結(jié)點(diǎn)的左偏高

11、樹和左偏重樹的最右路徑長(zhǎng)度最多為log2（m+1）7、左偏樹不作為復(fù)習(xí)要點(diǎn)七、第8章搜索樹1、二叉搜索樹的定義2、二叉搜索樹的中序遍歷序列是升序序列3、二叉搜索樹上的查找操作過程，插入操作過程，刪除操作中樹結(jié)構(gòu)的重組（重 點(diǎn)掌握當(dāng)被刪結(jié)點(diǎn)存在左右子樹時(shí)，樹結(jié)構(gòu)重組策略3。即用被刪結(jié)點(diǎn)P的 左子樹中最右下結(jié)點(diǎn)S中元素替代被刪元素，將S的左子樹掛接為其父結(jié)點(diǎn) 的右子樹。）4、二叉搜索樹上的前驅(qū)運(yùn)算和后繼運(yùn)算的操作過程。5、平衡二叉樹的定義，平衡因子的定義（平衡二叉樹上結(jié)點(diǎn)的平衡因子絕對(duì)值 不大于1）6、在含有n個(gè)結(jié)點(diǎn)的AVL樹上執(zhí)行搜索、插入、刪除操作的時(shí)間復(fù)雜度為 O（logn）7、AVL樹上插

12、入和刪除操作中的平衡旋轉(zhuǎn)操作不作為復(fù)習(xí)要點(diǎn)八、第9章圖1、圖的基本概念，包括無向圖、有向圖、頂點(diǎn)的度、頂點(diǎn)的入度和出度、完全 圖、子圖、簡(jiǎn)單路徑、簡(jiǎn)單環(huán)、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量、 生成樹。連通分量是無向圖中的極大連通子圖生成樹是無向連通圖的極小連通子圖在生成樹中每?jī)蓚€(gè)頂點(diǎn)間有且僅有一條路徑具有n個(gè)頂點(diǎn)，少于n-1條邊的圖一定是非連通圖具有n個(gè)頂點(diǎn)，多于n-1條邊的圖中必存在環(huán)具有n個(gè)頂點(diǎn)，n-1條邊的圖不一定是生成樹在無向圖中，所有頂點(diǎn)的度數(shù)之和是無向邊數(shù)的2倍在有向圖中，所有頂點(diǎn)的出度或入度之和等于有向邊數(shù)具有n個(gè)頂點(diǎn)的無向完全圖具有n(n-1)/2條邊；具有n個(gè)頂點(diǎn)的有向完

13、全圖 具有n(n-1)條弧例題：具有18個(gè)頂點(diǎn)的無向完全圖具有153條邊。若含有32個(gè)頂點(diǎn)的無向圖是一個(gè)環(huán)，則它有衛(wèi)二棵生成樹。具有n個(gè)頂點(diǎn)的無向連通圖的生成樹含有n-1 條邊。2、圖的存儲(chǔ)結(jié)構(gòu)無向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣不一定對(duì)稱。有向圖鄰接矩陣的第i行非零元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的出度，第i列非零 元素的個(gè)數(shù)為第i個(gè)頂點(diǎn)的入度，第i個(gè)頂點(diǎn)的度為第i行和第i列非零元 素的個(gè)數(shù)之和。用鄰接矩陣表示圖，很容易確定圖中任意兩個(gè)頂點(diǎn)是否有邊相連。在無向圖的鄰接表中，第i個(gè)頂點(diǎn)的度為第i條鏈表中的結(jié)點(diǎn)數(shù)；在無向圖 的鄰接表中，所有鏈表的結(jié)點(diǎn)總數(shù)是圖中邊數(shù)的2倍在有向圖的鄰接表中，第i個(gè)

14、頂點(diǎn)的出度為第i條鏈表中的結(jié)點(diǎn)數(shù)，為求結(jié) 點(diǎn)的入度需要遍歷整個(gè)鄰接表。在有向圖的鄰接表中，所有鏈表的結(jié)點(diǎn)總數(shù) 等于圖中的有向邊數(shù)在有向圖的逆鄰接表中，第i個(gè)頂點(diǎn)的入度為第i條鏈表中的結(jié)點(diǎn)數(shù)在鄰接表上容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任 兩個(gè)頂點(diǎn)i、j間是否有邊或弧相連，則需搜索第i條或第j條鏈表。鄰接表更適合于表示稀疏圖，鄰接矩陣更適合于表示稠密圖。給出一個(gè)圖，會(huì)用鄰接表或鄰接矩陣表示該圖例題：含有n個(gè)頂點(diǎn)，e條邊的無向圖對(duì)應(yīng)的鄰接表中有2e個(gè)鏈結(jié)點(diǎn)(不包括鄰接表的表頭結(jié)點(diǎn))。含有n個(gè)頂點(diǎn)，e條弧的有向圖對(duì)應(yīng)的鄰接表中有 個(gè)鏈結(jié)點(diǎn)(不包括鄰 接表的表頭結(jié)點(diǎn))。3、圖的廣度優(yōu)

15、先搜索和深度優(yōu)先搜索給出一個(gè)無向連通圖，會(huì)寫出它的深度優(yōu)先序列和廣度優(yōu)先序列，會(huì)畫出它 的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。廣度優(yōu)先搜索類似于樹的層次遍歷，深度優(yōu)先搜索類似于樹的先序遍歷從無向連通圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索或廣度優(yōu)先搜索即可訪 問所有頂點(diǎn)進(jìn)行圖的廣度優(yōu)先搜索時(shí)，需要用到隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)4、求最小生成樹的Prim算法給出一個(gè)無向連通網(wǎng)，會(huì)使用Prim算法求出它的最小生成樹，并能寫出求解過程。理 解課件中在Prim算法這一節(jié)給出的例題5、求單源最短路徑的Dijkstra算法給出一個(gè)有向賦權(quán)圖，會(huì)使用Dijkstra算法求從指定源點(diǎn)到其余頂點(diǎn)的最短路徑和最短 路徑長(zhǎng)度，并能寫

16、出求解過程。理解課件中在Dijkstra算法這一節(jié)給出的例題6、拓?fù)渑判驎?huì)對(duì)一個(gè)有向無環(huán)圖進(jìn)行拓?fù)渑判驒z查有向圖是否存在回路的一種方法是對(duì)有向圖進(jìn)行拓?fù)渑判?。若所有頂點(diǎn)均包含在拓 撲序列中，則有向圖中必不存在環(huán)。也可利用深度優(yōu)先遍歷進(jìn)行拓?fù)渑判颍赡稠旤c(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，最先退出dfs 過程的即出度為0的頂點(diǎn)，是拓?fù)湫蛄兄凶詈笠粋€(gè)頂點(diǎn)。但深度優(yōu)先遍歷算法會(huì)忽略圖 中有向環(huán)的存在，對(duì)于存在有向環(huán)的圖不能檢測(cè)出環(huán)的存在。7、關(guān)鍵路徑對(duì)給定的AOE網(wǎng)，能計(jì)算出各頂點(diǎn)所代表事件的最早和最晚發(fā)生時(shí)間，各活動(dòng)的最早 開始時(shí)間、最晚開始時(shí)間和時(shí)間余量，能找出關(guān)鍵活動(dòng)和關(guān)鍵路徑，求出工程的工期。 理解課件中在關(guān)鍵路徑這一節(jié)給出的例題只有在不改變關(guān)鍵路徑的情況下，提高關(guān)鍵活動(dòng)的速度才有效提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度8、二部圖的完全匹配一定是最大匹配，但最大