計算機二級公共基礎(chǔ)知識考前押題

1、計算機二級公共基礎(chǔ)知識考前 押題 作者: 日期： 1. 下列敘述中正確的是 A ）所謂算法就是計算方法/ B ）程序可以作為算法的二和描述方法 C）算法設(shè)計只需考慮得到計算結(jié)果 D）算法設(shè)計可以忽略算法的運算時間 B【解析】算法是指對解題方案的準確而完整的描 述，算法不等于數(shù)學(xué)上的計算方法，也不等于程序。 算法設(shè)計需要考慮可行性、確左性、有窮性與足夠 的情報，不能只考慮il算結(jié)果。算法設(shè)訃有窮性是 指操作步驟有限且能在有限時間內(nèi)完成，如果一個 算法執(zhí)行耗費的時間太長，即使最終得出了正確結(jié) 果，也是沒有意義的，。算法在實現(xiàn)時需要用具體 的程序設(shè)計語言描述，所以程序可以作為算法的一 種描述方法。

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

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

4、法的工作量。算法所執(zhí)行的基 本運算次數(shù)還與問題的規(guī)模有關(guān)：對應(yīng)一個固宦的 規(guī)模，算法所執(zhí)行的基本運算次數(shù)還可能與特泄的 輸入有關(guān)。 5 下列敘述中正確的是 A）解決同一個問題的不同算法的時間復(fù)雜度一般是 不同的 B）解決同一個問題的不同算法的時間復(fù)雜度必定 是相同的 C）對同一批數(shù)據(jù)作同一種處理，如果數(shù)據(jù)存儲結(jié)構(gòu) 不同，不同算法的時間復(fù)雜度肯泄相同 D）對同一批數(shù)據(jù)作不同的處理，如果數(shù)據(jù)存儲結(jié)構(gòu) 相同，不同算法的時間復(fù)雜度肯泄相同 A【解析】解決同一個問題的不同算法的時間復(fù)雜 度，可能相同也可能不相同。算法的時間復(fù)雜度與 數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)，對同一批數(shù)拯作同一種處理或 者不同處理，數(shù)據(jù)存儲結(jié)構(gòu)相

5、同或者不同，算法的 時間復(fù)雜度都可能相同或者不同。 6 下列敘述中正確的是 A）算法的空間復(fù)雜度是指算法程序中指令的條數(shù) B）壓縮數(shù)據(jù)存儲空間不會降低算法的空間復(fù)雜度 C）算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲空間 有關(guān) D）算法的空間復(fù)雜度是指算法程序控制結(jié)構(gòu)的復(fù) 雜程度 C【解析】算法的空間復(fù)雜度是指算法在執(zhí)行過程 中所需要的內(nèi)存空間。算法執(zhí)行期間所需的存儲空 間包括3個部分：輸入數(shù)據(jù)所占的存儲空間;程序 本身所占的存儲空間；算法執(zhí)行過程中所需要的額 外空間。 7. 為了降低算法的空間復(fù)雜度，要求算法盡量采 用原地工作（in pla ce） 0所謂原地工作是指 A）執(zhí)行算法時不使用額外空間

6、 B）執(zhí)行算法時不使用任何存儲空間 C）執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù) 據(jù)空間大小的變化而變化 D）執(zhí)行算法時所使用的額外空間固定（即不隨算法 所處理的數(shù)據(jù)空間大小的變化而變化） D【解析】對于算法的空間復(fù)雜度，如果額外空間量 相對于問題規(guī)模（即輸入數(shù)據(jù)所占的存儲空間）來 說是常數(shù)，即額外空間疑不隨問題規(guī)模的變化而變 化，則稱該算法是原地工作的。 8. 下列敘述中正確的是 A）算法的復(fù)雜度與問題的規(guī)模無關(guān) B）算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn) C）對數(shù)據(jù)進行壓縮存儲會降低算法的空間復(fù)雜度 D）數(shù)值型算法只需考慮計算結(jié)果的可靠性 C【解析】在許多實際問題中，為了減少算法所占 的

7、存儲空間，通產(chǎn)采用圧縮存儲技術(shù)，以便盡量減 少不必要的額外空間。 9. 下列敘述中正確的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)會影響算法的效率 B) 算法設(shè)計只需考慮結(jié)果的可靠性 C) 算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度 D )算法復(fù)雜度是用算法中指令的條數(shù)來度量的 A【解析】采用不同的存儲結(jié)構(gòu)，苴數(shù)據(jù)處理的效 率是不同的。因此，在進行數(shù)據(jù)處理時，選擇合適 的存儲結(jié)構(gòu)很重要。 10. 下列敘述中錯誤的是 A) 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)搦結(jié)構(gòu) B) 數(shù)搦結(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ù)元素是一個含

8、義很廣泛的概念，它 是數(shù)據(jù)的“基本單位”，在計算機中通常作為一個 整體進行考慮和處理。數(shù)據(jù)元素可以是一個數(shù)拯也 可以是被抽象岀的具有一左結(jié)構(gòu)數(shù)據(jù)集合，所以數(shù) 據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是期一數(shù)據(jù)結(jié)構(gòu)。滿足有 且只有一個根結(jié)點并且每一個結(jié)點最多有一個前 件，也最多有一個后件的非空的數(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

9、) 沒有根結(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ù)結(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é)點

10、：一個為右指針，用于 指向其后件結(jié)點，再加上頭指針，具有兩個以上的 指針，但雙向鏈表屬于線性結(jié)構(gòu)。非空線性結(jié)構(gòu)中 第一個結(jié)點沒有前件，最后一個結(jié)點無后件，英余 結(jié)點最多有一個前件，也最多有一個后件。向量也 滿足這個條件，屬于線性結(jié)構(gòu)。 13 .設(shè)數(shù)據(jù)結(jié)構(gòu)B = (D, R)，其中 D = a, b c, d, e, f R= (f, a ),(d, b),(e, d),(c, e ),(a , c) a該數(shù)據(jù)結(jié)構(gòu)為 A) 線性結(jié)構(gòu) B) 循環(huán)隊列 C) 循環(huán)鏈表 D) 非線性結(jié)構(gòu) A【解析】數(shù)拯的邏輯結(jié)構(gòu)有兩個要素:一是數(shù)據(jù)元 素的集合，通常記為D：二是D上的關(guān)系，它反映 了 D中各數(shù)據(jù)元素之

11、間的前后件關(guān)系，通常記為R 即一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D, R)o其中B表 示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)拯元素之間的前后 件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b 是D中的兩個數(shù)據(jù)，則二元組(a,b)表示a是b的 前件，b是a的后件。本題中R中的根結(jié)點為f,元 素順序為f -a-c-e-d-b,滿足線性結(jié)構(gòu)的條 件。 14. 設(shè)數(shù)據(jù)集合為D= 1,2,3,4,5) o 下列數(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 ),

12、 (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 34-5, D項5為跟結(jié)點，元素順序為5-4 -* 3 -2-1,均為線性結(jié)構(gòu)。C項中，元素3有兩個 前件，屬于非線性結(jié)構(gòu)。 15. 下列敘述中正確的是 A) 矩陣是非線性結(jié)構(gòu) B) 數(shù)組是長度固泄的線性表 0對線性表只能作插入與刪除運算 D) 線性表中各元素的數(shù)據(jù)類型可以不同 B【解析】矩陣也是線性表，只不過是比

13、較復(fù)雜的線 性表。線性表中各元素的數(shù)據(jù)類型必須相同。在線 性表中，不僅可以做插入與刪除運算，還可以進行 査找或?qū)€性表進行排序等操作。 16. 在線性表的順序存儲牡構(gòu)中，英存儲空間連續(xù)， 各個元素所占的字節(jié)數(shù) A不同,但元素的存儲順序與邏借順序一致 B) 不同,且其元素的存儲順序可以與邏借順序不一 致 C) 相同，元素的存儲順序與邏輯順序一致 D) 相同,但其元素的存儲順序可以與邏輯順序不一 致 C【解析】在線性表的順序存儲結(jié)構(gòu)中，英存儲空間 連續(xù)，各個元素所占的字右數(shù)相同，在存儲空間中 是按邏輯順序依次存放的。 17. 下列敘述中正確的是 A) 能采用順序存儲的必立是線性結(jié)構(gòu) B) 所有的線

14、性結(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) 在棧中，棧頂指針的動態(tài)變化決左棧中元素的個 數(shù) B) 在循環(huán)隊列中，隊尾指針的動態(tài)變化決左隊列的 長度 C) 在循環(huán)鏈表中，頭指針和鏈尾指針的動態(tài)變化決 定鏈表的長度 D) 在線性鏈表中，頭指針和鏈

15、尾指針的動態(tài)變化決 定鏈表的長度 A【解析】在棧中，通常用指針top來指示棧頂?shù)奈?置,用指針b o t tom指向棧底。棧頂指針top動 態(tài)反應(yīng)了棧中元素的變化情況。在循環(huán)隊列中，隊 頭指針和隊尾指針的動態(tài)變化決圮隊列的長度。鏈 式存儲結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的, 并且各結(jié)點在存儲空間中的位置關(guān)系與邏輯關(guān)系 也不一致，故頭指針和尾指針或棧頂指針無法決定 鏈表長度。 19. 設(shè)棧的順序存儲空間為S(l：m),初始狀態(tài)為 top二0。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，t op=m+l.則棧中的元素個數(shù)為 A) 0 B) m C) 不可能 D) m+1 C【解析】棧為空時，棧頂指針t

16、op= 0 ,經(jīng)過入棧和 退棧運算，指針始終指向棧頂元素。初始狀態(tài)為t op=0,當(dāng)棧滿時top二m,無法繼續(xù)入棧，top值不 可能為m+1。 20.設(shè)棧的存儲空間為S(l： 50),初始狀態(tài)為top二 一 1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后， top二3 0,則棧中的元素個數(shù)為 A) 20 B) 19 C) 3 1 D) 30 D【解析】棧的初始狀態(tài)為top=-l表示棧為空(沒 有規(guī)立棧中棧底必須是0),經(jīng)過一系列正常的入 棧與退棧操作后top = 30,則空間(1:30)中插入 了元素，共30個。 2 1.設(shè)棧的順序存儲空間為S(l:m),初始狀態(tài)為 to p =m+l,則棧中的數(shù)據(jù)元

17、素個數(shù)為 A) t op-m+ 1 B) m-top+l C) m-top D) top m B【解析】棧的初始狀態(tài)top二m+1,說明?？諘rtop =m+l (m在棧底，1是開口向上的)，入棧時棧頂指 針是減操作(top二top-1),退棧時棧頂指針是加 操作(top=top+l) 0本題可以假設(shè)棧中有x個元 素，當(dāng)滬0時，也就是棧中沒有元素，則to p = m+1：當(dāng)x二m時，也就是棧滿，則top二1,由此可以 得岀 t o p=m+l- x ,繼而得岀 x 二top-m+l。 2 2 .設(shè)棧的順序存儲空間為S(l:m),初始狀態(tài)為 t o p二m+1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作 后

18、,top=0,則棧中的元素個數(shù)為 A) 1 B ) m C) m+1 D) 不可能 D【解析】棧的初始狀態(tài)為top=m + l,說明?？?時to p二m+1,入棧時棧頂指針是減操作 (top二top-1)，退棧時棧頂指針是加操作(top = t o p+1)。棧滿時top二1,說明棧中不能再進行入棧操 作，top二0的情況不會出現(xiàn)。 23.設(shè)棧的存儲空間為S(l：m)，初始狀態(tài)為top二 m+1。經(jīng)過一系列入棧與退棧操作后，top=l 現(xiàn)又要將一個元素進棧，棧頂指針top值變?yōu)?A) 0 B ）發(fā)生棧滿的錯誤 C）m D）2 B【解析】棧的初始狀態(tài)為to p1 ,說明?？諘r top=m+l,入

19、棧時棧頂指針是減操作（t o p二top-1）, 退棧時棧頂指針是加操作（t op二top+1）。棧滿 時top二1,說明棧中不能再進行入棧操作（“上溢” 錯誤）。 2 4 .設(shè)棧的存儲空間為S （1 ：m）,初始狀態(tài)為t 0 p二m+1。經(jīng)過一系列入棧與退棧操作后，top=m 現(xiàn)又在棧中退岀一個元素后，棧頂指針top值為 A）0 B ）m 1 C）m + 1 D）產(chǎn)生棧空錯誤 C【解析】棧的順序存儲空間為S （1： m）,初始狀 態(tài)top二m + 1,所以這個棧是m在棧底，1是開口向 上的。經(jīng)過一系列入棧與退棧操作后top二m,則棧 中有1個元素，若現(xiàn)在又退出一個元素，那么棧頂 指針下移一位

20、，回到m+1的位置。 25. 設(shè)棧的存儲空間為S （1： 50）,初始狀態(tài)為 top二51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作 后，top二20,則棧中的元素個數(shù)為 A）31 B）3 0 C ） 2 1 D ） 20 A【解析】棧的初始狀態(tài)t op二5 1 ,故本棧是5 1在 棧底，入棧時棧頂指針是減操作（top二top-1）, 退棧時棧頂指針是加操作（top二t op+1） o當(dāng)top二2 0時，元素存儲在（20： 50）空間中，因此共有50- 2 0+1=31個元素。 26. 下列處理中與隊列有關(guān)的是 A）二叉樹的遍歷 B）操作系統(tǒng)中的作業(yè)調(diào)度 C）執(zhí)行程序中的過程調(diào)用 D）執(zhí)行程序中的循環(huán)

21、控制 B【解析】隊列是指允許在一端進行插入，而在另 一端進行刪除的線性表。由于最先進入隊列的元素 將最先岀隊,所以隊列具有“先進先出”的特性， 體現(xiàn)了 先來先服務(wù)”的原則。操作系統(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í)行程序，與隊列無關(guān)。執(zhí)行程序中 的循環(huán)控制是指算法的堆本控制結(jié)構(gòu)，包括對循壞 條件的判左與執(zhí)行循環(huán)體,與隊列無關(guān)。二叉樹是 一個有限的結(jié)點集合，二叉樹的遍歷是指不重復(fù)地 訪問二叉樹中的所有結(jié)點,與隊列無關(guān)。 2 7

22、.設(shè)有棧S和隊列Q,初始狀態(tài)均為空。首先依 次將A,B,C,D,E, F入棧，然后從棧中退岀三個元素 依次入隊，再將X,Y, Z入棧后，將棧中所有元素退 出并依次入隊，最后將隊列中所有元素退岀，則退 隊元素的順序為 A）DEFXYZA BC B）F EDZYXCBA C）FEDXYZCBA D）DEFZYXABC B【解析】棧是一種特殊的線性表，它所有的插入與 刪除都限立在表的同一端進行。隊列是指允許在一 端進行插入，而在列一端進行刪除的線性表。將A, B,C,D, E,F入棧后，棧中元素為ABCDE F,退 岀三個元素入隊，隊列元素為FED,將X, Y,Z入 棧后棧中元素為ABCXYZ,退棧

23、全部入隊后，隊列元 素為 FEDZYXCBAo 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)隊列中，在隊列滿和隊列為空時，隊頭指針 與隊尾指針均相同：當(dāng)需要插入的數(shù)據(jù)大于循環(huán)隊 列的存儲長度，入隊運算會覆蓋前而的數(shù)據(jù)，發(fā)生 溢出現(xiàn)象。 29. 下列敘述中正確的是 A）在循環(huán)隊列中，隊尾指針的動態(tài)變化決立隊列的 長度 B）在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化 決建隊列的長度 C ）在帶鏈的隊列中，隊頭指針與隊尾指針

24、的動態(tài)變 化決泄隊列的長度 D）在帶鏈的棧中，棧頂指針的動態(tài)變化決左棧中元 素的個數(shù) B【解析】在循環(huán)隊列中，隊頭指針和隊尾指針的 動態(tài)變化決左隊列的長度。帶鏈的棧和帶鏈的隊列 均采用鏈式存儲結(jié)構(gòu)，而在這種結(jié)構(gòu)中，各數(shù)據(jù)結(jié) 點的存儲序號是不連續(xù)的，并且各結(jié)點在存儲空間 中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾 指針或棧頂指針無法決左鏈表長度。 3 0 .循環(huán)隊列的存儲空間為Q(l:50)，初始狀態(tài) 為f r on t = r ear二5 0 0線過一系列正常的入隊與 退隊操作后，f r ont二rear= 2 5,此后又插入一個 元素，則循環(huán)隊列中的元素個數(shù)為 A) l,或5 0且產(chǎn)生上溢

25、錯誤 B) 51 C) 26 D) 2 A【解析】循環(huán)隊列長度為5 0,由初始狀態(tài)為f r on t二r ea r二5 0可知此時循環(huán)隊列為空。入隊運 算時，首先隊尾指針re ar進1 (即rea r + 1 ), 然后在隊尾指針re a r指向的位置插入新元素。當(dāng) 隊尾指針rea r二5 0 +1時，置rea r = 1。退隊 運算時，排頭指針fr o nt進1 (即fron t +1),然 后刪除f r o nt指針指向的位巻上的元素，當(dāng)排 頭指針 fro n t= 5 0+1 時，置 f r o nt二 1。當(dāng) fr o nt二rear二2 5時可知隊列空或者隊列滿，此后又插 入了一個元

26、素，如果之前隊列為空,插入操作之后 隊列里只有一個元素;如果插入之前隊列已滿(50 個元素)，執(zhí)行插入則會產(chǎn)生溢出錯誤。 31.循環(huán)隊列的存儲空間為Q (1:40),初始狀態(tài) 為front =rear=4 0o經(jīng)過一系列正常的入隊與 退隊操作后，f r on t二r e a r二1 5，此后又退出一 個元素，則循環(huán)隊列中的元素個數(shù)為 A) 14 6)15 C) 40 D) 3 9,或0且產(chǎn)生下溢錯誤 D【解析】當(dāng)f r ont二re a r= 1 5時可知隊列空或 者隊列滿,此后又退出一個元素，如果之前隊列為 空，退出操作會產(chǎn)生錯誤，隊列里有0個元素;如果 退出之前隊列已滿(40個元素)，執(zhí)行

27、退出后，隊列 里還有39個元素。 3 2.設(shè)循環(huán)隊列的存儲空間為Q(l:50),初始狀態(tài) 為front=rear二50?，F(xiàn)經(jīng)過一系列入隊與退隊操作 后，f r ont二rear二1，此后又正常地插入了兩個元 素。最后該隊列中的元素個數(shù)為 A) 3 B) 1 C) 2 D) 52 C【解析】由f ron t= rea r = 1可知隊列空或者 隊列滿，此后又可以正常地插入了兩個元素說明插 入前隊列為空，則插入后隊列元素個數(shù)為2。 33.設(shè)循環(huán)隊列的存儲空間為Q(l：m),初始狀態(tài)為 空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作后,fron t二m, rear=m-l,此后從該循環(huán)隊列中刪除一個元 素，則

28、隊列中的元素個數(shù)為7, _ A) m- B) m 2 C) 0 D) 1 B【解析】從排頭指針f ront指向的后一個位豊 直到隊尾指針r ear指向的位苣之間所有的元素均 為隊列中的元素。如果rea r-front 0,則隊列中 的元素個數(shù)為rea r-fro n t個；如果rear-fro n t0,則隊列中的元素個數(shù)為rear - f ront +m 該題中mlm,即re a rfron t 0 , 則該循環(huán)隊列中的元素個數(shù)為m (m-1 )二1。此 后從該循環(huán)隊列中插入一個元素，則隊列中的元素 個數(shù)為1+1= 2 o 35.設(shè)循環(huán)隊列為Q(l：m),其初始狀態(tài)為front = rear

29、=ma經(jīng)過一系列入隊與退隊運算后，f ront二30, rear二1 0?，F(xiàn)要在該循環(huán)隊列中作順序查 找，最壞情況下需要比較的次數(shù)為 A )1 9 B) 2 0 C) m- 1 9 D ) m-2 0 D【解析】fro n t=3 0 , rear二 1 0 , fro n t r ear, 則隊列中有10-3 0 +m二m-2 0個元素，在作順序查 找時，最壞情況下(最后一個元素才是要找的元素 或沒有要查找的元素)比較次數(shù)為m20次。 3 6.設(shè)循環(huán)隊列的存儲空間為Q(l：m),初始狀態(tài) 為fro n t二r ear二m。經(jīng)過一系列正常的操作后， front二1, rears。為了在該隊列中

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

31、則該循環(huán)隊列中的元素個數(shù)為r e a r-fr o n t二rear- (re a r 1 )二1。因隊列中只有1個 元素，故尋找值最大的元素不需要進行比較，即比 較次數(shù)為0。 3 9 .線性表的鏈式存儲結(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)缺點如下 表所示。 類 型 占 八、 缺點 順 (1)可以 插入和 序 表 隨機存取 表中的任 意結(jié)點 (2)無需為 表示結(jié)點 間的邏輯 關(guān)系額外 增加存儲 空間 刪除運

32、算 效率低 (2)存儲 空間不便 于擴充 (3 )不便 于對存儲 空間的動 態(tài)分配 鏈 表 在進行 插入和刪 除運算時, 只需要改 變指針即 可,不需要 移動元素 (2)存儲 空間易于 擴充并且 方便空間 的動態(tài)分 配 需要額外 的空間 (指針域) 來表示數(shù) 據(jù)元素之 間的邏輯 關(guān)系，存儲 密度比順 序表低 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ù)組屬 于非線

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

34、循環(huán)鏈表是循環(huán)隊列的鏈式存儲結(jié)構(gòu) D）循環(huán)鏈表是非線性結(jié)構(gòu) B【解析】結(jié)點中具有兩個指針域的鏈表既可以是 雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構(gòu), 二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的 一種形式，屬于線性結(jié)構(gòu),采用鏈式存儲結(jié)構(gòu)，而 循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。 4 3 .帶鏈的棧與順序存儲的棧相比，苴優(yōu)點是 A）入棧與退棧操作方便 B）可以省略棧底指針 C）入棧操作時不會受棧存儲空間的限制而發(fā)生溢 出 D）所占存儲空間相同 C【解析】帶鏈的棧就是用一個線性鏈表來表示的 棧,線性鏈表不受存儲空間大小的限制，因此入棧 操作時不會受棧存儲空間的限制而發(fā)生溢岀（不需 考慮棧滿的問題

35、）。 44.下列敘述中正確的是 A）帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的 B）若帶鏈隊列的隊頭指針與隊尾指針相同，貝9隊列 為空 C ）若帶鏈隊列的隊頭指針與隊尾指針相同,則隊列 中至少有一個元素 D）不管是順序棧還是帶鏈的棧，在操作過程中北棧 底指針均是固定不變的 A【解析】由于帶鏈棧利用的是計算機存儲空間中 的所有空閑存儲結(jié)點，因此隨棧的操作棧頂棧底指 針動態(tài)變化。帶鏈的隊列中若只有一個元素，則頭 指針與尾指針相同。 4 5 .帶鏈棧空的條件是 A）t op=bo t t om=NULL B ）to p =-1 且 bot t om = NULL C）top=N U LL 且 bott

36、om =-l D）t o p=bottom= 1 A【解析】在帶鏈的棧中，只會岀現(xiàn)棧空和非空兩種 狀態(tài)。當(dāng)棧為空時,有top=bot tom=NULL;當(dāng)棧 非空時,top指向鏈表的第一個結(jié)點（棧頂）。 4 6.在帶鏈棧中，經(jīng)過一系列正常的操作后，如果 t op二b o t tom,則棧中的元素個數(shù)為 A）0或 1 B）0 C）1 D）棧滿 A【解析】帶鏈棧就是沒有附加頭結(jié)點、運算受限 的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底 指針指向的存儲單元中存有一個元素，則當(dāng)t o p二 bot tom時，棧中的元素個數(shù)為1;如果棧底指針 指向的存儲單元中沒有元素，則當(dāng)top= b o t tom

37、時，棧中的元素個數(shù)為0。 4 7.某帶鏈棧的初始狀態(tài)為t o p=bottom=NU L L,經(jīng)過一系列正常的入棧與退棧操作后，top二b ottom二2 0。該棧中的元素個數(shù)為 A）0 B）1 C ） 20 D）不確定 B【解析】帶鏈的棧就是用一個單鏈表來表示的棧, 棧中的每一個元素對應(yīng)鏈表中的一個結(jié)點。棧為空 時，頭指針和尾指針都為NULL;棧中只有一個元 素時，頭指針和尾指針都指向這個元素。 48.某帶鏈棧的初始狀態(tài)為top二b o ttom =NULL, 經(jīng)過一系列正常的入棧與退棧操作后，t o p =1 0 , bottom =20o該棧中的元素個數(shù)為 A ）0 B）1 C）10 D

38、）不確定 D【解析】帶鏈的棧使用了鏈表來表示棧，而鏈表中 的元素存儲在不連續(xù)的地址中,因此當(dāng)top二1 0 , bottom=20時，不能確直衣中元素的個數(shù)。 49.帶鏈隊列空的條件是 A）front=re a r= N ULL B）f ront=- 1 且 rear=NULL C）f r o n t=NULL 且 rear= 1 D ）f r ont=rear=-l A【解析】帶鏈的隊列就是用一個單鏈表來表示的 隊列，隊列中的每一個元素對應(yīng)鏈表中的一個結(jié) 點。隊列空時,頭指針和尾指針都為NULL。 5 0.在帶鏈隊列中，經(jīng)過一系列正常的操作后，如 果front= rear,則隊列中的元素個數(shù)

39、為 A）0 B）1 C）0 或 1 D）隊列滿 C【解析】帶鏈隊列空時，頭指針和尾指針都為NULL； 隊列中只有一個元素時，頭指針和尾指針都指向這 個元素。 51. 某帶鏈的隊列初始狀態(tài)為fro n t=r e ar= N ULLe經(jīng)過一系列正常的入隊與退隊操作后，front= r e a 1 0 o該隊列中的元素個數(shù)為 A）0 B）1 C）1 或0 D）不確定 B【解析】帶鏈隊列空時，頭指針和尾指針都為null; 隊列中只有一個元素時，頭指針和尾指針都指向這 個元素。 52. 某帶鏈的隊列初始狀態(tài)為front= r e ar二NUL L。經(jīng)過一系列正常的入隊與退隊操作后,fro nt = 1

40、0, r e ar二5。該隊列中的元素個數(shù)為 A ）4 B）5 C ） 6 D）不確定 D【解析】帶鏈的隊列使用了鏈表來表示隊列，而鏈 表中的元素存儲在不連續(xù)的地址中，因此當(dāng) front=10, rea r二5時，不能確定隊列中元素的個 數(shù)。 5 3 .下列敘述中錯誤的是 A）循環(huán)鏈表中有一個表頭結(jié)點 B）循環(huán)鏈表是循環(huán)隊列的存儲結(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)鏈表是

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

42、但是表頭結(jié)點并不是它的一個后件。 5 6.下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是 A）樹 B）向量 C）二維表 D）矩陣 A【解析】由左義可以知道，樹為一種簡單的非線 性結(jié)構(gòu)。在數(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間 的關(guān)系具有明顯的層次特性。 57.某棵樹中共有2 5個結(jié)點，且只有度為3的結(jié) 點和葉子結(jié)點，其中葉子結(jié)點有7個，則該樹中度 為3的結(jié)點數(shù)為 A）6 B）7 C）8 D）不存在這樣的樹 D【解析】根拯題意,樹中只有度為3的結(jié)點和葉 子結(jié)點（7個），則度為3的結(jié)點有25-7=18個; 又根據(jù)樹中的結(jié)點數(shù)二樹中所有結(jié)點的度之和+1， 設(shè)度為3的結(jié)點數(shù)為n,則3n+l二25,得n二8。兩種方 式得到的度

43、為3的結(jié)點數(shù)不同，故不存在這樣的樹。 5 8.某棵樹的度為4,且度為4、3、2、1的結(jié)點 個數(shù)分別為1、2、3、4,則該樹中的葉子結(jié)點數(shù)為 A) ll B) 9 C ) 10 D) 8 A【解析】設(shè)葉子結(jié)點數(shù)為n,根據(jù)樹中的結(jié)點數(shù)= 樹中所有結(jié)點的度之和+1,得4X1+3X2 + 2X3 + lX4+nX0 + l二2 1 ,則 n = 2 1-1-2 3-4=11。 5 9 .設(shè)一棵樹的度為3,共有27個結(jié)點，英中度為 3, 2, 0的結(jié)點數(shù)分別為4, 1, 10o該樹中度為 1的結(jié)點數(shù)為 A) 11 B) 12 C) 13 D) 不可能有這樣的樹 B【解析】設(shè)度為1的結(jié)點數(shù)為n,根據(jù)樹中的

44、結(jié)點 數(shù)二樹中所有結(jié)點的度之和+1，得3 X4+2X1+1X n+OXl 0+1=27,則 n=12o 6 0.設(shè)一棵度為3的樹，其中度為2, 1,0的結(jié)點 數(shù)分別為3,1, 6。該樹中度為3的結(jié)點數(shù)為 A) 1 B) 2 C) 3 D) 不可能有這樣的樹 A【解析】設(shè)樹的結(jié)點數(shù)為n,則度為3的結(jié)點數(shù)為 n-3-1-6二n-l 0 ,根據(jù)樹中的結(jié)點數(shù)二樹中所有結(jié) 點的度之和+1,得3X (n-10)+2X3+l X 1+0 X 6+1二n,解得n= 1 1,則度為3的結(jié)點數(shù)為n -10=11 -10= 1。 61.設(shè)一棵樹的度為3,苴中沒有度為2的結(jié)點，且 葉子結(jié)點數(shù)為5。該樹中度為3的結(jié)點數(shù)

45、為 A) 3 B) 1 C) 2 D) 不可能有這樣的樹 C【解析】設(shè)樹的結(jié)點數(shù)為m,度為3的結(jié)點數(shù)為 n,則度為1的結(jié)點數(shù)為mn5,根據(jù)樹中的結(jié) 點數(shù)二樹中所有結(jié)點的度之和+1,得3Xn+lX (m-n -5) +5X0+l=m,則 n二2。 6 2 .度為3的一棵樹共有30個結(jié)點，荘中度為3 , 1的結(jié)點個數(shù)分別為3,4。則該樹中的葉子結(jié)點數(shù) 為 A) 14 B) 15 C) 16 D) 不可能有這樣的樹 B【解析】設(shè)葉子結(jié)點數(shù)為n ,則度為2的結(jié)點數(shù) 為30-3-4-n= 2 3-n,根據(jù)樹中的結(jié)點數(shù)二樹中所有 結(jié)點的度之和+ 1,得3X3 + 2X (2 3-n) -IX 4+0 Xn

46、+l = 30 ,則 n=15 3 5 0 ,故 不存在這樣的二叉樹。 68. 某二叉樹的深度為7,苴中有64個葉子結(jié)點，則 該二叉樹中度為1的結(jié)點數(shù)為 A) O B) 1 C) 2 D) 63 A【解析】葉子結(jié)點有64個,根據(jù)在二叉樹中度為 0的結(jié)點(葉子結(jié)點)總比度為2的結(jié)點多一個，則 度為2的結(jié)點數(shù)為6 3個;又深度為m的二叉樹最 多有21- 1個結(jié)點，則該二叉樹最多有2 7-1 = 1 27個結(jié)點。6 4 + 6 3二127,因此該樹不存在度為 1的結(jié)點。 69. 深度為7的二叉樹共有12 7個結(jié)點，則下列 說法中錯誤的是 A) 該二叉樹是滿二叉樹 B) 該二叉樹有一個度為1的結(jié)點 C

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

48、,貝lj25_,-ln2s-l, 1 5nW 31。因此，結(jié)點數(shù)不能為15。 71. 某完全二叉樹共有256個結(jié)點，則該完全二叉樹 的深度為 A) 7 B) 8 C) 9 D) 1O C【解析】根據(jù)完全二叉樹的性質(zhì)：具有n個結(jié)點的 完全二叉樹的深度為log:n + 1 o本題中完全二 叉樹共有256個結(jié)點，則深度為log=256+l=8+ 1 二9。 72. 深度為7的完全二叉樹中共有12 5個結(jié)點，則 該完全二叉樹中的葉子結(jié)點數(shù)為 A) 6 2 B) 63 C) 64 D) 6 5 B【解析】在滿二叉樹的第k層上有廣個結(jié)點、且 深度為m的滿二叉樹有2- 1個結(jié)點，則深度為6的 滿二叉樹共有2

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

50、-1個。再根據(jù)完全二 叉樹的泄義，度為1的結(jié)點有0個或1個,假設(shè)度1 結(jié)點為0個，a+0+a 1 =2n,得2a=2 n - 1 ,由于 結(jié)點個數(shù)必須為整數(shù)，假設(shè)不成立：當(dāng)度為1的結(jié) 點為1個時,a+l+a-l=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) 順序存儲

51、結(jié)構(gòu)一定是線性結(jié)構(gòu) C【解析】在訃算機中，二叉樹通常采用鏈式存儲 結(jié)構(gòu)，但對于滿二叉樹和完全二叉樹來說，可以按 層進行順序存儲。因此A項錯誤，C項正確。雖然 滿二叉樹和完全二叉樹可以采用順序存儲結(jié)構(gòu)，但 仍是一種非線性結(jié)構(gòu)，因此D項錯誤。雙向鏈表也 有兩個指針域，因此B項錯誤。 7 6.有二叉樹如下圖所示： 則前序序列為 a)abdegcfh B) DBGEAFHC C) DGEBHFCA D) A B CDEFGH A【解析】前序遍歷首先訪問根結(jié)點,然后遍歷左子 樹，最后遍歷右子樹：在遍歷左、右子樹時，仍然 先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 故本題前序序列是ABDEGCFH。

52、中序遍歷首先遍歷左子樹，然后訪問跟結(jié)點，最后適 歷右子樹：在遍歷左、右子樹時,仍然先遍歷左子樹, 然后訪問跟結(jié)點，最后遍歷右子樹。故本題的中序序 列是 DBGEA FHCo 后序遍歷首先遍歷左子樹，然后遍歷右子樹,最后訪 問根結(jié)點;在遍歷左、右子樹時,仍然先遍歷左子樹, 然后遍歷右子樹，最后訪問根結(jié)點。故本題的后序 序列是DGEB HFCAo 77.設(shè)二叉樹的前序序列為A B DEGHCF I J ,中序序 列為DBGEHACIFJo則后序序列為 A) J I HGFED C BA B) DGHEBIJFCA C) GHU I) EFBCA I) ) ABCDEFGHIJ B【解析】三叉樹的前

53、序序列為ABDEGHC F I J,由 于前序適歷首先訪問根結(jié)占，可以確泄該二叉樹的 根結(jié)點是A。再由中序序列為DBGEHACIFJ,可以得 到結(jié)點D、B、G、E、H位于根結(jié)點的左子樹上，結(jié) 點C、I、F、J位于根結(jié)點的右子樹上。由于中序 遍歷和后序遍歷都是先遍歷左子樹，故本題后序遍 歷首先訪問D結(jié)點：再由后序遍歷是最后訪問根結(jié) 點,故本題后序遍歷最后訪問的結(jié)點是根結(jié)點A 采用排除法可知，后續(xù)序列為DGHEBIJFCAo 78. 某二叉樹的中序遍歷序列為CBADE,后序迪歷 序列為CBEDA,則前序遍歷序列為 A) CBADE B) CBEDA C) ABCDE D) EDCBA C【解析】二

54、叉樹的后序遍歷序列為CBEDA,由于 后序遍歷最后訪問根結(jié)點，可以確泄該二叉樹的根 結(jié)點是A。再由中序遍歷序列為CBADE,可以得到 子序列(CB) 泄在左子樹中，子序列(DE) 左 在右子樹中。結(jié)點C、B在中序序列和后序序列中 順序未變，說明結(jié)點B是結(jié)點C的父結(jié)點;結(jié)點D、 E在中序序列和后序序列中順序相反，說明結(jié)點D 是結(jié)點E的父結(jié)點。因此該二叉樹的前序遍歷序列 為 ABCDE。 79. 某二叉樹的前序序列為ABCDEFG,中序序列為D C BAEFG,則該二叉樹的深度(根結(jié)點在第1層)為 A) 2 B) 3 C) 4 D) 5 C【解析】二叉樹的前序序列為ABCDEFG,則A為 根結(jié)點：

55、中序序列為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. 設(shè)二叉樹的前序序列與中序序列均為ABC DE F G II,則該二叉樹的后序序列為 A) ABCDH GFE B) DCBAHGFE OEFGIIABC D D) HGFEDCBA D【解析】二叉樹的前序序列與中序序列均為ABC DEFGII,可知二叉樹根結(jié)點為A,且根結(jié)點A只 有右子樹，

56、沒有左子樹。同理,可以推出結(jié)點B只 有右子樹無左子樹。依此類推，垓二叉樹除葉子結(jié) 點外，每個結(jié)點只有右子材無左子樹。因此該二叉 樹的后序序列為H GFEDCBA。 81.某二叉樹的后序遍歷序列與中序颯歷序列相同, 均為ABCDEF,則按層次輸出（同一層從左到右） 的序列為 A）CBAFED B）FEDCBA C）DEFCBA D）ABCD E F B【解析】該二叉樹的后序颯歷序列與中序遍歷序 列均為ABCDEF,則根結(jié)點為F;根結(jié)點F只有左子 樹，右子樹為空。即A B CDE是根結(jié)點F的右子樹集 合。這樣問題就轉(zhuǎn)化為就后序遍歷序列與中序遍歷 序列均為ABCDE的子樹，同理可得左子樹集合的根 結(jié)

57、點為E,且根結(jié)點只有左子樹右子樹。依次類推， 該二叉樹除葉子結(jié)點外，每個結(jié)點只有左子樹無右 子樹，結(jié)構(gòu)如下： 按層次輸出（同一層從左到右）的序列為FEDCB A。 82.某二叉樹的前序序列為ABDFHCEG,中序序列 為HFDBACEG。該二叉樹按層次輸岀（同一層從左 到右）的序列為 A）HGFEDCBA B）HFDBGECA C）ABCDEFGH D）ACEGBDFH C 解析】二叉樹的前序序列為ABDFHCEG,可以確 泄這個二叉樹的根結(jié)點是A;再由中序序列H FDBACEG,可以得到I【F D B為根結(jié)點A的左子樹, CEG為根結(jié)點A的右子樹。同理依次對左子樹II F DB和右子樹CEG

58、進行同樣的推理，得到該二叉樹 的結(jié)構(gòu)如下： 該二叉樹按層次輸岀（同一層從左到右）的序列為 A BCD EFGIIo 8 3 .某完全二叉樹按層次輸出（同一層從左到右） 的序列為ABCDE FGH。該完全二叉樹的前序序列為 A）A BCDEFGH B）AB DHECFG CJHDBEAFCG D）HDEBFGCA B【解析】完全二叉樹的特點是除最后一層外，每 一層上的結(jié)點數(shù)均達到最大值;在最后一層上只缺 少右邊的若干結(jié)點。根據(jù)這一特點,再根據(jù)題意輸 出序列為A B C DEFGH,可以得到該二叉樹的結(jié)構(gòu) 如下： 故此完全二叉樹的前序序列為ABD【I ECFG。 84.設(shè)非空二叉樹的所有子樹中，其

59、左子樹上的結(jié) 點值均小于根結(jié)點值，而右子樹上的結(jié)點值均不小 于根結(jié)點值，則稱該二叉樹為排序二叉樹。對排序 二叉樹的遍歷結(jié)果為有序序列的是 A）前序序列 B）中序序列 C）后序序列 D）前序序列或后序序列 B【解析】中序遍歷的次序是先遍歷左子樹，再遍 歷根結(jié)點，最后遍歷右子樹。而在排序二叉樹中， 左子樹結(jié)點值根結(jié)點值W右子樹結(jié)點值，要使對 排序二叉樹的颯歷結(jié)果為有序序列，只能采用中序 遍歷。 8 5 .設(shè)二叉樹中共有1 5個結(jié)點，其中的結(jié)點值 互不相同。如果該二叉樹的前序序列與中序序列相 同，則該二叉樹的深度為 A )4 B) 6 C) 15 D) 不存在這樣的二叉樹 C【解析】在具有n個結(jié)點的

60、二叉樹中，如果各結(jié) 點值互不相同，若該二叉樹的前序序列與中序序列 相同，則說明該二叉樹只有右子樹,左子樹為空，二 叉樹的深度為n ;若該二叉樹的后序序列與中序序 列相同，則說明該二叉樹只有左子樹，右子樹為空, 二叉樹的深度為n。故本題中二叉樹的深度為15 8 6.在長度為n的順序表中查找一個元素,假設(shè)需 要査找的元素一左在表中，并且元素出現(xiàn)在表中每 個位置上的可能性是相同的，則在平均情況下需要 比較的次數(shù)為 A) n / 4 B) n C) 3n/4 D) (n+l)/2 D【解析】在順序表中查找，最好情況下第一個元 素就是要査找的元素，則比較次數(shù)為1 ；在最壞情 況下，最后一個元素才是要找的