- 相關(guān)推薦
數(shù)據(jù)庫(kù)技術(shù)知識(shí)數(shù)據(jù)結(jié)構(gòu)的算法
對(duì)于將要參加計(jì)算機(jī)等級(jí)考試的考生來(lái)說(shuō)，計(jì)算機(jī)等級(jí)考試的知識(shí)點(diǎn)輔導(dǎo)是非常重要的復(fù)習(xí)資料。以下是小編收集的數(shù)據(jù)庫(kù)技術(shù)知識(shí)數(shù)據(jù)結(jié)構(gòu)的算法，希望大家認(rèn)真閱讀!
1、數(shù)據(jù)：數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位
2、數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算
3、主要的數(shù)據(jù)存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)(邏輯和物理相鄰，存儲(chǔ)密度大)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)：
順序存儲(chǔ)計(jì)算公式 Li=L0+(i-1)×K 順序結(jié)構(gòu)可以進(jìn)行隨機(jī)存取;插人、刪除運(yùn)算會(huì)引起相應(yīng)節(jié)點(diǎn)的大量移動(dòng)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：a、指針域可以有多個(gè)，可以指向空，比比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小
b、邏輯上相鄰的節(jié)點(diǎn)物理上不一定相鄰。 c、插人、刪除等不需要大量移動(dòng)節(jié)點(diǎn)
4、順序表：一般情況下，若長(zhǎng)度為n的順序表，在任何位置插入或刪除的概率相等，元素移動(dòng)的平均次數(shù)為n/2(插入)和(n-1)/2(刪除)。
5、鏈表：線性鏈表(單鏈表和雙向鏈表等等)和非線性鏈表
線性鏈表也稱為單鏈表，其每個(gè)一節(jié)點(diǎn)中只包含一個(gè)指針域，雙鏈表中，每個(gè)節(jié)點(diǎn)中設(shè)置有兩個(gè)指針域。(注意結(jié)點(diǎn)的插入和刪除操作)
6、棧：“后進(jìn)先出”(LIFO)表。棧的應(yīng)用：表達(dá)式求解、二叉樹(shù)對(duì)稱序周游、快速排序算法、遞歸過(guò)程的實(shí)現(xiàn)等
7、隊(duì)列：“先進(jìn)先出”線性表。應(yīng)用：樹(shù)的層次遍歷
8、串：由零個(gè)或多個(gè)字符組成的有限序列。
9、多維數(shù)組的順序存儲(chǔ)：
10、稀疏矩陣的存儲(chǔ)：下三角矩陣順序存儲(chǔ)
其他常見(jiàn)的存儲(chǔ)方法還有三元組法和十字鏈表法
11、廣義表：由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表
12、樹(shù)型結(jié)構(gòu)：非線性結(jié)構(gòu)。常用的樹(shù)型結(jié)構(gòu)有樹(shù)和二叉樹(shù)。
二叉樹(shù)與樹(shù)的區(qū)別：二叉樹(shù)不是樹(shù)的特殊情況，樹(shù)和二叉樹(shù)之間最主要的區(qū)別是：二叉樹(shù)的節(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使在節(jié)點(diǎn)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。
13、樹(shù)(森林)與二叉樹(shù)之間的轉(zhuǎn)換(要會(huì)轉(zhuǎn)換)
14、二叉樹(shù)和樹(shù)的周游(遍歷)
二叉樹(shù)的周游主要有以下3種方式：前序法(NLR)、對(duì)稱序法(LNR)、后序法(LRN)
周游樹(shù)和樹(shù)林：深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。深度優(yōu)先方式又可分為按先根次序和按后根次序周游
樹(shù)與二叉樹(shù)周游之間的對(duì)應(yīng)關(guān)系：按先根次序周游樹(shù)正好與按前序法周游樹(shù)對(duì)應(yīng)的二叉樹(shù)等同，后根次序周游樹(shù)正好與按對(duì)稱序法周游對(duì)應(yīng)的二叉樹(shù)等同
按廣度優(yōu)先方式就是層次次序周游
15、二叉樹(shù)的存儲(chǔ)和線索
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：二叉樹(shù)的llink一rlink法存儲(chǔ)表示
線索二叉樹(shù)：在有n個(gè)節(jié)點(diǎn)的二叉樹(shù)的且llink - rlink法存儲(chǔ)表示中，必定有n+1個(gè)空指針域
16、哈夫曼樹(shù)：一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和WPL。
17、查找：
(1)順序查找：平均查找長(zhǎng)度為(n +1 )/2次，時(shí)間復(fù)雜度為O(n)
(2)二分法查找：線性表節(jié)點(diǎn)必須按關(guān)鍵碼值排序，且線性表是以順序存儲(chǔ)方式存儲(chǔ)的。查找成功比較次數(shù)log2n，查找失敗比較次數(shù)log2n+1
(3)分塊查找：先是塊間查找，然后塊內(nèi)查找。
(4)散列表(哈希表Hash)的存儲(chǔ)和查找：處理沖突的方法：開(kāi)地址法(線性探測(cè)法)、拉鏈法等
負(fù)載因子(裝填因子)=表實(shí)際存儲(chǔ)的結(jié)點(diǎn)個(gè)數(shù)/表的最大能存儲(chǔ)結(jié)點(diǎn)個(gè)數(shù)(即表長(zhǎng))
二叉排序樹(shù)：每個(gè)結(jié)點(diǎn)左子樹(shù)的所有關(guān)鍵碼值都小于該結(jié)點(diǎn)關(guān)鍵碼值，右子樹(shù)所有結(jié)點(diǎn)關(guān)鍵碼值都大于該結(jié)點(diǎn)關(guān)鍵碼值。對(duì)稱周游二叉排序樹(shù)，得到一個(gè)有序序列，時(shí)間復(fù)雜度O(log2n)
B樹(shù)和B+樹(shù)：M階樹(shù)，每個(gè)結(jié)點(diǎn)至多有M-1個(gè)關(guān)鍵碼，至少有M/2(取上界)-1個(gè)關(guān)鍵碼。B樹(shù)適合隨機(jī)查找，不適合順序查找。B+樹(shù)適合順序查找。
18、排序
直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法要了解。
直接選擇排序、希爾排序、快速排序和堆排序是不穩(wěn)定排序，其他排序?yàn)榉�(wěn)定排序
【數(shù)據(jù)庫(kù)技術(shù)知識(shí)數(shù)據(jù)結(jié)構(gòu)的算法】相關(guān)文章：
JavaScript數(shù)據(jù)結(jié)構(gòu)與算法中集合的實(shí)現(xiàn)09-06
JavaScript-JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之圖和圖算法,10-25
關(guān)于Oracle數(shù)據(jù)庫(kù)替代加密算法08-21
手球的相關(guān)技術(shù)知識(shí)07-26
編制安全技術(shù)知識(shí)要點(diǎn)09-08
地鐵施工安全技術(shù)知識(shí)09-08
網(wǎng)絡(luò)技術(shù)知識(shí)題庫(kù)08-08