數(shù)據(jù)：是對客觀事物的符號表示。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，也稱節(jié)點（node）或記錄（record）。 數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)項：有獨立含義的數(shù)據(jù)最小單位，也稱域(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ù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。 ????線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對一個的關(guān)系。 ????樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系。 ????圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個對多個的關(guān)系。 邏輯結(jié)構(gòu)：抽象反映數(shù)據(jù)元素之間的邏輯關(guān)系。（算法設(shè)計） 物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。（算法實現(xiàn)） 存儲結(jié)構(gòu)分為： ????順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系。 鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。 算法：對特定問題求解步驟的一種描述。 算法的五個重要特性：有窮性，確定性，可行性，輸入和輸出。 算法設(shè)計的原則或要求：正確性，可讀性，健壯性，效率與低存儲量需求。 衡量算法效率的方法：事后統(tǒng)計法和事前分析估算法?。 算法執(zhí)行時間的增長率和 f(n) 的增長率相同，則可記作：T (n) = O(f(n))，稱T (n) 為算法的(漸近)時間復(fù)雜度?? 算法運行時間的衡量準(zhǔn)則：以基本操作在算法中重復(fù)執(zhí)行的次數(shù)。 棧：限定僅在表尾進行插入或刪除操作線性表。入棧：插入元素的操作；出棧：刪除棧頂元素的操作。 隊列：只能在隊首進行刪除、隊尾進行插入的線性表。允許插入的一端叫隊尾，刪除的一端叫隊頭。串：由零個或多個字符組成的有限序列；空串：零個字符的串；長度：串中字符的數(shù)目； 空串：零個字符的串；子串：；串中任意個連續(xù)的字符組成的子序列；位置：字符在序列中的序號； 相等：串的值相等；空格串：由一個或多個空格組成的串，空格串的長度為串中空格字符的個數(shù)。 存儲位置：LOC(i ,j)=LOC(0,0)+(b

2

*i+j)L 結(jié)點:包含一個數(shù)據(jù)元素及若干指向其子樹的分支；結(jié)點的度:?結(jié)點擁有的子樹； 樹的度:樹中所有結(jié)點的度的最大值；葉子結(jié)點:?度為零的結(jié)點；分支結(jié)點:?度大于零的結(jié)點 樹的深度：樹中葉子結(jié)點所在的最大層次????森林：m棵互不相交的樹的集合。

二叉樹的性質(zhì)：

性質(zhì) 1：在二叉樹的第 i?層上至多有2

i-1

個結(jié)點。(i≥1) 性質(zhì) 2：深度為 k 的二叉樹上至多含 2

k

-1 個結(jié)點。（k≥1） 性質(zhì) 3: 對任何一棵二叉樹，若它含有n

0

個葉子結(jié)點、n

2

個度為?2?的結(jié)點， ?????????則必存在關(guān)系式：n

0

?= n

2

+1。 性質(zhì) 4: 具有 n 個結(jié)點的完全二叉樹的深度為 ???log

2

n??+1。 滿二叉樹：指的是深度為

k

且含有

2

k

-1

個結(jié)點的二叉樹。? 完全二叉樹：樹中所含的

n

個結(jié)點和滿二叉樹中編號為

1

至

n

的結(jié)點一一對應(yīng)。? 路徑長度：路徑上分支的數(shù)目。樹的路徑長度：樹根到每個結(jié)點的路徑長度之和。? 樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記作：WPL(T) =?Sw

k

l

k

帶權(quán)路徑?長度最小的二叉樹，稱為最優(yōu)樹二叉樹或赫夫曼樹。? 關(guān)鍵路徑：路徑長度最長的路徑。 ? 頂點：數(shù)據(jù)元素vi稱為頂點 邊、?。篜 (vi,vj)表示頂點vi和頂點vj之間的直接連線，在無向圖中稱為邊，在有向圖中稱為弧。任意兩個頂點構(gòu)成的偶對(vi,vj)∈E是無序的，該連線稱為邊。是有序的，該連線稱為弧。弧頭、弧尾：帶箭頭的一端稱為弧頭，不帶箭頭的一端稱為弧尾。 頂點的度(TD)=出度(OD)+入度(ID)? 圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。 通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。 排序的分類： 按待排序記錄所在位置 ????內(nèi)部排序：待排序記錄存放在內(nèi)存 ????外部排序：排序過程中需對外存進行訪問的排序 按排序依據(jù)原則 插入排序：直接插入排序、折半插入排序、希爾排序 交換排序：冒泡排序、快速排序 選擇排序：簡單選擇排序、堆排序 歸并排序：2-路歸并排序 基數(shù)排序