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

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

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

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

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

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

6、第四章的考核知識點的講解）5樹的存儲結構1）給出一棵樹，畫出該樹的雙親表示法、孩子鏈表表示法、帶雙親的孩子鏈表表示法及孩子兄弟鏈表表示法的示意圖。 （2000/4 考過）2）給出一棵樹的某一種存儲結構的示意圖，畫出對應的樹。（未考過）6樹的遍歷給出一棵樹， 寫出對該樹進行先根遍歷、 后根遍歷及層次遍歷的序列。（未考過）7二叉樹與樹、林的相互轉換1）將一棵二叉樹轉換為樹。 （未考過）2）將一棵樹轉換為二叉樹。 （未考過）3）將林轉換為一棵二叉樹。 （未考過）4）將二叉樹轉換為林。（未考過）8夠造哈夫曼樹給出一組權值，構造一棵哈夫曼樹并求帶權路徑長度。（未考過）9圖的存儲結構1）給出一個圖，畫出該

7、圖的鄰接矩陣或鄰接表存儲示意圖。（考過）2005/10試給出下圖的鄰接矩陣和鄰接表表示?！痉治觥苦徑泳仃嚧鎯Ψ椒ㄊ怯靡粋€二維數(shù)組存放頂點之間關系的信息。對于不帶權的有向圖，如果一個頂點到另一個頂點有邊， 用 1 表示；否則，用 0 表示；對于帶權的有圖，如果一個頂點到另一個頂點有邊，用邊的權值表示；否則，用表示。 鄰接表存儲方法的核心思想是對于具有 n 個頂點的圖建立 n 個線性鏈表。每一個鏈表最前面都分別設置一個稱之為表頭結點的結點， n 個結點構成一個數(shù)組結構。第 i 個鏈表中的每一個鏈結點稱之為表結點。 對帶權的圖， 其鄰接表中的每個表結點都要增加一個權值域?！窘獯稹款}中圖的鄰接矩陣為：

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

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