數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱(chēng)節(jié)點(diǎn)（node）或記錄（record）。

數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)項(xiàng)：有獨(dú)立含義的數(shù)據(jù)最小單位，也稱(chēng)域(field)。

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)

????集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。

????線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。

????樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。

????圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。

邏輯結(jié)構(gòu)：抽象反映數(shù)據(jù)元素之間的邏輯關(guān)系。（算法設(shè)計(jì)）

物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。（算法實(shí)現(xiàn)）

存儲(chǔ)結(jié)構(gòu)分為：

????順序存儲(chǔ)結(jié)構(gòu)：借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。

算法：對(duì)特定問(wèn)題求解步驟的一種描述。

算法的五個(gè)重要特性：有窮性，確定性，可行性，輸入和輸出。

算法設(shè)計(jì)的原則或要求：正確性，可讀性，健壯性，效率與低存儲(chǔ)量需求。

衡量算法效率的方法：事后統(tǒng)計(jì)法和事前分析估算法?。

算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同，則可記作：T (n) = O(f(n))，稱(chēng)T (n) 為算法的(漸近)時(shí)間復(fù)雜度??

算法運(yùn)行時(shí)間的衡量準(zhǔn)則：以基本操作在算法中重復(fù)執(zhí)行的次數(shù)。

棧：限定僅在表尾進(jìn)行插入或刪除操作線性表。入棧：插入元素的操作；出棧：刪除棧頂元素的操作。

隊(duì)列：只能在隊(duì)首進(jìn)行刪除、隊(duì)尾進(jìn)行插入的線性表。允許插入的一端叫隊(duì)尾，刪除的一端叫隊(duì)頭。串：由零個(gè)或多個(gè)字符組成的有限序列；空串：零個(gè)字符的串；長(zhǎng)度：串中字符的數(shù)目；

空串：零個(gè)字符的串；子串：；串中任意個(gè)連續(xù)的字符組成的子序列；位置：字符在序列中的序號(hào)；

相等：串的值相等；空格串：由一個(gè)或多個(gè)空格組成的串，空格串的長(zhǎng)度為串中空格字符的個(gè)數(shù)。

存儲(chǔ)位置：LOC(i ,j)=LOC(0,0)+(b2*i+j)L

結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支；結(jié)點(diǎn)的度:?結(jié)點(diǎn)擁有的子樹(shù)；

樹(shù)的度:樹(shù)中所有結(jié)點(diǎn)的度的最大值；葉子結(jié)點(diǎn):?度為零的結(jié)點(diǎn)；分支結(jié)點(diǎn):?度大于零的結(jié)點(diǎn)

樹(shù)的深度：樹(shù)中葉子結(jié)點(diǎn)所在的最大層次????森林：m棵互不相交的樹(shù)的集合。

二叉樹(shù)的性質(zhì)：

性質(zhì) 1：在二叉樹(shù)的第 i?層上至多有2i-1 個(gè)結(jié)點(diǎn)。(i≥1)

性質(zhì) 2：深度為 k 的二叉樹(shù)上至多含 2k-1 個(gè)結(jié)點(diǎn)。（k≥1）

性質(zhì) 3: 對(duì)任何一棵二叉樹(shù)，若它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為?2?的結(jié)點(diǎn)，

?????????則必存在關(guān)系式：n0?= n2+1。

性質(zhì) 4: 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ???log2n??+1。

滿(mǎn)二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。?

完全二叉樹(shù)：樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)中編號(hào)為 1 至 n 的結(jié)點(diǎn)一一對(duì)應(yīng)。?

路徑長(zhǎng)度：路徑上分支的數(shù)目。樹(shù)的路徑長(zhǎng)度：樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。?

樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記作：WPL(T) =?Swklk

帶權(quán)路徑?長(zhǎng)度最小的二叉樹(shù)，稱(chēng)為最優(yōu)樹(shù)二叉樹(shù)或赫夫曼樹(shù)。?

關(guān)鍵路徑：路徑長(zhǎng)度最長(zhǎng)的路徑。

?

頂點(diǎn)：數(shù)據(jù)元素vi稱(chēng)為頂點(diǎn)

邊、?。篜 (vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間的直接連線，在無(wú)向圖中稱(chēng)為邊，在有向圖中稱(chēng)為弧。任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)(vi,vj)∈E是無(wú)序的，該連線稱(chēng)為邊。是有序的，該連線稱(chēng)為弧?；☆^、弧尾：帶箭頭的一端稱(chēng)為弧頭，不帶箭頭的一端稱(chēng)為弧尾。

頂點(diǎn)的度(TD)=出度(OD)+入度(ID)?

圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。

通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。

排序的分類(lèi)：

按待排序記錄所在位置

????內(nèi)部排序：待排序記錄存放在內(nèi)存

????外部排序：排序過(guò)程中需對(duì)外存進(jìn)行訪問(wèn)的排序

按排序依據(jù)原則

插入排序：直接插入排序、折半插入排序、希爾排序

交換排序：冒泡排序、快速排序

選擇排序：簡(jiǎn)單選擇排序、堆排序

歸并排序：2-路歸并排序

基數(shù)排序