數(shù)據(jù)結(jié)構(gòu)知識點簡潔版

1、個人收集整理-ZQ第一章概論數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理地信息地載體數(shù)據(jù)元素是數(shù)據(jù)地基本單位，可以由若干個數(shù)據(jù)項組成數(shù)據(jù)項是具有獨立含義地最小標(biāo)識單位.數(shù)據(jù)結(jié)構(gòu)地定義：邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨立于計算機線性結(jié)構(gòu)：一對一關(guān)系.線性結(jié)構(gòu)：多對多關(guān)系.存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機語言地實現(xiàn).順序存儲結(jié)構(gòu)：如數(shù)組.鏈?zhǔn)酱鎯Y(jié)構(gòu)：如鏈表.索引存儲結(jié)構(gòu)：稠密索引：每個結(jié)點都有索引項.稀疏索引：每組結(jié)點都有索引項.散列存儲結(jié)構(gòu)：如散列表.數(shù)據(jù)運算.對數(shù)據(jù)地操作.定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算集合常用地有：檢索、插入、刪除、更新、排序.數(shù)據(jù)類型：是一個值地集合以及在這些值上

2、定義地一組操作地總稱結(jié)構(gòu)類型：由用戶借助于描述機制定義，是導(dǎo)出類型抽象數(shù)據(jù)類型：是抽象數(shù)據(jù)地組織和與之地操作.相當(dāng)于在概念層上描述問題.優(yōu)點是將數(shù)據(jù)和操作封裝在一起實現(xiàn)了信息隱藏程序設(shè)計地實質(zhì)是對實際問題選擇一種好地數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好地算法算法取決于數(shù)據(jù)結(jié)構(gòu).算法是一個良定義地計算過程，以一個或多個值輸入，并以一個或多個值輸出評價算法地好壞地因素：算法是正確地；執(zhí)行算法地時間；執(zhí)行算法地存儲空間（主要是輔助存儲空間）；算法易于理解、編碼、調(diào)試.時間復(fù)雜度：是某個算法地時間耗費，它是該算法所求解問題規(guī)模地函數(shù).漸近時間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度地數(shù)量級.評價一個算法地

3、時間性能時，主要標(biāo)準(zhǔn)就是算法地漸近時間復(fù)雜度.文檔來自于網(wǎng)絡(luò)搜索算法中語句地頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素地取值相關(guān)時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階（）、對數(shù)階（）、線性階（）、線性對數(shù)階（）、平方階（人）、立方階（人）、次方階（人）、指數(shù)階（人）.文檔來自于網(wǎng)絡(luò)搜索空間復(fù)雜度：是某個算法地空間耗費，它是該算法所求解問題規(guī)模地函數(shù)算法地時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度第二章線性表線性表是由沖數(shù)據(jù)元素組成地有限序列.是空表；非空表，只能有一個開始結(jié)點，有且只能有一個終端結(jié)點線性表上定義地基本運算：構(gòu)造空表：（）求表長：（）取結(jié)點：（，）文檔來自于網(wǎng)絡(luò)搜索查找：（，）插入

4、：（，）刪除：（，）文檔來自于網(wǎng)絡(luò)搜索順序表是按線性表地邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)地存儲單元中在存儲單元中地各元素地物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關(guān)系是一致地.地址計算：（）（）（）*；（首地址為）在順序表中實現(xiàn)地基本運算：插入：平均移動結(jié)點次數(shù)為；平均時間復(fù)雜度均為（）.刪除：平均移動結(jié)點次數(shù)為（）；平均時間復(fù)雜度均為（）.個人收集整理-ZQ線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點地邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點間地邏輯關(guān)系，在存儲每個結(jié)點值地同時，還存儲了其后繼結(jié)點地地址信息（即指針或鏈）.這兩部分信息組成鏈表中地結(jié)點結(jié)構(gòu).一個單鏈表由頭指針地名字來命名.文檔來自于網(wǎng)絡(luò)搜索單鏈

5、表運算：建立單鏈表頭插法：>生成地順序與輸入順序相反.平均時間復(fù)雜度均為（）.文檔來自于網(wǎng)絡(luò)搜索尾插法：；（）；>平均時間復(fù)雜度均為（）文檔來自于網(wǎng)絡(luò)搜索加頭結(jié)點地算法：對開始結(jié)點地操作無需特殊處理，統(tǒng)一了空表和非空表查找按序號：與查找位置有關(guān)，平均時間復(fù)雜度均為（）.按值：與輸入實例有關(guān)，平均時間復(fù)雜度均為（）.插入運算：（，）；>>>平均時間復(fù)雜度均為（）文檔來自于網(wǎng)絡(luò)搜索刪除運算：（，）；>；>>；（）；平均時間復(fù)雜度均為（）文檔來自于網(wǎng)絡(luò)搜索單循環(huán)鏈表是一種首尾相接地單鏈表，終端結(jié)點地指針域指向開始結(jié)點或頭結(jié)點鏈表終止條件是以指針等于頭指

6、針或尾指針.采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表優(yōu)點是查找頭指針和尾指針地時間都是（），不用遍歷整個鏈表雙鏈表就是雙向鏈表，就是在單鏈表地每個結(jié)點里再增加一個指向其直接前趨地指針域，形成兩條不同方向地鏈.由頭指針惟一確定.文檔來自于網(wǎng)絡(luò)搜索雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表雙鏈表上地插入和刪除時間復(fù)雜度均為（）.順序表和鏈表地比較：基于空間：順序表地存儲空間是靜態(tài)分配，存儲密度為；適于線性表事先確定其大小時采用鏈表地存儲空間是動態(tài)分配，存儲密度<適于線性表長度變化大時采用基于時間：順序表是隨機存儲結(jié)構(gòu)，當(dāng)線性表地操作主要是查找時，宜采用以插入和刪除操作為主地線性表宜采

7、用鏈表做存儲結(jié)構(gòu)若插入和刪除主要發(fā)生在表地首尾兩端，則宜采用尾指針表示地單循環(huán)鏈表第三章棧和隊列棧（）是僅限制在表地一端進(jìn)行插入和刪除運算地線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底.表中無元素時為空棧.棧地修改是按后進(jìn)先出地原則進(jìn)行地，我們又稱棧為表（）.通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu).文檔來自于網(wǎng)絡(luò)搜索棧地基本運算有六種：構(gòu)造空棧：（）判?？眨海ǎ┡袟M：（）文檔來自于網(wǎng)絡(luò)搜索進(jìn)棧：（，）退棧：（）取棧頂元素：（）文檔來自于網(wǎng)絡(luò)搜索在順序棧中有土溢”和下溢”地現(xiàn)象.上溢”是棧頂指針指出棧地外面是出錯狀態(tài).下溢”可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移地條件.文檔來自于網(wǎng)絡(luò)搜索順序棧中

8、地基本操作有六種：構(gòu)造空棧判?？张袟M進(jìn)棧退棧取棧頂元素鏈棧則沒有上溢地限制，因此進(jìn)棧不要判棧滿鏈棧不需要在頭部附加頭結(jié)點，只要有鏈表地頭指針就可以了鏈棧中地基本操作有五種：構(gòu)造空棧判?？者M(jìn)棧退取棧頂元素隊列（）是一種運算受限地線性表，插入在表地一端進(jìn)行，而刪除在表地另一端進(jìn)行，允許刪除地一端稱為隊頭（），允許插入地一端稱為隊尾（），隊列地操作原則是先進(jìn)先出地，又稱作表（）.隊列也有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu).文檔來自于網(wǎng)絡(luò)搜索隊列地基本運算有六種：置空隊：（）判隊空：（）判隊滿：（）文檔來自于網(wǎng)絡(luò)搜索人隊：（，）出隊：（）取隊頭元素：（）文檔來自于網(wǎng)絡(luò)搜索個人收集整理-ZQ順序隊列地限上

9、溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間這時整個向量空間及隊列是空地卻產(chǎn)生了土溢”現(xiàn)象.為了克服假上溢”現(xiàn)象引入循環(huán)向量地概念，是把向量空間形成一個頭尾相接地環(huán)形，這時隊列稱循環(huán)隊列判定循環(huán)隊列是空還是滿，方法有三種：文檔來自于網(wǎng)絡(luò)搜索一種是另設(shè)一個布爾變量來判斷；第二種是少用一個元素空間，入隊時先測試（）？滿：空；第三種就是用一個計數(shù)器記錄隊列中地元素地總數(shù)隊列地鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列，一個鏈隊列就是一個操作受限地單鏈表.為了便于在表尾進(jìn)行插入（入隊）地操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定.鏈隊列不存在隊滿和上溢地問題.在鏈隊列地出隊算法中，要注意當(dāng)

10、原隊中只有一個結(jié)點時，出隊后要同進(jìn)修改頭尾指針并使隊列變空.文檔來自于網(wǎng)絡(luò)搜索第四章串串是零個或多個字符組成地有限序列.空串：是指長度為零地串，也就是串中不包含任何字符（結(jié)點）空白串：指串中包含一個或多個空格字符地串在一個串中任意個連續(xù)字符組成地子序列稱為該串地子串，包含子串地串就稱為主串子串在主串中地序號就是指子串在主串中首次出現(xiàn)地位置空串是任意串地子串，任意串是自身地子串串分為兩種：串常量在程序中只能引用不能改變；串變量地值可以改變串地基本運算有：求串長（*）串復(fù)制（*,*）文檔來自于網(wǎng)絡(luò)搜索串聯(lián)接（*,*）串比較（*,*）字符定位（*,）文檔來自于網(wǎng)絡(luò)搜索串是特殊地線性表（結(jié)點是字符），

11、所以串地存儲結(jié)構(gòu)與線性表地存儲結(jié)構(gòu)類似串地順序存儲結(jié)構(gòu)簡稱為順序串.順序串又可按存儲分配地不同分為：靜態(tài)存儲分配：直接用定長地字符數(shù)組來定義.優(yōu)點是涉及串長地操作速度快，但不適合插入、鏈接操作.動態(tài)存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串地長度分配存儲單元串地鏈?zhǔn)酱鎯褪怯脝捂湵淼胤绞酱鎯Υ?，串地這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串鏈串與單鏈表地差異只是它地結(jié)點數(shù)據(jù)域為單個字符為了解決存儲密度”低地狀況，可以讓一個結(jié)點存儲多個字符，即結(jié)點地大小順序串上子串定位地運算：又稱串地模式匹配”或串匹配”，是在主串中查找出子串出現(xiàn)地位置.在串匹配中，將主串稱為目標(biāo)（串），子串稱為模式（串）這是比

12、較容易理解地，串匹配問題就是找出給定模式串在給定目標(biāo)串中首次出現(xiàn)地有效位移或者是全部有效位移.最壞地情況下時間復(fù)雜度是（），假如與同階地話則它是（人）.文檔來自于網(wǎng)絡(luò)搜索鏈串上地子串定位運算位移是結(jié)點地址而不是整數(shù)第五章多維數(shù)組數(shù)組一般用順序存儲地方式表示.存儲地方式有：行優(yōu)先順序，也就是把數(shù)組逐行依次排列.、列優(yōu)先順序，就是把數(shù)組逐列依次排列.文檔來自于網(wǎng)絡(luò)搜索地址地計算方法：按行優(yōu)先順序排列地數(shù)組：（）（）（）*（）*.文檔來自于網(wǎng)絡(luò)搜索按列優(yōu)先順序排列地數(shù)組：（）（）（）*（）*.矩陣地壓縮存儲：為多個相同地非零元素分配一個存儲空間；對零元素不分配空間特殊矩陣地概念：所謂特殊矩陣是指非零

13、元素或零元素分布有一定規(guī)律地矩陣稀疏矩陣地概念：一個矩陣中若其非零元素地個數(shù)遠(yuǎn)遠(yuǎn)小于零元素地個數(shù)，則該矩陣稱為稀疏矩陣特殊矩陣地類型：對稱矩陣：滿足（）（）.個人收集整理-ZQ元素總數(shù)（）（，），（，），（）（）（*（）*.文檔來自于網(wǎng)絡(luò)搜索三角矩陣：上三角陣：*（）,（）（）*.文檔來自于網(wǎng)絡(luò)搜索下三角陣：*（）,（）（）*.對角矩陣：，（）（）*.稀疏矩陣地壓縮存儲方式用三元組表把非零元素地值和它所在地行號列號做為一個結(jié)點存放在一起，用這些結(jié)點組成地一個線性表來表示.但這種壓縮存儲方式將失去隨機存儲功能.文檔來自于網(wǎng)絡(luò)搜索加入行表記錄每行地非零元素在三元組表中地起始位置，即帶行表地三元組表

14、.第六章樹樹是個結(jié)點地有限集合，非空時必須滿足：只有一個稱為根地結(jié)點；其余結(jié)點形成個不相交地子集，并稱根地子樹.文檔來自于網(wǎng)絡(luò)搜索根是開始結(jié)點；結(jié)點地子樹數(shù)稱度；度為地結(jié)點稱葉子（終端結(jié)點）；度不為地結(jié)點稱分支結(jié)點（非終端結(jié)點）；除根外地分支結(jié)點稱內(nèi)部結(jié)點；有序樹是子樹有左，右之分地樹；無序樹是子樹沒有左，右之分地樹；森林是個互不相交地樹地集合；樹地四種不同表示方法：樹形表示法；嵌套集合表示法；凹入表示法廣義表表示法.二叉樹地定義：是珞結(jié)點地有限集，它是空集（）或由一個根結(jié)點及兩棵互不相交地分別稱作這個根地左子樹和右子樹地二叉樹組成.文檔來自于網(wǎng)絡(luò)搜索二叉樹不是樹地特殊情形，與度數(shù)為地有序樹不

15、同二叉樹地個重要性質(zhì)：二叉樹上第層上地結(jié)點數(shù)目最多為人（）（書.；深度為地二叉樹至多有（人）個結(jié)點（分；在任意一棵二叉樹中，若終端結(jié)點地個數(shù)為，度為地結(jié)點數(shù)為，則；具有個結(jié)點地完全二叉樹地深度為（）.滿二叉樹是一棵深度為，結(jié)點數(shù)為（人）地二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點；二叉樹地順序存儲結(jié)構(gòu)就是把二叉樹地所有結(jié)點按照層次順序存儲到連續(xù)地存儲單元中.（存儲前先將其畫成完全二叉樹）文檔來自于網(wǎng)絡(luò)搜索樹地存儲結(jié)構(gòu)多用地是鏈?zhǔn)酱鎯?地結(jié)構(gòu)為，把所有類型地結(jié)點，加上一個指向根結(jié)點地型頭指針就構(gòu)成了二叉樹地鏈?zhǔn)酱鎯Y(jié)構(gòu)，稱為二叉鏈表.文檔來自于網(wǎng)絡(luò)搜索它就是由根指針唯一確定地.共有

16、個指針域，個空指針.根據(jù)訪問結(jié)點地次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）.文檔來自于網(wǎng)絡(luò)搜索時間復(fù)雜度為（）.利用二叉鏈表中地個空指針域來存放指向某種遍歷次序下地前趨結(jié)點和后繼結(jié)點地指針，這些附加地指針就稱為線索”，加上線索地二叉鏈表就稱為線索鏈表.線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結(jié)點地前序前趨和后序后繼并沒有什么作用.文檔來自于網(wǎng)絡(luò)搜索樹和森林及二叉樹地車t換是唯一對應(yīng)地轉(zhuǎn)換方法：樹變二叉樹：兄弟相連，保留長子地連線.二叉樹變樹：結(jié)點地右孩子與其雙親連.森林變二叉樹：樹變二叉樹，各個樹地根相連樹地存儲結(jié)構(gòu)

17、：有雙親鏈表表示法：結(jié)點，對于求指定結(jié)點地雙親或祖先十分方便，但不適于求指定結(jié)個人收集整理-ZQ點地孩子及后代.文檔來自于網(wǎng)絡(luò)搜索孩子鏈表表示法：為樹中每個結(jié)點設(shè)置一個孩子鏈表，并將存放在一個向量中.文檔來自于網(wǎng)絡(luò)搜索雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合孩子兄弟鏈表表示法：結(jié)點結(jié)構(gòu)，附加兩個分別指向該結(jié)點地最左孩子和右鄰兄弟地指針域.文檔來自于網(wǎng)絡(luò)搜索樹地前序遍歷與相對應(yīng)地二叉樹地前序遍歷一致；樹地后序遍歷與相對應(yīng)地二叉樹地中序遍歷一致樹地帶權(quán)路徑長度是樹中所有葉結(jié)點地帶權(quán)路徑長度之和樹地帶權(quán)路徑長度最小地二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）.在葉子地權(quán)值相同地二叉樹中，完全二叉樹地路

18、徑長度最短哈夫曼樹有個葉結(jié)點，共有個結(jié)點，沒有度為地結(jié)點，這類樹又稱為嚴(yán)格二叉樹變長編碼技術(shù)可以使頻度高地字符編碼短，而頻度低地字符編碼長，但是變長編碼可能使解碼產(chǎn)生二義性如、這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符地編碼都不是其他字符編碼地前綴，這種碼稱為前綴碼（其實是非前綴碼）.文檔來自于網(wǎng)絡(luò)搜索哈夫曼樹地應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布地最優(yōu)前綴碼.哈夫曼編碼地構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼，右路徑上寫代碼，然后從上到下到葉結(jié)點地相應(yīng)路徑上地代碼地序列就是該結(jié)點地最優(yōu)前綴碼.文檔來自于網(wǎng)絡(luò)搜索第七章圖圖地

19、邏輯結(jié)構(gòu)特征就是其結(jié)點（頂點）地前趨和后繼地個數(shù)都是沒有限制地，即任意兩個結(jié)點之間之間都可能相關(guān).文檔來自于網(wǎng)絡(luò)搜索圖（，），是頂點地有窮非空集合，是頂點偶對地有窮集有向圖：每條邊有方向；無向圖：每條邊沒有方向有向完全圖：具有*（）條邊地有向圖；無向完全圖：具有*（）條邊地?zé)o向圖；有根圖：有一個頂點有路徑到達(dá)其它頂點地有向圖；簡單路徑：是經(jīng)過頂點不同地路徑；簡單回路是開始和終端重地簡單路徑；網(wǎng)絡(luò)：是帶權(quán)地圖.圖地存儲結(jié)構(gòu)：鄰接矩陣表示法：用一個階方陣來表示圖地結(jié)構(gòu)是唯一地，適合稠密圖無向圖：鄰接矩陣是對稱地.有向圖：行是出度，列是入度建立鄰接矩陣算法地時間是（人），其時間復(fù)雜度為（人）鄰接表表

20、示法：用頂點表和鄰接表構(gòu)成不是唯一地，適合稀疏圖頂點表結(jié)構(gòu)，指針域存放鄰接表頭指針.鄰接表：用頭指針確定.無向圖稱邊表；有向圖又分出邊表和逆鄰接表；鄰接表結(jié)點結(jié)構(gòu)為，時間復(fù)雜度為（）.，空間復(fù)雜度為（）.圖地遍歷：深度優(yōu)先遍歷：借助于鄰接矩陣地列.使用棧保存已訪問結(jié)點.廣度優(yōu)先遍歷：借助于鄰接矩陣地行.使用隊列保存已訪問結(jié)點.生成樹地定義：若從圖地某個頂點出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點，則遍歷時經(jīng)過地邊和圖地所有頂點構(gòu)成地子圖稱作該圖地生成樹.文檔來自于網(wǎng)絡(luò)搜索最小生成樹：圖地生成樹不唯一，從不同地頂點出發(fā)可得到不同地生成樹，把權(quán)值最小地生成樹稱為最小生成樹（）.文檔來自于網(wǎng)絡(luò)搜索構(gòu)造最小

21、生成樹地算法：算法地時間復(fù)雜度為（人）與邊數(shù)無關(guān)適于稠密圖.個人收集整理-ZQ算法地時間復(fù)雜度為（），主要取決于邊數(shù)，較適合于稀疏圖最短路徑地算法：算法，時間復(fù)雜度為（人）.類似于算法.拓?fù)渑判颍菏菍⒂邢驘o環(huán)圖中所有頂點排成一個線性序列，若<,>e（）,則在線性序列在之前，這種線性序列稱為拓?fù)湫蛄?文檔來自于網(wǎng)絡(luò)搜索拓?fù)渑判蛞灿袃煞N方法：無前趨地頂點優(yōu)先，每次輸出一個無前趨地結(jié)點并刪去此結(jié)點及其出邊，最后得到地序列即拓?fù)湫蛄?無后繼地結(jié)點優(yōu)先：每次輸出一個無后繼地結(jié)點并刪去此結(jié)點及其入邊，最后得到地序列是逆拓?fù)湫蛄?第八章排序記錄中可用某一項來標(biāo)識一個記錄，則稱為關(guān)鍵字項，該數(shù)據(jù)項

22、地值稱為關(guān)鍵字排序是使文件中地記錄按關(guān)鍵字遞增（或遞減）次序排列起來基本操作：比較關(guān)鍵字大??；改變指向記錄地指針或移動記錄存儲結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)經(jīng)過排序后這些具有相同關(guān)鍵字地記錄之間地相對次序保持不變，則稱這種排序方法是穩(wěn)定地，否則排序算法是不穩(wěn)定地.文檔來自于網(wǎng)絡(luò)搜索排序過程中不涉及數(shù)據(jù)地內(nèi)、外存交換則稱之為內(nèi)部排序”（內(nèi)排序），反之，若存在數(shù)據(jù)地內(nèi)外存交換，則稱之為外排序.文檔來自于網(wǎng)絡(luò)搜索內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序評價排序算法好壞地標(biāo)準(zhǔn)主要有兩條：執(zhí)行時間和所需地輔助空間，另外算法地復(fù)雜程序也是要考慮地一個因素.插入排序：直接插

23、入排序：逐個向前插入到合適位置.哨兵（監(jiān)視哨）有兩個作用：作為臨變量存放是在查找循環(huán)中用來監(jiān)視下標(biāo)變量是否越界.直接插入排序是就地地穩(wěn)定排序.時間復(fù)雜度為（人），比較次數(shù)為（）（）；移動次數(shù)為（）（）散列技術(shù)：將結(jié)點按其關(guān)鍵字地散列地址存儲到散列表地過程稱為散列.散列函數(shù)地選擇有兩條標(biāo)準(zhǔn)：簡單和均勻.；文檔來自于網(wǎng)絡(luò)搜索希爾排序：等間隔地數(shù)據(jù)比較并按要求順序排列，最后間隔為希爾排序是就地地不穩(wěn)定排序.時間復(fù)雜度為（人），比較次數(shù)為（人）；移動次數(shù)為（人）；交換排序：冒泡排序：自下向上確定最輕地一個.文檔來自于網(wǎng)絡(luò)搜索自上向下確定最重地一個.囪下向上確定最輕地一個，后自上向下確定最重地一個冒泡排

24、序是就地地穩(wěn)定排序.時間復(fù)雜度為（人），比較次數(shù)為（）；移動次數(shù)為（）；文檔來自于網(wǎng)絡(luò)搜索快速排序：以第一個元素為參考基準(zhǔn)，設(shè)定、動兩個指針，發(fā)生交換后指針交換位置，直到指針重合.重復(fù)直到排序完成.文檔來自于網(wǎng)絡(luò)搜索快速排序是非就地地不穩(wěn)定排序.時間復(fù)雜度為（），比較次數(shù)為（）；選擇排序：文檔來自于網(wǎng)絡(luò)搜索直接選擇排序：選擇最小地放在比較區(qū)前.直接選擇排序就地地不穩(wěn)定排序.時間復(fù)雜度為（人）.比較次數(shù)為（）；堆排序建堆：按層次將數(shù)據(jù)填入完全二叉樹，從（）處向前逐個調(diào)整位置然后將樹根與最后一個葉子交換值并斷開與樹地連接并重建堆，直到全斷開堆排序是就地不穩(wěn)定地排序，時間復(fù)雜度為（），不適宜于記錄數(shù)

25、較少地文件歸并排序：先兩個一組排序，形成（）組，再將兩組并一組，直到剩下一組為止歸并排序是非就地穩(wěn)定排序，時間復(fù)雜度是（），分配排序：箱排序：按關(guān)鍵字地取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱箱排序地平均時間復(fù)雜度是線性地（）.基數(shù)排序：從低位到高位依次對關(guān)鍵字進(jìn)行箱排序.6/8個人收集整理-ZQ基數(shù)排序是非就穩(wěn)定地排序，時間復(fù)雜度是（*）.各種排序方法地比較和選擇：待排序地記錄數(shù)目；較大地要用時間復(fù)雜度為（）地排序方法；文檔來自于網(wǎng)絡(luò)搜索記錄地大?。ㄒ?guī)模）；記錄大最好用鏈表作為存儲結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實現(xiàn)；關(guān)鍵字地結(jié)構(gòu)及其初始狀態(tài)；對穩(wěn)定性地要求；語言工具地條件；

26、存儲結(jié)構(gòu)；時間和輔助空間復(fù)雜度.第九章查找查找地同時對表做修改操作（如插入或刪除）則相應(yīng)地表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表.衡量查找算法效率優(yōu)劣地標(biāo)準(zhǔn)是在查找過程中對關(guān)鍵字需要執(zhí)行地平均比較次數(shù)（即平均查找長度）.線性表查找地方法：順序查找：逐個查找，（）；文檔來自于網(wǎng)絡(luò)搜索二分查找：取中點（）比較，若小就比左區(qū)間，大就比右區(qū)間.用二叉判定樹表示.（匯（每層結(jié)點數(shù)*層數(shù)）.文檔來自于網(wǎng)絡(luò)搜索分塊查找.要求分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中地最大關(guān)鍵字及其位置建立有序索引表.文檔來自于網(wǎng)絡(luò)搜索二叉排序樹（）定義是：二叉排序樹是空樹或者滿足如下性質(zhì)地二叉樹：若它地左子樹

27、非空，則左子樹上所有結(jié)點地值均小于根結(jié)點地值；若它地右子樹非空，則右子樹上所有結(jié)點地值均大于根結(jié)點地值；左、右子樹本身又是一棵二叉排序樹.二叉排序樹地插入、建立、刪除地算法平均時間性能是（）.二叉排序樹地刪除操作可分三種情況進(jìn)行處理：*是葉子，則直接刪除*,即將*地雙親*中指向*地指針域置空即可.*只有一個孩子*,此時只需將*和*地雙親直接連接就可刪去*.*有兩個孩子，則先將*結(jié)點地中序后繼結(jié)點地數(shù)據(jù)到*,刪除中序后繼結(jié)點.文檔來自于網(wǎng)絡(luò)搜索關(guān)于樹（多路平衡查找樹）.它適合在磁盤等直接存取設(shè)備上組織動態(tài)地查找表，是一種外查找算法.建立地方式是從下向上拱起.文檔來自于網(wǎng)絡(luò)搜索常見地散列函數(shù)構(gòu)地造方法：平方取中法：（人）除余法：表長為，相乘取整法：（*（*（*）；隨機數(shù)法：（）.處理沖突地方法：開放定址法：一般形式為（）W哆開放定址