算法與數(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)元素；表空間無(wú)法動(dòng)態(tài)擴(kuò)充，需預(yù)先按最大空間分配，存儲(chǔ)空間利用率低；相鄰元素的物理位置相鄰無(wú)需為維護(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)、兄 弟、堂兄弟、祖先、子孫、樹的高度、有序樹、無(wú)序樹。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是二叉樹的根，無(wú)父結(jié)點(diǎn)；否則父結(jié)點(diǎn)是i/2ii如果2in，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉結(jié)點(diǎn)）；否則左孩子編號(hào)為2iiii如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子；否則右孩子為結(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、圖的基本概念，包括無(wú)向圖、有向圖、頂點(diǎn)的度、頂點(diǎn)的入度和出度、完全 圖、子圖、簡(jiǎn)單路徑、簡(jiǎn)單環(huán)、連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量、 生成樹。連通分量是無(wú)向圖中的極大連通子圖生成樹是無(wú)向連通圖的極小連通子圖在生成樹中每?jī)蓚€(gè)頂點(diǎn)間有且僅有一條路徑具有n個(gè)頂點(diǎn)，少于n-1條邊的圖一定是非連通圖具有n個(gè)頂點(diǎn)，多于n-1條邊的圖中必存在環(huán)具有n個(gè)頂點(diǎn)，n-1條邊的圖不一定是生成樹在無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和是無(wú)向邊數(shù)的2倍在有向圖中，所有頂點(diǎn)的出度或入度之和等于有向邊數(shù)具有n個(gè)頂點(diǎn)的無(wú)向完全圖具有n(n-1)/2條邊；具有n個(gè)頂點(diǎn)的有向完

13、全圖 具有n(n-1)條弧例題：具有18個(gè)頂點(diǎn)的無(wú)向完全圖具有153條邊。若含有32個(gè)頂點(diǎn)的無(wú)向圖是一個(gè)環(huán)，則它有衛(wèi)二棵生成樹。具有n個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹含有n-1 條邊。2、圖的存儲(chǔ)結(jié)構(gòu)無(wú)向圖的鄰接矩陣一定是對(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)是否有邊相連。在無(wú)向圖的鄰接表中，第i個(gè)頂點(diǎn)的度為第i條鏈表中的結(jié)點(diǎn)數(shù)；在無(wú)向圖 的鄰接表中，所有鏈表的結(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條邊的無(wú)向圖對(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è)無(wú)向連通圖，會(huì)寫出它的深度優(yōu)先序列和廣度優(yōu)先序列，會(huì)畫出它 的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。廣度優(yōu)先搜索類似于樹的層次遍歷，深度優(yōu)先搜索類似于樹的先序遍歷從無(wú)向連通圖的任一頂點(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ú)向連通網(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è)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判驒z查有向圖是否存在回路的一種方法是對(duì)有向圖進(jìn)行拓?fù)渑判颉Ｈ羲许旤c(diǎn)均包含在拓 撲序列中，則有向圖中必不存在環(huán)。也可利用深度優(yōu)先遍歷進(jìn)行拓?fù)渑判?，由某頂點(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、二部圖的完全匹配一定是最大匹配，但最大