數(shù)據(jù)結(jié)構導論串講筆記

1、F1）已知出棧序列，寫出可能的入棧序列并分析操作過程。2）已知入棧序列，寫出可能的出棧序列并分析操作過程。2004/1如下圖所示，輸入元素為（A,B,C）,在棧的輸出端得到一個輸出序列ABC,求出在棧的輸入端所有可能的輸入序列。ABC,5項Yj、輸出驪輸入驪棧【分析】A,B,C三個字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA六種，按堆棧操作的先進后出（或后進先出）的原則，只有輸入序列為BCA時，輸出無法得到ABC。因為輸入序列為BCA時，要想先輸出A,必須BCA均入棧，但這樣只能得到序列ACB。其余五種輸入序列都可在輸出端得到序列ABC?！窘獯稹緼BC、ACB、BAC、

2、CAB、CBA2.隊列的操作分析順序隊中元素入隊出隊操作及隊列的狀態(tài)。（考過）2003/10設有一順序隊列sq,容量為5,初始狀態(tài)時sq.front=sq.rear=0,畫出做完下列操作后隊列及其頭尾指針的狀態(tài)變化情況，若不能入隊，請簡述其理。(1)d,e,b入隊(2)d,e出隊(3)i,j入隊(4)b出隊(5)n,o,p入隊j-Sq.rearjiibHSq.rearb-Sq.rearbe*-Sq.front-Sq.frontd*Sq.rear*-Sq.front(a)初態(tài)(b)d,Sq.fronte,b入隊(c)d,e出隊(d)i,j入隊(Sq.front【解答】 隊列及其頭尾指針的狀態(tài)變化

3、情況如下圖所示*-Sq.rear第5步操作無法進行，因隊列已滿。e）b出隊F3.二叉樹的存儲結(jié)構1）給出一棵二叉樹，畫出二叉鏈表示意圖及順序存儲示意圖。2004/10考過）2003/10畫出下列二叉樹的二叉鏈表表示圖。(2000/102003/10【解答】二叉樹的二叉鏈表表示【分析】按照給出的順序存儲結(jié)構，先繪制出一棵包括空結(jié)點的完全二叉樹，然后去掉空結(jié)點就是所求的二叉樹。【解答】4.二叉樹的遍歷1)給出一棵二叉樹，寫出對該二叉樹進行先根遍歷、中根遍歷及后根遍歷的序列。ABCDAAEAAAAA/U/UFG（2005/1考過）2)給出二叉樹的順序存儲示意圖，畫出二叉樹。2005/1已知某二叉樹的

4、順序存儲結(jié)構如下所示，試畫出該二叉樹。(2001/102004/12005/10考過)2005/10對于如下圖所示二叉樹，分別寫出其先根遍歷、中根遍歷和后根遍歷的結(jié)點訪問序列?！痉治觥扛鶕?jù)二叉樹三種遍歷方法的原理，很容易寫出該二叉樹的先根遍歷、中根遍歷和后根遍歷的結(jié)點訪問序【解答】先根遍歷的結(jié)點訪問序：A,B,D,E,F,C后根遍歷的結(jié)點訪問序：F,E,D,B,C,A2）給出一棵二叉樹的先根遍歷和中根遍歷序列，恢復二叉樹，寫出后根遍歷的序列。（2002/10考過）2002/10現(xiàn)有某二叉樹，按先根遍歷的序列為ABDEFCGH,按中根遍歷的序列為DEFBGHCA,試畫出此二叉樹。【分析】由先根遍

5、歷和中根遍歷恢復二叉樹的方法：在先根序列中確定根結(jié)點（最前面那個結(jié)點一定是根結(jié)點），然后根據(jù)根結(jié)點在中根序列中的位置分出根結(jié)點的左、右子樹（根結(jié)點前面的那些結(jié)點為根結(jié)點的左子樹上的結(jié)點，根結(jié)點后面的那些結(jié)點為根結(jié)點的右子樹上的結(jié)點）?；謴驮摱鏄涞娜魏我豢米訕涞倪^程仍然遵循這個原則。【解答】二叉樹如下圖所示3）給出一棵二叉樹的后根遍歷和中根遍歷序列，恢復二叉樹，寫出先根遍歷的序列?？歼^，但可能考注意第四章的考核知識點的講解）5.樹的存儲結(jié)構1）給出一棵樹，畫出該樹的雙親表示法、孩子鏈表表示法、帶雙親的孩子鏈表表示法及孩子兄弟鏈表表示法的示意圖。（2000/4考過）2）給出一棵樹的某一種存儲結(jié)構

6、的示意圖，畫出對應的樹。（未考過）6.樹的遍歷給出一棵樹，寫出對該樹進行先根遍歷、后根遍歷及層次遍歷的序列。（未考過）中根遍歷的結(jié)點訪問序:B,F,E,ABCDGEFH7.二叉樹與樹、林的相互轉(zhuǎn)換1）將一棵二叉樹轉(zhuǎn)換為樹。（未考過）2）將一棵樹轉(zhuǎn)換為二叉樹。（未考過）3）將林轉(zhuǎn)換為一棵二叉樹。（未考過）4）將二叉樹轉(zhuǎn)換為林。（未考過）8.夠造哈夫曼樹給出一組權值，構造一棵哈夫曼樹并求帶權路徑長度。（未考過）9.圖的存儲結(jié)構1）給出一個圖，畫出該圖的鄰接矩陣或鄰接表存儲示意圖。（考過）2005/10試給出下圖的鄰接矩陣和鄰接表表示?！痉治觥苦徑泳仃嚧鎯Ψ椒ㄊ怯靡粋€二維數(shù)組存放頂點之間關系的信息。

7、對于不帶權的有向圖，如果一個頂點到另一個頂點有邊，用1表示；否則，用0表示；對于帶權的有圖，如果一個頂點到另一個頂點有邊，用邊的權值表示；否則，用 8 表示。鄰接表存儲方法的核心思想是對于具有n個頂點的圖建立n個線性鏈表。每一個鏈表最前面都分別設置一個稱之為表頭結(jié)點的結(jié)點，n個結(jié)點構成一個數(shù)組結(jié)構。第i個鏈表中的每一個鏈結(jié)點稱之為表結(jié)點。對帶權的圖，其鄰接表中的每個表結(jié)點都要增加一個權值域?！窘獯稹款}中圖的鄰接矩陣為：vV1246vV32vV4711vV513V0v1v2v3vV1V2V3V4V5題中圖的鄰接表為：2）給出一個圖的鄰接表，畫出該圖的所有連通分量。（考過）2002/10已知無向圖

8、G的鄰接表如下圖所示，請畫出其所有的連通分量。V1|3|5|:AV2A4A5IdI|AV3*1V4A,2A11IcI.AV53【分析】根據(jù)鄰接表，很容易畫出其所有的連通分量。【解答】畫出的連通分量如下圖所示3）給出一個圖的鄰接矩陣，畫出該圖的所有連通分量。（考過）2003/1已知無向圖G的鄰接矩陣如下圖。假設對其訪問時每行元素必須從右到左，請畫出其所有的連通分量，并且寫出按深度優(yōu)先搜索時各連通分量的訪問序列。VV000010站00101VV201000VV310000W401000V0V1v2V3VV0V1V2V3V4【分析】根據(jù)鄰接表，很容易畫出其所有的連通分量?！窘獯稹慨嫵龅倪B通分量如下圖

9、所示深度優(yōu)先搜索時各連通分量的訪問序列：V1V2V4V0V310.圖的遍歷1）給出一個圖的鄰接表，寫出從某一點出發(fā)進行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。（2000/102001/102004/12004/10考過）2004/1已知無向圖G的鄰接表如下圖所示，請寫出其從頂點V2開始的深度優(yōu)先搜索的序列。一的?！窘獯稹可疃葍?yōu)先搜索序列：V2V5V3V1V42）給出一個圖的鄰接矩陣，寫出從某一點出發(fā)進行廣度優(yōu)先搜索和深度優(yōu)先搜索的遍歷序列。（2003/10考過）2003/10已知無向圖G的鄰接矩陣如下圖所示， 請寫出從V0開始的深度優(yōu)先搜索的序列。vV。01(J)假設對其每行元素訪問時必須從右到左,100111011【分析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲結(jié)構，所得到的遍歷序列是惟vV110vV211【分析】根據(jù)深度優(yōu)先搜索的算法思想和題中給定的存儲結(jié)構