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

1、數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講筆記1）已知出棧序列，寫出可能的入棧序列并分析操作過程。2）已知入棧序列，寫出可能的出棧序列并分析操作過程。2004/1 如下圖所示，輸入元素為（ A，B，C），在棧的輸出端得到一個(gè)輸出序列 ABC ，求出在棧的輸入端所有可能的輸入序列。AB輸輸?！痉治觥?A，B，C 三個(gè)字符排成的序列可以有：ABC 、ACB 、BAC 、BCA 、CAB 、CBA六種，按堆棧操作的先進(jìn)后出（或后進(jìn)先出）的原則，只有輸入序列為 BCA 時(shí)，輸出無法得到 ABC 。因?yàn)檩斎胄蛄袨?BCA 時(shí)，要想先輸出 A，必須 BCA 均入棧，但這樣只能得到序列 ACB 。其余五種輸入序列都可在輸出端得到序列

2、 ABC ?！窘獯稹?ABC 、ACB 、BAC 、CAB 、CBA2隊(duì)列的操作分析順序隊(duì)中元素入隊(duì)出隊(duì)操作及隊(duì)列的狀態(tài)。（考過）2003/10 設(shè)有一順序隊(duì)列 sq，容量為 5，初始狀態(tài)時(shí) sqfront=sq rear=0 ，畫出做完下列操作后隊(duì)列及其頭尾指針的狀態(tài)變化情況， 若不能入隊(duì)，請(qǐng)簡述其理。1） d，e，b 入隊(duì)2） d，e 出隊(duì)3） i，j 入隊(duì)4） b 出隊(duì)5） n，o，p 入隊(duì)【解答】隊(duì)列及其頭尾指針的狀態(tài)變化情況如下圖所示jSq.r jSq.rbiiSq.fSq. b Sq.r bSq.feSq.fdSq.rSq.fSq.f（ a）初態(tài)（ b） d，e， b 入隊(duì)（ c）

3、d， e 出隊(duì)（ d） i， j 入隊(duì)（ e）b 出隊(duì)第 5 步操作無法進(jìn)行，因隊(duì)列已滿。3二叉樹的存儲(chǔ)結(jié)構(gòu)1） 給出一棵二叉樹，畫出二叉鏈表示意圖及順序存儲(chǔ)示意圖。 （ 2000/10 2003/10 2004/10考過）2003/10畫出下列二叉樹的二叉鏈表表示圖。ACBD E FG H【解答】二叉樹的二叉鏈表表示ABCDEGH2） 給出二叉樹的順序存儲(chǔ)示意圖，畫出二叉樹。（2005/1考過）2005/1 已知某二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下所示，試畫出該二叉樹。A B C D E F G 【分析】按照給出的順序存儲(chǔ)結(jié)構(gòu)， 先繪制出一棵包括空結(jié)點(diǎn)的完全二叉樹， 然后去掉空結(jié)點(diǎn)就是所求的二叉樹?！?/p>

4、解答】所求二叉樹如下圖ABCDEFG4二叉樹的遍歷1）給出一棵二叉樹，寫出對(duì)該二叉樹進(jìn)行先根遍歷、中根遍歷及后根遍歷的序列。 （2001/10 2004/1 2005/10考過）2005/10對(duì)于如下圖所示二叉樹， 分別寫出其先根遍歷、中根遍歷和后根遍歷的結(jié)點(diǎn)訪問序列。ABCBDEF【分析】根據(jù)二叉樹三種遍歷方法的原理，很容易寫出該二叉樹的先根遍歷、 中根遍歷和后根遍歷的結(jié)點(diǎn)訪問序【解答】先根遍歷的結(jié)點(diǎn)訪問序： A，B，D，E，F(xiàn)，C中根遍歷的結(jié)點(diǎn)訪問序：B，F(xiàn)，E，D，A ，C后根遍歷的結(jié)點(diǎn)訪問序：F，E，D，B，C， A2）給出一棵二叉樹的先根遍歷和中根遍歷序列，恢復(fù)二叉樹，寫出后根遍歷的

5、序列。 （2002/10考過）2002/10 現(xiàn)有某二叉樹，按先根遍歷的序列為 ABDEFCGH ，按中根遍歷的序列為 DEFBGHCA ，試畫出此二叉樹?！痉治觥坑上雀闅v和中根遍歷恢復(fù)二叉樹的方法：在先根序列中確定根結(jié)點(diǎn) （最前面那個(gè)結(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ù)該二叉樹的任何一棵子樹的過程仍然遵循這個(gè)原則?！窘獯稹慷鏄淙缦聢D所示ABDCGFH3）給出一棵二叉樹的后根遍歷和中根遍歷序列，恢復(fù)二叉樹，寫出先根遍歷的序列。 （未考過，但可能考注意

6、第四章的考核知識(shí)點(diǎn)的講解）5樹的存儲(chǔ)結(jié)構(gòu)1）給出一棵樹，畫出該樹的雙親表示法、孩子鏈表表示法、帶雙親的孩子鏈表表示法及孩子兄弟鏈表表示法的示意圖。 （2000/4 考過）2）給出一棵樹的某一種存儲(chǔ)結(jié)構(gòu)的示意圖，畫出對(duì)應(yīng)的樹。（未考過）6樹的遍歷給出一棵樹， 寫出對(duì)該樹進(jìn)行先根遍歷、 后根遍歷及層次遍歷的序列。（未考過）7二叉樹與樹、林的相互轉(zhuǎn)換1）將一棵二叉樹轉(zhuǎn)換為樹。 （未考過）2）將一棵樹轉(zhuǎn)換為二叉樹。 （未考過）3）將林轉(zhuǎn)換為一棵二叉樹。 （未考過）4）將二叉樹轉(zhuǎn)換為林。（未考過）8夠造哈夫曼樹給出一組權(quán)值，構(gòu)造一棵哈夫曼樹并求帶權(quán)路徑長度。（未考過）9圖的存儲(chǔ)結(jié)構(gòu)1）給出一個(gè)圖，畫出該

7、圖的鄰接矩陣或鄰接表存儲(chǔ)示意圖。（考過）2005/10試給出下圖的鄰接矩陣和鄰接表表示?！痉治觥苦徑泳仃嚧鎯?chǔ)方法是用一個(gè)二維數(shù)組存放頂點(diǎn)之間關(guān)系的信息。對(duì)于不帶權(quán)的有向圖，如果一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)有邊， 用 1 表示；否則，用 0 表示；對(duì)于帶權(quán)的有圖，如果一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)有邊，用邊的權(quán)值表示；否則，用表示。 鄰接表存儲(chǔ)方法的核心思想是對(duì)于具有 n 個(gè)頂點(diǎn)的圖建立 n 個(gè)線性鏈表。每一個(gè)鏈表最前面都分別設(shè)置一個(gè)稱之為表頭結(jié)點(diǎn)的結(jié)點(diǎn)， n 個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組結(jié)構(gòu)。第 i 個(gè)鏈表中的每一個(gè)鏈結(jié)點(diǎn)稱之為表結(jié)點(diǎn)。 對(duì)帶權(quán)的圖， 其鄰接表中的每個(gè)表結(jié)點(diǎn)都要增加一個(gè)權(quán)值域。【解答】題中圖的鄰接矩陣為：

8、v 0246V8v1v 21v 3711v 4V13v0 v1v2 v3v123VVV題中圖的鄰接表為：V223 44 6 V38V273 1 V21 2）給出一個(gè)圖的鄰接表，畫出該圖的所有連通分量。（考過）2002/10已知無向圖 G 的鄰接表如下圖所示，請(qǐng)畫出其所有的連通分量。V35V4V51V2V13【分析】根據(jù)鄰接表， 很容易畫出其所有的連通分量?！窘獯稹慨嫵龅倪B通分量如下圖所示VVVVV3）給出一個(gè)圖的鄰接矩陣，畫出該圖的所有連通分量。（考過）2003/1 已知無向圖G 的鄰接矩陣如下圖。假v000010Vv100101v0201000v 310000vV4010000 v1 v2

9、v3 vV0V1V2設(shè)對(duì)其訪問時(shí)每行元素必須從右到左， 請(qǐng)畫出其所有的連通分量， 并且寫出按深度優(yōu)先搜索時(shí)各連通分量的訪問序列?！痉治觥扛鶕?jù)鄰接表， 很容易畫出其所有的連通分量?！窘獯稹慨嫵龅倪B通分量如下圖所示VVVVV深度優(yōu)先搜索時(shí)各連通分量的訪問序列：V1V2V4V0V310圖的遍歷1）給出一個(gè)圖的鄰接表，寫出從某一點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。（ 2000/10 2001/10 2004/1 2004/10考過）2004/1已知無向圖 G 的鄰接表如下圖所示，請(qǐng)寫出其從頂點(diǎn) V 2 開始的深度優(yōu)先搜索的序列。V321V543V2145V235V234【分析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲(chǔ)結(jié)構(gòu)，所得到的遍歷序列是惟一的?！窘獯稹可疃葍?yōu)先搜索序列：V 2V 5V3V1V 42）給出一個(gè)圖的鄰接矩陣，寫出從某一點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。2003/10 考過）2003/10 已知無向圖G的鄰接矩陣如下圖所示，假設(shè)對(duì)其每行元素訪問時(shí)必須從右到左，請(qǐng)v001100V10111v 1v0211011v 301101vV401110v0v1v2v3v寫出從 V 0 開始的深度優(yōu)先搜索的序列。【分析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲(chǔ)結(jié)構(gòu)，所得到的遍歷序列是惟一的?！窘獯稹可疃葍?yōu)先搜索序列：V0V2V4V