2012年二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法重點(diǎn)講解

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

　　◆算法的基本概念

　　1. 算法：是對(duì)問題處理方案的正確而完整的描述，是求解問題的方法，是指令的有效序列。

　　2. 具有5個(gè)特性：

　　(1) 有窮性(在有窮步后完成)算法程序的運(yùn)行時(shí)間是有限的

　　(2) 確定性(每一步都有確定的含義)

　　(3) 可行性

　　(4) 輸入(一個(gè)算法有零個(gè)或多個(gè)輸入)

　　(5) 輸出(一個(gè)算法有一個(gè)或多個(gè)輸出)

　　3. 算法的復(fù)雜度

　　包括：時(shí)間復(fù)雜度和空間復(fù)雜度。 二者沒有必然的聯(lián)系。

　　時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量或基本運(yùn)算次數(shù)。

　　空間復(fù)雜度：算法所需要的空間的度量。

　　◆數(shù)據(jù)結(jié)構(gòu)的定義

　　1. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的操作

　　數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的外部結(jié)構(gòu)，指各數(shù)據(jù)元素之間的邏輯關(guān)系，反映人們對(duì)數(shù)據(jù)含義的解釋。 包括：線性結(jié)構(gòu)(線性表、棧、隊(duì)列)和非線性結(jié)構(gòu)(樹和圖)

　　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。

　　一個(gè)邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)。

　　◆ 線性表：線性表中元素的個(gè)數(shù)n(n>=0)定義為線性表的長(zhǎng)度。

　　順序存儲(chǔ)是線性表的一種最常用的存儲(chǔ)方式。

　　線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)和順序存取的存儲(chǔ)結(jié)構(gòu)。

　　1.棧：是限定在表尾進(jìn)行插入和刪除操作的線性表。 具有記憶功能 只能順序存儲(chǔ)(錯(cuò))

　　允許插入和刪除的一端叫棧頂。另一端叫棧底。

　　后進(jìn)先出的線性表

　　2隊(duì)列：是限定在一端插入而在另一端刪除，插入端叫隊(duì)尾，刪除端叫對(duì)頭。

　　先進(jìn)先出的線性表

　　3棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

　　循環(huán)隊(duì)列屬于線性表存儲(chǔ)結(jié)構(gòu)中順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的前者。

　　◆ 樹

　　1.定義:樹的結(jié)點(diǎn)、度(結(jié)點(diǎn)的度)、葉子(終端結(jié)點(diǎn))、數(shù)的度、深度、有序樹和無序數(shù)

　　2.二叉樹：結(jié)點(diǎn)至多有兩棵子樹，并且二叉樹的子樹有之分，次序不能顛倒。

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

　　★ 深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。

　　★ 對(duì)任一個(gè)二叉樹T，如果其葉子(終端結(jié)點(diǎn)數(shù))為n，度為二的結(jié)點(diǎn)數(shù)為m,則n=m+1.

　　★ 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k+1，其中k是㏒2n的整數(shù)部分。

　　2. 二叉樹的遍歷

　　▼先序遍歷(根—左—右)

　　▼中序遍歷(左—根—右)

　　▼后序遍歷(左—右—根)

　　◆查找算法

　　(1)順序查找

　　順序查找的平均查找長(zhǎng)度為(n+1)/2，最壞的情況下比較的次數(shù)為n

　　(2) 二分查找

　　限定于順序存儲(chǔ)的有序線性表

　　◆排序算法

　　(1)插入類排序

　　▲直接插入排序

　　▲折半插入排序

　　▲希爾排序

　　(2)交換類排序

　　▲冒泡排序 最壞情況下的比較次數(shù)n(n-1)/2

　　▲快速排序 最壞情況下的比較次數(shù)n(n-1)/2

　　(3)選擇類排序

　　例題精選:

　　1. 設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn),則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為:350

　　2. 已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列為：cedba

　　3. 要求內(nèi)存量最大的是：歸并排序

　　4. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的是：邏輯結(jié)構(gòu)

　　5. 棧底至棧頂依次存放元素A.B.C.D,在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是：DCBEA

　　6. 已知數(shù)據(jù)表A 中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采取的算法是：直接插入排序

　　7. 用鏈?zhǔn)奖硎揪�性表的優(yōu)點(diǎn)是：便于插入和刪除操作。