1、數據結構數據結構考研輔導考研輔導 例題詳解例題詳解浙江大學計算機學院浙江大學計算機學院內容提綱內容提綱真題解答真題解答1分類測試分類測試2線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組A樹與圖樹與圖B查找與排序查找與排序C真題解答真題解答v單項選擇題：單項選擇題：140小題，每小題小題，每小題2分，分，共共80分。下列每題給出的四個選項中，只分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。有一個選項是最符合題目要求的。1.為解決計算機主機與打印機之間速度不匹配問為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數據緩沖區，主機將要題，通常設置一個打印數據緩沖區，主機將

2、要輸出的數據依次寫入該緩沖區，而打印機則依輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是構應該是 ？ A. 棧棧B. 隊列隊列C. 樹樹D. 圖圖4真題解答真題解答2.設棧設棧S和隊列和隊列Q的初始狀態均為空，元素的初始狀態均為空，元素a, b, c, d, e, f, g依次進入棧依次進入棧S。若每個元素出棧后。若每個元素出棧后立即進入隊列立即進入隊列Q，且，且7個元素出隊的順序是個元素出隊的順序是b, d, c, f, e, a, g，則棧，則棧S的容量至少是的容量至少是A. 1B. 2C. 3D. 4 ab

3、 cdefg5真題解答真題解答3.給定二叉樹如下圖所示。設給定二叉樹如下圖所示。設N代表二叉樹的根，代表二叉樹的根，L代表根結點的左子樹，代表根結點的左子樹，R代表根結點的右子代表根結點的右子樹。若遍歷后的結點序列為樹。若遍歷后的結點序列為3，1，7，5，6，2，4，則其遍歷方式是，則其遍歷方式是A. LRN B. NRLC. RLND. RNL12345676真題解答真題解答4.下列二叉排序樹中，滿足平衡二叉樹定義的是下列二叉排序樹中，滿足平衡二叉樹定義的是A. B. C. D.7真題解答真題解答5.已知一棵完全二叉樹的第已知一棵完全二叉樹的第6層（設根為第層（設根為第1層）層）有有8個葉結

4、點，則該完全二叉樹的結點個數最個葉結點，則該完全二叉樹的結點個數最多是多是A. 39B. 52C. 111D. 1196層共層共26 1 = 63個個32 8 = 24488真題解答真題解答6.將森林轉換為對應的二叉樹，若在二叉樹中，將森林轉換為對應的二叉樹，若在二叉樹中，結點結點u是結點是結點v的父結點的父結點，則在原來的的父結點的父結點，則在原來的森林中，森林中，u和和v可能具有的關系是可能具有的關系是 I. 父子關系父子關系II. 兄弟關系兄弟關系III. u的父結點與的父結點與v的父結點是兄弟關系的父結點是兄弟關系A. 只有只有II B. I和和IIC. I和和III D. I、II和

5、和IIIuvuvuvuv9真題解答真題解答7.下列關于無向連通圖特征的敘述中，正確的是下列關于無向連通圖特征的敘述中，正確的是I. 所有頂點的度之和為偶數所有頂點的度之和為偶數II. 邊數大于頂點個數減邊數大于頂點個數減1III. 至少有一個頂點的度為至少有一個頂點的度為1A. 只有只有IB. 只有只有IIC. I和和IID. I和和III10真題解答真題解答8.下列敘述中，不符合下列敘述中，不符合m階階B樹定義要求的是樹定義要求的是 A. 根結點最多有根結點最多有m棵子樹棵子樹B. 所有葉結點都在同一層上所有葉結點都在同一層上C. 各結點內關鍵字均升序或降序排列各結點內關鍵字均升序或降序排列

6、D. 葉結點之間通過指針鏈接葉結點之間通過指針鏈接11真題解答真題解答9.已知關鍵字序列已知關鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字是小根堆（最小堆），插入關鍵字3，調整，調整后得到的小根堆是后得到的小根堆是 A. 3，5，12，8，28，20，15，22，19B. 3，5，12，19，20，15，22，8，28C. 3，8，12，5，20，15，22，28，19D. 3，12，5，8，28，20，15，22，195812192820152235128282015221912真題解答真題解答10. 若數據元素序列若數據元素序列11，12，13，7，8，

7、9，23，4，5是采用下列排序方法之一得到是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法的第二趟排序后的結果，則該排序算法只能是只能是A. 起泡排序起泡排序B. 插入排序插入排序C. 選擇排序選擇排序D. 二路歸并排序二路歸并排序13真題解答真題解答綜合應用題：綜合應用題：4147小題，共小題，共70分。請將答分。請將答案寫在答題紙指定位置上。案寫在答題紙指定位置上。41. （10分）帶權圖（權值非負，表示邊連接的兩頂點間的距離）分）帶權圖（權值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短的最短路徑問題是找出從初始頂點到目標頂點之間的一

8、條最短路徑。假設從初始頂點到目標頂點之間存在路徑，現有一種解路徑。假設從初始頂點到目標頂點之間存在路徑，現有一種解決該問題的方法決該問題的方法： 設最短路徑初始時僅包含初始頂點，令當前頂點設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點；為初始頂點； 選擇離選擇離u最近且尚未在最短路徑中的一個頂點最近且尚未在最短路徑中的一個頂點v，加入到最短路徑，加入到最短路徑中，修改當前頂點中，修改當前頂點u = v； 重復步驟重復步驟，直到，直到u是目標頂點時為止。是目標頂點時為止。 請問上述方法能否求得最短路徑？若該方法可行，請證明之；請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則請舉

9、例說明。否則請舉例說明。14真題解答真題解答【參考答案參考答案】該方法不一定能求得最短路徑。該方法不一定能求得最短路徑。舉例說明：舉例說明： 圖圖a 圖圖b 圖圖a中，設初始頂點為中，設初始頂點為1，目標頂點為，目標頂點為4，欲求從頂點，欲求從頂點1到頂點到頂點4之間的最短路之間的最短路徑。顯然這兩點之間的最短路徑長度為徑。顯然這兩點之間的最短路徑長度為2。但利用給定方法求得的路徑長度。但利用給定方法求得的路徑長度為為3，這條路徑并不是這兩點之間的最短路徑。，這條路徑并不是這兩點之間的最短路徑。 圖圖b中，設初始頂點為中，設初始頂點為1，目標頂點為，目標頂點為3，欲求從頂點，欲求從頂點1到頂點

10、到頂點3之間的最短路之間的最短路徑。利用給定的方法，無法求出頂點徑。利用給定的方法，無法求出頂點1到頂點到頂點3的路徑。的路徑。 此題目給出的算法的關鍵錯誤是，將局部最優作為全局最優處理，從此題目給出的算法的關鍵錯誤是，將局部最優作為全局最優處理，從而采用了貪心的方法。解答時只要能體現而采用了貪心的方法。解答時只要能體現“局部最優不等于全局最優局部最優不等于全局最優”的思想，就可以得到的思想，就可以得到60%的分數。的分數。143211123211215真題解答真題解答42. （15分）已知一個帶有表頭結點的單鏈表，結點結構為分）已知一個帶有表頭結點的單鏈表，結點結構為 ，假設該鏈表只給出了頭

11、指針，假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，。在不改變鏈表的前提下，請設計一個請設計一個盡可能高效盡可能高效的算法，查找鏈表中倒數第的算法，查找鏈表中倒數第k個位置上個位置上的結點（的結點（k為整數）。若查找成功，算法輸出該結點的為整數）。若查找成功，算法輸出該結點的data域域的值，并返回的值，并返回1；否則，只返回；否則，只返回0。要求。要求：（1）描述算法的基本設計思想；）描述算法的基本設計思想；（2）描述算法的詳細實現步驟；）描述算法的詳細實現步驟；（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使）根據設計思想和實現步驟，采用程序設計語言描述算法（使用用C或

12、或C+或或JAVA語言實現），關鍵之處請給出簡要注釋。語言實現），關鍵之處請給出簡要注釋。datalink16真題解答真題解答【參考答案參考答案】（1）算法的基本設計思想：）算法的基本設計思想： 定義兩個指針變量定義兩個指針變量p和和q，初始時均指向頭結點的下一個結點。，初始時均指向頭結點的下一個結點。p指針指針沿鏈表移動；當沿鏈表移動；當p指針移動到第指針移動到第k個結點時，個結點時，q指針開始與指針開始與p指針同步指針同步移動；當移動；當p指針移動到鏈表最后一個結點時，指針移動到鏈表最后一個結點時，q指針所指元素為倒數指針所指元素為倒數第第k個結點。個結點。（2）算法的詳細實現步驟：）算法

13、的詳細實現步驟： count = 0, p和和q指向鏈表表頭結點的下一個結點；指向鏈表表頭結點的下一個結點； 若若p為空，轉為空，轉； 若若count等于等于k，則，則q指向下一個結點；否則，指向下一個結點；否則，count = count + 1； p指向下一個結點，轉步驟指向下一個結點，轉步驟； 若若count等于等于k，則查找成功，輸出該結點的，則查找成功，輸出該結點的data域的值，返回域的值，返回1；否則，查找失敗，返回否則，查找失敗，返回0； 算法結束。算法結束。 17bool WrongMethod( LinkList list, int k )LinkList p, q;int

14、 count = 0;p = q = list-link;while ( p ) p = p-link;if ( count link;if ( count data);return 1;18bool KthCountedBackwards( LinkList list, int k )LinkList p, q;int count = 0;p = q = list-link;while ( p & countlink;count+; if ( p )while ( p ) p = p-link;q = q-link; if ( count data);return 1;（3）算法實現

15、：typedef struct ListNode *ListPtr;typedef struct ListNode ElementType data;ListPtr link;ListPtr LinkList;19真題解答真題解答v類似題目：類似題目：給定一單鏈表，判斷其鏈接是否存在回路，給定一單鏈表，判斷其鏈接是否存在回路，要求額外空間復雜度為要求額外空間復雜度為O(1)。算法思路為：令算法思路為：令2個指針從頭結點開始，以不同的步長個指針從頭結點開始，以不同的步長1和和2前進；前進；若它們再次相遇于同一結點，則鏈表中存在回路。實現代碼如下：若它們再次相遇于同一結點，則鏈表中存在回路。實現代

16、碼如下：bool IsCycle( LinkList list ) int i;LinkList p1, p2;p1 = p2 = list;while ( true ) for ( i=0; ilink;if ( p1 = p2 ) return true; p2 = p2-link; return 0;20真題解答真題解答v類似題目：類似題目：令指針令指針p指向非空鏈表中的一個結點，且該指向非空鏈表中的一個結點，且該結點不在表尾。設計算法將結點不在表尾。設計算法將p所指的結點刪除。所指的結點刪除。注意到題目中特別申明該結點注意到題目中特別申明該結點不在表尾不在表尾，即該結點的后繼結點不為，

17、即該結點的后繼結點不為空，于是我們可以將其后繼結點的內容復制到該結點，然后將其后繼空，于是我們可以將其后繼結點的內容復制到該結點，然后將其后繼結點刪除即可。實現代碼如下：結點刪除即可。實現代碼如下：void DeleteThisP( LinkList p ) LinkList tmp = p-link;p-data = tmp-data;p-link = tmp-link;free( tmp );21分類測試分類測試v 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組v 樹與圖樹與圖v 查找與排序查找與排序22v 自測題自測題在具有在具有n個結點的單鏈表中，實現下列個結點的單鏈表中，實現下列哪

18、個操作，其算法的時間復雜度是哪個操作，其算法的時間復雜度是O(n) A遍歷鏈表和求鏈表的第遍歷鏈表和求鏈表的第i個結點個結點 B在地址為在地址為p的結點之后插入一個結點的結點之后插入一個結點 C刪除開始結點刪除開始結點 D刪除地址為刪除地址為p的結點的后繼結點的結點的后繼結點 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組23v 自測題自測題令令P代表入棧，代表入棧，O代表出棧。則將一個字符串代表出棧。則將一個字符串3 * a +b/c變為變為3 a * b c / +的堆棧操作序列是哪的堆棧操作序列是哪個？（例如將個？（例如將ABC變成變成BCA的操作序列是的操作序列是PPOPOO。）。）

19、A. PPPOOOPPOPPOOO B. POPOPOPPOPPOOO C. POPPOOPPOPPOOO D. POPPOOPPOPOOPO 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組24v 自測題自測題某線性表中最常用的操作是在最后一個元素之某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用什后插入一個元素和刪除第一個元素，則采用什么存儲方式最節省運算時間？么存儲方式最節省運算時間？ A. 單鏈表單鏈表B. 僅有頭指針的單循環鏈表僅有頭指針的單循環鏈表C. 雙鏈表雙鏈表D. 僅有尾指針的單循環鏈表僅有尾指針的單循環鏈表線性表、堆棧、隊列、數組線性表、堆棧、

20、隊列、數組25v 自測題自測題線性表在什么情況下適用于使用鏈式線性表在什么情況下適用于使用鏈式結構實現結構實現?A. 需經常修改中的結點值需經常修改中的結點值B. 需不斷對進行刪除插入需不斷對進行刪除插入C. 中含有大量的結點中含有大量的結點D. 中結點結構復雜中結點結構復雜 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組26v 自測題自測題對于一個具有對于一個具有n個結點的單鏈表，在給個結點的單鏈表，在給定值為定值為x的結點后插入一個新結點的時的結點后插入一個新結點的時間復雜度為間復雜度為. O(n). O(1). O(n/2). O(n2) 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數

21、組27v 自測題自測題設一個棧的輸入序列是設一個棧的輸入序列是 1，2，3，4，5,則下則下列序列中，是棧的合法輸出序列的是？列序列中，是棧的合法輸出序列的是？ A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 4線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組28v 自測題自測題若已知一個棧的入棧序列是若已知一個棧的入棧序列是1，2，3，n，其輸出序列為，其輸出序列為p1，p2，p3，pn。若若p1=n，則，則pi為為：A. iB. n i C. n i + 1D. 不確定不確定 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組29v 自測題自測題

22、將將5個字母個字母 ooops 按此順序入棧，則按此順序入棧，則有多少種不同的出棧順序可以仍然得到有多少種不同的出棧順序可以仍然得到 ooops？A. 1B. 3 C. 5D. 6 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組30v 自測題自測題鏈表不具有的特點是鏈表不具有的特點是：A. 插入、刪除不需要移動元素插入、刪除不需要移動元素 B. 可隨機訪問任一元素可隨機訪問任一元素 C. 不必事先估計存儲空間不必事先估計存儲空間 D. 所需空間與線性長度成正比所需空間與線性長度成正比 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組31v 自測題自測題若某表最常用的操作是在最后一個結點之若某

23、表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則后插入一個結點或刪除最后一個結點。則采用哪種存儲方式最節省運算時間采用哪種存儲方式最節省運算時間？A. 單鏈表單鏈表 B. 雙鏈表雙鏈表 C. 單循環鏈表單循環鏈表D. 帶頭結點的雙循環鏈表帶頭結點的雙循環鏈表 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組32v 自測題自測題若某線性表最常用的操作是存取任一指定若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算序號的元素和在最后進行插入和刪除運算，則利用哪種存儲方式最節省時間，則利用哪種存儲方式最節省時間？A. 順序表順序表 B. 雙鏈表雙鏈表 C.

24、單循環鏈表單循環鏈表D. 帶頭結點的雙循環鏈表帶頭結點的雙循環鏈表 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組33v 自測題自測題數組數組A1.5,1.6每個元素占每個元素占5個單元，將其個單元，將其按行優先次序存儲在起始地址為按行優先次序存儲在起始地址為1000的連的連續的內存單元中，則元素續的內存單元中，則元素A5,5的地址為的地址為A. 1140B. 1145C. 1120D. 1125 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組1000 + (29 1)*534v 自測題自測題已知兩個堆棧已知兩個堆棧S1和和S2的相關操作為：的相關操作為： Push( X, S )：將元素

25、：將元素X壓入堆棧壓入堆棧S；Pop( S )：將堆棧：將堆棧S的棧頂元素退棧；的棧頂元素退棧；IsFull( S )：判斷堆棧：判斷堆棧S是否已滿，若滿則返回是否已滿，若滿則返回1，否則返，否則返回回0；IsEmpty( S )：判斷堆棧：判斷堆棧S是否為空，若空則返回是否為空，若空則返回1，否，否則返回則返回0。 現想用這兩個堆棧實現一個隊列，請用上述堆棧操現想用這兩個堆棧實現一個隊列，請用上述堆棧操作實現隊列的的入列（作實現隊列的的入列（Enqueue）和出列（）和出列（Dequeue）功能。）功能。線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組35v利用堆棧的后進先出特點，利用堆棧的

26、后進先出特點，經過兩次經過兩次“后進先出后進先出”轉變為轉變為“先進先進先出先出”，即元素先經過堆棧，即元素先經過堆棧S1再經過堆棧再經過堆棧S2，從而實現隊列的，從而實現隊列的功能。功能。v入隊的原理相對簡單，向入隊的原理相對簡單，向S1中壓入即可。問題是當中壓入即可。問題是當S1滿時，為滿時，為了能最大限度不浪費空間，我們應檢查了能最大限度不浪費空間，我們應檢查S2。這里假設。這里假設S1和和S2容量相同。若容量相同。若S2是空的，我們可以將是空的，我們可以將S1中的元素逐一退棧，并中的元素逐一退棧，并壓入壓入S2中。新入列的元素就可以壓入騰空的中。新入列的元素就可以壓入騰空的S1了。只有

27、在了。只有在S2還沒有空、且還沒有空、且S1已滿的情況下，模擬隊列中才不能再接受新元已滿的情況下，模擬隊列中才不能再接受新元素。素。v當需要出隊時，首先判斷模擬隊列是否為空。若當需要出隊時，首先判斷模擬隊列是否為空。若S1和和S2都是空都是空的，則應返回錯誤信息。若出隊請求是合法的，則檢查的，則應返回錯誤信息。若出隊請求是合法的，則檢查S2。若。若S2為空，則為空，則S1必不為空，將必不為空，將S1中的元素逐一退棧，并壓入中的元素逐一退棧，并壓入S2中。這時中。這時S2中棧底存的是中棧底存的是S1的棧頂元素，也即最晚入列的元素的棧頂元素，也即最晚入列的元素；棧頂存的是；棧頂存的是S1的棧底元素

28、，也即最早入列的元素。這時的棧底元素，也即最早入列的元素。這時S2退退棧就相當于隊列的出隊，實現了先進先出。棧就相當于隊列的出隊，實現了先進先出。線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組36v 自測題自測題請設計盡可能高效的算法，顛倒一個英文句子中單請設計盡可能高效的算法，顛倒一個英文句子中單詞的順序，例如將詞的順序，例如將“this is a test”轉換為轉換為“test a is this”。設該句子以字符數組方式存放在。設該句子以字符數組方式存放在S中，并中，并已知其長度為已知其長度為N。 線性表、堆棧、隊列、數組線性表、堆棧、隊列、數組此題的核心在于顛倒一個字符串，方法是令

29、此題的核心在于顛倒一個字符串，方法是令p1和和p2兩兩個指針分別從字符串頭尾向中心移動，不斷交換它們各個指針分別從字符串頭尾向中心移動，不斷交換它們各自所指的字符。自所指的字符。顛倒整個句子方法是先將整句作為一個字符串，完全顛倒整個句子方法是先將整句作為一個字符串，完全顛倒，再將其中的每個單詞識別出來，分別顛倒回來。顛倒，再將其中的每個單詞識別出來，分別顛倒回來。參考答案中的代碼可以處理單詞間不只一個空格的情況。參考答案中的代碼可以處理單詞間不只一個空格的情況。37v 自測題自測題設高為設高為h的二叉樹只有度為的二叉樹只有度為0和和2的結點，的結點，則此類二叉樹的結點數至少為則此類二叉樹的結點

30、數至少為_，最多，最多為為_？ A. 2h-1 + 1, 2h 1B. 2h, 2h 1 C. 2h 1, 2h 1D. 2h 1, 2h-1 1樹與圖樹與圖38樹與圖樹與圖v自測題自測題三叉樹中，度為三叉樹中，度為1的結點有的結點有5個，度為個，度為2的結點的結點3個，度為個，度為3的結點的結點2個，問該樹含有幾個葉結點？個，問該樹含有幾個葉結點？ A.8B.10C.12D.13N1 = 5; N2 = 3; N3 = 2N = N0 + 10N 1 = 5*1 + 3*2 + 2*339樹與圖樹與圖v自測題自測題一棵樹有一棵樹有 n1 個孩子數為個孩子數為1的結點的結點, n2個孩子數個孩

31、子數為為2的結點的結點, , nm個孩子數為個孩子數為m的結點，則的結點，則該樹的葉結點數為該樹的葉結點數為 A B C Dmiini2)1(1miini2)(1miini2) 1( 11)1(1miini40樹與圖樹與圖v自測題自測題對二叉排序樹進行什么遍歷可以得到從小到大對二叉排序樹進行什么遍歷可以得到從小到大的排序序列的排序序列 ？ A.前序遍歷前序遍歷B.中序遍歷中序遍歷C.后序遍歷后序遍歷D.層次遍歷層次遍歷 41樹與圖樹與圖v自測題自測題在下述結論中，正確的是在下述結論中，正確的是只有一個結點的二叉樹的度為只有一個結點的二叉樹的度為0; 二叉樹的度為二叉樹的度為2；二叉樹的左右子樹

32、可任意交換；二叉樹的左右子樹可任意交換；深度為深度為K的完全二叉樹的結點個數小于或等于深度相同的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。的滿二叉樹。 A B C D42樹與圖樹與圖v自測題自測題12個結點的個結點的AVL樹的最大深度是？樹的最大深度是？ A.3B.4C.5D.6等價問題：深度等價問題：深度為為h的的AVL樹的最樹的最少結點數是？少結點數是？43樹與圖樹與圖v自測題自測題對于一個共有對于一個共有n個結點、個結點、k條邊的森林，共有幾條邊的森林，共有幾棵樹？棵樹？ A.n k B.n k + 1C.n k 1D.不能確定不能確定每棵有每棵有m個結點的樹必有個結點的樹必有m

33、-1條邊條邊n = mk = m t （t是樹的個數）是樹的個數）t = ?44樹與圖樹與圖v自測題自測題設森林設森林F中有三棵樹，第一，第二，第中有三棵樹，第一，第二，第三棵樹的結點個數分別為三棵樹的結點個數分別為M1，M2和和M3。與森林與森林F對應的二叉樹根結點的右子樹對應的二叉樹根結點的右子樹上的結點個數是上的結點個數是 AM1 BM1+M2 CM3 DM2+M3 45v 自測題自測題設每個設每個d叉樹的結點有叉樹的結點有d個指針指向子樹，個指針指向子樹，有有n個結點的個結點的d叉樹有多少叉樹有多少空鏈域？空鏈域？A. n(d-1)B. n(d-1)+1C. ndD. 以上都不是以上都

34、不是 樹與圖樹與圖n個結點有個結點有nd個指針個指針除了根，每個結點被除了根，每個結點被1個指針所指個指針所指 nd (n 1)46v 自測題自測題哪種樹，樹中任何結點到根結點路徑上的哪種樹，樹中任何結點到根結點路徑上的各結點值是有序的？各結點值是有序的？A. 堆堆B. 二叉排序樹二叉排序樹C. 完全二叉樹完全二叉樹D. 以上都不是以上都不是 樹與圖樹與圖47v 自測題自測題某二叉樹的中序序列和后序序列正好相某二叉樹的中序序列和后序序列正好相反，則該二叉樹一定是反，則該二叉樹一定是A. 空或只有一個結點空或只有一個結點B. 高度等于其結點數高度等于其結點數C. 任一結點無左孩子任一結點無左孩子

35、D. 任一結點無右孩子任一結點無右孩子 樹與圖樹與圖48v 自測題自測題設設n、m為一棵二叉樹上的兩個結點，為一棵二叉樹上的兩個結點，在中序遍歷時，在中序遍歷時，n在在m前的條件是前的條件是An在在m右方右方Bn是是m祖先祖先Cn在在m左方左方Dn是是m子孫子孫樹與圖樹與圖49v 自測題自測題請設計算法求二叉樹中葉結點的個數。請設計算法求二叉樹中葉結點的個數。樹與圖樹與圖int CountLeaf ( Tree T ) /這里假設樹不為空這里假設樹不為空 int LeafNum; if ( !T-LeftChild & !T-RightChild ) return 1; else if

36、 ( T-LeftChild ) LeafNum = CountLeaf( T-LeftChild );if ( T-RightChild ) LeafNum += CountLeaf( T-RightChild );return LeafNum; 50v 自測題自測題樹中任意兩結點之間都存在一條路徑，兩結點的樹中任意兩結點之間都存在一條路徑，兩結點的距離即定義為路徑的長度。距離最遠的兩個結點距離即定義為路徑的長度。距離最遠的兩個結點的距離定義為樹的的距離定義為樹的“直徑直徑”。給定一棵用二叉鏈。給定一棵用二叉鏈表存儲的二叉樹，其結點構造為如圖。指針表存儲的二叉樹，其結點構造為如圖。指針Roo

37、t指向根結點。請設計時間復雜度為指向根結點。請設計時間復雜度為O(n)的的算法（算法（n為樹中結點的個數）求二叉樹的直徑。為樹中結點的個數）求二叉樹的直徑。樹與圖樹與圖Left_ChildDataRight_Child直徑直徑 = max( 左樹深度左樹深度 + 右樹深度右樹深度 )51樹與圖樹與圖int BinaryTreeHeight( Tree T, int *MaxHeightSumP )if ( !T ) return 0;int LeftHeight = BinaryTreeHeight( T-LeftChild, MaxHeightSumP );int RightHeight =

38、 BinaryTreeHeight( T-RightChild, MaxHeightSumP );(*MaxHeightSumP) = max( LeftHeight + RightHeight, *MaxHeightSumP );return max( LeftHeight, RightHeight ) + 1;int FindRadOfTree( Tree Root )int MaxHeightSum = 0;BinaryTreeHeight( Root, &MaxHeightSum );return MaxHeightSum;52v自測題自測題(考研大綱中例題考研大綱中例題)已知

39、一棵二叉樹采用二叉鏈表存儲。現定義二叉已知一棵二叉樹采用二叉鏈表存儲。現定義二叉樹中結點樹中結點X0的根路徑為從根結點到的根路徑為從根結點到X0的一條路徑的一條路徑，請編寫算法輸出該二叉樹中最長的根路徑（多，請編寫算法輸出該二叉樹中最長的根路徑（多條最長根路徑中只輸出一條即可。算法可用條最長根路徑中只輸出一條即可。算法可用C或或C+或或JAVA語言實現）。語言實現）。參考答案：參考答案：v此題要求最長的根路徑，該路徑的長度就是樹的深度。解題思此題要求最長的根路徑，該路徑的長度就是樹的深度。解題思路分兩步走：首先求樹的深度，同時記住最深的那個葉子結點路分兩步走：首先求樹的深度，同時記住最深的那個

40、葉子結點；然后對樹做先序遍歷，在遍歷過程中找最深的那個葉子結點；然后對樹做先序遍歷，在遍歷過程中找最深的那個葉子結點。當找到時，存在系統堆棧中的結點就構成了最長的根路徑。當找到時，存在系統堆棧中的結點就構成了最長的根路徑。整個算法在最壞情況下會執行兩次樹的遍歷，復雜度是整個算法在最壞情況下會執行兩次樹的遍歷，復雜度是O(n)（n為樹中結點的個數）。為樹中結點的個數）。v另外有算法用一個數組保存路徑上的結點，在求樹深的同時不另外有算法用一個數組保存路徑上的結點，在求樹深的同時不斷更新最深路徑，雖然程序結構相對簡單，但復雜度顯然超過斷更新最深路徑，雖然程序結構相對簡單，但復雜度顯然超過線性。線性。

41、 樹與圖樹與圖53v 自測題自測題給定一個整數給定一個整數x，以及一個可能的查找的，以及一個可能的查找的關鍵字序列關鍵字序列 K0, , KN-1 ，請設計，請設計算法判別一個序列是否是一個可能的二叉算法判別一個序列是否是一個可能的二叉排序樹上進行的查找序列。（例如：排序樹上進行的查找序列。（例如：1, 4, 2, 3 就是查找就是查找3的序列，對應二叉排序的序列，對應二叉排序樹如圖。而樹如圖。而2, 4, 1, 3就不可能是。）要就不可能是。）要求算法時間復雜度為求算法時間復雜度為O(N)。樹與圖樹與圖1234答案答案1：先構造樹，再判斷是否二叉排序樹：先構造樹，再判斷是否二叉排序樹54樹與

42、圖樹與圖bool Is_BST_sequence( int K , int N ) if (N=2) return true; Create root for K0 ; Parent = root ; for (i=1 ; ikey key) Parent-rightchild = node ; else Parent-leftchild = node ; Parent = node ; return IS_BST(root, &min, &max) ;可以用簡單的后序遍歷嗎？可以用簡單的后序遍歷嗎？432751655樹與圖樹與圖bool IS_BST( Tree T, int

43、* min, int* max ) if ( !T-leftchild & !T-rightchild ) (*min) = (*max) = T-key ; return true ; Left_flag = Right_flag = false ; if ( (T-leftchild & IS_BST(T-leftchild, &lmin, &lmax)& T-key lmax) | !T-leftchild ) Left_flag = true ; if ( (T-rightchild & IS_BST(T-rightchild, &

44、;rmin, &rmax)& T-key rightchild ) Right_flag = true ; if (Left_flag & Right_flag) if (T-leftchild) (*min) = lmin ; else (*min) = T-key ; if (T-rightchild) (*max) = rmax ; else (*max) = T-key ; return true ; else return false ;56樹與圖樹與圖答案答案2：#define IsInRange(n) (nmin)bool Is_BST_sequence(

45、 int K , int N, int X )min = MIN_ELEMENT; max = MAX_ELEMENT;for( i=0; i X )max = Ki;else if( Ki RightChild )SortBST( T-RightChild, x ); if ( T-data data ); if ( T-LeftChild )SortBST( T-LeftChild, x );58v 自測題自測題在有在有N個結點且為完全二叉樹的二叉排序樹個結點且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數的數量中查找一個鍵值，其平均比較次數的數量級為（）。級為（）。 A. O(l

46、ogN)B. O(N)C. O(NlogN)D. O(N2) 樹與圖樹與圖59v 自測題自測題給定鏈表表示的二叉樹，判斷其是否為完給定鏈表表示的二叉樹，判斷其是否為完全二叉樹。全二叉樹。答案：對于完全二叉樹，其關鍵特點是：答案：對于完全二叉樹，其關鍵特點是：若某結點無左孩子就不應有右孩子。算法若某結點無左孩子就不應有右孩子。算法基本思路是利用隊列做樹的層次遍歷，當基本思路是利用隊列做樹的層次遍歷，當發現第一個缺少孩子的結點時，用發現第一個缺少孩子的結點時，用Flag標標記。而一旦發現了一個缺少孩子的結點，記。而一旦發現了一個缺少孩子的結點，其后的所有結點都不能再有孩子。若在其后的所有結點都不能

47、再有孩子。若在Flag為為1的情況下還發現某結點有非空孩子的情況下還發現某結點有非空孩子結點，則必非完全二叉樹。結點，則必非完全二叉樹。樹與圖樹與圖60樹與圖樹與圖bool IsCompleteBinaryTree( Tree T ) int Flag = 0; /0表示尚未發現結點有空子樹表示尚未發現結點有空子樹if ( !T ) return TRUE; EnQueue( Q, T ); while (!IsEmpty(Q)T = DeQueue(Q);if ( T-LeftChild & !Flag ) EnQueue( Q, T-LeftChild ); else if ( T

48、-LeftChild ) return FALSE; else Flag =1; /結點有空子樹結點有空子樹if ( T-RightChild & !Flag )EnQueue( Q, T-RightChild );else if ( T-RightChild ) return FALSE; else Flag =1; /結點有空子樹結點有空子樹 return TRUE; 61v 自測題自測題森林的二叉樹用森林的二叉樹用T表示。已知表示。已知T的前序和的前序和中序遍歷結果，請畫出對應的森林中序遍歷結果，請畫出對應的森林前序：前序：A B C D E F G H I J K L中序：中序

49、：C B E F D G A J I K L H樹與圖樹與圖ABCDEFGHIJKLAHBDGCEFIKLJ62v 自測題自測題設一段文本中包含字符設一段文本中包含字符a, b, c, d, e，其出，其出現頻率相應為現頻率相應為3, 2, 5, 1, 1。則經過哈夫曼。則經過哈夫曼編碼后，文本所占字節數為編碼后，文本所占字節數為A. 40B. 36C. 25D. 12 樹與圖樹與圖127425321163v 自測題自測題給定字符出現頻率以及哈夫曼編碼的正確給定字符出現頻率以及哈夫曼編碼的正確長度，現對于任一套輸入的編碼，判斷其長度，現對于任一套輸入的編碼，判斷其是否哈夫曼編碼。是否哈夫曼編碼

50、。樹與圖樹與圖64樹與圖樹與圖核心部分：核心部分：while (codeij != 0) if (codeij = 0) if ( !tmp-left_child ) tmp-left_child = new_node();else if (tmp-left_child-data 0) ok = false; tmp = tmp-left_child;if (codeij = 1) if ( !tmp-right_child ) tmp-right_child = new_node();else if (tmp-right_child-data 0) ok = false; tmp = tmp

51、-right_child;j+;if (!tmp-left_child & !tmp-right_child) tmp-data = fi;else ok = false;Length += fi * j; /計算編碼長度計算編碼長度65v 自測題自測題在在AOE網中，什么是關鍵路徑？網中，什么是關鍵路徑？A. 最短回路最短回路B. 從第一個事件到最后一個事件的最短路徑從第一個事件到最后一個事件的最短路徑C. 最長回路最長回路D. 從第一個事件到最后一個事件的最長路徑從第一個事件到最后一個事件的最長路徑樹與圖樹與圖66v 自測題自測題用用DFS遍歷一個無環有向圖，并在遍歷一個無環有向圖

52、，并在DFS算算法退棧返回時打印相應的頂點，則輸出的法退棧返回時打印相應的頂點，則輸出的頂點序列是？頂點序列是？A. 逆拓撲有序逆拓撲有序 B. 拓撲有序拓撲有序 C. 無序的無序的D. 以上都不對以上都不對樹與圖樹與圖1234DFS: 4, 3, 2, 167v 自測題自測題已知有向圖已知有向圖G=(V, E)，其中，其中V = v1, v2, v3, v4, v5, v6，E = , , , , , , , 。G的拓撲的拓撲序列是序列是?A. v3, v4, v1, v5, v2, v6B. v1, v3, v4, v5, v2, v6C. v3, v1, v4, v5, v2, v6D.

53、 v1, v4, v3, v5, v2, v6樹與圖樹與圖12345668v 自測題自測題任何一個帶權無向連通圖的最小生成樹任何一個帶權無向連通圖的最小生成樹 A. 是唯一的是唯一的B. 是不唯一的是不唯一的C. 有可能不唯一有可能不唯一D. 有可能不存在有可能不存在樹與圖樹與圖69v 自測題自測題一個有一個有n個頂點的強連通圖至少有多少條邊個頂點的強連通圖至少有多少條邊？An(n-1)Bn-1CnDn+1樹與圖樹與圖70v 自測題自測題對于有向圖，其鄰接矩陣表示比鄰接表表對于有向圖，其鄰接矩陣表示比鄰接表表示更易于示更易于A求一個頂點的入度求一個頂點的入度B求一個頂點的出邊鄰接點求一個頂點的

54、出邊鄰接點C進行圖的深度優先遍歷進行圖的深度優先遍歷D進行圖的廣度優先遍歷進行圖的廣度優先遍歷樹與圖樹與圖71v 自測題自測題在圖中自在圖中自a點開始進行深度優先遍歷算法可能得到點開始進行深度優先遍歷算法可能得到的結果為的結果為A. a, b, e, c, d, fB. a, e, d, f, c, bC. a, c, f, e, b, dD. a, e, b, c, f, d樹與圖樹與圖abecdf72v 自測題自測題在圖中自在圖中自a點開始進行廣度優先遍歷算法可能得到點開始進行廣度優先遍歷算法可能得到的結果為的結果為A. a, b, e, c, d, fB. a, e, d, f, c,

55、bC. a, c, f, e, b, dD. a, e, b, c, f, d樹與圖樹與圖abecdf73v 自測題自測題以下哪個命題是正確的？以下哪個命題是正確的？ A. 對于帶權無向圖對于帶權無向圖G = (V, E)，M是是G的最小生成的最小生成樹，則樹，則M中任意兩點中任意兩點V1到到V2的路徑一定是它們的路徑一定是它們之間的最短路徑。之間的最短路徑。B. P是頂點是頂點s到到t的最短路徑，如果該圖中的所有路的最短路徑，如果該圖中的所有路徑的權值都加徑的權值都加1，P仍然是仍然是s到到t的最短路徑。的最短路徑。C. 深度優先遍歷也可用于完成拓撲排序。深度優先遍歷也可用于完成拓撲排序。D

56、. 以上都不是。以上都不是。樹與圖樹與圖74v 自測題自測題下列說法不正確的是下列說法不正確的是 A圖的遍歷是從給定的源點出發每一個頂點圖的遍歷是從給定的源點出發每一個頂點僅被訪問一次僅被訪問一次 B遍歷的基本算法有兩種：深度遍歷和廣度遍歷的基本算法有兩種：深度遍歷和廣度遍歷遍歷 C圖的深度遍歷不適用于有向圖圖的深度遍歷不適用于有向圖D圖的深度遍歷是一個遞歸過程圖的深度遍歷是一個遞歸過程 樹與圖樹與圖75v 自測題自測題下圖中每個頂點表示一個島，每條邊表示島嶼間建下圖中每個頂點表示一個島，每條邊表示島嶼間建橋的成本，找到一個算法計算正確的造橋方法，使橋的成本，找到一個算法計算正確的造橋方法，使

57、得所有的島嶼都能連通，并且總的造價最小，給出得所有的島嶼都能連通，并且總的造價最小，給出這個算法的名字，并給出求解過程。這個算法的名字，并給出求解過程。 樹與圖樹與圖1215303525171572010512ABCGFED求最小生成樹：求最小生成樹：注意到給出的圖中有注意到給出的圖中有7個結點、個結點、12條邊，屬于邊稀疏的情況，用條邊，屬于邊稀疏的情況，用克魯斯卡爾算法克魯斯卡爾算法是合適的。若給是合適的。若給出一個完全圖，則普里姆出一個完全圖，則普里姆(Prim)算法將是更好的選擇。算法將是更好的選擇。 76v 自測題自測題某省調查鄉村交通狀況，得到的統計表中某省調查鄉村交通狀況，得到的

58、統計表中列出了任意兩村莊間的距離。省政府列出了任意兩村莊間的距離。省政府“暢暢通工程通工程”的目標是使全省任何兩個村莊間的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可公路相連，只要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。要），并要求鋪設的公路總長度為最小。要解決這個問題，問：解決這個問題，問：(1) 可用什么數據結構表示城鎮和道路？可用什么數據結構表示城鎮和道路？(2) 請描述效率最高的算法。請描述效率最高的算法。 樹與圖樹與圖答案：最小生成樹；答案：最小生成樹；Prim77v 自測題自測

59、題某省調查城鎮交通狀況，得到現有城鎮道某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通路統計表，表中列出了每條道路直接連通的城鎮。省政府的城鎮。省政府“暢通工程暢通工程”的目標是使的目標是使全省任何兩個城鎮間都可以實現交通（但全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接不一定有直接的道路相連，只要互相間接通過道路可達即可），并要求增設的道路通過道路可達即可），并要求增設的道路條數為最少。要解決這個問題，問：條數為最少。要解決這個問題，問：(1) 可用什么數據結構表示城鎮和道路？可用什么數據結構表示城鎮和道路？ (2) 請用偽碼描述效率最高的解

60、法。請用偽碼描述效率最高的解法。 樹與圖樹與圖答案：答案：DSF數連通集個數數連通集個數 1 78v 自測題自測題給定給定n個村莊之間的交通圖，若村莊個村莊之間的交通圖，若村莊i和和j之間有道之間有道路，則將頂點路，則將頂點i和和j用邊連接，邊上的用邊連接，邊上的Wij表示這條表示這條道路的長度，現在要從這道路的長度，現在要從這n個村莊中選擇一個村莊個村莊中選擇一個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短離醫院最遠的村莊到醫院的路程最短? 樹與圖樹與圖答案：答案：先用先用Floyd求任意求任意2點間最短路；點間最短路；對每個村莊，求它到其他村莊的最短路中最長的；對每個村莊，求它到其他村莊的最短路中最長的；找所有找所有n條最長路中最短的，那