2014(下)數(shù)據(jù)結構復習

1、2014（下）數(shù)據(jù)結構復習2014下數(shù)據(jù)結構復習提綱第1章緒論有關術語；算法.算法復雜度的分析和計算方法 例題：1. 下面算法的時間復雜度為0( n )。int f( unsigned int n )if(n = = 0lln = =l) return 1;else returen n ( n - 1); 2- for (i=l, s=0； i<=n； i+) t=l； for(J=l； j<=i； j+) t=t*j； s=s+t； 時間復雜度為0(1?) 第2-3章線性表，棧和隊列線性表的概念、存儲結構.痣入與刪除操作；棧和隊列的概念，理 解棧頂指針、隊首、隊尾指針的意義和作用

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

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

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

5、n-l.3. 設用權 6, 10, 13, 14, 20, 37 構造 Huffman 樹，則該 Huffman 樹的 根結點的權值為100.（仔細驗算構造Huffman樹）4. 一棵深度為k的滿二叉樹的結點總數(shù)為21, 棵深度為k的完全二 叉樹的結點總數(shù)的最小值為2応最大值為2匕1。5. 深度為K的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹.6. 設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF,則該 二叉樹的前序遍歷序列為ABDECF ,中序遍歷序列為DBEAFC ,后序 遍歷序列為DEBFCA.7. 一棵完全二叉樹中共有768結點，則該樹中共有384個葉子結點。8. 深度

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

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

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

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

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

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