數(shù)據(jù)結(jié)構(gòu)_(嚴(yán)蔚敏C語言版)_學(xué)習(xí)、復(fù)習(xí)提綱

1、期末復(fù)習(xí)第一章 緒論 復(fù)習(xí)基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)算 法概 念邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)運(yùn)算數(shù)據(jù)：計(jì)算機(jī)處理的信息總稱數(shù)據(jù)項(xiàng)：最小單位數(shù)據(jù)元素：最基本單位數(shù)據(jù)對(duì)象：元素集合數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。概念：數(shù)據(jù)元素之間的關(guān)系線性結(jié)構(gòu)：一對(duì)一非線性結(jié)構(gòu) 樹：一對(duì)多圖：多對(duì)多順序存儲(chǔ)結(jié)構(gòu)鏈表存儲(chǔ)結(jié)構(gòu)索引。散列。算法描述：指令的有限有序序列算法特性有窮性確定性可行性輸入輸出算法分析時(shí)間復(fù)雜度空間復(fù)雜度1、計(jì)算機(jī)算法必須具備輸入、輸出、可行性、確定性、有窮性個(gè)特性。2、算法分析的兩個(gè)主要方面是空間復(fù)雜度和時(shí)間復(fù)雜度。3、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。4、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。5、數(shù)據(jù)結(jié)構(gòu)是

2、帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈接、散列和索引四種基本類型。第二章 線性表 復(fù)習(xí)線性表順序存儲(chǔ)結(jié)構(gòu)鏈表存儲(chǔ)結(jié)構(gòu)概 念基本特點(diǎn)基本運(yùn)算定義邏輯關(guān)系：前趨 后繼節(jié)省空間隨機(jī)存取插、刪效率低插入刪除單鏈表雙向鏈表特點(diǎn)一個(gè)指針域+一個(gè)數(shù)據(jù)域多占空間查找費(fèi)時(shí)插、刪效率高無法查找前趨結(jié)點(diǎn)運(yùn)算特點(diǎn)：單鏈表+前趨指針域運(yùn)算插入刪除循環(huán)鏈表特點(diǎn)：單鏈表的尾結(jié)點(diǎn)指針指向附加頭結(jié)點(diǎn)。運(yùn)算：聯(lián)接1、在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，包括一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針 、一個(gè)指向后繼結(jié)點(diǎn)的指針2、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元3、線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作4、線性表采用順序

3、存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)優(yōu)缺點(diǎn)比較。5、簡單算法第三章 棧和隊(duì)列 復(fù)習(xí)棧存儲(chǔ)結(jié)構(gòu)棧的概念：在一端操作的線性表運(yùn)算算法棧的特點(diǎn)：先進(jìn)后出 LIFO初始化進(jìn)棧push出棧pop隊(duì)列順序隊(duì)列循環(huán)隊(duì)列隊(duì)列概念：在兩端操作的線性表假溢出鏈隊(duì)列隊(duì)列特點(diǎn)：先進(jìn)先出 FIFO基本運(yùn)算順序：鏈隊(duì)：隊(duì)空：front=rear隊(duì)滿：front=(rear+1)%MAXSIZE隊(duì)空： frontrear初始化判空進(jìn)隊(duì)出隊(duì)取隊(duì)首元素1、 棧和隊(duì)列的異同點(diǎn)。2、 棧和隊(duì)列的基本運(yùn)算3、 出棧和出隊(duì)4、 基本運(yùn)算第四章 串 復(fù)習(xí)串存儲(chǔ)結(jié)構(gòu)運(yùn) 算概 念順序串鏈表串定義：由n(1)個(gè)字符組成的有限序列S=”c1c2c3 cn”串長度、空

4、白串、空串。緊縮格式非緊縮格式以字節(jié)為單位的存儲(chǔ)格式（C語言用數(shù)組或指針表示）基本運(yùn)算strlen(s)串長度strcat(s1,s2)聯(lián)接strcmp(s1,s2)比較strcpy(s1,s2)復(fù)制strstr(s1,s2)子串查詢模式匹配失敗鏈接值匹配算法單字符鏈表串多字符鏈表串串變量的存儲(chǔ)映像：串名、串值對(duì)應(yīng)關(guān)系表第五章 數(shù)組和廣義表 復(fù)習(xí)數(shù)組順序存儲(chǔ)方式壓縮存儲(chǔ)方式行優(yōu)先順序存放列優(yōu)先順序存放C語言數(shù)組：行優(yōu)先下標(biāo)從0開始，公式變化稀疏矩陣應(yīng) 用表達(dá)式程序調(diào)用廣義表運(yùn) 算定義：n(0)個(gè)元素的有限序列表頭：Head(A)= a1概念：長度、深度、原子、子表存儲(chǔ)結(jié)構(gòu)(鏈表)表尾：Tail

5、(A)=(a2,a3,an)tp表結(jié)點(diǎn)特殊矩陣對(duì)稱矩陣三角矩陣對(duì)角矩陣三元組存儲(chǔ)：三元組 m n t鏈表存儲(chǔ)：十字鏈表hptag=1tp原子結(jié)點(diǎn)hptag=0第六章 樹 復(fù)習(xí)樹二叉樹概 念二叉樹定義：樹中結(jié)點(diǎn)的度2 有序樹可為空樹（n=0）性質(zhì)定義：遞歸定義，不為空雙親、孩子、葉子、兄弟、祖先樹深、結(jié)點(diǎn)的度、有序樹、無序樹存儲(chǔ)方式順序：滿、完全二叉樹鏈表：二叉、三叉鏈表先根遍歷序列中根遍歷序列 后根遍歷序列1. 第i層至多有2i-1個(gè)結(jié)點(diǎn)。2. 數(shù)深為k的二叉樹，至多有2k-1個(gè)結(jié)點(diǎn)。3. n0=n2+14. n個(gè)結(jié)點(diǎn)的二叉樹樹深為log2n/2+15. 雙親結(jié)點(diǎn)為i，做孩子結(jié)點(diǎn)的編號(hào)為2i，

6、有孩子2i+1。二叉樹的遍歷已知先根、中根序列畫樹；已知后根、中根序列畫樹；先根線索中根線索 后根線索線索二叉樹線索樹的畫法樹、森林與二叉樹的相互轉(zhuǎn)換樹、森林的遍歷樹、森林二叉排序樹樹的應(yīng)用哈夫曼樹左 中 右小 中 大哈夫曼樹的畫法編碼：左0右11、三個(gè)結(jié)點(diǎn)可以組成2種不同形態(tài)的樹。 2、一個(gè)稀疏矩陣Am*n采用三元組形式表示，若完成了其的轉(zhuǎn)置運(yùn)算要經(jīng)過哪幾步:矩陣的行、列數(shù)值互換 、矩陣元素所在行列值互換、元素在矩陣中排列的位置）重新排列3、若二叉樹中每一層結(jié)點(diǎn)的個(gè)數(shù)都達(dá)到了最大，則稱為一棵滿二叉樹。4、樹最適合用來表示現(xiàn)有元素之間具有分支層次關(guān)系的數(shù)據(jù)5、哈夫曼樹是帶權(quán)路徑長度最小的二叉樹

7、。6、以下那些項(xiàng)為用十字鏈表表示的稀疏矩陣元素結(jié)點(diǎn)信息元素所在行和列 、元素的值 、指向該元素所在行的下一個(gè)元素的指針 、指向該元素所在列的下一個(gè)元素的指針。 7、一個(gè)廣義表可以為其它廣義表所共享。8、廣義表可以是一個(gè)多層次的結(jié)構(gòu)。9、壓縮存儲(chǔ)的三角矩陣和對(duì)稱矩陣的存儲(chǔ)空間相同。10、廣義表中的元素類型可以不相同。11、兩個(gè)稀疏矩陣的和仍為稀疏矩陣。12、二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。13、對(duì)于一棵具有n個(gè)節(jié)點(diǎn)的樹，該樹中所有節(jié)點(diǎn)的度數(shù)之和為n-1。14、樹和森林的遍歷中有中序遍歷。15、二叉樹用鏈?zhǔn)酱鎯?chǔ)時(shí)，空鏈域數(shù)多于非空鏈域數(shù)。16、由森林轉(zhuǎn)換成二叉樹，其根節(jié)

8、點(diǎn)的右子樹總是空的。17、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。18、當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹的WPL值為最小時(shí)，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。x 19、某二叉樹的先序遍歷序列和中序遍歷序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無左孩子的非空二叉樹。20、某二叉樹的先序遍歷序列和后序遍歷序列相同的二叉樹為空樹或僅有一個(gè)結(jié)點(diǎn)的非空二叉樹。21、某二叉樹的后序遍歷序列和中序遍歷序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無左孩子的非空二叉樹。x22、某二叉樹的先序遍歷序列和后序遍歷序列相反的二叉樹為高度等于結(jié)點(diǎn)數(shù)的二叉樹。滿二叉樹就是除葉子結(jié)點(diǎn)外的任何結(jié)點(diǎn)均有兩

9、個(gè)孩子結(jié)點(diǎn)，且所有的葉子結(jié)點(diǎn)都在同一層上的二叉樹。23、用一維數(shù)組存放二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)，這是錯(cuò)誤的說法24、在度為k的樹中，至少有一個(gè)度為k的結(jié)點(diǎn)。25、在非空完全二叉樹中，只有最下面一層的結(jié)點(diǎn)為葉結(jié)點(diǎn)。26、在完全二叉樹中，沒有左孩子的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。27、 特殊矩陣主要形式有對(duì)稱矩陣、上三角矩陣、下三角矩陣、對(duì)角矩陣28、在結(jié)點(diǎn)數(shù)目一定的前提下，各種形態(tài)的二叉樹中，完全二叉樹具有最小深度。 29、在所有深度相同的二叉樹中，滿二叉樹具有最大結(jié)點(diǎn)數(shù)目。30、給定一組權(quán)值，構(gòu)造出來的哈夫曼樹是不惟一的。31、哈夫曼樹中不存在度為1的結(jié)點(diǎn)。 32、線索二叉樹中的每個(gè)結(jié)點(diǎn)通常包含

10、有5個(gè)數(shù)據(jù)成員。33、判斷兩個(gè)串相等的充分必要條件有兩個(gè):兩個(gè)串的長度相等;兩個(gè)串上對(duì)應(yīng)位置的字符相同 34、下列哪些是廣義表的特性:層次性 、共享性 、遞歸性35、稀疏矩陣元素的三元組表示的項(xiàng):元素所在行 、元素所在列 、元素的值 第七章 圖 復(fù)習(xí)圖存儲(chǔ)結(jié)構(gòu)概念二叉樹定義：樹中結(jié)點(diǎn)的度2 有序樹可為空樹（n=0）鄰接矩陣鄰接鏈表、逆鄰接鏈表定義：G=(V, E)無向圖、有向圖路徑、回路（環(huán)）、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量頂點(diǎn)的度：TD(Vi)=ID(Vi)+OD(Vi)邊與度的關(guān)系：2e=TD(Vi) (1in)網(wǎng)絡(luò)：AOV網(wǎng)、AOE網(wǎng)深度優(yōu)先遍歷序列DFS廣度優(yōu)

11、先遍歷序列BFS圖的遍歷Prim普里姆算法Kruskal 克魯斯卡爾算法生成樹最小生成樹頂點(diǎn)ßà頂點(diǎn)Dijkstra 迪杰斯特拉 單源點(diǎn)à其它頂點(diǎn)Floyd 弗洛伊德：用鄰接矩陣計(jì)算最短路徑拓?fù)渑判颍篈OV網(wǎng)應(yīng) 用關(guān)鍵路徑：AOE網(wǎng)用鄰接鏈表存儲(chǔ)：從小編號(hào)開始遍歷1、強(qiáng)連通分量是有向圖的極大連通子圖。連通分量指的是無向圖中的極大連通子圖。2、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的2倍。3、最短路徑的生成斯算法可用迪杰斯特拉算法。4、有向圖的鄰接表表示適用于求頂點(diǎn)的出度，逆鄰接鏈表適用于求頂點(diǎn)的入度。5、最小生成樹只能是帶權(quán)連通圖的運(yùn)算。6、一個(gè)有向無環(huán)圖的拓

12、撲排序的序列是不唯一的。7、一個(gè)圖的鄰接矩陣表示法是惟一的。一個(gè)圖的鄰接表表示法是不惟一的。8、若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。若一個(gè)有向圖中存在回路，則該圖的拓?fù)溆行蛐蛄胁淮嬖凇?、用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)無關(guān)，與頂點(diǎn)數(shù)有關(guān)。10、有n個(gè)頂點(diǎn)的無向圖, 采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。11、鄰接表中邊結(jié)點(diǎn)數(shù)目為奇數(shù)的圖一定是有向圖。12、不同的求最小生成樹的方法最后得到的生成樹是不一定相同的。13、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的2倍。14、在一個(gè)有向圖的拓樸序列中，若頂點(diǎn)a在頂點(diǎn)

13、b之前，則圖中必有一條弧<a,b>，這是不正確的說法。15、關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)的最長路徑。任意AOE網(wǎng)的關(guān)鍵路徑是不唯一的。16、有向圖中一個(gè)頂點(diǎn)的度應(yīng)該是它的出度與人度之和。17、n個(gè)頂點(diǎn)的無向圖最多有n(n-1)/2條邊，n個(gè)頂點(diǎn)的有向圖最多有n(n-1)條邊。18、在無向圖中，若頂點(diǎn)i到頂點(diǎn)j有路徑，則這兩個(gè)頂點(diǎn)之間是連通的。19、連通圖的最小生成樹是不惟一的。20、鄰接矩陣主要用來表示頂點(diǎn)之間的關(guān)系。若表示某圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。21、若表示某圖的鄰接矩陣中出現(xiàn)了全零行或者全零列，則該圖一定是非連通圖或非強(qiáng)連通圖22、無向圖的鄰接表中邊結(jié)點(diǎn)數(shù)目一

14、定為偶數(shù)。23、最短路徑一定是簡單路徑。24、不能對(duì)強(qiáng)連通圖進(jìn)行拓?fù)渑判颉?5、存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，因此可以只存儲(chǔ)鄰接矩陣的下（上）三角部分。26、在AOE網(wǎng)絡(luò)中可以有多條關(guān)鍵路徑。27、用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）的關(guān)鍵路徑是指從源點(diǎn)到終點(diǎn)的路徑長度最長的路徑。28、對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點(diǎn)。29、圖中各個(gè)頂點(diǎn)的編號(hào)是人為的，不是它本身固有的，因此可以根據(jù)需要進(jìn)行改變。30、連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)31、圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的結(jié)點(diǎn)32、有向圖的遍歷可采用廣度優(yōu)先搜索方法33、在AOE網(wǎng)中，減小任

15、一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減少，是錯(cuò)誤的。34、AOE網(wǎng)工程工期為關(guān)鍵路徑上的權(quán)之和35、在關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必須在關(guān)鍵路徑上36、任何一個(gè)關(guān)鍵活動(dòng)提前完成，不一定將使整個(gè)工程提前完成37、求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的38、一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同39、關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上40、在AOV網(wǎng)中弧表示優(yōu)先關(guān)系，是一種有向無環(huán)圖，AOV網(wǎng)拓?fù)渑判虻慕Y(jié)果不惟一確定41、最小生成樹可以用普里姆、克魯斯卡爾算法。、42、表示圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣、鄰接表 、鄰接多重表 ）。43、圖的深度優(yōu)先搜索算法類似于二叉樹的（前序遍歷

16、 ）。44、具有n個(gè)頂點(diǎn)、e條邊的無向圖采用鄰接矩陣存儲(chǔ)方法。則鄰接矩陣的大小為（n×n）。45、圖的廣度優(yōu)先搜索算法類似于二叉樹的 按層次遍歷46、一個(gè)連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖47、任何一個(gè)連通圖的生成樹一棵或多棵48鄰接表中邊結(jié)點(diǎn)數(shù)目為偶數(shù)的圖可能是無向圖，也可能是有向圖。第八章 查找 復(fù)習(xí)查找概念：查找的定義：確定一個(gè)已給的數(shù)據(jù)是否出現(xiàn)在某個(gè)數(shù)據(jù)表中。MSL：最大查找長度：最多比較次數(shù)；ASL：平均查找長度：平均比較次數(shù)；順序表：記錄的邏輯順序與其在計(jì)算機(jī)存儲(chǔ)器中存儲(chǔ)的順序一致的表。順序查找：O(n)二分查找（折半查找）：條件有序表 ，O(log2n)

17、靜態(tài)查找（線性表的查找）二叉排序樹的查找平衡二叉樹：平衡因子 平衡技術(shù)方法動(dòng)態(tài)查找哈希函數(shù)哈希表(散列技術(shù))解決沖突方法開放地址平方取中除留余數(shù)線性探測(cè)線性補(bǔ)償探測(cè)隨機(jī)探測(cè)鏈地址法： 外鏈地址法1、常用處理沖突的兩類方法是開放地址法和拉鏈法。2、如在查找的同時(shí)對(duì)表修改，則相應(yīng)的表稱動(dòng)態(tài)查找表。3、二叉平衡樹又稱AVL樹。4、二分查找法要求待查表的關(guān)鍵字的值必須有序。5、哈希法是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。6、對(duì)有序表而言，采用二分查找總比采用順序查找法速度快。7、一般來說，用哈希函數(shù)得到的地址，沖突不可能避免，只能盡可能減少。8、在二叉排序樹中插入新結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，僅需改動(dòng)

18、某個(gè)結(jié)點(diǎn)的指針，使它由空變?yōu)榉强占纯伞?、只要按值有序排列的線性表采用順序存儲(chǔ)結(jié)構(gòu)就可以采用折半查找方法。 10、分塊查找過程是首先查找索引表，然后再到相應(yīng)的塊中具體查找記錄。 11、在散列文件中進(jìn)行查找不涉及關(guān)鍵字的比較。 12、散列沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)了多個(gè)不同的散列地址。 13、在采用鏈地址法處理沖突的散列表中，散列函數(shù)值相同的關(guān)鍵字是鏈接在同一個(gè)鏈表中的。 14、裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。15、散列表的查找效率主要取決于處理沖突方法 、 散列函數(shù) 。16、二分查找要求結(jié)點(diǎn)有序、順序存儲(chǔ)17、散列函數(shù)的構(gòu)造方法有直接定址法、數(shù)字分析法、平方取中法、除留

19、余數(shù)法等幾種。 18、按存儲(chǔ)器不同，可以將排序方法分為內(nèi)部排序、外部排序。19、對(duì)于折半搜索所對(duì)應(yīng)的判定樹，它既是一棵二叉搜索樹、 理想平衡樹的樹.20、散列查找是由鍵值（ 散列函數(shù)值）確定散列表中的位置，并進(jìn)行存儲(chǔ)或查找。21、采用二分查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（ O(log2n )）。22、采用順序查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（ （n+1）/2 ）。23、通常把查找過程中對(duì)關(guān)鍵字需要執(zhí)行的（ ASL ）作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。24、在表長是N的順序表中，實(shí)施順序查找，在查找不成功時(shí)，與關(guān)鍵字比較的次數(shù)（N+1 ）。25、如果要求一個(gè)線性

20、表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則采用（分塊 ）查找方法。26、線性表必須是（ 用向量存儲(chǔ)的有序表），才能進(jìn)行二分查找。27、設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最小比較次數(shù)是（1 ）。27、（ 散列查找）不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法。28、采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為（(n+1)/2）29、哈希表長m14，哈希函數(shù)H（key）key11。表中已有4個(gè)結(jié)點(diǎn)： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 ,其余地址為空 如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是(9 ).

21、30、采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分( 25)個(gè)結(jié)點(diǎn)最佳。31、查找表是以（ 集合 ）為查找結(jié)構(gòu)的。 32、在表長是N的順序表中，實(shí)施順序查找，在查找不成功時(shí)，與關(guān)鍵字比較的次數(shù)（ N+1 ）。33、對(duì)于長度為n的順序存儲(chǔ)的有序表，若采用折半查找，則對(duì)所有元素的查找長度中最大的為(log2(n+1) )的值向上取整。 34、對(duì)于長度為n的順序存儲(chǔ)的有序表，若采用折半查找，則對(duì)所有元素的查找長度中最大的為(log2n)的值的向下取整加1。 35、對(duì)于長度為9的順序存儲(chǔ)的有序表，若采用折半查找在等概率情況下查找成功

22、的平均查找長度為 ( 25 )除以9。 36、對(duì)于長度為18的順序存儲(chǔ)的有序表，若采用折半查找，則查找第15個(gè)元素的查找長度為( 4 )。37、在一棵高度為h的具有n個(gè)元素的二叉查找樹中，查找一個(gè)元素的最大查找長度為( h+1 )。38、向具有n個(gè)結(jié)點(diǎn)的二叉查找樹中插入一個(gè)元素的時(shí)間復(fù)雜度大致為( O(log2n ) )。39、從具有n個(gè)結(jié)點(diǎn)的二叉查找樹中查找一個(gè)元素時(shí)，在等概率情況下進(jìn)行成功查找的時(shí)間復(fù)雜度大致為(O(log2n) )。40、向一棵AVL樹插入元素時(shí)，可能引起對(duì)最小不平衡子樹的調(diào)整過程，此調(diào)整分為( 4 )種旋轉(zhuǎn)類型。41、散列函數(shù)應(yīng)該有這樣的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（同等）概率

23、取其值域范圍內(nèi)的每一個(gè)值。42、散列地址空間為0m-1，k為表項(xiàng)的關(guān)鍵碼，散列函數(shù)采用除留余數(shù)法，即Hash(k)=k%p。為了減少發(fā)生沖突的頻率，一般取p為（小于m的最大質(zhì)數(shù)）。43、解決散列法中出現(xiàn)的沖突問題常采用的方法是（ 線性探查法、雙散列法、開散列法）。44、采用線性探查法解決沖突時(shí)所產(chǎn)生的一系列后繼散列地址（可以大于或小于原散列地址 ）。45、200 個(gè)元素采用二分查找時(shí)，最大的比較次數(shù)是（ 8 ）。 46、為了有效利用散列查找技術(shù)，需要解決問題是找一個(gè)好的散列函數(shù)、設(shè)計(jì)有效的解決沖突的方法 47、散列表的地址區(qū)間為 0 一 16 ，散列函數(shù)為 Hl ( K ) = K % 17

24、，采用線性探測(cè)法解決沖突，將關(guān)鍵字序列 26 , 25 , 72 , 38 , 8 , 18 , 59 依次存儲(chǔ)到散列表中。,元素 59 存放在散列表中的地址為（ 11 ）。 48、具有 4 層結(jié)點(diǎn)的二叉平衡樹中結(jié)點(diǎn)個(gè)數(shù)至少有（ 7 ）。49、散列查找是由鍵值（散列函數(shù)值 ）確定散列表中的位置，并進(jìn)行存儲(chǔ)或查找。第九章 排序 復(fù)習(xí)內(nèi)部排序插入排序排序的定義：把一批雜亂無章的數(shù)據(jù)序列重新排列成有序序列的過程。直接插入排序：O(n2)穩(wěn)定折半插入排序：O(n2)穩(wěn)定希爾排序：O(n1.3)不穩(wěn)定交換排序冒泡排序：O(n2)穩(wěn)定快速排序：O(nlog2n)不穩(wěn)定選擇排序簡單選擇排序：O(n2)穩(wěn)定堆

25、排序：O(nlog2n)不穩(wěn)定歸并排序：二路歸并排序：O(nlog2n)穩(wěn)定1、直接插入排序的方法要求被排序的數(shù)據(jù)必須是順序存儲(chǔ)。2、監(jiān)視哨的作用是在查找循環(huán)條件中用來監(jiān)視下標(biāo)變量是否越界。3、具有相同的關(guān)鍵字的紀(jì)錄之間的相對(duì)次序保持不變的方法是穩(wěn)定的，否則是不穩(wěn)定的。4、堆排序是一種選擇排序。5、每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此中插入的方法叫做插入排序。6、對(duì)于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下需要的時(shí)間為O(n*n)。7、堆是一個(gè)鍵值序列k1,k2, kn,對(duì)i=1,2,|_n/2_|,滿足( kik2i且kik2i+1(2i+1n)8、在順序表 ( 3

26、, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為(4 ) 9、當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。10、平衡的二叉排序樹的任何子樹都是平衡的二叉排序樹。 11、一棵 m 階 B 樹中每個(gè)結(jié)點(diǎn)最多有 m-1 個(gè)關(guān)鍵碼，最少有 ém/2ù-1個(gè)關(guān)鍵碼。12、在索引順序結(jié)構(gòu)的搜索中，對(duì)索引表既可以采取順序搜索，也可以采用折半搜索。13、堆排序是一種不穩(wěn)定的排序算法。14、快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終位置上。15、對(duì) n 個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是 O ( nlog2n)。16、具有相同的關(guān)鍵字的記錄之間的相對(duì)次序保持不變的方法是穩(wěn)定的，否則是不穩(wěn)定的。17、直接選擇排序是一種不穩(wěn)定的排序方法。18、當(dāng)輸入序列已經(jīng)基本有序時(shí)，起泡排序需要比較關(guān)鍵碼的次數(shù)，比快速排序還要