【正文】 完美WORD格式編輯 。開放定址法：裝填因子α≤1。，順序查找和二分查找所需要進(jìn)行的關(guān)鍵字僅取決于表長，而散列表查找所需要進(jìn)行的比較次數(shù)和待查結(jié)點(diǎn)有關(guān)。有m個(gè)散列地址就有m個(gè)鏈表。二次探查法：d+12，d12，d+22，d22拉鏈法：存儲(chǔ)結(jié)構(gòu)是鏈表時(shí)常用。：開放定址法和拉鏈法。這是一種最簡單也最常用的方法。數(shù)字分析法：從中提取數(shù)字分布比較均勻的若干位作為散列地址。直接地址法：計(jì)算簡單，并且沒有沖突。如何盡量避免沖突和沖突發(fā)生后如何解決沖突，就成了散列存儲(chǔ)的兩個(gè)關(guān)鍵問題。具有相同散列地址的關(guān)鍵字稱為同義詞。，是一種由關(guān)鍵字到地址的直接轉(zhuǎn)換方法。+樹是一種文件組織的B樹的變形樹，通常有兩個(gè)頭指針root和sqt，前者指向根結(jié)點(diǎn)，后者指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。d、每個(gè)非根結(jié)點(diǎn)中所含的關(guān)鍵字個(gè)數(shù)滿足：?m/2?1≤n≤m1，因?yàn)槊總€(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)正好是關(guān)鍵字總數(shù)加1，所以處根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有?m/2?棵子樹，至多有m棵子樹。 一棵m(m≥3)階的B樹，或?yàn)榭諛?，或?yàn)闈M足下列性質(zhì)的m叉樹 a、每個(gè)結(jié)點(diǎn)至少包含下列信息域；b、每個(gè)結(jié)點(diǎn)至多有m棵子樹；c、若樹為非空，則根結(jié)點(diǎn)至少有1個(gè)關(guān)鍵字，至多有m1個(gè)關(guān)鍵字。平衡二叉樹：既能滿足BST性質(zhì)又能保證二叉排序樹的深度在任何情況下均為O(log2n)。s是p的右子樹中最左邊的結(jié)點(diǎn)且沒有左子樹。即p是左子樹則p的子樹變?yōu)閒的左子樹；c、若p既有左子樹又有右子樹，任選一種方法：(1)、用p的直接前驅(qū)結(jié)點(diǎn)代替p，即從p的左子樹中選擇值最大的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。 二叉排序樹的刪除：被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f。二叉排序樹的查找與給定值的比較次數(shù)不會(huì)超過樹的深度。同樣一組關(guān)鍵字序列，由于其輸入順序不同，所得到的二叉排序樹也有所不同，含有n個(gè)結(jié)點(diǎn)的二叉排序樹不是唯一的。c、左右子樹本身又各是一棵二叉排序樹。 上述三種查找的時(shí)間復(fù)雜度分別是O(n)、O(log2n)和O(n的平方根)(二叉查找樹)：或者是一棵空樹，或者具有下面性質(zhì)：a、若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。 分塊查找的優(yōu)點(diǎn)是，在表中插入或刪除一個(gè)記錄時(shí)，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進(jìn)行插入或刪除操作，因?yàn)閴K內(nèi)記錄是無序的，所以插入或刪除比較容易，無需移動(dòng)大量記錄。 順序查找缺點(diǎn)是n較大時(shí)，查找成功約為(n+1)/2，失敗需要比較n+1次。 分塊查找的基本思想是：首先查找索引表，可用二分查找或順序查找，然后在確定的塊中進(jìn)行順序查找。(分塊查找)：是一種介于順序查找和二分查找之間的查找方法?？梢姡植檎业淖顗男阅芎推骄阅芟喈?dāng)接近。查找成功時(shí)的平均查找長度 (n+1)/nlog2(n+1)1，當(dāng)n很大時(shí)，可近似用log2(n+1)1表示。 從判定樹上可見，關(guān)鍵字比較的次數(shù)恰好為該結(jié)點(diǎn)在樹中的層數(shù)。由于二分查找是在有序表上進(jìn)行的，所以其對(duì)應(yīng)的判定樹必定是一棵二叉排序樹。查找過程是遞歸的。 對(duì)于有序表來說，該算法的平均查找長度是(n+1)/2。如果查找成功和不成功機(jī)會(huì)相等，那么平均查找長度3(n+1)/4。 運(yùn)算查找的主要操作是關(guān)鍵字的比較，因此把查找過程中的平均比較次數(shù)(也稱為平均查找長度)作為衡量算法效率優(yōu)劣的標(biāo)準(zhǔn)。第八章：查找，是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。一般的排序方法都可以在順序結(jié)構(gòu)上實(shí)現(xiàn)，當(dāng)記錄本身信息量較大時(shí)，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。：本章除基數(shù)排序外，都是在順序表上實(shí)現(xiàn)的。d趟箱排序。箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子數(shù)目太多。：前面方法都至少需要進(jìn)行?nlogn?次比較，而分配排序?qū)r(shí)間復(fù)雜度降為O(n)。：首先將待排序文件看成n個(gè)長度為1的有序子文件，把這些子文件兩兩歸并，得到?n/2?個(gè)長度為2的有序子文件，然后再將他們兩兩歸并，如此反復(fù)，直到得到一個(gè)長度為n的有序文件，此稱為二路歸并排序。從?n/2?開始。堆排序是一個(gè)不斷建堆的過程。基本思想：在排序過程中，將記錄數(shù)組R[1..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大或最小記錄。初始情況是有序區(qū)為空，無序區(qū)中R[1..n]，第一趟從R[1..n]選擇最小記錄與R[1]交換。 直接選擇排序：初始時(shí)，R[1..n]為無序區(qū)，R[1]為空；第一趟是在R[1..n]中選出最小的記錄與R[1]交換，R[1]為有序區(qū)；第二趟是在R[2..n]中選出最小的記錄與R[2]交換，R[1..2]為有序區(qū)?？焖倥判蚴沁f歸的，需要一個(gè)?？臻g，空間復(fù)雜度O(log2n)?？焖倥判蚴遣环€(wěn)定的。比較和交換從兩端向中間進(jìn)行。是穩(wěn)定的排序算法。 冒泡排序(起泡排序)：通過相鄰元素之間比較和交換，使較小移向頂部，從后往前兩兩比較。希爾排序的時(shí)間依賴于增量序列，最后一個(gè)增量必須是1，盡量避免增量互為倍數(shù)的情況。希爾排序(縮小增量排序)：算法不穩(wěn)定。 是穩(wěn)定的算法。時(shí)間復(fù)雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。所以R[0]稱為哨兵。 直接插入排序：每次從無序區(qū)取出第一個(gè)元素把它插入到有序區(qū)的適當(dāng)位置，使之成為新的有序區(qū)，經(jīng)過n1次插入后完成。排序的時(shí)間開銷，一般情況下可用算法中關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來衡量。評(píng)價(jià)排序算法的標(biāo)準(zhǔn)：執(zhí)行算法需要的時(shí)間，以及算法所需要的附加空間。內(nèi)部排序又分為五類：插入、選擇、交換、歸并和分配排序。第七章 排序，經(jīng)過排序后，這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。 拓?fù)渑判驅(qū)嶋H上是對(duì)鄰接表表示的圖G進(jìn)行遍歷的過程。c、重復(fù)上述步驟，直到全部頂點(diǎn)都已輸出或圖中剩余的頂點(diǎn)中沒有前趨頂點(diǎn)為止。 拓?fù)渑判虻拿枋鏊枷耄篴、在有向圖中選一個(gè)沒有前趨(入度為零)的頂點(diǎn)，且輸出之。 檢測(cè)的方法是：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄校艟W(wǎng)中所有頂點(diǎn)都在他的拓?fù)湫蛄兄?，則AOV網(wǎng)必定不存在環(huán)。 將有向無環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列，若u，v∈E（G），則在線性序列u在v之前，這種線性序列稱為拓?fù)湫蛄小！⊥負(fù)渑判颍鹤庸こ谭Q為活動(dòng)，頂點(diǎn)代表活動(dòng)，有向邊代表活動(dòng)的先后關(guān)系?？唆斔箍朘ruskal算法的時(shí)間復(fù)雜度為O（eloge），主要取決于邊數(shù)，較適合于稀疏圖。 最小生成樹：圖的生成樹不唯一，把權(quán)值最小的生成樹稱為最小生成樹（MST）。 因此，一個(gè)具有n個(gè)頂點(diǎn)的生成樹有且僅有n1條邊，但有n1條邊的圖不一定是生成樹，同一個(gè)圖可以有不同的生成樹。時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e)，空間復(fù)雜度都是O(n)。共需要搜索n2個(gè)矩陣元素，時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e)。 深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。：遍歷圖的算法是求解圖的連通性、圖的拓?fù)渑判虻人惴ǖ幕A(chǔ)。建立鄰接表的時(shí)間復(fù)雜度是O(n+e)。將無向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表，將鄰接表的表頭向量稱為頂點(diǎn)表。若G是帶權(quán)圖，只要把1換成相應(yīng)邊上的權(quán)值即可，0的位置上可以不動(dòng)或?qū)⑵鋼Q成無窮大表示。 鄰接矩陣表示法：vi,vj或(vi,vj)是邊，則值為1，不是邊則值為0。：鄰接矩陣和鄰接表表示法。若在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。無向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個(gè)，即其自身，而非連通的無向圖有多個(gè)連通分量。在無向圖中，任意兩頂點(diǎn)都有路徑，則稱兩頂點(diǎn)連通。在有向圖中，n的取值范圍是0n(n1)，將具有n(n1)條邊的有向圖稱為有向完全圖。無向圖的頂點(diǎn)對(duì)用圓括號(hào)表示(vi,vj)。第六章 圖，頂點(diǎn)集合和邊集合，也可以圖G只有頂點(diǎn)而沒有邊。因此設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。設(shè)計(jì)一種長短不等的編碼，則必須保證任一字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼。 ③ 哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為1的分支結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n1個(gè)結(jié)點(diǎn)。注意：① 初始森林中的n棵二叉樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子這棵樹便是哈夫曼樹?！　?2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(當(dāng)這樣的樹不止兩棵樹時(shí)，可以從中任選兩棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個(gè)新結(jié)點(diǎn)作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關(guān)緊要)，將這兩個(gè)孩子的權(quán)值之和作為新樹根的權(quán)值。 ③ 最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。完全二叉樹就是這種路徑長度最短的二叉樹。 哈夫曼樹不一定是二叉樹。① 前序遍歷森林等同于前序遍歷該森林對(duì)應(yīng)的二叉樹② 后序遍歷森林等同于中序遍歷該森林對(duì)應(yīng)的二叉樹，樹種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度。對(duì)下面(a)圖中所示的森林進(jìn)行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE。：一般都只給出兩種次序遍歷樹的方法：前序(先根次序)遍歷和后序(后根次序)遍歷。 　這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈表表示完全一樣。：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域，即可得樹的孩子兄弟鏈表表示。：孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。：：雙親鏈表表示法利用樹中每個(gè)結(jié)點(diǎn)的雙親唯一性，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parent，惟一地表示任何棵樹。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根