計算機二級選擇

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

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

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

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

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

6、化而變化）D【解析】對于算法的空間復雜度，如果額外空間量相對于 問題規(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é)構(gòu)會影響算法的效率B）算法設計只需考慮結(jié)果的可靠性C）算法復雜度是指算法控制結(jié)構(gòu)的復雜程度D

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

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

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

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

11、件。14設數(shù)據(jù)集合為D= 1, 2, 3, 4, 5 。下列數(shù)據(jù)結(jié)構(gòu)B=(D, R) 中為非線性結(jié)構(gòu)的是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), (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é)點，元 素順序為2 5 43 1,屬于線性結(jié)構(gòu)；同理B項1為根結(jié) 點，元素順序為1 2 3 4 5, D項5為跟結(jié)點，元素順序 為5 4 3 2 1，均

12、為線性結(jié)構(gòu)。C項中，元素3有兩個前 件，屬于非線性結(jié)構(gòu)。15下列敘述中正確的是A) 矩陣是非線性結(jié)構(gòu)B) 數(shù)組是長度固定的線性表C) 對線性表只能作插入與刪除運算D) 線性表中各元素的數(shù)據(jù)類型可以不同B【解析】矩陣也是線性表，只不過是比較復雜的線性表。線 性表中各元素的數(shù)據(jù)類型必須相同。在線性表中，不僅可以 做插入與刪除運算，還可以進行查找或?qū)€性表進行排序等 操作。16在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素 所占的字節(jié)數(shù)A不同，但元素的存儲順序與邏輯順序一致B) 不同，且其元素的存儲順序可以與邏輯順序不一致C) 相同，元素的存儲順序與邏輯順序一致D) 相同，但其元素的存儲順序可以

13、與邏輯順序不一致C【解析】在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各 個元素所占的字節(jié)數(shù)相同，在存儲空間中是按邏輯順序依次 存放的。17下列敘述中正確的是A) 能采用順序存儲的必定是線性結(jié)構(gòu)B) 所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)C) 具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)D) 循環(huán)隊列是隊列的鏈式存儲結(jié)構(gòu)B【解析】所有的線性結(jié)構(gòu)都可以用數(shù)組保存，即都可以采用 順序存儲結(jié)構(gòu)。而反過來不可以，完全二叉樹也能用數(shù)組保 存(按層次依次存放到數(shù)據(jù)元素中)，但完全二叉樹不屬于非 線性結(jié)構(gòu)。雙向鏈表具有兩個以上的指針，但屬于線性結(jié)構(gòu)。 循環(huán)隊列是隊列的順序存儲結(jié)構(gòu)。18下列敘述中正確的是A) 在棧中，

14、棧頂指針的動態(tài)變化決定棧中元素的個數(shù)B) 在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度C) 在循環(huán)鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的 長度D) 在線性鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的 長度A【解析】在棧中，通常用指針 top來指示棧頂?shù)奈恢?，用?針bottom指向棧底。棧頂指針top動態(tài)反應了棧中元素的變 化情況。在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決 定隊列的長度。鏈式存儲結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序號是 不連續(xù)的，并且各結(jié)點在存儲空間中的位置關系與邏輯關系 也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。19. 設棧的順序存儲空間為 S(1:m),初始狀

15、態(tài)為top=0?，F(xiàn)經(jīng)過 一系列正常的入棧與退棧操作后，top=m+1 ，則棧中的元素 個數(shù)為A) 0B) mC) 不可能D) m+1C【解析】棧為空時，棧頂指針top=0，經(jīng)過入棧和退棧運算， 指針始終指向棧頂元素。初始狀態(tài)為top=0，當棧滿時top=m， 無法繼續(xù)入棧，top值不可能為m+1。20. 設棧的存儲空間為S(1:50)初始狀態(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，

16、則空間(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 )，退棧時棧頂指針是加操作(top=top+1 )。本題 可以假設棧中有x個元素，當x=0時，也就是棧中沒有元素， 則top=m+1 ；當x=m時，也就是棧滿，則top=1，由此可以 得出top=m+1-x，繼而得出 m-top+1。22. 設棧的

17、順序存儲空間為 S(1:m),初始狀態(tài)為top=m+1。現(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. 設棧的存儲空間為S(1:m)初始狀態(tài)為top=m+1。經(jīng)過一 系列入棧與退棧操作后，top=1。現(xiàn)又要將一個元素進棧，棧 頂指針top值變?yōu)锳) 0B) 發(fā)生棧滿的錯誤C) mD) 2

18、B【解析】棧的初始狀態(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【解析】棧的順序存儲空間為 S(1: m),初始狀態(tài)top=m+1， 所以這個棧是m在棧底，1是開口向上的。經(jīng)過一系列入棧 與退棧操作后top=m，則棧中有1個元素，

19、若現(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+仁31個元素。26. 下列處理中與隊列有關的是A) 二叉樹的遍歷B) 操作系統(tǒng)中的作業(yè)調(diào)度C) 執(zhí)行程序中的過程調(diào)用D) 執(zhí)行程序中的循

20、環(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é) 構(gòu)，包括對循環(huán)條件的判定與執(zhí)行循環(huán)體，與隊列無關。二 叉樹是一個有限的結(jié)點集合，二叉樹的遍歷是指不重復地訪 問二叉樹中的所有結(jié)點，與隊列無關。27. 設有棧

21、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，退出三個元素入隊，隊列元素為FED，將X,Y,Z 入棧后棧中元素為ABCXYZ，退棧全部入隊后，隊列元素為 FED

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

23、指針的動態(tài)變化決定棧中元素的個數(shù) B【解析】在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決 定隊列的長度。帶鏈的棧和帶鏈的隊列均采用鏈式存儲結(jié)構(gòu)， 而在這種結(jié)構(gòu)中，各數(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)隊列長度為 50,由初始狀態(tài)為fron

24、t=rear=50 可知此時循環(huán)隊列為空。入隊運算時，首先隊尾指針rear進1(即rea葉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)，初始狀態(tài)為

25、 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。現(xiàn)經(jīng)過一系列入隊與退隊操作后， front=rear=1，此后又正常地插入了兩個元素。最后該隊列中 的

26、元素個數(shù)為A) 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個；

27、如果rear-front<0，則隊列中的元素個數(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)為空。現(xiàn)經(jīng)過 一系列正常的入隊與退隊操作后，front=m-1，rear=m，此后 再向該循環(huán)隊列中插入一個元素，則隊列中的元素個數(shù)為A) mB) m-1C) 1D) 2D【解析】該題中 m-1<m,即卩rear-front>0，則該循環(huán)隊列中 的元素個數(shù)為 m- (

28、m-1) =1。此后從該循環(huán)隊列中插入一個 元素，則隊列中的元素個數(shù)為 1+1=2。35. 設循環(huán)隊列為Q(1:m)，其初始狀態(tài)為front=rear=m。經(jīng)過 一系列入隊與退隊運算后，front=30，rear=10o現(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)，初始狀

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

30、【解析】該題中 rear-front=front-1- front<0，則該循環(huán)隊列 中的元素個數(shù)為 rear-front+50=front-1- front+50=49。在該隊 列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為49-仁 48o38設循環(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-

31、front=rear- (rear-1) =1。因隊列中只有1 個元素，故尋找值最大的元素不需要進行比較，即比較次數(shù) 為0o39線性表的鏈式存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈式存儲結(jié) 構(gòu)的優(yōu)點有A) 節(jié)省存儲空間B) 插入與刪除運算效率高C) 便于查找D) 排序時減少元素的比較次數(shù)B【解析】線性表的順序存儲結(jié)構(gòu)稱為順序表，線性表的鏈式 存儲結(jié)構(gòu)稱為鏈表，兩者的優(yōu)缺點如下表所示。類型優(yōu)點缺點順序表(1) 可以隨機存取表中 的任意結(jié)點(2) 無需為表示結(jié)點間 的邏輯關系額外增加存 儲空間(1) 插入和刪除運算 效率低(2) 存儲空間不便于 擴充(3) 不便于對存儲空 間的動態(tài)分配鏈表(1) 在進行插入

32、和刪除 運算時，只需要改變指 針即可，不需要移動元 素(2) 存儲空間易于擴充 并且方便空間的動態(tài)分 配需要額外的空間(指針 域)來表示數(shù)據(jù)元素之 間的邏輯關系，存儲密 度比順序表低40. 下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈式存儲的是A) 雙向鏈表B) 循環(huán)隊列C) 二叉鏈表D) 二維數(shù)組A【解析】雙向鏈表也叫雙鏈表，是鏈表(采用鏈式存儲結(jié)構(gòu)) 的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接 后繼和直接前驅(qū)。循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。二 叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。41. 在線性表的鏈式存儲結(jié)構(gòu)中，其存儲空間一般是不連續(xù)的， 并且A) 前件結(jié)點的存儲序號小于后件結(jié)點的存儲序號B) 前件

33、結(jié)點的存儲序號大于后件結(jié)點的存儲序號C) 前件結(jié)點的存儲序號可以小于也可以大于后件結(jié)點的存儲 序號D) 以上三種說法均不正確C【解析】在線性表的鏈式存儲結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序 號是不連續(xù)的，并且各結(jié)點在存儲空間中的位置關系與邏輯 關系也不一致，因此前件結(jié)點的存儲序號與后件結(jié)點的存儲 序號之間不存在大小關系。42 .下列敘述中正確的是A) 結(jié)點中具有兩個指針域的鏈表一定是二叉鏈表B) 結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是 非線性結(jié)構(gòu)C) 循環(huán)鏈表是循環(huán)隊列的鏈式存儲結(jié)構(gòu)D) 循環(huán)鏈表是非線性結(jié)構(gòu)B【解析】結(jié)點中具有兩個指針域的鏈表既可以是雙向鏈表也 可以是二叉鏈表，雙向鏈表是線

34、性結(jié)構(gòu)，二叉鏈表屬于非線 性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構(gòu)， 采用鏈式存儲結(jié)構(gòu)，而循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。 43.帶鏈的棧與順序存儲的棧相比，其優(yōu)點是A) 入棧與退棧操作方便B) 可以省略棧底指針C) 入棧操作時不會受棧存儲空間的限制而發(fā)生溢出D) 所占存儲空間相同C【解析】帶鏈的棧就是用一個線性鏈表來表示的棧，線性鏈表不受存儲空間大小的限制，因此入棧操作時不會受棧存儲 空間的限制而發(fā)生溢出(不需考慮棧滿的問題)。44 .下列敘述中正確的是A) 帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的B) 若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列為空C) 若帶鏈隊列的隊頭指針與隊

35、尾指針相同，則隊列中至少有 一個元素D) 不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均 是固定不變的A【解析】由于帶鏈棧利用的是計算機存儲空間中的所有空閑 存儲結(jié)點，因此隨棧的操作棧頂棧底指針動態(tài)變化。帶鏈的 隊列中若只有一個元素，則頭指針與尾指針相同。45.帶鏈?？盏臈l件是A) top=bottom=NULLB) top=-1 且 bottom=NULLC) top=NULL 且 bottom=-1D) top=bottom=-1A【解析】在帶鏈的棧中，只會出現(xiàn)棧空和非空兩種狀態(tài)。當 棧為空時，有top=bottom=NULL ;當棧非空時，top指向鏈 表的第一個結(jié)點(棧頂)。46在

36、帶鏈棧中，經(jīng)過一系列正常的操作后， 如果top=bottom , 則棧中的元素個數(shù)為A) 0 或 1B) 0C) 1D) 棧滿A【解析】帶鏈棧就是沒有附加頭結(jié)點、運算受限的單鏈表。 棧頂指針就是鏈表的頭指針。如果棧底指針指向的存儲單元 中存有一個元素，則當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【解析】帶鏈的

37、棧就是用一個單鏈表來表示的棧，棧中的每 一個元素對應鏈表中的一個結(jié)點。棧為空時，頭指針和尾指 針都為NULL ;棧中只有一個元素時，頭指針和尾指針都指 向這個元素。48某帶鏈棧的初始狀態(tài)為 top=bottom=NULL ,經(jīng)過一系列正 常的入棧與退棧操作后，top=10 , bottom=20。該棧中的元素 個數(shù)為A) 0B) 1C) 10D) 不確定D【解析】帶鏈的棧使用了鏈表來表示棧，而鏈表中的元素 存儲在不連續(xù)的地址中，因此當 top=10，bottom=20時，不 能確定棧中元素的個數(shù)。49.帶鏈隊列空的條件是A) fro nt=rear=NULLB) fro nt=-1 且 rea

38、r=NULLC) front=NULL 且 rear=-1D) fro nt=rear=-1A【解析】帶鏈的隊列就是用一個單鏈表來表示的隊列，隊列中的每一個元素對應鏈表中的一個結(jié)點。隊列空時，頭指針 和尾指針都為NULL °50在帶鏈隊列中，經(jīng)過一系列正常的操作后，如果front=rear， 則隊列中的元素個數(shù)為A) 0B) 1C) 0 或 1D) 隊列滿C【解析】帶鏈隊列空時，頭指針和尾指針都為NULL ;隊列中只有一個元素時，頭指針和尾指針都指向這個元素。51 某帶鏈的隊列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列 正常的入隊與退隊操作后，front=rear=10 &

39、#176;該隊列中的元素個 數(shù)為A) 0B) 1C) 1 或 0D) 不確定B【解析】帶鏈隊列空時，頭指針和尾指針都為null;隊列中只有一個元素時，頭指針和尾指針都指向這個元素。52某帶鏈的隊列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列 正常的入隊與退隊操作后，front=10, rear=5°該隊列中的元素 個數(shù)為A) 4B) 5C) 6D) 不確定D【解析】帶鏈的隊列使用了鏈表來表示隊列，而鏈表中的 元素存儲在不連續(xù)的地址中，因此當front=10,rear=5時，不能確定隊列中元素的個數(shù)。53. 下列敘述中錯誤的是A) 循環(huán)鏈表中有一個表頭結(jié)點B) 循環(huán)鏈表是循環(huán)隊

40、列的存儲結(jié)構(gòu)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é)構(gòu)，循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。54. 從表中任何一個結(jié)點位置出發(fā)就可以不重復地訪問到表中其他所有結(jié)點的鏈表是A) 循環(huán)鏈表B) 雙向鏈表C) 單向鏈表D) 二叉鏈表A【解析】在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈， 只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)不重復 地訪問到表中其他所

41、有結(jié)點。55非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構(gòu)A) 有根結(jié)點也有葉子結(jié)點B) 沒有根結(jié)點但有葉子結(jié)點C) 有根結(jié)點但沒有葉子結(jié)點D) 沒有根結(jié)點也沒有葉子結(jié)點A【解析】循環(huán)鏈表表頭結(jié)點為根結(jié)點，鏈表的最后一個結(jié)點 為葉子節(jié)點，雖然它含有一個指向表頭結(jié)點的指針，但是表 頭結(jié)點并不是它的一個后件。56.下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A) 樹B) 向量C) 二維表D) 矩陣A【解析】由定義可以知道，樹為一種簡單的非線性結(jié)構(gòu)。在 數(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關系具有明顯的層 次特性。57某棵樹中共有25個結(jié)點，且只有度為3的結(jié)點和葉子結(jié)點， 其中葉子結(jié)點有7個，則該樹中度為3的結(jié)點數(shù)為A) 6B) 7C

42、) 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é)點數(shù)為A) 11B) 9C) 10D) 8A【解析】設葉子結(jié)點數(shù)為 n，根據(jù)樹中的結(jié)點數(shù)=樹中所有 結(jié)點的度之和 +1，得 4X 1+3 X2+2 X 3+1 X 4+nx 0+1=21,則 n=21-1-2-3-4=11

43、°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,得3X 4+2 X 1+1 x n+0 X 10+1=27，則 n=12。60設一棵度為3的樹，其中度為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 ,

44、得 3X(n-10) +2 X 3+1 X 1+0 X6+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ù)=樹中所有結(jié)點的度 之和 +1，得 3X n +1 X( m-n-5) +5 X0+仁m，貝U n=2。62度為3的一棵樹共有30個結(jié)點，其中度為3,1的結(jié)點個數(shù) 分別為3,4。則該樹中的葉子結(jié)點數(shù)為A) 14B) 15C) 16D) 不可

45、能有這樣的樹B【解析】設葉子結(jié)點數(shù)為n,則度為2的結(jié)點數(shù)為30-3-4- n=23-n,根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1,得 3X 3+2 X( 23-n) +1 X 4+0 Xn+仁30，則 n=15。63. 設某棵樹的度為3,其中度為2,1,0的結(jié)點個數(shù)分別為3,4,15則該樹中總結(jié)點數(shù)為A) 不可能有這樣的樹B) 30C) 22D) 35A【解析】設樹的總結(jié)點數(shù)為n,則度為3的結(jié)點數(shù)為n-3-4-15=n-22,根據(jù)樹中的結(jié)點數(shù)=樹中所有結(jié)點的度之和+1,得 3X( n-22) +2X 3+1 X 4+0 X15+1=n，貝U n=27.5，求 出的結(jié)點數(shù)不為整數(shù)，故不可能有這

46、樣的樹存在。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的結(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. 某二叉樹共

47、有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é)點，其中200個為葉子結(jié)點，則 該二叉樹中度為2的結(jié)點數(shù)為A) 不可能有這樣的二叉樹B) 150C) 199D) 149A【解析】葉子結(jié)點數(shù)為200,根據(jù)在二叉樹中度為0的結(jié)點 (葉子結(jié)點)總比度為2的結(jié)點多一個，則度為2的結(jié)點數(shù)為199,

48、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,因此該樹不存在度 為1的結(jié)點。69. 深度為7的二叉樹共有127個結(jié)點，則下列說法中錯誤的 是A) 該二叉樹是滿二叉樹B) 該二叉樹有一個度為1的結(jié)點C) 該二叉樹是完全二叉樹D) 該二叉樹有64個葉子結(jié)點

49、B【解析】滿二叉樹滿足深度為 m的二叉樹最多有2m-1個結(jié) 點，本題中二叉樹深度為 7且有127個結(jié)點，滿足27-仁127, 達到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹。滿 二叉樹第k層上有2-1結(jié)點，則該二叉樹的葉子結(jié)點數(shù)為 27-1=64個。滿二叉樹不存在度為1的結(jié)點。70. 深度為5的完全二叉樹的結(jié)點數(shù)不可能是A) 15B) 16C) 17D) 18A【解析】設完全二叉樹的結(jié)點數(shù)為 n，根據(jù)深度為k的二叉 樹至多有2-1個結(jié)點，再根據(jù)完全二叉樹的定義可知，2k-1-1<n< 2k-1o本題中完全二叉樹的深度為 5,則25-1-1<n < 25-1, 15&l

50、t;n< 31。因此，結(jié)點數(shù)不能為15o71. 某完全二叉樹共有256個結(jié)點，則該完全二叉樹的深度為A) 7B) 8C) 9D) 10C【解析】根據(jù)完全二叉樹的性質(zhì)： 具有n個結(jié)點的完全二叉 樹的深度為log2n+1。本題中完全二叉樹共有256個結(jié)點，則 深度為10256+仁8+仁9。72. 深度為7的完全二叉樹中共有 125個結(jié)點，則該完全二叉 樹中的葉子結(jié)點數(shù)為A) 62B) 63C) 64D) 65B【解析】在滿二叉樹的第k層上有2k-1個結(jié)點、且深度為 m 的滿二叉樹有2m-1個結(jié)點，則深度為6的滿二叉樹共有 26-1=63個結(jié)點，第6層上有26-1 =32個結(jié)點。本題是深度為7

51、 的完全二叉樹，則前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-1個。再根據(jù)完全二叉樹的定義， 度為1的結(jié)點有0個或 1個，假設度1結(jié)點為

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

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

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

55、位于根結(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在中序序 列和后

56、序序列中順序未變，說明結(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é)點的右子樹上。故 二叉樹深度為4。80. 設二叉樹的前序序列與中序序列均為 ABCDEFGH，