2014年計(jì)算機(jī)三級(jí)數(shù)據(jù)庫背誦資料：第二章

第二章 數(shù)據(jù)結(jié)構(gòu)算法

　　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á)式求解、二叉樹對(duì)稱序周游、快速排序算法、遞歸過程的實(shí)現(xiàn)等

　　7、隊(duì)列：“先進(jìn)先出”線性表。應(yīng)用：樹的層次遍歷

　　8、串：由零個(gè)或多個(gè)字符組成的有限序列。

　　9、多維數(shù)組的順序存儲(chǔ)：

　　10、稀疏矩陣的存儲(chǔ)：下三角矩陣順序存儲(chǔ)

　　其他常見的存儲(chǔ)方法還有三元組法和十字鏈表法

　　11、廣義表：由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表

　　12、樹型結(jié)構(gòu)：非線性結(jié)構(gòu)。常用的樹型結(jié)構(gòu)有樹和二叉樹。

　　二叉樹與樹的區(qū)別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區(qū)別是：二叉樹的節(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使在節(jié)點(diǎn)只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。

　　13、樹(森林)與二叉樹之間的轉(zhuǎn)換(要會(huì)轉(zhuǎn)換)

　　14、二叉樹和樹的周游(遍歷)

　　二叉樹的周游主要有以下3種方式：前序法(NLR)、對(duì)稱序法(LNR)、后序法(LRN)

　　周游樹和樹林：深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。深度優(yōu)先方式又可分為按先根次序和按后根次序周游

　　樹與二叉樹周游之間的對(duì)應(yīng)關(guān)系：按先根次序周游樹正好與按前序法周游樹對(duì)應(yīng)的二叉樹等同，后根次序周游樹正好與按對(duì)稱序法周游對(duì)應(yīng)的二叉樹等同

　　按廣度優(yōu)先方式就是層次次序周游

　　相關(guān)推薦：

　　2014年計(jì)算機(jī)等考上機(jī)六大注意事項(xiàng)

　　2014年計(jì)算機(jī)三級(jí)數(shù)據(jù)庫技術(shù)重點(diǎn)筆記匯總

　　2014年計(jì)算機(jī)三級(jí)數(shù)據(jù)庫技術(shù)上機(jī)試題及答案匯總