數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)綱要第一部分要點(diǎn)問題求解物理結(jié)構(gòu)和邏輯結(jié)構(gòu)的體現(xiàn)算法的特征算法和程序的區(qū)別算法復(fù)雜性分類時(shí)間復(fù)雜性、空間復(fù)雜性最壞情況下、最好情況下和平均情況下的復(fù)雜性漸進(jìn)性態(tài)度量:O常見算法復(fù)雜性Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)考查難點(diǎn)程序段算法復(fù)雜性的計(jì)算實(shí)例代碼段for(j=1;j<=n;j++)的時(shí)間復(fù)雜性是

B

。for(k=n;k>=1;k/=2)count++;A、O(n2)B、O(nlogn)C、O(logn)D、O(n)代碼段分析方法直觀分析遞歸求解快速排序算法時(shí)間復(fù)雜性分析第二章要點(diǎn)ADT表數(shù)學(xué)模型線性關(guān)系數(shù)組實(shí)現(xiàn)各種實(shí)現(xiàn)的時(shí)間復(fù)雜性優(yōu)缺點(diǎn)指針實(shí)現(xiàn)各種實(shí)現(xiàn)的時(shí)間復(fù)雜性優(yōu)缺點(diǎn)指針實(shí)現(xiàn)和數(shù)組實(shí)現(xiàn)的優(yōu)缺點(diǎn)對(duì)比數(shù)組和指針實(shí)現(xiàn)的結(jié)合間接尋址方法實(shí)現(xiàn)線性表游標(biāo)實(shí)現(xiàn)線性表鏈表的衍生循環(huán)鏈表雙鏈表考查難點(diǎn)指針實(shí)現(xiàn)下各種運(yùn)算的指針變化以及含義各種實(shí)現(xiàn)的算法復(fù)雜性實(shí)例向一個(gè)有127個(gè)元素的有序線性表（數(shù)組實(shí)現(xiàn)）中插入一個(gè)隨機(jī)的新元素并依然保持有序性，平均要移動(dòng)

63.5

個(gè)元素。（考查點(diǎn)為數(shù)組實(shí)現(xiàn)線性表插入運(yùn)算的平均時(shí)間復(fù)雜性）

(插入操作：后移？，刪除運(yùn)算：前移？）各種運(yùn)算的具體實(shí)現(xiàn)和線性表的應(yīng)用實(shí)例循環(huán)雙鏈表中在p所指結(jié)點(diǎn)之后插入結(jié)點(diǎn)s的操作是

D

。A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->nextB、p->next=s;p->next->prior=s;s->prior=p;s->next=p->nextC、s->prior=p;s->next=p->next;p->next=s;p->next->prior=sD、s->prior=p;s->next=p->next;p->next->prior=s;p->next=s第三章要點(diǎn)ADT棧數(shù)學(xué)模型LIFO存儲(chǔ)特性數(shù)組實(shí)現(xiàn)各種運(yùn)算的實(shí)現(xiàn)棧的經(jīng)典應(yīng)用括號(hào)匹配問題等考查難點(diǎn)棧LIFO特性的應(yīng)用實(shí)例4個(gè)元素a1，a2，a3和a4依次通過一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)如圖，不可能的出棧順序是

C

。 A、a4，a3，a2，a1 B、a3，a2，a4，a1 C、a3，a1，a4，a2 D、a3，a4，a2，a1第四章要點(diǎn)ADT隊(duì)列數(shù)學(xué)模型FIFO的存儲(chǔ)特性指針實(shí)現(xiàn)各種運(yùn)算的實(shí)現(xiàn)循環(huán)數(shù)組實(shí)現(xiàn)當(dāng)前游標(biāo)下一單元的確定方法滿隊(duì)列和空隊(duì)列的區(qū)分各種運(yùn)算的實(shí)現(xiàn)考查難點(diǎn)隊(duì)列FIFO特性的應(yīng)用棧和隊(duì)列的配合使用實(shí)例設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該能容納

4

個(gè)元素。隊(duì)列的循環(huán)數(shù)組實(shí)現(xiàn)方法實(shí)例順序循環(huán)隊(duì)列中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)中最多可有MAX個(gè)元素，則元素入隊(duì)列時(shí)隊(duì)尾指針的變化為

(rear+1)%MAX

；元素出隊(duì)列時(shí)隊(duì)頭指針的變化為

(front+1)%MAX

。第六章要點(diǎn)簡(jiǎn)單排序算法冒泡排序、插入排序、選擇排序算法思想穩(wěn)定性能算法時(shí)間復(fù)雜性比較次數(shù)交換次數(shù)最壞情況最好情況快速排序算法分而治之算法策略，遞歸實(shí)現(xiàn)分解算法的主要思想算法時(shí)間復(fù)雜性的遞歸求解和性能影響因素不穩(wěn)定排序歸并排序算法分而治之的算法策略穩(wěn)定排序算法時(shí)間復(fù)雜性的遞歸求解堆排序算法數(shù)據(jù)結(jié)構(gòu)堆的運(yùn)用堆排序算法的實(shí)現(xiàn)不穩(wěn)定排序算法時(shí)間復(fù)雜性考查難點(diǎn)所有排序算法的時(shí)間復(fù)雜性及其應(yīng)用實(shí)例

在輸入已經(jīng)有序的情況下，整個(gè)冒泡排序算法需要執(zhí)行n(n-1)/2

次元素比較操作。

所有排序算法的排序過程重現(xiàn)

對(duì)關(guān)鍵字序列(72，87，61，23，94，16，05，58)進(jìn)行堆排序，使之按關(guān)鍵字遞減次序排列。請(qǐng)寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。初始堆7287612394160558，第一趟7287612394160558，第二趟7287052394166158，第三趟7223055694166187。

特定情形和要求下排序算法的選擇和比較實(shí)例

1.以下排序算法中，

B

在數(shù)據(jù)基本有序時(shí)效率最好。A快速排序B冒泡排序C堆排序D計(jì)數(shù)排序

2.舉例說明快速排序算法的最好時(shí)間性能發(fā)生在什么情況下，最壞時(shí)間性能又發(fā)生在什么情況下？（冒泡排序、選擇排序、插入排序、…）第七章樹要點(diǎn)樹的性質(zhì)及其應(yīng)用樹的遍歷運(yùn)算遞歸實(shí)現(xiàn)樹/森林與二叉樹的轉(zhuǎn)化方法左兒子右兄弟表示法的衍生二叉樹/滿二叉樹/完全二叉樹的重要性質(zhì)及其計(jì)算樹的高度的定義和概念二叉樹的順序存儲(chǔ)結(jié)構(gòu)各結(jié)點(diǎn)之間的邏輯關(guān)系二叉樹的指針實(shí)現(xiàn)二叉樹結(jié)點(diǎn)類和二叉樹類遍歷運(yùn)算四種常見遍歷方式考查難點(diǎn)樹/二叉樹性質(zhì)的計(jì)算實(shí)例設(shè)一棵完全二叉樹具有988個(gè)結(jié)點(diǎn)，則此完全二叉樹有

494

個(gè)葉子結(jié)點(diǎn)，有

493

個(gè)度為2的結(jié)點(diǎn)，有

1

個(gè)結(jié)點(diǎn)只有非空左子樹，有

0

個(gè)結(jié)點(diǎn)只有非空右子樹，樹的高度為

9。

遍歷運(yùn)算及其應(yīng)用實(shí)例1已知某棵二叉樹按中序遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK，按后序遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJIA，該二叉樹按前序遍歷所得到的結(jié)點(diǎn)序列為ABCDGEIHFJK。

第八章要點(diǎn)集合位向量表示法有序鏈表表示法各種運(yùn)算實(shí)現(xiàn)中有序性的體現(xiàn)實(shí)例在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使其仍然有序，其算法的時(shí)間復(fù)雜性為

。AO(logn)BO(1)CO(n2)DO(n)第九章要點(diǎn)符號(hào)表的實(shí)現(xiàn)散列表開散列實(shí)現(xiàn)思想閉散列實(shí)現(xiàn)思想散列沖突解決機(jī)制散列函數(shù)實(shí)例設(shè)有一組關(guān)鍵字{101003245581263292004000}，散列表大小hashSize=13，表項(xiàng)下標(biāo)從0到12，散列函數(shù)h(x)采用先將關(guān)鍵碼各位數(shù)字折疊相加,再用%hashSize將相加的結(jié)果映像到表中的辦法，采用二次散列技術(shù)（h2i-1(x)=|h(x)+i2|%hashsize，h2i(x)=|h(x)-i2|%hashsize解決沖突，畫出相應(yīng)的閉散列表，并指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼分別產(chǎn)生了多少次沖突。（要給出詳細(xì)求解過程）(等概率情況下，查找成功的平均查找長(zhǎng)度)h(10)=(1+0)%13=1放入表項(xiàng)1h(100)=(1+0+0)%13=1100與10發(fā)生一次沖突h1(100)=(h(100)+1*1)%13=2，放入表項(xiàng)2…下標(biāo)關(guān)鍵字沖突次數(shù)058011002100133044000532062003789450101261112901209第十章要點(diǎn)字典二叉搜索樹存儲(chǔ)特征搜索、插入和刪除運(yùn)算的實(shí)現(xiàn)二叉搜索樹的效率及其影響因素第十一章要點(diǎn)優(yōu)先隊(duì)列堆存儲(chǔ)特征堆的數(shù)組實(shí)現(xiàn)堆化運(yùn)算插入和刪除運(yùn)算的實(shí)現(xiàn)以及時(shí)間復(fù)雜性哈夫曼樹特點(diǎn)帶權(quán)路徑長(zhǎng)度的定義哈夫曼樹的構(gòu)造方法哈夫曼編碼及其應(yīng)用堆化運(yùn)算實(shí)例已知序列{17，31，13，11，20，35，25，8}，請(qǐng)將上述序列初始建為一個(gè)極小化堆，并給出輸出前兩個(gè)最小關(guān)鍵字后重建的堆。（要求畫出初始建堆和兩次調(diào)整后堆的示意圖）。（判斷某一個(gè)序列是否是堆）哈夫曼編碼的應(yīng)用實(shí)例假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。畫出以該8個(gè)字母為葉結(jié)點(diǎn)的哈夫曼樹，每個(gè)葉結(jié)點(diǎn)的權(quán)重就是頻率，為計(jì)算方法，一般將權(quán)重轉(zhuǎn)化為整數(shù)第十三章要點(diǎn)圖的鄰接矩陣表示法不同類型圖的鄰接矩陣含義實(shí)現(xiàn)圖的鄰接表表示法不同類型圖的鄰接表中結(jié)點(diǎn)類型的定義實(shí)現(xiàn)圖的遍歷廣度優(yōu)先搜索策略隊(duì)列的使用深度優(yōu)先搜索策略遞歸實(shí)現(xiàn)兩種遍歷方法在鄰接矩陣和鄰接表的實(shí)現(xiàn)下的時(shí)間復(fù)雜性最短路徑問題單源最短路徑問題Dijkstra算法算法思想及其應(yīng)用迭代過程邊權(quán)非負(fù)性的特征所有點(diǎn)對(duì)之間的最短路徑Floyd算法算法的迭代求解思想及其應(yīng)用時(shí)間復(fù)雜性最小生成樹生成樹的概念：極小連通子圖最小生成樹性質(zhì)Prim算法算法思想貪心策略的應(yīng)用迭代過程Kruskal算法算法思想貪心策略的應(yīng)用迭代過程考查難點(diǎn)圖的性質(zhì)及其計(jì)算實(shí)例在一個(gè)具有6個(gè)頂點(diǎn)的無向圖中，要連