計算機二級公共基礎知識考前押題

1、未來教育 內(nèi)部資料1.下列敘述中正確的是 A)所謂算法就是計算方法B)程序可以作為算法的一種描述方法C)算法設計只需考慮得到計算結(jié)果D)算法設計可以忽略算法的運算時間B【解析】算法是指對解題方案的準確而完整的描述，算法不等于數(shù)學上的計算方法，也不等于程序。算法設計需要考慮可行性、確定性、有窮性與足夠的情報，不能只考慮計算結(jié)果。算法設計有窮性是指操作步驟有限且能在有限時間內(nèi)完成，如果一個算法執(zhí)行耗費的時間太長，即使最終得出了正確結(jié)果，也是沒有意義的，。算法在實現(xiàn)時需要用具體的程序設計語言描述，所以程序可以作為算法的一種描述方法。2.下列關于算法的描述中錯誤的是 A)算法強調(diào)動態(tài)的執(zhí)行過程，不同于

2、靜態(tài)的計算公式B)算法必須能在有限個步驟之后終止C)算法設計必須考慮算法的復雜度D)算法的優(yōu)劣取決于運行算法程序的環(huán)境D【解析】算法設計不僅要考慮計算結(jié)果的正確性，還要考慮算法的時間復雜度和空間復雜度。3.下列敘述中正確的是A)算法的復雜度包括時間復雜度與空間復雜度B)算法的復雜度是指算法控制結(jié)構的復雜程度C)算法的復雜度是指算法程序中指令的數(shù)量D)算法的復雜度是指算法所處理的數(shù)據(jù)量A【解析】算法復雜度是指算法在編寫成可執(zhí)行程序后，運行時所需要的資源，資源包括時間資源和內(nèi)存資源。算法的復雜度包括時間復雜度與空間復雜度。算法的時間復雜度是指執(zhí)行算法所需要的計算工作量；算法的空間復雜度是指算法在執(zhí)

3、行過程中所需要的內(nèi)存空間。4.下列敘述中正確的是A)算法的時間復雜度與計算機的運行速度有關B)算法的時間復雜度與運行算法時特定的輸入有關C)算法的時間復雜度與算法程序中的語句條數(shù)成正比D)算法的時間復雜度與算法程序編制者的水平有關B【解析】為了能夠比較客觀地反映出一個算法的效率，在度量一個算法的工作量時，不僅應該與所使用的計算機、程序設計語言以及程序編制者無關，而且還應該與算法實現(xiàn)過程中的許多細節(jié)無關。為此，可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運算次數(shù)還與問題的規(guī)模有關；對應一個固定的規(guī)模，算法所執(zhí)行的基本運算次數(shù)還可能與特定的輸入有關。5.下列敘述

4、中正確的是 A)解決同一個問題的不同算法的時間復雜度一般是不同的B)解決同一個問題的不同算法的時間復雜度必定是相同的C)對同一批數(shù)據(jù)作同一種處理，如果數(shù)據(jù)存儲結(jié)構不同，不同算法的時間復雜度肯定相同D)對同一批數(shù)據(jù)作不同的處理，如果數(shù)據(jù)存儲結(jié)構相同，不同算法的時間復雜度肯定相同A【解析】解決同一個問題的不同算法的時間復雜度，可能相同也可能不相同。算法的時間復雜度與數(shù)據(jù)存儲結(jié)構無關，對同一批數(shù)據(jù)作同一種處理或者不同處理，數(shù)據(jù)存儲結(jié)構相同或者不同，算法的時間復雜度都可能相同或者不同。6.下列敘述中正確的是A)算法的空間復雜度是指算法程序中指令的條數(shù)B)壓縮數(shù)據(jù)存儲空間不會降低算法的空間復雜度C)算法

5、的空間復雜度與算法所處理的數(shù)據(jù)存儲空間有關D)算法的空間復雜度是指算法程序控制結(jié)構的復雜程度C【解析】算法的空間復雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。算法執(zhí)行期間所需的存儲空間包括3個部分：輸入數(shù)據(jù)所占的存儲空間；程序本身所占的存儲空間；算法執(zhí)行過程中所需要的額外空間。7.為了降低算法的空間復雜度，要求算法盡量采用原地工作(in place)。所謂原地工作是指 A)執(zhí)行算法時不使用額外空間B)執(zhí)行算法時不使用任何存儲空間C)執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D)執(zhí)行算法時所使用的額外空間固定（即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化）D【解析】對

6、于算法的空間復雜度，如果額外空間量相對于問題規(guī)模（即輸入數(shù)據(jù)所占的存儲空間）來說是常數(shù)，即額外空間量不隨問題規(guī)模的變化而變化，則稱該算法是原地工作的。8.下列敘述中正確的是A)算法的復雜度與問題的規(guī)模無關B)算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)C)對數(shù)據(jù)進行壓縮存儲會降低算法的空間復雜度D)數(shù)值型算法只需考慮計算結(jié)果的可靠性C【解析】在許多實際問題中，為了減少算法所占的存儲空間，通產(chǎn)采用壓縮存儲技術，以便盡量減少不必要的額外空間。9.下列敘述中正確的是A)數(shù)據(jù)的存儲結(jié)構會影響算法的效率B)算法設計只需考慮結(jié)果的可靠性C)算法復雜度是指算法控制結(jié)構的復雜程度D)算法復雜度是用算法中指令的條數(shù)來

7、度量的A【解析】采用不同的存儲結(jié)構，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理時，選擇合適的存儲結(jié)構很重要。10.下列敘述中錯誤的是 A)數(shù)據(jù)結(jié)構中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構B)數(shù)據(jù)結(jié)構中的數(shù)據(jù)元素不能是另一數(shù)據(jù)結(jié)構C)空數(shù)據(jù)結(jié)構可以是線性結(jié)構也可以是非線性結(jié)構D)非空數(shù)據(jù)結(jié)構可以沒有根結(jié)點B【解析】數(shù)據(jù)元素是一個含義很廣泛的概念，它是數(shù)據(jù)的“基本單位”，在計算機中通常作為一個整體進行考慮和處理。數(shù)據(jù)元素可以是一個數(shù)據(jù)也可以是被抽象出的具有一定結(jié)構數(shù)據(jù)集合，所以數(shù)據(jù)結(jié)構中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構。滿足有且只有一個根結(jié)點并且每一個結(jié)點最多有一個前件，也最多有一個后件的非空的數(shù)據(jù)結(jié)構認為

8、是線性結(jié)構，不滿足條件的結(jié)構為非線性結(jié)構。空數(shù)據(jù)結(jié)構可以是線性結(jié)構也可以是非線性結(jié)構。非空數(shù)據(jù)結(jié)構可以沒有根結(jié)點，如非性線結(jié)構“圖”就沒有根結(jié)點。11.下列敘述中正確的是A)非線性結(jié)構可以為空B)只有一個根結(jié)點和一個葉子結(jié)點的必定是線性結(jié)構C)只有一個根結(jié)點的必定是線性結(jié)構或二叉樹D)沒有根結(jié)點的一定是非線性結(jié)構A【解析】如果一個非空的數(shù)據(jù)結(jié)構滿足下列兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構為線性結(jié)構。如果一個數(shù)據(jù)結(jié)構不是線性結(jié)構，則稱之為非線性結(jié)構。線性結(jié)構和非線性結(jié)構都可以是空的數(shù)據(jù)結(jié)構。樹只有一個根結(jié)點，但不論有幾個葉子結(jié)點，樹都是非線性結(jié)

9、構。12.下列敘述中錯誤的是A)向量是線性結(jié)構B)非空線性結(jié)構中只有一個結(jié)點沒有前件C)非空線性結(jié)構中只有一個結(jié)點沒有后件D)具有兩個以上指針域的鏈式結(jié)構一定屬于非線性結(jié)構D【解析】雙向鏈表每個結(jié)點有兩個指針，一個為左指針，用于指向其前件結(jié)點；一個為右指針，用于指向其后件結(jié)點，再加上頭指針，具有兩個以上的指針，但雙向鏈表屬于線性結(jié)構。非空線性結(jié)構中第一個結(jié)點沒有前件，最后一個結(jié)點無后件，其余結(jié)點最多有一個前件，也最多有一個后件。向量也滿足這個條件，屬于線性結(jié)構。13.設數(shù)據(jù)結(jié)構B=(D, R)，其中 D= a, b, c, d, e,

10、 f  R= (f, a), (d, b), (e, d), (c, e), (a, c)  該數(shù)據(jù)結(jié)構為 A)線性結(jié)構B)循環(huán)隊列C)循環(huán)鏈表D)非線性結(jié)構A【解析】數(shù)據(jù)的邏輯結(jié)構有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關系，它反映了D中各數(shù)據(jù)元素之間的前后件關系，通常記為R。即一個數(shù)據(jù)結(jié)構可以表示成B=（D,R）。其中B表示數(shù)據(jù)結(jié)構。為了反映D中各數(shù)據(jù)元素之間的前后件關系，一般用二元組來表示。例如，假設a與b是D中的兩個數(shù)據(jù)，則二元組（a,b）表示

11、a是b的前件，b是a的后件。本題中R中的根結(jié)點為f，元素順序為facedb，滿足線性結(jié)構的條件。14.設數(shù)據(jù)集合為D= 1, 2, 3, 4, 5 。下列數(shù)據(jù)結(jié)構 B=(D, R)中為非線性結(jié)構的是 A)R= (2,5), (5,4), (3,1), (4,3) B)R= (1,2), (2,3), (3,4), (4,5) C)R= (1,2), (2,3), (4,3), 

12、(3,5) D)R= (5,4), (4,3), (3,2), (2,1) C【解析】A項中，R=(2,5),(5,4),(3,1),(4,3)，2為根結(jié)點，元素順序為25431，屬于線性結(jié)構；同理B項1為根結(jié)點，元素順序為12345，D項5為跟結(jié)點，元素順序為54321，均為線性結(jié)構。C項中，元素3有兩個前件，屬于非線性結(jié)構。15.下列敘述中正確的是A)矩陣是非線性結(jié)構B)數(shù)組是長度固定的線性表C)對線性表只能作插入與刪除運算D)線性表中各元素的數(shù)據(jù)類型可以不同B【解析】矩陣也是線性表，只不過是比較復雜的線性表。線性表中各元素的數(shù)據(jù)

13、類型必須相同。在線性表中，不僅可以做插入與刪除運算，還可以進行查找或?qū)€性表進行排序等操作。16.在線性表的順序存儲結(jié)構中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù) A不同，但元素的存儲順序與邏輯順序一致B)不同，且其元素的存儲順序可以與邏輯順序不一致C)相同，元素的存儲順序與邏輯順序一致D)相同，但其元素的存儲順序可以與邏輯順序不一致C【解析】在線性表的順序存儲結(jié)構中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)相同，在存儲空間中是按邏輯順序依次存放的。17.下列敘述中正確的是 A)能采用順序存儲的必定是線性結(jié)構B)所有的線性結(jié)構都可以采用順序存儲結(jié)構C)具有兩個以上指針的鏈表必定是非線性結(jié)構D)循環(huán)隊

14、列是隊列的鏈式存儲結(jié)構B【解析】所有的線性結(jié)構都可以用數(shù)組保存，即都可以采用順序存儲結(jié)構。而反過來不可以，完全二叉樹也能用數(shù)組保存（按層次依次存放到數(shù)據(jù)元素中），但完全二叉樹不屬于非線性結(jié)構。雙向鏈表具有兩個以上的指針，但屬于線性結(jié)構。循環(huán)隊列是隊列的順序存儲結(jié)構。18.下列敘述中正確的是A)在棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)B)在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度C)在循環(huán)鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度D)在線性鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度A【解析】在棧中，通常用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。棧頂指針top動

15、態(tài)反應了棧中元素的變化情況。在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度。鏈式存儲結(jié)構中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，并且各結(jié)點在存儲空間中的位置關系與邏輯關系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。19.設棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個數(shù)為A) 0 B)m C)不可能D)m+1C【解析】棧為空時，棧頂指針top=0，經(jīng)過入棧和退棧運算，指針始終指向棧頂元素。初始狀態(tài)為top=0，當棧滿時top=m，無法繼續(xù)入棧，top值不可能為m+1。20.設棧的存儲空間為S(1:50)，

16、初始狀態(tài)為top=-1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=30，則棧中的元素個數(shù)為A)20B)19C)31D)30D【解析】棧的初始狀態(tài)為top=-1表示棧為空（沒有規(guī)定棧中棧底必須是0），經(jīng)過一系列正常的入棧與退棧操作后top=30，則空間（1:30）中插入了元素，共30個。21.設棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=m+1，則棧中的數(shù)據(jù)元素個數(shù)為 A)top-m+1B)m-top+1C)m-topD)top-mB【解析】棧的初始狀態(tài)top=m+1，說明?？諘rtop=m+1（m在棧底，1是開口向上的），入棧時棧頂指針是減操作（top=top-1），退棧時棧頂指針是加操

17、作（top=top+1）。本題可以假設棧中有x個元素，當x=0時，也就是棧中沒有元素，則top=m+1；當x=m時，也就是棧滿，則top=1，由此可以得出top=m+1-x，繼而得出x=top-m+1。22.設棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=m+1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=0，則棧中的元素個數(shù)為A)1B)mC)m+1D)不可能D【解析】棧的初始狀態(tài)為top=m+1，說明棧空時top=m+1，入棧時棧頂指針是減操作（top=top-1），退棧時棧頂指針是加操作（top=top+1）。棧滿時top=1，說明棧中不能再進行入棧操作，top=0的情況不會出現(xiàn)。23

18、.設棧的存儲空間為S(1:m)，初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后，top=1。現(xiàn)又要將一個元素進棧，棧頂指針top值變?yōu)锳)0 B)發(fā)生棧滿的錯誤C)mD)2B【解析】棧的初始狀態(tài)為top=m+1，說明?？諘rtop=m+1，入棧時棧頂指針是減操作（top=top-1），退棧時棧頂指針是加操作（top=top+1）。棧滿時top=1，說明棧中不能再進行入棧操作（“上溢”錯誤）。24.設棧的存儲空間為S(1:m)，初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后，top=m。現(xiàn)又在棧中退出一個元素后，棧頂指針top值為A)0B)m-1C)m+1D)產(chǎn)生棧空錯誤C【解析】棧的

19、順序存儲空間為S(1: m)，初始狀態(tài)top=m+1，所以這個棧是m在棧底，1是開口向上的。經(jīng)過一系列入棧與退棧操作后top=m，則棧中有1個元素，若現(xiàn)在又退出一個元素，那么棧頂指針下移一位，回到m+1的位置。25.設棧的存儲空間為S(1:50)，初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=20，則棧中的元素個數(shù)為A)31B)30C)21D)20A【解析】棧的初始狀態(tài)top=51，故本棧是51在棧底，入棧時棧頂指針是減操作（top=top-1），退棧時棧頂指針是加操作（top=top+1）。當top=20時，元素存儲在(20:50)空間中，因此共有50-20+1=31個

20、元素。26.下列處理中與隊列有關的是 A)二叉樹的遍歷B)操作系統(tǒng)中的作業(yè)調(diào)度C)執(zhí)行程序中的過程調(diào)用D)執(zhí)行程序中的循環(huán)控制B【解析】隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。由于最先進入隊列的元素將最先出隊，所以隊列具有“先進先出”的特性，體現(xiàn)了“先來先服務”的原則。操作系統(tǒng)中的作業(yè)調(diào)度是指根據(jù)一定信息，按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進程插入就緒隊列的過程。執(zhí)行程序中的過程調(diào)用一般指函數(shù)調(diào)用，需要調(diào)用時候轉(zhuǎn)入被調(diào)用函數(shù)地址執(zhí)行程序，與隊列無關。執(zhí)行程序中的循環(huán)控制是指算法的基本控制結(jié)構，包括對循環(huán)條件的判定與執(zhí)行循環(huán)體，與隊列無關。

21、二叉樹是一個有限的結(jié)點集合，二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點，與隊列無關。27.設有棧S和隊列Q，初始狀態(tài)均為空。首先依次將A,B,C,D,E,F入棧，然后從棧中退出三個元素依次入隊，再將X,Y,Z入棧后，將棧中所有元素退出并依次入隊，最后將隊列中所有元素退出，則退隊元素的順序為A)DEFXYZABCB)FEDZYXCBAC)FEDXYZCBAD)DEFZYXABCB【解析】棧是一種特殊的線性表，它所有的插入與刪除都限定在表的同一端進行。隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。將A,B,C,D,E,F入棧后，棧中元素為ABCDEF，退出三個元素入隊，隊列元素為FE

22、D，將X,Y,Z入棧后棧中元素為ABCXYZ，退棧全部入隊后，隊列元素為FEDZYXCBA。28.下列敘述中正確的是 A)循環(huán)隊列是順序存儲結(jié)構B)循環(huán)隊列是鏈式存儲結(jié)構C)循環(huán)隊列空的條件是隊頭指針與隊尾指針相同D)循環(huán)隊列的插入運算不會發(fā)生溢出現(xiàn)象A【解析】循環(huán)隊列是隊列的一種順序存儲結(jié)構。在循環(huán)隊列中，在隊列滿和隊列為空時，隊頭指針與隊尾指針均相同；當需要插入的數(shù)據(jù)大于循環(huán)隊列的存儲長度，入隊運算會覆蓋前面的數(shù)據(jù)，發(fā)生溢出現(xiàn)象。29.下列敘述中正確的是A)在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度B)在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度C)在帶鏈的隊列中，隊頭指針

23、與隊尾指針的動態(tài)變化決定隊列的長度D)在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)B【解析】在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度。帶鏈的棧和帶鏈的隊列均采用鏈式存儲結(jié)構，而在這種結(jié)構中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，并且各結(jié)點在存儲空間中的位置關系與邏輯關系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。30.循環(huán)隊列的存儲空間為 Q(1:50)，初始狀態(tài)為 front=rear=50。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=25，此后又插入一個元素，則循環(huán)隊列中的元素個數(shù)為A)1，或50且產(chǎn)生上溢錯誤B)51C)26D)2A【解析】循環(huán)隊列長

24、度為50，由初始狀態(tài)為front=rear=50可知此時循環(huán)隊列為空。入隊運算時，首先隊尾指針rear進1（即rear+1），然后在隊尾指針rear指向的位置插入新元素。當隊尾指針rear=50+1時，置rear=1。退隊運算時，排頭指針front進1（即front+1），然后刪除front指針指向的位置上的元素，當排頭指針front=50+1時，置front=1。當front=rear=25時可知隊列空或者隊列滿，此后又插入了一個元素，如果之前隊列為空，插入操作之后隊列里只有一個元素；如果插入之前隊列已滿(50個元素)，執(zhí)行插入則會產(chǎn)生溢出錯誤。31.循環(huán)隊列的存儲空間為 Q(1:40)，初

25、始狀態(tài)為 front=rear=40。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=15，此后又退出一個元素，則循環(huán)隊列中的元素個數(shù)為A) 14B)15C)40D)39，或0且產(chǎn)生下溢錯誤D【解析】當front=rear=15時可知隊列空或者隊列滿，此后又退出一個元素，如果之前隊列為空，退出操作會產(chǎn)生錯誤，隊列里有0個元素；如果退出之前隊列已滿(40個元素)，執(zhí)行退出后，隊列里還有39個元素。32.設循環(huán)隊列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50?，F(xiàn)經(jīng)過一系列入隊與退隊操作后，front=rear=1，此后又正常地插入了兩個元素。最后該隊列中的元素個數(shù)為A)

26、3B)1C)2D)52C【解析】由front=rear=1可知隊列空或者隊列滿,此后又可以正常地插入了兩個元素說明插入前隊列為空，則插入后隊列元素個數(shù)為2。33.設循環(huán)隊列的存儲空間為Q(1:m)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作后，front=m，rear=m-1，此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為A)m-1B)m-2C)0D)1B【解析】從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。如果rear-front>0，則隊列中的元素個數(shù)為rear-front個；如果rear-front<0，則隊列中的

27、元素個數(shù)為rear-front+m。該題中m-1<m，即rear-front<0，則該循環(huán)隊列中的元素個數(shù)為（m-1）-m+m=m-1。此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為m-1-1=m-2。34.設循環(huán)隊列的存儲空間為Q(1:m)，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作后，front=m-1，rear=m，此后再向該循環(huán)隊列中插入一個元素，則隊列中的元素個數(shù)為A) m B)m-1C)1D)2D【解析】該題中m-1<m，即rear-front>0，則該循環(huán)隊列中的元素個數(shù)為m-（m-1）=1。此后從該循環(huán)隊列中插入一個元素，則隊列中的元素個數(shù)為1

28、+1=2。35.設循環(huán)隊列為Q(1:m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊與退隊運算后，front=30，rear=10。現(xiàn)要在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)為 A)19B)20C)m-19D)m-20D【解析】front=30，rear=10，front>rear，則隊列中有10-30+m=m-20個元素，在作順序查找時，最壞情況下（最后一個元素才是要找的元素或沒有要查找的元素）比較次數(shù)為m-20次。36.設循環(huán)隊列的存儲空間為Q(1:m)，初始狀態(tài)為 front=rear=m。經(jīng)過一系列正常的操作后，front=1，rear=m。為了在

29、該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A)0B)1C)m-2D)m-1C【解析】該題中1<m，即rear-front>0，則該循環(huán)隊列中的元素個數(shù)為m-1。此在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為m-1-1=m-2。37.設循環(huán)隊列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front-1=rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A)48B)49C)1D)0A【解析】該題中rear-front=front-1- front<0，則該循環(huán)隊列中的元素個數(shù)為rear-fr

30、ont+50=front-1- front+50=49。在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為49-1=48。38.設循環(huán)隊列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear-1。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A)1B)0C)49D)50B【解析】該題中rear-front=rear-（rear-1）>0，則該循環(huán)隊列中的元素個數(shù)為rear-front=rear-（rear-1）=1。因隊列中只有1個元素，故尋找值最大的元素不需要進行比較，即比較次數(shù)為0。39.線性表的鏈式存儲結(jié)

31、構與順序存儲結(jié)構相比，鏈式存儲結(jié)構的優(yōu)點有 A)節(jié)省存儲空間B)插入與刪除運算效率高C)便于查找D)排序時減少元素的比較次數(shù)B【解析】線性表的順序存儲結(jié)構稱為順序表，線性表的鏈式存儲結(jié)構稱為鏈表，兩者的優(yōu)缺點如下表所示。類型優(yōu)點 缺點順序表（1）可以隨機存取表中的任意結(jié)點（2）無需為表示結(jié)點間的邏輯關系額外增加存儲空間（1）插入和刪除運算效率低（2）存儲空間不便于擴充（3）不便于對存儲空間的動態(tài)分配鏈表（1）在進行插入和刪除運算時，只需要改變指針即可，不需要移動元素（2）存儲空間易于擴充并且方便空間的動態(tài)分配需要額外的空間（指針域）來表示數(shù)據(jù)元素之間的邏輯關系，存儲密度比順序表低40.下列結(jié)構

32、中屬于線性結(jié)構鏈式存儲的是A)雙向鏈表B)循環(huán)隊列C)二叉鏈表D)二維數(shù)組A【解析】雙向鏈表也叫雙鏈表，是鏈表（采用鏈式存儲結(jié)構）的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。循環(huán)隊列是隊列的一種順序存儲結(jié)構。二叉鏈表和二維數(shù)組屬于非線性結(jié)構。41.在線性表的鏈式存儲結(jié)構中，其存儲空間一般是不連續(xù)的，并且 A)前件結(jié)點的存儲序號小于后件結(jié)點的存儲序號B)前件結(jié)點的存儲序號大于后件結(jié)點的存儲序號C)前件結(jié)點的存儲序號可以小于也可以大于后件結(jié)點的存儲序號D)以上三種說法均不正確C【解析】在線性表的鏈式存儲結(jié)構中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，并且各結(jié)點在存儲空間中的位置關系

33、與邏輯關系也不一致，因此前件結(jié)點的存儲序號與后件結(jié)點的存儲序號之間不存在大小關系。42.下列敘述中正確的是 A)結(jié)點中具有兩個指針域的鏈表一定是二叉鏈表B)結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構，也可以是非線性結(jié)構C)循環(huán)鏈表是循環(huán)隊列的鏈式存儲結(jié)構D)循環(huán)鏈表是非線性結(jié)構B【解析】結(jié)點中具有兩個指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構，二叉鏈表屬于非線性結(jié)構。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構，采用鏈式存儲結(jié)構，而循環(huán)隊列是隊列的一種順序存儲結(jié)構。43.帶鏈的棧與順序存儲的棧相比，其優(yōu)點是 A)入棧與退棧操作方便B)可以省略棧底指針C)入棧操作時不會受棧存儲

34、空間的限制而發(fā)生溢出D)所占存儲空間相同C【解析】帶鏈的棧就是用一個線性鏈表來表示的棧，線性鏈表不受存儲空間大小的限制，因此入棧操作時不會受棧存儲空間的限制而發(fā)生溢出（不需考慮棧滿的問題）。44.下列敘述中正確的是 A)帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的B)若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列為空C)若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列中至少有一個元素D)不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的A【解析】由于帶鏈棧利用的是計算機存儲空間中的所有空閑存儲結(jié)點，因此隨棧的操作棧頂棧底指針動態(tài)變化。帶鏈的隊列中若只有一個元素，則頭指針與尾指針相同。45.帶鏈棧

35、空的條件是 A)top=bottom=NULLB)top=-1 且 bottom=NULLC)top=NULL 且 bottom=-1D)top=bottom=-1A【解析】在帶鏈的棧中，只會出現(xiàn)?？蘸头强諆煞N狀態(tài)。當棧為空時，有top=bottom=NULL；當棧非空時，top指向鏈表的第一個結(jié)點（棧頂）。46.在帶鏈棧中，經(jīng)過一系列正常的操作后，如果top=bottom，則棧中的元素個數(shù)為 A)0 或 1B)0C)1D)棧滿A【解析】帶鏈棧就是沒有附加頭結(jié)點、運算受限的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底指針指向的存儲單元中

36、存有一個元素，則當top=bottom時，棧中的元素個數(shù)為1；如果棧底指針指向的存儲單元中沒有元素，則當top=bottom時，棧中的元素個數(shù)為0。47.某帶鏈棧的初始狀態(tài)為top=bottom=NULL，經(jīng)過一系列正常的入棧與退棧操作后，top=bottom=20。該棧中的元素個數(shù)為 A)0B)1C)20D)不確定B【解析】帶鏈的棧就是用一個單鏈表來表示的棧，棧中的每一個元素對應鏈表中的一個結(jié)點。棧為空時，頭指針和尾指針都為NULL；棧中只有一個元素時，頭指針和尾指針都指向這個元素。48.某帶鏈棧的初始狀態(tài)為top=bottom=NULL，經(jīng)過一系列正常的入棧與退棧操作后，top=10，bo

37、ttom=20。該棧中的元素個數(shù)為 A)0 B)1C)10D)不確定D【解析】帶鏈的棧使用了鏈表來表示棧，而鏈表中的元素存儲在不連續(xù)的地址中，因此當top=10，bottom=20時，不能確定棧中元素的個數(shù)。49.帶鏈隊列空的條件是 A)front=rear=NULLB)front=-1 且 rear=NULLC)front=NULL 且 rear=-1D)front=rear=-1A【解析】帶鏈的隊列就是用一個單鏈表來表示的隊列，隊列中的每一個元素對應鏈表中的一個結(jié)點。隊列空時，頭指針和尾指針都為NULL。50.在帶鏈隊列中，經(jīng)過一系列正常的操作后，如

38、果front=rear，則隊列中的元素個數(shù)為 A)0B)1C)0 或 1D)隊列滿C【解析】帶鏈隊列空時，頭指針和尾指針都為NULL；隊列中只有一個元素時，頭指針和尾指針都指向這個元素。51.某帶鏈的隊列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=10。該隊列中的元素個數(shù)為 A)0B)1C)1或0D)不確定B【解析】帶鏈隊列空時，頭指針和尾指針都為null；隊列中只有一個元素時，頭指針和尾指針都指向這個元素。52.某帶鏈的隊列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊與退隊操作后，front=10,&

39、#160;rear=5。該隊列中的元素個數(shù)為 A)4 B)5C)6D)不確定D【解析】帶鏈的隊列使用了鏈表來表示隊列，而鏈表中的元素存儲在不連續(xù)的地址中，因此當front=10,rear=5時，不能確定隊列中元素的個數(shù)。53.下列敘述中錯誤的是 A)循環(huán)鏈表中有一個表頭結(jié)點B)循環(huán)鏈表是循環(huán)隊列的存儲結(jié)構C)循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點D)循環(huán)鏈表實現(xiàn)了空表與非空表運算的統(tǒng)一B【解析】循環(huán)鏈表是指在單鏈表的第一個結(jié)點前增加一個表頭結(jié)點，隊頭指針指向表頭結(jié)點，最后一個結(jié)點的指針域的值由NULL改為指向表頭結(jié)點。循環(huán)鏈表是線性表的一種鏈式存儲結(jié)構，循環(huán)隊列是隊列的

40、一種順序存儲結(jié)構。54.從表中任何一個結(jié)點位置出發(fā)就可以不重復地訪問到表中其他所有結(jié)點的鏈表是A)循環(huán)鏈表B)雙向鏈表C)單向鏈表D)二叉鏈表A【解析】在循環(huán)鏈表中，所有結(jié)點的指針構成了一個環(huán)狀鏈，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)不重復地訪問到表中其他所有結(jié)點。55.非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構 A)有根結(jié)點也有葉子結(jié)點B)沒有根結(jié)點但有葉子結(jié)點C)有根結(jié)點但沒有葉子結(jié)點D)沒有根結(jié)點也沒有葉子結(jié)點A【解析】循環(huán)鏈表表頭結(jié)點為根結(jié)點，鏈表的最后一個結(jié)點為葉子節(jié)點，雖然它含有一個指向表頭結(jié)點的指針，但是表頭結(jié)點并不是它的一個后件。56.下列結(jié)構中為非線性結(jié)構的是A)樹B)向量C)二

41、維表D)矩陣A【解析】由定義可以知道，樹為一種簡單的非線性結(jié)構。在數(shù)這種數(shù)據(jù)結(jié)構中，所有數(shù)據(jù)元素之間的關系具有明顯的層次特性。57.某棵樹中共有25個結(jié)點，且只有度為3的結(jié)點和葉子結(jié)點，其中葉子結(jié)點有7個，則該樹中度為3的結(jié)點數(shù)為A)6B)7C)8D)不存在這樣的樹D【解析】根據(jù)題意，樹中只有度為3的結(jié)點和葉子結(jié)點（7個），則度為3的結(jié)點有25-7=18個；又根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，設度為3的結(jié)點數(shù)為n,則3n+1=25,得n=8。兩種方式得到的度為3的結(jié)點數(shù)不同，故不存在這樣的樹。58.某棵樹的度為4，且度為4、3、2、1的結(jié)點個數(shù)分別為1、2、3、4，則該樹中的葉子結(jié)點

42、數(shù)為A)11B)9C)10D)8A【解析】設葉子結(jié)點數(shù)為n，根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，得4×1+3×2+2×3+1×4+n×0+1=21,則n=21-1-2-3-4=11。59.設一棵樹的度為3，共有27個結(jié)點，其中度為3，2，0的結(jié)點數(shù)分別為4，1，10。該樹中度為1的結(jié)點數(shù)為 A) 11B) 12C) 13D)不可能有這樣的樹B【解析】設度為1的結(jié)點數(shù)為n，根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，得3×4+2×1+1×n+0×10+1=27，則n=12。60.設一棵度為3的樹，其

43、中度為2，1，0的結(jié)點數(shù)分別為3，1，6。該樹中度為3的結(jié)點數(shù)為A)1B)2C)3D)不可能有這樣的樹A【解析】設樹的結(jié)點數(shù)為n，則度為3的結(jié)點數(shù)為n-3-1-6=n-10，根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，得3×（n-10）+2×3+1×1+0×6+1=n，解得n=11，則度為3的結(jié)點數(shù)為n-10=11-10=1。61.設一棵樹的度為3，其中沒有度為2的結(jié)點，且葉子結(jié)點數(shù)為5。該樹中度為3的結(jié)點數(shù)為 A) 3B)1C) 2D)不可能有這樣的樹C【解析】設樹的結(jié)點數(shù)為m，度為3的結(jié)點數(shù)為n，則度為1的結(jié)點數(shù)為m-n-5, 根據(jù)樹中的結(jié)點數(shù)=樹中

44、所有結(jié)點的度之和+1，得3×n+1×（m-n-5）+5×0+1=m，則n=2。62.度為3的一棵樹共有30個結(jié)點，其中度為3,1的結(jié)點個數(shù)分別為3,4。則該樹中的葉子結(jié)點數(shù)為A) 14B) 15C) 16D)不可能有這樣的樹B【解析】設葉子結(jié)點數(shù)為n，則度為2的結(jié)點數(shù)為30-3-4-n=23-n，根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，得3×3+2×（23-n）+1×4+0×n+1=30，則n=15。63.設某棵樹的度為3，其中度為2,1,0的結(jié)點個數(shù)分別為3,4,15。則該樹中總結(jié)點數(shù)為A)不可能有這樣的樹B)30C)

45、22D)35A【解析】設樹的總結(jié)點數(shù)為n，則度為3的結(jié)點數(shù)為n-3-4-15=n-22，根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1，得3×（n-22）+2×3+1×4+0×15+1=n，則n=27.5，求出的結(jié)點數(shù)不為整數(shù)，故不可能有這樣的樹存在。64.某二叉樹共有845個結(jié)點，其中葉子結(jié)點有45個，則度為1的結(jié)點數(shù)為 A)400B)754C)756D)不確定C【解析】葉子結(jié)點有45個，根據(jù)在二叉樹中度為0的結(jié)點（葉子結(jié)點）總比度為2的結(jié)點多一個，則度為2的結(jié)點數(shù)為44個，因此度為1的結(jié)點數(shù)為845-45-44=756個。65.某二叉樹中有15個度為1的

46、結(jié)點，16個度為2的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為 A)32B)46C)48D)49C【解析】根據(jù)在二叉樹中度為0的結(jié)點（葉子結(jié)點）總比度為2的結(jié)點多一個，得度為0的結(jié)點數(shù)為16+1=17個，故總的結(jié)點數(shù)=17+15+16=48個。66.某二叉樹共有730個結(jié)點，其中度為1的結(jié)點有30個，則葉子結(jié)點個數(shù)為 A) 1B)351C) 350D)不存在這樣的二叉樹D【解析】設葉子結(jié)點數(shù)為n，根據(jù)在二叉樹中度為0的結(jié)點（葉子結(jié)點）總比度為2的結(jié)點多一個，則度為2的結(jié)點數(shù)為n-1,n+n-1+30=730，得n=350.5。由于結(jié)點數(shù)只能為整數(shù)，所以不存在這樣的二叉樹。67.某二叉樹中共有350個結(jié)點，

47、其中200個為葉子結(jié)點，則該二叉樹中度為2的結(jié)點數(shù)為 A)不可能有這樣的二叉樹B)150C)199D)149A【解析】葉子結(jié)點數(shù)為200，根據(jù)在二叉樹中度為0的結(jié)點（葉子結(jié)點）總比度為2的結(jié)點多一個，則度為2的結(jié)點數(shù)為199，199+200>350，故不存在這樣的二叉樹。68.某二叉樹的深度為7，其中有64個葉子結(jié)點，則該二叉樹中度為1的結(jié)點數(shù)為 A)0B)1C)2D)63A【解析】葉子結(jié)點有64個，根據(jù)在二叉樹中度為0的結(jié)點（葉子結(jié)點）總比度為2的結(jié)點多一個，則度為2的結(jié)點數(shù)為63個；又深度為m的二叉樹最多有2m-1個結(jié)點，則該二叉樹最多有27-1=127個結(jié)點。64+63=127，因

48、此該樹不存在度為1的結(jié)點。69.深度為7的二叉樹共有127個結(jié)點，則下列說法中錯誤的是 A)該二叉樹是滿二叉樹B)該二叉樹有一個度為1的結(jié)點C)該二叉樹是完全二叉樹D)該二叉樹有64個葉子結(jié)點B【解析】滿二叉樹滿足深度為m的二叉樹最多有2m-1個結(jié)點，本題中二叉樹深度為7且有127個結(jié)點，滿足27-1=127，達到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹。滿二叉樹第k層上有2k-1結(jié)點，則該二叉樹的葉子結(jié)點數(shù)為27-1=64個。滿二叉樹不存在度為1的結(jié)點。70.深度為5的完全二叉樹的結(jié)點數(shù)不可能是 A)15B)16C)17D)18A【解析】設完全二叉樹的結(jié)點數(shù)為n，根據(jù)深度為k的二叉樹至多

49、有2k-1個結(jié)點，再根據(jù)完全二叉樹的定義可知，2k-1-1<n2k-1。本題中完全二叉樹的深度為5，則25-1-1<n25-1，15<n31。因此，結(jié)點數(shù)不能為15。71.某完全二叉樹共有256個結(jié)點，則該完全二叉樹的深度為 A)7B)8C)9D)10C【解析】根據(jù)完全二叉樹的性質(zhì)：具有n個結(jié)點的完全二叉樹的深度為log2n+1。本題中完全二叉樹共有256個結(jié)點，則深度為log2256+1=8+1=9。72.深度為的完全二叉樹中共有125個結(jié)點，則該完全二叉樹中的葉子結(jié)點數(shù)為 A)62B)63C)64D)65B【解析】在滿二叉樹的第k層上有2k-1個結(jié)點、且深度為m的滿二叉樹

50、有2m-1個結(jié)點，則深度為6的滿二叉樹共有26-1=63個結(jié)點，第6層上有26-1=32個結(jié)點。本題是深度為7的完全二叉樹，則前6層共有63個結(jié)點，第7層的結(jié)點數(shù)為125-63=62個且全為葉子結(jié)點。由于第6層上有32個結(jié)點，第7層上有62個結(jié)點，則第6層上有1個結(jié)點無左右子樹（該結(jié)點為葉子結(jié)點）。因此，該完全二叉樹中共有葉子結(jié)點62+1=63個。73.在具有2n個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為A)nB)n+1C)n-1D)n/2A【解析】由二叉樹的定義可知，樹中必定存在度為0的結(jié)點和度為2的結(jié)點，設度為0結(jié)點有a個，根據(jù)度為0的結(jié)點（即葉子結(jié)點）總比度為2的結(jié)點多一個，得度為2的結(jié)點有a

51、-1個。再根據(jù)完全二叉樹的定義，度為1的結(jié)點有0個或1個，假設度1結(jié)點為0個，a+0+a-1=2n，得2a=2n-1，由于結(jié)點個數(shù)必須為整數(shù)，假設不成立；當度為1的結(jié)點為1個時，a+1+a-1=2n，得a=n，即葉子結(jié)點個數(shù)為n。74.下列數(shù)據(jù)結(jié)構中為非線性結(jié)構的是 A)二叉鏈表B)循環(huán)隊列C)循環(huán)鏈表D)雙向鏈表A【解析】二叉樹的鏈式存儲結(jié)構也稱為二叉鏈表，二叉樹是樹的一種，屬于非線性結(jié)構。75.下列敘述中正確的是A)非完全二叉樹可以采用順序存儲結(jié)構B)有兩個指針域的鏈表就是二叉鏈表C)有的二叉樹也能用順序存儲結(jié)構表示D)順序存儲結(jié)構一定是線性結(jié)構C【解析】在計算機中，二叉樹通常采用鏈式存儲

52、結(jié)構，但對于滿二叉樹和完全二叉樹來說，可以按層進行順序存儲。因此A項錯誤，C項正確。雖然滿二叉樹和完全二叉樹可以采用順序存儲結(jié)構，但仍是一種非線性結(jié)構，因此D項錯誤。雙向鏈表也有兩個指針域，因此B項錯誤。76.有二叉樹如下圖所示：則前序序列為A)ABDEGCFHB)DBGEAFHCC)DGEBHFCAD)ABCDEFGHA【解析】前序遍歷首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。故本題前序序列是ABDEGCFH。中序遍歷首先遍歷左子樹，然后訪問跟結(jié)點，最后遍歷右子樹；在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問跟結(jié)點

53、，最后遍歷右子樹。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點；在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。故本題的后序序列是DGEBHFCA。77.設二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為 A)JIHGFEDCBAB)DGHEBIJFCA C)GHIJDEFBCAD)ABCDEFGHIJB【解析】二叉樹的前序序列為ABDEGHCFIJ，由于前序遍歷首先訪問根結(jié)點，可以確定該二叉樹的根結(jié)點是A。再由中序序列為DBGEHACIFJ，可以得到結(jié)點D、B、G、E、H位于根結(jié)點的左子樹

54、上，結(jié)點C、I、F、J位于根結(jié)點的右子樹上。由于中序遍歷和后序遍歷都是先遍歷左子樹，故本題后序遍歷首先訪問D結(jié)點；再由后序遍歷是最后訪問根結(jié)點，故本題后序遍歷最后訪問的結(jié)點是根結(jié)點A。采用排除法可知，后續(xù)序列為DGHEBIJFCA。78.某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBEDA，則前序遍歷序列為 A)CBADEB)CBEDAC)ABCDED)EDCBAC【解析】二叉樹的后序遍歷序列為CBEDA，由于后序遍歷最后訪問根結(jié)點，可以確定該二叉樹的根結(jié)點是A。再由中序遍歷序列為CBADE，可以得到子序列（CB）一定在左子樹中，子序列（DE）一定在右子樹中。結(jié)點C、B在中序序列和后序

55、序列中順序未變，說明結(jié)點B是結(jié)點C的父結(jié)點；結(jié)點D、E在中序序列和后序序列中順序相反，說明結(jié)點D是結(jié)點E的父結(jié)點。因此該二叉樹的前序遍歷序列為ABCDE。79. 某二叉樹的前序序列為ABCDEFG，中序序列為DCBAEFG，則該二叉樹的深度（根結(jié)點在第1層）為A)2B)3C)4D)5C【解析】二叉樹的前序序列為ABCDEFG，則A為根結(jié)點；中序序列為DCBAEFG，可知結(jié)點D、C、B位于根結(jié)點的左子樹上，結(jié)點E、F、G位于根結(jié)點的右子樹上。另外，結(jié)點B、C、D在前序序列和中序序列中順序相反，則說明這三個結(jié)點依次位于前一個結(jié)點的左子樹上；結(jié)點E、F、G順序未變，則說明這三個結(jié)點依次位于前一個結(jié)點

56、的右子樹上。故二叉樹深度為4。80.設二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為 A)ABCDHGFEB)DCBAHGFEC)EFGHABCDD)HGFEDCBAD【解析】二叉樹的前序序列與中序序列均為ABCDEFGH，可知二叉樹根結(jié)點為A，且根結(jié)點A只有右子樹，沒有左子樹。同理，可以推出結(jié)點B只有右子樹無左子樹。依此類推，該二叉樹除葉子結(jié)點外，每個結(jié)點只有右子樹無左子樹。因此該二叉樹的后序序列為HGFEDCBA。81.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為A)CBAFEDB)FEDCBA C)DEFCBA

57、D)ABCDEFB【解析】該二叉樹的后序遍歷序列與中序遍歷序列均為ABCDEF，則根結(jié)點為F；根結(jié)點F只有左子樹，右子樹為空。即ABCDE是根結(jié)點F的右子樹集合。這樣問題就轉(zhuǎn)化為就后序遍歷序列與中序遍歷序列均為ABCDE的子樹，同理可得左子樹集合的根結(jié)點為E，且根結(jié)點只有左子樹右子樹。依次類推，該二叉樹除葉子結(jié)點外，每個結(jié)點只有左子樹無右子樹，結(jié)構如下：按層次輸出（同一層從左到右）的序列為FEDCBA。82.某二叉樹的前序序列為ABDFHCEG，中序序列為HFDBACEG。該二叉樹按層次輸出（同一層從左到右）的序列為 A)HGFEDCBAB)HFDBGECAC)ABCDEFGH D)ACEGBDFHC【解析】二叉樹的前序序列為ABDFHCEG，可以確定這個二叉樹的根結(jié)點是A；再由中序序列HFDBACEG，可以得到HFDB為根結(jié)點A的左子樹，CEG為根結(jié)點A的右子樹。同理依次對左子樹HFDB和右子樹CEG進行同樣的推理，得到該二叉樹的結(jié)構如下：該二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。83.某完全二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該完全二叉樹的前序序列為 A)ABCDEFGH B)ABDHECFGC)HDBEAFCGD)HDEBFGCAB【解析】完全二叉樹的特點是除最后一層外