結構(本科)復習提要

1、個人資料整理僅限學習使用數(shù)據(jù)結構復習提要清華大學計算機系殷人昆數(shù)據(jù)結構課程是計算機科學與技術專業(yè)的一門重要的專業(yè)基礎課。用數(shù)字計算機解決任何應用問題都離不開數(shù)據(jù)表示和數(shù)據(jù)處理，使用面向?qū)ο蠹夹g開發(fā)軟件，數(shù)據(jù)表示更成為軟件構成的基礎。而數(shù)據(jù)表示和數(shù)據(jù)處理的核心問題之一就是數(shù)據(jù)結構及其操作的實現(xiàn)。這正是數(shù)據(jù)結構課程的內(nèi)容。從這個意義上來說, 數(shù)據(jù)結構課程在知識學習和技能培養(yǎng)兩個方面都處于關鍵地位。b5E2RGbCAP一、課程要求數(shù)據(jù)結構是電大計算機科學與技術專業(yè)本科生的專業(yè)基礎課程之一，該課程是后續(xù)課程如操作系統(tǒng)、計算機網(wǎng)絡等課程的先修課程，在整個教案體系中占據(jù)非常重要的地位。該課程主要討論在軟件

2、開發(fā)中如何進行數(shù)據(jù)結構和算法的設計。因此，用抽象數(shù)據(jù)類型以及面向?qū)ο蟮姆椒ńM織、存儲各種類型的數(shù)據(jù)是本課程的重點，也是學員需要掌握的重點。面向?qū)ο蠓椒ㄒ约敖Y構化技術都是建立高質(zhì)量軟件的技術，通過數(shù)據(jù)結構課程的學習和實踐，可以加深對這些先進軟件開發(fā)方法的理解和體會。因此，數(shù)據(jù)結構課程的任務是按照軟件工程思想，介紹用面向過程和面向?qū)ο蠓椒ㄟM行數(shù)據(jù)設計和程序設計的基本思想，在必要的課程實踐中逐步熟練掌握。p1EanqFDPw通過本課程的學習，應達到知識和技能兩方面的目標：1、知識方面 ：從數(shù)據(jù)結構的類定義和對象的使用，以及存儲表示和操作的實現(xiàn)兩個層次，系統(tǒng)地學習和掌握常用的基本數(shù)據(jù)結構(包括數(shù)組、順

3、序表、多項式、字符串、鏈表、棧與隊列、優(yōu)先級隊列、廣義表、樹與森林、二叉樹、堆、集合、圖、搜索結構、索引結構、散列結構等>及其不同的實現(xiàn)，了解并掌握分析、比較和選擇不同數(shù)據(jù)結構、不同存儲結構、不同算法的原則和方法，為后續(xù)課程的學習打好基礎。DXDiTa9E3d2、技能方面 ：系統(tǒng)地學習和掌握對象類的設計方法和面向?qū)ο蟮某绦蛟O計風格，在不同的存儲結構上實現(xiàn)的算法的設計思想，從中體會和掌握選擇結構的方法和算法設計的思考方式及技巧，提高分析問題和解決問題的能力。RTCrpUDGiT二、考核要求1、命題依據(jù)命題依據(jù)是電大計算機科學與技術專業(yè)本科生數(shù)據(jù)結構教案大綱。2、考核要求本課程考核的重點是考

4、察學員對各種數(shù)據(jù)結構的理解程度和基于這些數(shù)據(jù)結構進行算法設計的能力。具體考核要求分為幾個層次：5PCzVD7HxA理解 ：要求學員理解各種數(shù)據(jù)結構的層次、各種數(shù)據(jù)結構的特點、各種數(shù)據(jù)結構設計的基本思想。1/15個人資料整理僅限學習使用掌握：要求學員能較好地理解和運用一兩個知識點進行簡單的算法設計。綜合應用 ：要求學員能綜合運用多個知識點的內(nèi)容進行比較復雜的應用程序開發(fā)。3、命題原則在教案大綱和考核說明所規(guī)定的目的、要求和內(nèi)容范圍之內(nèi)命題。試卷的考察要求覆蓋面廣，并適當突出重點。試卷兼顧各個能力層次，理解占40%，簡單運用占40%，綜合運用占20%。試卷的難易程度和題量適當，按難易程度分為四個層

5、次：容易占20%，較易占30%，較難占30%，難占 20%。 jLBHrnAILg4、試卷題型單選題 ：給出一些有關數(shù)據(jù)結構性質(zhì)、特點及一些簡單算法性能的不完全敘述，要求學員從題后給出的供選擇的答案中選擇合適的答案，補足這些敘述。 xHAQX74J0X 填空題 ：給出程序說明及一段部分語句缺失的程序，讓學員補充成為完整的程序。簡答題 ：應用作圖方法或簡單計算，使用給定數(shù)據(jù)建立或操作一些數(shù)據(jù)結構。理解問答題 ：給出一段程序，就程序回答一些問題，如給出程序運行結果、根據(jù)要求進行適當修改等。綜合算法題 ：給出算法設計要求，編制出部分算法程序，用來考察幾個知識點的綜合應用。具體形式見后面所附“試卷類型

6、及規(guī)范解答舉例”。5、考核形式采用期末考核與平時成績相結合的方式。其中平時考核：視平時作業(yè)< 包括筆做題和上機題）的完成情況給分，占考核總成績的20% ，能夠按時、按質(zhì)、按量完成平時作業(yè)者方可得滿分；LDAYtRyKfE期末考核：采用筆試，它占總成績的80% ，考試方式為閉卷，答題時限 120 分鐘。以上兩個成績累計60 分以上 < 包括 60 分）算考核通過 。附錄：試卷類型及規(guī)范解答舉例一、單選題 從供選擇的答案中選出正確的答案，將其編號填入括號<）中 1、在數(shù)據(jù)結構的討論中把數(shù)據(jù)結構從邏輯上分為<A）。2、采用線性鏈表表示一個向量時，要求占用的存儲空間地址<

7、B）。3 、采用順序搜索方法查找長度為n 的順序表時，搜索成功的平均搜索長度為<C）。4、在一個單鏈表中，若q 結點是p 結點的前驅(qū)結點，若在q 與 p 之間插入結點s，則執(zhí)行 <D）。 Zzz6ZB2Ltk5、如果想在4092 個數(shù)據(jù)中只需要選擇其中最小的5 個，采用 <E）方法最好。6、設有兩個串t 和 p，求 p 在 t 中首次出現(xiàn)的位置的運算叫做<F ）。2/15個人資料整理僅限學習使用7、在數(shù)組A 中，每一個數(shù)組元素Aij 占用 3 個存儲字，行下標i 從 1 到 8，列下標j從 1 到 10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的

8、存儲字數(shù)是 < G ）。 dvzfvkwMI18、將一個遞歸算法改為對應的非遞歸算法時，通常需要使用<H ）。9、一個隊列的進隊列順序是1, 2, 3, 4，則出隊列順序為 <I）。10、在循環(huán)隊列中用數(shù)組A0.m-1存放隊列元素，其隊頭和隊尾指針分別為front 和rear ，則當前隊列中的元素個數(shù)是< J）。 rqyn14ZNXI【供選擇的答案 】A ：內(nèi)部結構與外部結構靜態(tài)結構與動態(tài)結構線性結構與非線性結構緊湊結構與非緊湊結構B ：必須是連續(xù)的部分地址必須是連續(xù)的一定是不連續(xù)的可連續(xù)可不連續(xù)C：n n/2(n-1>/2(n+1>/2D ：s link=

9、 p link 。 p link = s。p link = s。 s link = q。 EmxvxOtOcop link = s link 。s link = p。q link = s。 s link = p。 SixE2yXPq5E：起泡排序堆排序錦標賽排序快速排序F：求子串模式匹配串替換串連接G：80100240270H ：棧隊列循環(huán)隊列優(yōu)先隊列I ：4,3,2,12,4,3,11, 2, 3, 4 3, 2, 1, 46ewMyirQFLJ：( front - rear + 1> % m ( rear - front + 1> %m(front - rear + m>

10、 %m( rear - front + m> %m二、閱讀理解題 給出下列遞歸過程的執(zhí)行結果(1> voidunknown ( int w > if ( w > unknown( w- 1 >。for ( int i = 1 。 i <= w。 i+ > cout << w<<' ' 。cout << endl 。調(diào)用語句為unknown(4>。(2> voidunknown ( int n > cout << n % 10 。if ( int ( n / 10 >

11、 > unknown ( int ( n/ 10 > >。調(diào)用語句為unknown (582> 。(3> int unknown ( int m > int value。if ( ! m > value = 3 。3/15個人資料整理僅限學習使用elsevalue = unknown ( m-1 > + 5 。return value。執(zhí)行語句為cout << unknown (3>。三、填空題設單鏈表結構為structListNode int data。ListNode * link。下面的程序是以單鏈表為存儲結構, 實現(xiàn)二路

12、歸并排序的算法, 要求鏈表不另外占用存儲空間 , 排序過程中不移動結點中的元素, 只改各鏈結點中的指針, 排序后 r 仍指示結果鏈表的第一個結點。在初始狀態(tài)下, 所有待排序記錄鏈接在一個以r 為頭指針的單鏈表中。例如 ,kavU42VRUs在算法實現(xiàn)時，利用了一個隊列做為輔助存儲, 存儲各有序鏈表構成的歸并段的鏈頭指針。初始時 , 各初始歸并段為只有一個結點的有序鏈表。隊列的數(shù)據(jù)類型為Queue, 其可直接使用的相關操作有y6v3ALoS89置空隊列操作： makeEmpty ( >。將指針 x 加入到隊列的隊尾操作： EnQueue ( ListNode * x >。退出隊頭元素

13、 , 其值由函數(shù)返回的操作： ListNode * DlQueue ( > 。判隊列空否的函數(shù) , 空則返回 1, 不空則返回0： int IsEmpty( >。解決方法提示：程序首先對待排序的單鏈表進行一次掃描, 將它劃分為若干有序的子鏈表, 其表頭指針存放在一個指針隊列中。M2ub6vSTnP當隊列不空時 , 從隊列中退出兩個有序子鏈表, 對它們進行二路歸并 , 結果鏈表的表頭指針存放到隊列中。 0YujCfmUCw如果隊列中退出一個有序子鏈表后變成空隊列, 則算法結束。這個有序子鏈表即為所求。在算法實現(xiàn)時有 6 處語句缺失，請閱讀程序后補上。(1> 兩路歸并算法void

14、merge ( ListNode * ha , ListNode * hb,ListNode * & hc > eUts8ZQVRdListNode *pa, *pb, *pc 。if ( ha data <= hb data > hc = ha。 pa = ha link 。 pb = hb。sQsAEJkW5Telse hc = hb。 pb = hblink 。 pa = ha 。 pc = hc。while ( pa&& pb >if (> pclink = pa。 pc = pa。4/15個人資料整理僅限學習使用。else pc

15、link = pb。 pc = pb。if ( pa >pclink = pa。elsepc link = pb。(2> 歸并排序主程序voidmergesort ( ListNode * r > ListNode* s, t。 QueueQ。if ( !r > return 。s = r 。while ( s > t = s link 。while ( t != 0 && s data <= t data > s = t。 t = t link 。 GMsIasNXkAif ( t > slink = 0 。s = t。whil

16、e ( ! Q.IsEmpty ( > > r = Q.DlQueue( >。if ( Q.IsEmpty ( > > break 。s = Q.DlQueue( >。merge( r , s, t >。四、簡答題(1> 在一個有 n 個元素的順序表的第i 個元素 <1i n）之前插入一個新元素時，需要向后移動多少個元素？ TIrRGchYzg(2> 當一個棧的進棧序列為 1234567時，可能的出棧序列有多少種？6457321 是否是合理的出棧序列？ 7EqZcWLZNX(3> 簡單 <直接）選擇排序是一種穩(wěn)定的排序方法

17、嗎？試舉例說明？(4> 設有序順序表為 10, 20, 30, 40, 50, 60, 70，采用折半搜索時，搜索成功的平均搜索長度是多少？lzq7IGf02E五、綜合算法題試設計一個實現(xiàn)下述要求的查找運算函數(shù)Locate 。設有一個帶表頭結點的雙向鏈表L ，每個結點有4 個數(shù)據(jù)成員：指向前驅(qū)結點的指針llink 、指向后繼結點的指針rlink ，存放字符數(shù)據(jù)的成員data 和訪問頻度freq。所有結點的freq 初始時都為0。每當在鏈表上進5/15個人資料整理僅限學習使用行一次 Locate( L, x> 操作時，令元素值為x 的結點的訪問頻度freq 加 1，并將該結點前移，鏈

18、接到與它的訪問頻度相等的結點后面，使得鏈表中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。zvpgeqJ1hk【試卷答案】一、答案 :A ：B ：C：D：E：F：G：H ：I ：J： NrpoJac3v1二、答案：(1> 1223334444(2>285(3>18三、答案：pa data <= pb datapa = pa linkpb = pb linkQ.EnQueue( r >Q.EnQueue( s >Q.EnQueue( t >1nowfTG4KI四、答案：(1> n- i + 1(2> 可能的出棧序列有種

19、， 6457321 不是合理的出棧序列。(3> 是不穩(wěn)定的排序方法。下面就是不穩(wěn)定的例子。只要能舉出反例即可。 275275*512061 i = 1061275*512275 i = 2061275 *512275 i = 3061275 *275512 (4>ASLsucc= (1*1 + 2*2 + 3*4 > / 7 = 17 / 7五、答案：(1> 定義鏈表結構structDoubleListNode char data。int freq。DoubleListNode * llink , * rlink 。初始時，所有結點的freq 域的值都為0。(2>

20、 定義函數(shù)6/15個人資料整理僅限學習使用DoubleListNode * locate ( DoubleListNode * f。 char& x > fjnFLDa5Zo DoubleListNode *p , * q。p = f rlink 。/* 跳過表頭結點*/while ( p != NULL && p data != x > p = p rlink 。 /* 搜索 */ tfnNhnE6e5 if (p > p freq +。 q = p llink 。p rlink llink = q。 q rlink = p rlink 。/* 從鏈

21、中摘下p*/ HbmVN777sLwhile ( q != f && q freq < p freq > q =qllink 。p llink = q。p rlink = q rlink 。 qrlink llink = p。q rlink = p。/* 在 q 后面插入p*/return p。三、數(shù)據(jù)結構復習提要第一章有關數(shù)據(jù)結構和算法分析的基本知識本章主要討論貫穿和應用于整個數(shù)據(jù)結構課程始終的基本概念和性能分析方法。學習本章的內(nèi)容，將為后續(xù)章節(jié)的學習打下良好的基礎。V7l4jRB8Hs本章復習的要點：1、基本知識點要求理解的概念包括：數(shù)據(jù)，數(shù)據(jù)對象，數(shù)據(jù)元素或數(shù)

22、據(jù)成員，數(shù)據(jù)結構，數(shù)據(jù)類型，數(shù)據(jù)抽象，抽象數(shù)據(jù)類型，數(shù)據(jù)結構的抽象層次，面向?qū)ο螅瑢ο笈c類的關系，類的繼承關系，對象間的消息通信等。需要對各個概念進行區(qū)分與比較。例如，按照面向?qū)ο蠼＜夹g的要求，把建立對象類作為一個層次，把建立對象間的關系<即建立結構）作為另外的層次。因此，在軟件開發(fā)中做數(shù)據(jù)結構設計時，不但要設計對象類，類的屬性，類的操作，還要建立類的實例之間的關系。從這個角度考慮，把數(shù)據(jù)結構定義為數(shù)據(jù)對象及對象中各數(shù)據(jù)成員之間關系的集合是合理的。又例如，對象類class 或 struct 與 C 中的結構類型 struct 的區(qū)別在于前者不但有對象的狀態(tài)描述<數(shù)據(jù)成員），還加入

23、了操作< 成員函數(shù)），描述對象的行為，這樣可以體現(xiàn)一個完整的實體概念，而后者不行。再例如，傳統(tǒng)的數(shù)據(jù)結構概念從數(shù)據(jù)結構的邏輯結構、物理結構和相關操作等3個方面進行討論。它反映了數(shù)據(jù)結構設計的不同層次：邏輯結構屬于問題解決范疇，物理結構是邏輯結構在計算機中的存儲方式。但在面向?qū)ο箝_發(fā)模式中，本課程中涉及的數(shù)據(jù)結構都屬于基本數(shù)據(jù)結構，但有的屬于應用級的數(shù)據(jù)結構，如稀疏矩陣，字符串，棧與隊列，優(yōu)先級隊列，圖等；有的屬于實現(xiàn)級的數(shù)據(jù)結構，如數(shù)組，鏈表，堆，索引，散列表等。83lcPA59W92、有關算法的概念和簡單的算法性能分析方法算法的5 個特性表明算法的實現(xiàn)屬于面向過程的開發(fā)模式，即傳統(tǒng)的“

24、輸入計算輸出”模式。算法的應用要求明確算法的時間和空間代價。因此，必須理解算法的定義和算法的 5 個特性，掌握簡單的時間復雜度估計和空間復雜度估計方法<不討論程序復雜性）。7/15個人資料整理僅限學習使用mZkklkzaaP3、描述語言要求數(shù)據(jù)結構的描述既要體現(xiàn)算法的邏輯，又要體現(xiàn)面向?qū)ο蟮母拍?，需要一種能夠兼有面向?qū)ο蠛兔嫦蜻^程雙重特性的描述語言。傳統(tǒng)的Pascal 語言和 C 語言只是面向過程的語言，不能適應面向?qū)ο蟮拈_發(fā)模式。因此，采用C+ 語言描述。要求學員基本掌握C+ 語言的基本概念和用C+ 語言編寫應用程序的基本技術。例如，用類定義抽象數(shù)據(jù)類型的方式，定義模板類、抽象類的方法

25、，函數(shù)與參數(shù)的定義，建立類<公有、私有）繼承的方法，例外與異常的處理等等，都需要掌握。AVktR43bpw4、復習參考題 ： 1- 1， 1- 2， 1- 4， 1- 7， 1- 8， 1- 9第二章數(shù)組本章主要討論數(shù)組抽象數(shù)據(jù)類型及利用數(shù)組實現(xiàn)的順序表、字符串等數(shù)據(jù)結構。它們都是線性結構。但數(shù)組是直接存取結構，可以根據(jù)數(shù)組元素的下標直接在數(shù)組中存取該元素，而利用它實現(xiàn)的順序表是順序存取結構，所有數(shù)據(jù)元素集中存儲于表的前端。字符串是順序表的特化。ORjBnOwcEd本章復習的要點：1、基本知識點理解作為抽象數(shù)據(jù)類型定義的數(shù)組類，掌握在C+ 中數(shù)組的定義和初始化方法，明確靜態(tài)數(shù)組和動態(tài)數(shù)組

26、的不同特點和使用，特別需要注意的是數(shù)組的存儲結構不一定是一個連續(xù)的存儲空間，當數(shù)組存放于一個連續(xù)的存儲空間時叫做數(shù)組的順序存儲方式。要求掌握一維數(shù)組、二維數(shù)組、三維數(shù)組的地址計算方法。需要明確：數(shù)組是一種實現(xiàn)級的結構。 2MiJTy0dTT其次，需要理解順序表的定義和特點，順序表的類定義及其主要操作，如搜索、插入和刪除的實現(xiàn)，掌握對它們的性能估計，包括搜索算法的平均搜索長度，插入與刪除算法中的對象平均移動次數(shù)。還要掌握順序表實例的定義和使用事例。gIiSpiue7A此外，需要理解字符串的定義，字符串抽象數(shù)據(jù)類型的類定義，字符串中各種重載操作的實現(xiàn)和使用，簡單的模式匹配算法和匹配事例。uEh0U

27、1Yfmh2、算法設計靜態(tài)數(shù)組對象的定義，動態(tài)數(shù)組對象的定義數(shù)組中數(shù)組元素的原地逆置遞歸計算數(shù)組長度、數(shù)組中所有元素的和及平均值在順序表中搜索值為item 的元素，在有序順序表中搜索值為item 的元素在有序順序表中插入新元素item 到第 i 個位置在有序順序表中刪除第i 個元素兩個有序順序表的合并，m 個有序順序表的合并3、復習參考題： 2-3，2-5，2-7，2-8，2-9，2-10，2-13， 2-14， 2-15， 2-16IAg9qLsgBX8/15個人資料整理僅限學習使用第三章鏈接表本章主要討論最簡單的鏈表結構單鏈表。詳細地介紹了單鏈表的抽象數(shù)據(jù)類型，單鏈表的類定義，相應操作的實

28、現(xiàn)，引入了帶表頭結點的單鏈表結構。進一步定義了用模板描述的單鏈表類。作為一種應用，討論了一元多項式的類定義及其加法操作的實現(xiàn)。此外，討論了循環(huán)鏈表和雙向鏈表。在復習這一章時需要對C+ 語言中的指針和引用類型的使用有清楚的理解。對帶表頭結點的鏈表和不帶表頭結點的鏈表在插入、刪除、搜索時的差別有清楚的認識。而且需要明確：鏈表是一種實現(xiàn)級的結構。本章復習的要點：1、基本知識點WwghWvVhPE單鏈表是一種線性結構，鏈表各結點的物理存儲可以是不連續(xù)的，因此各結點的邏輯次序與物理存放次序可以不一致。必須理解單鏈表的定義和特點，單鏈表的抽象數(shù)據(jù)類型和類定義，單鏈表成員函數(shù)，如構造函數(shù)、搜索、插入、刪除等

29、操作的實現(xiàn)，對比帶表頭結點單鏈表的搜索、插入、刪除操作，比較其優(yōu)缺點。其次是循環(huán)鏈表的定義和特點，它與單鏈表的差別，它的搜索、插入、刪除操作的實現(xiàn)。最后是雙向鏈表的定義，它的插入與刪除操作的實現(xiàn)。asfpsfpi4k2、算法設計單鏈表的迭代求解算法，包括統(tǒng)計鏈表結點個數(shù)，在鏈表中尋找與給定值value 匹配的結點，在鏈表中尋找第i 個結點，在鏈表中第i 個位置插入新結點，刪去第i 個結點，單鏈表各結點順序逆轉(zhuǎn)算法，在單鏈表中按從左到右和從右到左的順序遍歷的逆轉(zhuǎn)鏈算法。 ooeyYZTjj1帶表頭結點的單鏈表的迭代算法，包括統(tǒng)計鏈表結點個數(shù)，在鏈表中尋找與給定值value 匹配的結點，在鏈表中尋

30、找第 i 個結點，在鏈表中第 i 個位置插入新結點，刪去第 i 個結點，連續(xù)刪除鏈表中含有 value 值的結點，兩個有序鏈表的合并。 BkeGuInkxI單鏈表的遞歸算法，包括統(tǒng)計鏈表結點個數(shù)，在鏈表中尋找與給定值value 匹配的結點，在鏈表中尋找第i 個結點，求鏈表各結點值的和，求鏈表各結點的值的平均值。PgdO0sRlMo循環(huán)鏈表的迭代算法：包括統(tǒng)計鏈表結點個數(shù)，在鏈表中尋找與給定值value 匹配的結點，在鏈表中尋找第i 個結點，在鏈表中第i 個位置插入新結點，刪去第i 個結點，將循環(huán)鏈表鏈入單鏈表的表頭。3cdXwckm15多項式的建立，兩個多項式的相加，兩個多項式的相減。用單鏈表

31、實現(xiàn)字符串操作，每個結點僅存一個字符。3、復習參考題 ：3- 1， 3- 2， 3- 6， 3- 8， 3- 9， 3- 10第四章棧與隊列本章主要討論3 種線性結構：棧、隊列與優(yōu)先級隊列。這3 種結構都是順序存取的表，而且都是限制存取點的表。棧限定只能在表的一端<棧頂）插入與刪除，其特點是先進后出。隊列和優(yōu)先級隊列限定只能在表的一端<隊尾）插入在另一端<隊頭）刪除，不過優(yōu)先級隊列在插入和刪除時需要根據(jù)數(shù)據(jù)對象的優(yōu)先級做適當?shù)恼{(diào)整，令優(yōu)先級最高的對象9/15<heap），本個人資料整理僅限學習使用調(diào)整到隊頭，其特點是優(yōu)先級高的先出。而隊列不調(diào)整，其特點是先進先出。這幾種

32、結構在開發(fā)各種軟件時非常有用。h8c52WOngM本章復習的要點：1、基本知識點要求理解棧的定義和特點，棧的抽象數(shù)據(jù)類型和在遞歸和表達式計算中的使用，在棧式鐵路調(diào)車線上當進棧序列為 1, 2, 3, , n 時，可能的出棧序列計數(shù)，棧的順序存儲表示和鏈接存儲表示，特別要注意，鏈式棧的棧頂應在鏈頭，插入與刪除都在鏈頭進行。另外，需要理解隊列的定義和特點，隊列的抽象數(shù)據(jù)類型和在分層處理中的使用，隊列的順序存儲表示 <循環(huán)隊列）和鏈接存儲表示，需要注意的是，鏈式隊列的隊頭應在鏈頭，隊尾應在鏈尾。還需要理解優(yōu)先級隊列的定義和特點。優(yōu)先級隊列的最佳存儲表示是堆章介紹的表示看懂即可。v4bdyGio

33、us2、算法設計棧的 5 種操作 <進棧、退棧、取棧頂元素、判?？?、置空棧）的在順序存儲表示下的實現(xiàn)，以及在鏈接存儲表示下的實現(xiàn)。J0bm4qMpJ9使用棧的后綴表達式計算算法雙棧共用一個數(shù)組的進棧、退棧、置空棧、判?？账惴皸M、?？諚l件使用兩個棧模擬一個隊列時的進隊列和出隊列算法循環(huán)隊列的進隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn)使用 tag 區(qū)分隊列空和隊列滿的循環(huán)隊列的進隊列和出隊列操作的實現(xiàn)鏈式隊列的進隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn)使用隊尾指針rear 和隊列長度length 的鏈式隊列的進隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的

34、實現(xiàn)XVauA9grYP隊列在分層處理中的使用事例<楊輝三角形按層次打?。╇p端隊列的順序存儲表示及其進隊列、出隊列算法及隊空、隊滿條件3、復習參考題 ：4- 2， 4- 4， 4- 9， 4- 10， 4- 12， 4-14第五章 遞歸與廣義表本章主要討論遞歸過程和廣義表。一個遞歸的定義可以用遞歸的過程計算，一個遞歸的數(shù)據(jù)結構可以用遞歸的過程實現(xiàn)它的各種操作，一個遞歸問題也可以用遞歸的過程求解。因此，遞歸算法的設計是必須掌握的基本功。遞歸算法的一般形式：bR9C6TJscwvoidp( 參數(shù)表 > if ( 遞歸結束條件 >可直接求解步驟；基本項else p ( 較小的參數(shù)&

35、gt;。 歸納項在設計遞歸算法時，可以先考慮在什么條件下可以直接求解。如果可以直接求解，考慮求解的步驟，設計基本項；如果不能直接求解，考慮是否可以把問題規(guī)?？s小求解，設計歸納項，從而給出遞歸求解的算法。必須通過多個遞歸過程的事例，理解遞歸。但需要10/15個人資料整理僅限學習使用說明的是，遞歸過程在時間方面是低效的。pN9LBDdtrd廣義表是一種表，它的特點是允許表中套表。因此，它不一定是線性結構。它可以是復雜的非線性結構，甚至允許遞歸?？梢杂枚嘀劓湵矶x廣義表。在討論廣義表時，特別注意遞歸在廣義表操作實現(xiàn)中的應用。DJ8T7nHuGT本章復習的要點：1、基本知識點要求理解遞歸的概念：什么是

36、遞歸？遞歸的定義、遞歸的數(shù)據(jù)結構、遞歸問題以及遞歸問題的遞歸求解方法。理解遞歸過程的機制與利用遞歸工作棧實現(xiàn)遞歸的方法。通過迷宮問題，理解遞歸解法，從而掌握利用棧如何實現(xiàn)遞歸問題的非遞歸解法。在廣義表方面，要求理解廣義表的概念，廣義表的幾個性質(zhì)，用圖表示廣義表的方法，廣義表操作的使用，廣義表存儲結構的實現(xiàn)，廣義表的訪問算法，以及廣義表的遞歸算法。 QF81D7bvUA 2、算法設計求解漢諾塔問題，掌握分治法的解題思路。求解迷宮問題、八皇后問題，掌握回溯法的解題思路。對比單鏈表的遞歸解法和非遞歸解法，掌握單向遞歸問題的迭代解法。計算廣義表結點個數(shù)，廣義表深度，廣義表長度的遞歸算法。輸出廣義表各個

37、原子所在深度的非遞歸算法。判斷兩個廣義表相等的遞歸算法。廣義表的按深度方向遍歷和按層次<廣度）方向遍歷的遞歸算法。使用棧的廣義表的按深度方向遍歷的非遞歸算法。遞歸的廣義表的刪除算法3、復習參考題 ： 5- 1， 5- 3， 5- 4， 5- 5， 5- 7， 5- 8第六章樹與森林本章主要介紹了樹與森林、二叉樹的定義、性質(zhì)、操作和相關算法的實現(xiàn)。特別是二叉樹的遍歷算法，它們與許多以此為基礎的遞歸算法都必須認真學習。因為樹的先根遍歷次序與對應二叉樹表示的前序遍歷次序一致，樹的后根遍歷次序與對應二叉樹的后序遍歷次序一致，因此可以據(jù)此得出樹的遍歷算法。線索化二叉樹是直接利用二叉鏈表的空鏈指針記

38、入前驅(qū)和后繼線索，從而簡化二叉樹的遍歷。堆是一種二叉樹的應用，可以用它作為優(yōu)先級隊列的實現(xiàn)。它的存儲表示是完全二叉樹的順序存儲方式，它的定義不要求堆中的數(shù)據(jù)有序，但要求雙親結點與子女結點必須滿足某種關系。本章最后討論霍夫曼樹。這種樹是擴充二叉樹，要求在外結點上帶有權值，在構造霍夫曼樹時必須注意一個新結點的左子女上所帶的權值小于右子女上所帶的權值，這不是霍夫曼樹必須這樣，而是實現(xiàn)算法造成這種結果。此外，作為霍夫曼樹的應用，引入霍夫曼編碼。通常讓霍夫曼樹的左分支代表編碼“ 0 ”，右分支代表編碼“1 ”，得到霍夫曼編碼。這是一種不等長編碼，可以有效地實現(xiàn)數(shù)據(jù)壓縮。4B7a9QFw9h本章復習的要點

39、是：1、基本知識點11/15個人資料整理僅限學習使用要求理解樹和森林的定義，樹的抽象數(shù)據(jù)類型，二叉樹的定義，二叉樹的性質(zhì)，二叉樹的抽象數(shù)據(jù)類型，二叉樹的數(shù)組表示和鏈表存儲表示。要求掌握二叉樹的遍歷，包括中序遍歷、前序遍歷、后序遍歷方法，要求理解二叉樹的計數(shù)方法及從二叉樹遍歷結果得到二叉樹的方法。對于線索化二叉樹，要求理解什么是線索，中序線索化二叉樹的結構特性及尋找某結點的前驅(qū)和后繼的方法。此外，需要理解堆的定義及其實現(xiàn)的方法，本章只考慮用完全二叉樹的順序存儲來實現(xiàn)。還需要理解堆的建立，插入與刪除過程。要求掌握樹 / 森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法。最后要求掌握霍夫曼樹的實現(xiàn)方法及霍夫曼編碼的

40、概念。 ix6iFA8xoX2、算法設計建立二叉樹的遞歸算法。前序、中序、后序遍歷二叉樹的遞歸算法。使用棧的前序、中序、后序遍歷的非遞歸算法。統(tǒng)計二叉樹結點個數(shù)，二叉樹葉結點個數(shù)，二叉樹高度的遞歸算法。自左向右鏈接二叉樹葉結點的遞歸算法。判斷兩棵二叉樹相等和交換二叉樹左、右子女指針的遞歸算法。通過二叉樹的遍歷建立前序線索化二叉樹和中序線索化二叉樹的算法。中序線索化二叉樹上的中序遍歷算法。前序線索化二叉樹上的前序遍歷算法。后序線索化二叉樹上的后序遍歷算法。利用堆實現(xiàn)優(yōu)先級隊列的操作。堆的自上向下和自下向上的調(diào)整算法。堆的插入與刪除算法。樹的先根、后根、層次遍歷算法<基于樹的二叉樹表示）。建

41、立霍夫曼樹的算法3、 復習參考題： 6- 4， 6- 6， 6- 7， 6- 8， 6- 9， 6- 10， 6- 12，6- 14， 6- 16， 6- 17， 6- 18， 6-19， 6- 20，6- 21， 6- 22wt6qbkCyDE第七章集合與搜索集合是最基本的抽象數(shù)據(jù)類型之一。本章討論了集合的三種存儲表示：位數(shù)組表示、有序鏈表表示、并查集。在本章的后半部分，討論了與集合相關的搜索方法和簡單的性能分析方法，包括適用于靜態(tài)搜索表的順序搜索和折半搜索及代表動態(tài)搜索表的二叉搜索樹和 AVL 樹。可以使用擴充的二叉搜索樹描述順序搜索和折半搜索，從而推導出估算搜索效率的公式。靜態(tài)搜索表在整

42、個程序的運行期間結構不會變化，其搜索效率隨著表中對象的個數(shù) n 不斷增長。動態(tài)搜索表因各個對象的輸入順序不同，得到的搜索表的形態(tài)不同，典型的是二叉搜索樹。在具有 n 個對象的二叉搜索樹中，搜索效率最高的是高度最低的二叉搜索樹。為確保二叉搜索樹始終保持搜索效率最高，必須在輸入新的對象時判斷二叉搜索樹是否“失去平衡”，并進行適當?shù)钠胶庑D(zhuǎn)，使二叉搜索樹的高度降到最低。這就是AVL 樹。在 AVL 樹的討論中，4 種平衡旋轉(zhuǎn)，選擇參加平衡旋轉(zhuǎn)的3 個結點是關鍵，必須12/15個人資料整理僅限學習使用加以注意。Kp5zH46zRk本章復習的要點是：1、基本知識點必須理解集合及其表示方法，包括位數(shù)組表示

43、、有序鏈表表示及其相關操作的實現(xiàn)算法集合及其表示。理解并查集實現(xiàn)的方法。理解搜索的概念，理解靜態(tài)搜索表結構，掌握靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法，掌握等搜索概率的最佳二叉搜索樹的構造方法，并掌握 AVL 樹的構造、插入、刪除時的調(diào)整方法及其性能分析，重點是 AVL 樹的定義、平衡化旋轉(zhuǎn)、 AVL 樹的插入和刪除、 AVL 樹的高度。 Yl4HdOAA612、算法設計用有序鏈表表示集合時的求集合的并、交、差的算法并查集中的構造函數(shù)、求根及合并算法并查集中根據(jù)樹的高度和根據(jù)樹中結點個數(shù)進行合并的算法設置監(jiān)視哨的順序搜索算

44、法和不設監(jiān)視哨的順序搜索算法有序順序表的順序搜索算法有序順序表的折半搜索的遞歸算法和非遞歸算法二叉搜索樹的搜索、插入和刪除算法計算 AVL 樹中指定結點高度的遞歸算法及利用此算法計算結點平衡因子的算法3、 復 習 參 考 題 ： 7- 2， 7- 4， 7- 5， 7- 7， 7- 8，7- 9， 7- 10， 7- 11， 7- 12， 7- 15， 7-16， 7- 18，7- 19， 7- 20， 7- 22ch4PJx4BlI第八章圖圖是一種重要的非線性結構。它的特點是每一個頂點都可以與其它頂點相關聯(lián)，與樹不同，圖中各個頂點的地位都是平等的，對頂點的編號都是人為的。通常，定義圖由兩個集

45、合構成：一個是頂點的非空有窮集合，一個是頂點與頂點之間關系(邊 >的有窮集合。對圖的處理要區(qū)分有向圖與無向圖。它的存儲表示可以使用鄰接矩陣，可以使用鄰接表，前者屬順序表示，后者屬鏈接表示。在本章著重討論了圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，附帶引入了生成樹與生成森林的概念。對于帶權圖，給出了最小生成樹的兩種方法：Prim 算法和 Kruskal 算法，后者使用了最小堆和并查集作為它的輔助求解手段。在解決最短路徑問題時，采用了逐步求解的策略。最后討論了作工程計劃時常用的活動網(wǎng)絡。涉及的主要概念是拓撲排序和關鍵路徑，在解決應用問題時它們十分有用。qd3YfhxCzo本章復習的要點是：1、基本

46、知識點主要要求理解圖的基本概念，包括圖的定義、圖的連通性、圖的路徑和路徑長度、圖中各頂點的度及度的度量、無向連通圖的最大邊數(shù)和最小邊數(shù)，有向強連通圖的最大邊數(shù)與最小邊數(shù)等。掌握圖的存儲表示，包括鄰接矩陣和鄰接表，以及這些存儲表示上的典型操作，如構造、求根、找第一個鄰接頂點、找下一個鄰接頂點等操作的實現(xiàn)算法。并要求掌握圖的兩種遍歷算法：深度優(yōu)先搜索和廣度優(yōu)先搜索算法，以及求解連通性問題的方13/15個人資料整理僅限學習使用法。理解求解關節(jié)點及構造重連通圖的方法。此外，要求掌握構造最小生成樹的Prim 算法和 Kruskal 方法，掌握活動網(wǎng)絡的拓撲排序算法，掌握求解關鍵路徑的方法。需要注意的是，

47、讓某個關鍵活動提前完成，是否能讓整個工程提前完成。E836L11DO52、算法設計建立無向帶權圖的鄰接表的算法，要求輸入邊的數(shù)目隨機而定。圖的深度優(yōu)先搜索的遞歸算法。利用圖的深度優(yōu)先搜索的遞歸算法建立圖的深度優(yōu)先生成森林(用左子女右兄弟表示 >的算法。圖的廣度優(yōu)先搜索算法。利用圖的廣度優(yōu)先搜索算法建立圖的廣度優(yōu)先生成森林(用左子女右兄弟表示>的算法。求解最小生成樹的Prim 算法，注意nearvex 和 lowcost 輔助數(shù)組的變化。求解最小生成樹的Kruskal 算法，注意minheap 和 UFset 的變化。求解最短路徑的dijkstra 算法，注意dist 輔助數(shù)組的變化。有向圖中求解拓撲排序的算法，要求用鄰接表作為圖的存儲表示。注意算法執(zhí)行過程中入度為零的頂點棧的變化。 S42ehLvE3M有向圖中求解拓撲排序的算法，要求用鄰接矩陣作為圖的存儲表示。3、 復 習 參 考 題 ： 8- 4， 8- 5， 8- 7， 8- 8， 8- 9， 8- 10， 8- 11，8- 1