數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講筆記

1、1、選擇題和填空題：這兩部分共56分，這56分中大部分分?jǐn)?shù)是很好得的，做好下面兩條，相信你一定能拿到不少分。理解和掌握串講中“考核知識點(diǎn)的內(nèi)容” 做相關(guān)的練習(xí)題，尤其是歷年的真題，可參照機(jī)械工業(yè)出版社出版的數(shù)據(jù)結(jié)構(gòu)導(dǎo)論學(xué)習(xí)輔導(dǎo)與真題解析。2、應(yīng)用題：共6小題，每小題5分，全書可以以應(yīng)用題的方式出考題的17類知識點(diǎn)（已經(jīng)考過的有12類），我后面會結(jié)合歷年考同學(xué)題給大家講解可以以應(yīng)用題的方式出考題的17類知識點(diǎn)，同學(xué)應(yīng)該很好的理解和掌握已經(jīng)考過的12類知識點(diǎn)，對沒有考過的四類知識點(diǎn)，要看懂教材上的相關(guān)例題。3、算法設(shè)計：考核點(diǎn)主要集中在第2章的有關(guān)單鏈表的算法、第4章的二叉樹遍歷的有關(guān)算法和第8章

2、的排序的相關(guān)算法，我后面會結(jié)合歷年考題給大家講解相關(guān)算法，同學(xué)在理解的基礎(chǔ)上要多搜集一些相關(guān)算法.11類可能出應(yīng)用題的知識點(diǎn)1 棧的操作2000/4 2001/10 2002/10 2004/1 考過1）已知出棧序列，寫出可能的入棧序列并分析操作過程。2）已知入棧序列，寫出可能的出棧序列并分析操作過程。2004/1如下圖所示，輸入元素為（A，B，C），在棧的輸出端得到一個輸出序列ABC，求出在棧的輸入端所有可能的輸入序列。 輸出端輸入端棧ABC【分析】A，B，C三個字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA六種，按堆棧操作的先進(jìn)后出（或后進(jìn)先出）的原則，只有輸入序列為

3、BCA時，輸出無法得到ABC。因為輸入序列為BCA時，要想先輸出A，必須BCA均入棧，但這樣只能得到序列ACB。其余五種輸入序列都可在輸出端得到序列ABC?！窘獯稹緼BC、ACB、BAC、CAB、CBA2隊列的操作分析順序隊中元素入隊出隊操作及隊列的狀態(tài)。（考過）2003/10設(shè)有一順序隊列sq，容量為5，初始狀態(tài)時sqfront=sqrear=0，畫出做完下列操作后隊列及其頭尾指針的狀態(tài)變化情況，若不能入隊，請簡述其理。 （1） d，e，b入隊（2） d，e出隊（3） i，j入隊（4） b出隊（5） n，o，p入隊【解答】隊列及其頭尾指針的狀態(tài)變化情況如下圖所示Sq.frontSq.rear

4、bedSq.frontSq.rearbSq.frontSq.rearjbiSq.frontSq.rearjiSq.frontSq.rear（a）初態(tài) （b）d，e，b入隊 （c） d，e出隊 （d） i，j入隊 （e）b出隊第5步操作無法進(jìn)行，因隊列已滿。3二叉樹的存儲結(jié)構(gòu)1） 給出一棵二叉樹，畫出二叉鏈表示意圖及順序存儲示意圖。（2000/10 2003/10 2004/10考過） 2003/10畫出下列二叉樹的二叉鏈表表示圖。 BEDFHGACB【解答】二叉樹的二叉鏈表表示BADCGFHE2） 給出二叉樹的順序存儲示意圖，畫出二叉樹。（2005/1考過）2005/1已知某二叉樹的順序存儲結(jié)

5、構(gòu)如下所示，試畫出該二叉樹。ABCDEFG【分析】按照給出的順序存儲結(jié)構(gòu)，先繪制出一棵包括空結(jié)點(diǎn)的完全二叉樹，然后去掉空結(jié)點(diǎn)就是所求的二叉樹。【解答】所求二叉樹如下圖ACBDEGF4二叉樹的遍歷1）給出一棵二叉樹，寫出對該二叉樹進(jìn)行先根遍歷、中根遍歷及后根遍歷的序列。（2001/10 2004/1 2005/10考過）2005/10對于如下圖所示二叉樹，分別寫出其先根遍歷、中根遍歷和后根遍歷的結(jié)點(diǎn)訪問序列。BEDFACB【分析】根據(jù)二叉樹三種遍歷方法的原理，很容易寫出該二叉樹的先根遍歷、中根遍歷和后根遍歷的結(jié)點(diǎn)訪問序【解答】先根遍歷的結(jié)點(diǎn)訪問序：A，B，D，E，F(xiàn)，C中根遍歷的結(jié)點(diǎn)訪問序：B，

6、F，E，D，A，C后根遍歷的結(jié)點(diǎn)訪問序：F，E，D，B，C，A2）給出一棵二叉樹的先根遍歷和中根遍歷序列，恢復(fù)二叉樹，寫出后根遍歷的序列。（2002/10考過）2002/10現(xiàn)有某二叉樹，按先根遍歷的序列為ABDEFCGH，按中根遍歷的序列為DEFBGHCA，試畫出此二叉樹。 【分析】由先根遍歷和中根遍歷恢復(fù)二叉樹的方法：在先根序列中確定根結(jié)點(diǎn)（最前面那個結(jié)點(diǎn)一定是根結(jié)點(diǎn)），然后根據(jù)根結(jié)點(diǎn)在中根序列中的位置分出根結(jié)點(diǎn)的左、右子樹（根結(jié)點(diǎn)前面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)，根結(jié)點(diǎn)后面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)）。恢復(fù)該二叉樹的任何一棵子樹的過程仍然遵循這個原則?！窘獯稹慷鏄淙缦聢D所

7、示BCDAKGHFE3）給出一棵二叉樹的后根遍歷和中根遍歷序列，恢復(fù)二叉樹，寫出先根遍歷的序列。（未考過，但可能考注意第四章的考核知識點(diǎn)的講解）5樹的存儲結(jié)構(gòu)1）給出一棵樹，畫出該樹的雙親表示法、孩子鏈表表示法、帶雙親的孩子鏈表表示法及孩子兄弟鏈表表示法的示意圖。（2000/4考過）2）給出一棵樹的某一種存儲結(jié)構(gòu)的示意圖，畫出對應(yīng)的樹。（未考過）6樹的遍歷給出一棵樹，寫出對該樹進(jìn)行先根遍歷、后根遍歷及層次遍歷的序列。（未考過）7二叉樹與樹、林的相互轉(zhuǎn)換1）將一棵二叉樹轉(zhuǎn)換為樹。（未考過）2）將一棵樹轉(zhuǎn)換為二叉樹。（未考過）3）將林轉(zhuǎn)換為一棵二叉樹。（未考過）4）將二叉樹轉(zhuǎn)換為林。（未考過）8夠

8、造哈夫曼樹給出一組權(quán)值，構(gòu)造一棵哈夫曼樹并求帶權(quán)路徑長度。（未考過）9圖的存儲結(jié)構(gòu)1）給出一個圖，畫出該圖的鄰接矩陣或鄰接表存儲示意圖。（考過）2005/10試給出下圖的鄰接矩陣和鄰接表表示。【分析】鄰接矩陣存儲方法是用一個二維數(shù)組存放頂點(diǎn)之間關(guān)系的信息。對于不帶權(quán)的有向圖，如果一個頂點(diǎn)到另一個頂點(diǎn)有邊，用1表示；否則，用0表示；對于帶權(quán)的有圖，如果一個頂點(diǎn)到另一個頂點(diǎn)有邊，用邊的權(quán)值表示；否則，用表示。 鄰接表存儲方法的核心思想是對于具有n個頂點(diǎn)的圖建立n個線性鏈表。每一個鏈表最前面都分別設(shè)置一個稱之為表頭結(jié)點(diǎn)的結(jié)點(diǎn)，n個結(jié)點(diǎn)構(gòu)成一個數(shù)組結(jié)構(gòu)。第i個鏈表中的每一個鏈結(jié)點(diǎn)稱之為表結(jié)點(diǎn)。對帶權(quán)的

9、圖，其鄰接表中的每個表結(jié)點(diǎn)都要增加一個權(quán)值域?！窘獯稹款}中圖的鄰接矩陣為：V1V2V3V4V5V1 V2 V3 V4 V5題中圖的鄰接表為：V1V3V4V5V222344627311213382）給出一個圖的鄰接表，畫出該圖的所有連通分量。（考過） 2002/10已知無向圖G的鄰接表如下圖所示，請畫出其所有的連通分量。 V1V3V4V5V242355113【分析】根據(jù)鄰接表，很容易畫出其所有的連通分量?！窘獯稹慨嫵龅倪B通分量如下圖所示V1V3V5V2V4V2V23）給出一個圖的鄰接矩陣，畫出該圖的所有連通分量。（考過）2003/1V0V1V2V3V4V0 V1 V2 V3 V4已知無向圖G的鄰

10、接矩陣如下圖。假設(shè)對其訪問時每行元素必須從右到左，請畫出其所有的連通分量，并且寫出按深度優(yōu)先搜索時各連通分量的訪問序列。 【分析】根據(jù)鄰接表，很容易畫出其所有的連通分量?！窘獯稹慨嫵龅倪B通分量如下圖所示V1V4V2V2V3V0V2 深度優(yōu)先搜索時各連通分量的訪問序列：V1V2V4 V0V310圖的遍歷1）給出一個圖的鄰接表，寫出從某一點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。（2000/10 2001/10 2004/1 2004/10考過） 2004/1已知無向圖G的鄰接表如下圖所示，請寫出其從頂點(diǎn)V2開始的深度優(yōu)先搜索的序列。 V1V3V4V5V23252141543234235【分

11、析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲結(jié)構(gòu)，所得到的遍歷序列是惟一的。 【解答】深度優(yōu)先搜索序列：V2V5V3V1V42）給出一個圖的鄰接矩陣，寫出從某一點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。（2003/10考過）V0V1V2V3V4V0 V1 V2 V3 V42003/10已知無向圖G的鄰接矩陣如下圖所示，假設(shè)對其每行元素訪問時必須從右到左，請寫出從V0開始的深度優(yōu)先搜索的序列。 【分析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲結(jié)構(gòu)，所得到的遍歷序列是惟一的。 【解答】深度優(yōu)先搜索序列：V0V2V4V3V111最小生成樹給出一個帶權(quán)圖，畫出所有可能的最小生成樹。（2005/1 2006/1考過） 2006/1試用Prim算法構(gòu)造下圖的最小生成樹，要求分步給出構(gòu)造過程。V2V2