1、數(shù)據(jù)結(jié)構(gòu)考研輔導 基礎(chǔ)復(fù)習,浙江大學計算機學院,內(nèi)容提綱,考研概述,考察目標 理解數(shù)據(jù)結(jié)構(gòu)的基本概念：掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。 在掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。,考研概述,考試形式 整卷滿分為150分，考試時間為180分鐘 數(shù)據(jù)結(jié)構(gòu)占45分，估計用時4550分鐘 單選題：40題2分/題，估計占10題20分左右，建議用時不超過2分鐘/題 綜合題：70分，估計占2題共2025分，建議用時不超過10分鐘/題,考研概述,復(fù)習計劃 基礎(chǔ)理論復(fù)習 例題詳解 題目范圍：真題1套 + 模擬題

2、9套 + 補充題 模擬題第10套將用于最后一天模擬考試,6,基礎(chǔ)內(nèi)容復(fù)習數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴蔚敏、吳偉民，清華大學出版社,線性表、堆棧、隊列、數(shù)組 樹與圖 查找與排序,線性表、堆棧、隊列、數(shù)組,線性表 定義：n個數(shù)據(jù)元素的有限序列 基本操作：隨機訪問、插入、刪除、前驅(qū)、后繼、倒序等 實現(xiàn)方式： 順序存儲：數(shù)組,Loc(ai),Loc(ai+1) = Loc(ai) + l,Loc(ai) = Loc(a1) + ?,(i -1) * l,線性表 實現(xiàn)方式： 順序存儲：數(shù)組,線性表、堆棧、隊列、數(shù)組, 是一種隨機存取的存儲結(jié)構(gòu)，方便隨機存取第i個數(shù)據(jù)元素, 插入、刪除復(fù)雜度為O(n)，需要移

3、動大量元素,自測題 在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是： 訪問第i個結(jié)點(1in)和求第i個結(jié)點的直接前驅(qū)(2in) 在第i個結(jié)點后插入一個新結(jié)點（1in） 刪除第i個結(jié)點（1in） 將n個結(jié)點從小到大排序,線性表、堆棧、隊列、數(shù)組,線性表、堆棧、隊列、數(shù)組,線性表 實現(xiàn)方式： 鏈式存儲：鏈表, 線性鏈表,頭指針H = 19,若 p-data = ai 則 p-next-data = ai+1,typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;,有時附加頭結(jié)點,自測題 線性表若

4、采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址: 必須是連續(xù)的 部分地址必須是連續(xù)的 一定是不連續(xù)的 連續(xù)或不連續(xù)都可以,線性表、堆棧、隊列、數(shù)組,線性表、堆棧、隊列、數(shù)組,線性表 實現(xiàn)方式： 鏈式存儲：鏈表 線性鏈表, 插入、刪除復(fù)雜度為O(1)，僅需修改指針而不需要移動元素, 是一種非隨機存取的存儲結(jié)構(gòu)，不方便隨機存取第i個數(shù)據(jù)元素,*靜態(tài)鏈表 （p.31-35）,自測題 下面的敘述不正確的是（ ） 線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比 線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān) 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比 線性表在順序存儲時，查

5、找第i個元素的時間同i的值無關(guān),線性表、堆棧、隊列、數(shù)組,自測題 在一個單鏈表中，若p所指的結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行： s-next=p; p-next=s; s-next=p-next; p-next=s; s-next=p-next; p=s; p-next=s; s-next=p;,線性表、堆棧、隊列、數(shù)組,自測題 在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是： p = p-next; p-next = p-next-next; p-next = p; p = p-next-next;,線性表、堆棧、隊列、數(shù)組,x,p,線性表、堆棧、隊列、數(shù)

6、組,線性表 實現(xiàn)方式： 鏈式存儲：鏈表 循環(huán)鏈表, 雙向鏈表,有時設(shè)尾指針可簡化某些操作，如兩表合并。,自測題 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用( )最節(jié)省時間。 單鏈表 單循環(huán)鏈表 帶尾指針的單循環(huán)鏈表 帶頭結(jié)點的雙循環(huán)鏈表,線性表、堆棧、隊列、數(shù)組,自測題 將線性表La和Lb頭尾連接，要求時間復(fù)雜度為O(1)，且占用輔助空間盡量小。應(yīng)該使用哪種結(jié)構(gòu)？ 單鏈表 單循環(huán)鏈表 帶尾指針的單循環(huán)鏈表 帶頭結(jié)點的雙循環(huán)鏈表,線性表、堆棧、隊列、數(shù)組,tmp = La-next; La-next = Lb-next; Lb-next = tmp;,19,線性表、堆棧、隊列、數(shù)

7、組,線性表 練習1：分別實現(xiàn)數(shù)組、單鏈表、循環(huán)鏈表、雙向鏈表的插入和刪除操作。 練習2：實現(xiàn)單鏈表的原地逆轉(zhuǎn)。 練習3：分別用一元多項式的兩種表示實現(xiàn)多項式加法。,自測題 給定2個帶有表頭結(jié)點的單鏈表的頭指針L1和L2，結(jié)點結(jié)構(gòu)為 。假設(shè)這2個鏈表的結(jié)點已經(jīng)按Data域遞增有序，請設(shè)計算法把它們合并成一個按Data域遞增有序的鏈表。注意：算法不能使用額外的結(jié)點空間。,線性表、堆棧、隊列、數(shù)組,算法思路為順序比較L1和L2當前所指的兩結(jié)點的Data域，將小的那個結(jié)點從原鏈表摘除，貼到合并鏈表的尾部。如此進行到至少其中一個鏈表為空。若此時另一個鏈表不為空，則將另一個鏈表整個貼到合并鏈表的尾部。注意

8、原始2個鏈表有2個頭結(jié)點，合并后只保留一個，需要釋放另一個的空間。,List MergeSortedLists( List L1, List L2 ) List L = L1; List Tail = L2; L1 = L1-Next; L2 = L2-Next; free( Tail ); Tail = L; /釋放第二個鏈表的表頭，并將新鏈表的表尾指針Tail初始化 while ( L1 ,自測題 給定2個帶有表頭結(jié)點的單鏈表的頭指針L1和L2，結(jié)點結(jié)構(gòu)為 。假設(shè)這2個鏈表的結(jié)點已經(jīng)按Data域遞增有序，請設(shè)計算法把它們合并成一個按Data域遞減有序的鏈表。注意：算法不能使用額外的結(jié)點空間

9、。,線性表、堆棧、隊列、數(shù)組,解題的基本思路不變，只要將原來的表尾插入改為表頭插入即可。當然，當其中一個鏈表為空而另一個鏈表不為空時，不能直接將剩余鏈表貼到表尾，而必須將剩余結(jié)點一個一個插入表頭。,自測題 若L1和L2是有序數(shù)組，其結(jié)點已經(jīng)按Data域遞增有序，請設(shè)計算法把它們合并成一個按Data域遞增有序的數(shù)組。注意：要求將L2并入L1，并且要求移動元素的次數(shù)盡可能少。,線性表、堆棧、隊列、數(shù)組,必須事先算好合并后L1的長度，然后從L1的最終尾部向前插入元素。插入過程與前面算法類似，但是是從尾部開始比較L1和L2相應(yīng)元素大小，將較大的元素先插入到后面的位置。,void MergeSorted

10、Arrays( ElementType L1, int N1, ElementType L2, int N2 ) int p1, p2, cur; p1 = N1-1; /p1指向L1當前處理的元素位置 p2 = N2-1; /p2指向L2當前處理的元素位置 cur = N1+N2-1; /cur指向下一個要插入的元素在L1中的最終位置 while ( (p1=0) ,堆棧 概念：后進先出，限定僅在表尾進行插入刪除的線性表。 表示與實現(xiàn)： 順序棧：數(shù)組，top+，top- 鏈棧：鏈表，top即為頭指針 應(yīng)用：括號匹配檢驗、表達式求值、n階Hanoi塔問題（典型遞歸）、迷宮問題,線性表、堆棧、隊

11、列、數(shù)組,自測題 判定一個棧ST(最多元素為m0)為空的條件是： ST-top != 0 ST-top = 0 ST-top != m0 ST-top = m0,線性表、堆棧、隊列、數(shù)組,自測題 有六個元素以6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？ 5 4 3 6 1 2 4 5 3 1 2 6 3 4 6 5 2 1 2 3 4 1 5 6,線性表、堆棧、隊列、數(shù)組,自測題 若一個棧的輸入序列為1，2，3，n，輸出序列的第一個元素是i，則第j個輸出元素是： i j 1 i j j i 1 不確定的,線性表、堆棧、隊列、數(shù)組,隊列 概念：先進先出，限定僅在隊尾進行插

12、入、僅在隊頭進行刪除的線性表。 表示與實現(xiàn)： 順序隊列：循環(huán)數(shù)組，(rear+1)%N, (front+1)%N 鏈棧：鏈表，front為頭指針，rear為尾指針 應(yīng)用：離散事件模擬,線性表、堆棧、隊列、數(shù)組,自測題 循環(huán)隊列用數(shù)組A0,N1存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是： (rear-front+N)%N rear-front+1 rear-front-1 rear-front,線性表、堆棧、隊列、數(shù)組,自測題 棧和隊列的共同特點是： 都是先進后出 都是先進先出 只允許在同一端點處插入和刪除 沒有共同點,線性表、堆棧、隊列、數(shù)組,數(shù)組 特殊矩

13、陣的壓縮存儲 對稱矩陣：,線性表、堆棧、隊列、數(shù)組,*上（下）三角矩陣同理存儲，或許多存儲一個常數(shù)（若另一半矩陣元素是非零常數(shù)）。,線性表、堆棧、隊列、數(shù)組,數(shù)組 特殊矩陣的壓縮存儲 m對角矩陣：,稀疏矩陣：,線性表、堆棧、隊列、數(shù)組,數(shù)組 特殊矩陣的壓縮存儲 稀疏矩陣： 三元組順序表：以行序為主序，順序排列為三元組的1維數(shù)組，并存行數(shù)、列數(shù)、非0元個數(shù)。,typedef struct inti, j; ElemTypev; Triple; typedef union TripledataMAXSIZE+1; intnrow, ncol, ntotal; Sparse_Matrix;,線性表、

14、堆棧、隊列、數(shù)組,數(shù)組 特殊矩陣的壓縮存儲 稀疏矩陣： 三元組順序表：快速轉(zhuǎn)置,對每列掃描整個數(shù)組：O(ncolntotal), 如何一步到位，放入正確位置？,numcol 第col列中非0元個數(shù)； cpotcol 第col列中第1個非0元在轉(zhuǎn)置矩陣中的位置；,cpot1 = 1; cpotcol = cpotcol-1 + numcol-1;,4,2,O( ncol + ntotal ),線性表、堆棧、隊列、數(shù)組,數(shù)組 特殊矩陣的壓縮存儲 稀疏矩陣： 行邏輯鏈接的順序表：矩陣相乘,typedef struct TripledataMAXSIZE+1; intrposMAXRC+1; intn

15、row, ncol, ntotal; Sparse_Matrix;,各行第1個非0元在數(shù)組中的位置,設(shè) M = A B，則有,關(guān)鍵： 對每個A.datap，找所有B.dataq，滿足( A.datap.j = B.dataq.i )，將(A.datap.vB.dataq.v)累加到相應(yīng)的臨時行向量，最后壓縮到M中。,O( ArowBcol + AtotalBtotal/Brow ),線性表、堆棧、隊列、數(shù)組,數(shù)組 特殊矩陣的壓縮存儲 稀疏矩陣： 十字鏈表：矩陣相加,計算 A + B 的復(fù)雜度為 O( Atotal + Btotal ),自測題 設(shè)稀疏矩陣A有t個非零元素，用二維數(shù)組存儲時占用m

16、*n個單元。問稀疏矩陣的三元組表示法在什么情況下比二維數(shù)組存儲節(jié)省空間？ t m*n t m*n/3 t m*n/3 1 t m*n 1,線性表、堆棧、隊列、數(shù)組,樹與圖,樹與二叉樹的概念 樹的概念：度(degree)；層(level) 注意：根為第1層；深度(depth) 結(jié)點的最大層次。 二叉樹的概念：左右有序 性質(zhì)1：第i層最多有2i-1個結(jié)點。 性質(zhì)2：深度為k的二叉樹最多有2k-1個結(jié)點。 性質(zhì)3：若n0為葉子數(shù)，n2為度為2的結(jié)點數(shù)，則有 n0= n2+1。 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為 log2n+1。,樹與二叉樹的概念 二叉樹的概念： 性質(zhì)5：對有n個結(jié)點且順序編號

17、的完全二叉樹，其任一結(jié)點 i 有,樹與圖,二叉樹的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)：數(shù)組 僅適用于完全二叉樹 鏈式存儲結(jié)構(gòu)： 在含有n個結(jié)點的二叉鏈表中有 個空鏈域。 二叉樹的遍歷 先序、 中序、 后序、 層次,樹與圖,Parent,1,2,3,4,5,6,7,n+1,自測題 一棵完全二叉樹共有2435個結(jié)點，則其中度為0的結(jié)點數(shù)為？ 1218 1217 不確定 812,樹與圖,388 + 210 388/2 = 1218,自測題 在一棵高度為h(假定樹根結(jié)點的層號為0)的完全二叉樹中，所含結(jié)點個數(shù)不小于 2h 1 2h+1 2h 1 2h,樹與圖,自測題 結(jié)點中序遍歷為xyz的不同二叉樹，它有幾種不同

18、狀態(tài)？ 3 4 5 6,樹與圖,自測題 前序遍歷和中序遍歷結(jié)果相同的二叉樹為 一般二叉樹 只有根結(jié)點的二叉樹 所有結(jié)點只有左子樹的二叉樹 所有結(jié)點只有右子樹的二叉樹,樹與圖,自測題 前序遍歷和后序遍歷結(jié)果相同的二叉樹為 一般二叉樹 只有根結(jié)點的二叉樹 所有結(jié)點只有左子樹的二叉樹 所有結(jié)點只有右子樹的二叉樹,樹與圖,自測題 已知中序遍歷和前序遍歷結(jié)果，給出算法求后序遍歷結(jié)果。,樹與圖,（1）從前序遍歷結(jié)果推斷該樹的樹根。 （2）找出左子樹和右子樹的中序和前序遍歷結(jié)果。 （3）重復(fù)上述過程，找出左、右子樹的根結(jié)點，并逐步往下擴展，直到生成一顆完整的二叉樹。,左,左,右,右,OutPostOrder(PreOrder, InOrder) /已知前序序列PreOrder、中序序列InOrder，求后序序列 1）應(yīng)用前述方法，從序列PreOrder和InOrder中推斷出： 樹的根r; 左子樹的前序遍歷序列PreOrderLeft 和中序遍歷序列InOrderLeft; 右子樹的前序遍歷序列PreOrderRight 和中序遍歷序列InOrderRig