2014數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

1、2014 （下）數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)2014下數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱第1章緒論有尖術(shù)語；算法、算法復(fù)雜度的分析和計算方法例題：1下面算法的時間復(fù)雜度為0( n) oint f( unsigned int n )if(n = = 0|n = = 1 ) return 1;else reture n n *f ( n T );2 for(i=1 、s=0 ； iv=n ； i+ ) t=1 ； for(j=1 ； j<=i ； j+) t=t*j ； s=s+t ； 時間復(fù)雜度為0()第2-3章線性表，棧和隊列線性表的概念、存儲結(jié)構(gòu)、插入與刪除操作；棧和隊列的概念，理 解棧頂指針、隊首、隊尾指針的意義和作

2、用，特別是循環(huán)隊列的頭、尾指針 的設(shè)置。為什么要這樣設(shè)置。它們基本操作的實現(xiàn)。判空和判滿？了解有尖應(yīng)用。例題：1 -在一個單鏈表中，若q所指結(jié)點是P所指結(jié)點的前驅(qū)結(jié)點，若在q與P 之間插入一個s所指的結(jié)點，則執(zhí)行的語句?(答：q>next=s; s->next=p):注意在某個已知結(jié)點前插需要執(zhí)行的語句？ 2注意循 環(huán)(鏈)隊列的判空和判滿的條件？(看書理解! ) 3對于一個具有n個結(jié)點 的單鏈表，在已知的結(jié)點P后插入一個新結(jié)點的時間復(fù)雜度為0(1)，在給定 值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為O(n)。4. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別

3、為 隊 頭指針和隊尾指針'則判斷隊滿的條件為(®r+l) %n= = front。執(zhí)行出隊操 作后其頭指針front如何？5. 線性表采用鏈式存儲時，結(jié)點的存儲地址連續(xù)與否均可；6鏈式棧刪除棧頂元素的操作序列為top=top->next.7. 在單鏈表中，指針P指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的 語句是 p->next=p->next>next.8. 判定“帶頭結(jié)點的鏈隊列為空”的條件是Q.front=Q.rear.9. 假設(shè)以數(shù)組seqn m 存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指 示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。則隊

4、滿的條件表達式為quelen = m ；隊空的條件表達式quelen = 0 ；隊頭元素位置的表達式 (rear quelen + m ) % m第6章樹和二叉樹樹和二叉樹的定義、完全二叉樹及其性質(zhì)、存儲表示及遍歷算法（遞 歸和非遞歸）、哈夫曼樹的概念。例題：1 -在一棵二叉樹中，度為0的結(jié)點個數(shù)為n。,度為2的結(jié)點個數(shù)為氐，則 no= H24-1 o （完全二叉樹性質(zhì)）例：二叉樹上葉結(jié)點數(shù)等于（雙分支結(jié)點數(shù) 加1 ）；對于一棵具有n個結(jié)點的二叉樹，當進行鏈接存儲時，其二叉鏈 表中的指針域的總數(shù)為勿個，其中個用于鏈接孩子結(jié)點，n+1個空閑 著。2. n個權(quán)構(gòu)成一棵Huffman樹，其節(jié)點總數(shù)為

5、2n-1.3. 設(shè)用權(quán) 6，10，13，14, 20 » 37 構(gòu)造 Huffman 樹、則該 Huffman 樹的 根結(jié)點的權(quán)值為100.（仔細驗算構(gòu)造Huffman樹）4. 一棵深度為k的滿二叉樹的結(jié)點總數(shù)為2<1，一棵深度為k的完全二叉樹 的結(jié)點總數(shù)的最小值為2k'1，最大值為2<1。5深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹6設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二 叉樹的前序遍歷序列為ABDECF，中序遍歷序列為DBEAFC ，后序 遍歷序 列為 DEBFCA.7一棵完全二叉樹中共有768結(jié)點，則該樹中共有38

6、4個葉子結(jié)點。8深度為k的完全二叉樹中最少有2k-1個結(jié)點。9.二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的 條件是任一結(jié)點無右孩子第7章圖圖的存儲及遍歷算法，圖的有尖概念，最短路徑，（最?。┥蓸淅?題：1由一個具有n個頂點的連通圖生成的最小生成樹中，具有條邊。2 有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個 數(shù)之和等于頂點i的出度，第i列中所有非零元素個數(shù)之和等于頂點i的入 度。3. 若要把n個頂點連接為一個連通圖，則至少需要條邊。4. 連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有條邊5 在 一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的2倍。6.

7、在一個具有n個頂點的無向完全圖中，包含有n （n-1） /2條邊， 在一個具有n個頂點的有向完全圖中，包含有n(n1)條邊。7無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行 深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為 0(乎)；用鄰接表作為圖的存 儲上述復(fù)雜度O(n+e).8. 在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為n2- 2e.9. 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,則e和 d的尖系為d=e.10. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則 e=d/211. 掌握最小生成樹算法例如使用普里姆(Prim)算法以A為源

8、點，構(gòu)造下圖 的最小代價生成樹，畫出各步的結(jié)果。也已知有向圖G如下所示，根據(jù)迪杰斯特 拉算法求頂點v0到其他頂點的最短距離終占乙八、從VO到各終點的d值和最短路徑的求解過 程i=1i=2i=3i=4V112(v0,v1)12 (vO,v1)7(vO,v4,v1)v24 (v0,v2)v39 (v0,v3)8(v0,v2,v3)7(v0,v4,v3)7(v0,v4,v3)v45 (vO,v4)5 (v0,v4)vjv2v4v1v3sv0,v2vO,v4vO,v4,v1v0,v4,v3第9章查找掌握二呑(折半)查找，二叉排序樹的概念及其上的插入和刪除有何特點，掌握哈希查找。 例題：1. 對于順序存

9、儲的有序表(5,12, 20, 26, 37, 42, 46, 50, 64)，若采用折半查找，則查找元素 26的比較次數(shù)為4。2. 有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有1個，比較兩次查找成功有結(jié)點數(shù)有2個，比較三次3 理解并掌握二叉排序樹的概念，會構(gòu)造二叉排序樹及查找、插入和刪除操作。4. 中序遍歷二叉排序樹可以得到一個從小到大的有序序列。5. 設(shè)哈希表HT表長m為13,哈希函數(shù)為H(k)=k MOD m給定的尖鍵值序列為19,14,23,10,68,20,84,27,55,11。試求出用線性探測法解決沖突時所構(gòu)造的哈希表，并求出在等概率的情況下查找成功的平均查找長度ASL(1

10、)表形態(tài):0123456789101112142768551920842310111212113122平均查找長度：ASL(10)=(1 *5+2*4+3*1)/10=1.66設(shè)一組初始記錄尖鍵字序列為(20，12, 42, 31，18，14，28)，則根 據(jù)這些記錄尖鍵字構(gòu)造的 二叉排序樹的平均查找長度是19/7.第10章內(nèi)部排序掌握基本排序方法的實現(xiàn)思想。例題：4假定對元素序列(7, 3, 5, 9,1,12, 8, 15進行快速排序，則進行第一次劃分 后，得到的左區(qū)間中元素的個數(shù)為3。2 設(shè)一組初始記錄尖鍵字序列為(60，80, 55, 40，42, 85)，則以第一個尖鍵字45為基準而

11、得到的一趟快速排序結(jié)果是42, 40, 55, 60, 80,85考試題型：一.單項選擇題(15X2分=30分)二填空題(10X2分=20分1 實現(xiàn)數(shù)據(jù)x進棧程序填空；2二叉樹中各類結(jié)點個數(shù)及尖系；3尖于無向圖 的度；4無向圖鄰接矩陣中找鄰接點；5二叉樹遍歷；6順序循環(huán)隊列元素 個數(shù)；7二叉排序樹平均查找長度；8哈夫曼樹構(gòu)造和哈夫曼樹的高度；9. 最小生成樹構(gòu)造及其上權(quán)值之和；10.二叉排序樹中插入一個新結(jié)點算法填 空。三解答題（5八6分=30分）1 循環(huán)隊列在特定設(shè)置下判滿判空，計算元素位置；2.給出鄰接矩陣，畫 出該圖，畫出深度優(yōu)先生成樹；3.填寫出散列表和平均查找長度;4.求某頂 點到其余各頂點的最短路徑；5.構(gòu)造一棵二叉排序樹，畫出刪去結(jié)點之后的 二叉排序樹.四算法閱讀題（2X6分=12分