計算機二級選擇題-數(shù)據(jù)結(jié)構(gòu)與算法核心

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

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

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

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

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

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

7、雜程度D）算法復雜度是用算法中指令的條數(shù)來度量的A【解析】采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理時， 選擇合適的存儲結(jié)構(gòu)很重要。下列敘述中錯誤的是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é)點。下列敘述中正確的是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)都可以

9、是空的數(shù)據(jù)結(jié)構(gòu)。 樹只 有一個根結(jié)點，但不論有幾個葉子結(jié)點，樹都是非線性結(jié)構(gòu)。下列敘述中錯誤的是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)。設(shè)數(shù)據(jù)結(jié)構(gòu) B=（D, R），其中D= a, b,

10、 c, 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 上的關(guān)系，它反映了 D 中各數(shù)據(jù)元素之間的前后件關(guān)系， 通常記為 R。即一個數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（ D,R）。其中 B表示數(shù)據(jù)結(jié)構(gòu)。為了反映 D 中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二 元組來表示。例如，假設(shè) a與 b是 D中的兩個數(shù)據(jù)，則二元組（ a,b）表示 a是 b的前件， b 是 a 的后件。本題中 R 中的根結(jié)點為 f，元素順序為 f

11、aced b，滿足線性結(jié)構(gòu)的條 件。設(shè)數(shù)據(jù)集合為 D= 1, 2, 3, 4, 5 。下列數(shù)據(jù)結(jié)構(gòu) B=（D, R）中為非線性結(jié)構(gòu)的是R= (2,5), (5,4), (3,1), (4,3) R= (1,2), (2,3), (3,4), (4,5) R= (1,2), (2,3), (4,3), (3,5) R= (5,4), (4,3), (3,2), (2,1) C【解析】 A項中， R=(2,5),(5,4),(3,1),(4,3)，2為根結(jié)點，元素順序為 25431，屬于 線性結(jié)構(gòu)；同理 B 項 1 為根結(jié)點，元素順序為 12345，D 項 5 為跟結(jié)點，元素順序 為 54321，

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

13、致 C【解析】在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)相同，在 存儲空間中是按邏輯順序依次存放的。下列敘述中正確的是能采用順序存儲的必定是線性結(jié)構(gòu)所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)循環(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)。4.棧和隊列下列敘述中正確的是在棧中，棧頂指針的動態(tài)變化決定棧中元素的

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

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

16、)，初始狀態(tài)為 top=m+1 ，則棧中的數(shù)據(jù)元素個數(shù)為top -m+1m-top+1m-toptop -mB【解析】棧的初始狀態(tài) top=m+1 ，說明?？諘r top=m+1(m 在棧底， 1 是開口向上的) ，入 棧時棧頂指針是減操作( top=top -1)，退棧時棧頂指針是加操作( top=top+1 )。本題可以假 設(shè)棧中有 x個元素，當x=0時，也就是棧中沒有元素， 則top=m+1 ；當 x=m時，也就是棧滿， 則 top=1 ，由此可以得出 top=m+1 -x ，繼而得出 x=m-top+1 。設(shè)棧的順序存儲空間為 S(1:m)，初始狀態(tài)為 top=m+1 。現(xiàn)經(jīng)過一系列正常

17、的入棧與退棧 操作后， top=0 ，則棧中的元素個數(shù)為1mm+1不可能D【解析】棧的初始狀態(tài)為top=m+1 ，說明棧空時 top=m+1 ，入棧時棧頂指針是減操作(top=top -1)，退棧時棧頂指針是加操作( top=top+1 )。棧滿時 top=1 ，說明棧中不能再進行 入棧操作， top=0 的情況不會出現(xiàn)。設(shè)棧的存儲空間為 S(1:m)，初始狀態(tài)為 top=m+1 。經(jīng)過一系列入棧與退棧操作后， top=1 ?，F(xiàn)又要將一個元素進棧，棧頂指針 top 值變?yōu)?發(fā)生棧滿的錯誤m2B【解析】棧的初始狀態(tài)為top=m+1 ，說明棧空時 top=m+1 ，入棧時棧頂指針是減操作(top=

18、top -1)，退棧時棧頂指針是加操作( top=top+1 )。棧滿時 top=1 ，說明棧中不能再進行 入棧操作(“上溢”錯誤) 。設(shè)棧的存儲空間為 S(1:m)，初始狀態(tài)為 top=m+1 。經(jīng)過一系列入棧與退棧操作后， top=m 。 現(xiàn)又在棧中退出一個元素后，棧頂指針 top 值為0m-1m+1產(chǎn)生?？斟e誤C【解析】棧的順序存儲空間為 S(1: m)，初始狀態(tài) top=m+1 ，所以這個棧是 m 在棧底， 1 是 開口向上的。 經(jīng)過一系列入棧與退棧操作后 top=m ，則棧中有 1個元素， 若現(xiàn)在又退出一個 元素，那么棧頂指針下移一位，回到 m+1 的位置。設(shè)棧的存儲空間為 S(1:

19、50)，初始狀態(tài)為 top=51 ?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后， top=20 ，則棧中的元素個數(shù)為31302120A【解析】棧的初始狀態(tài) top=51 ，故本棧是 51 在棧底，入棧時棧頂指針是減操作 ( top=top -1)， 退棧時棧頂指針是加操作 ( top=top+1 )。當 top=20 時，元素存儲在 (20:50) 空間中， 因此共有 50-20+1=31 個元素。下列處理中與隊列有關(guān)的是二叉樹的遍歷操作系統(tǒng)中的作業(yè)調(diào)度執(zhí)行程序中的過程調(diào)用執(zhí)行程序中的循環(huán)控制 B【解析】隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。由于最先進入隊 列的元素將最先出隊，所以隊

20、列具有“先進先出”的特性，體現(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í)行程序， 與隊列無關(guān)。 執(zhí)行程序中的循環(huán) 控制是指算法的基本控制結(jié)構(gòu)， 包括對循環(huán)條件的判定與執(zhí)行循環(huán)體， 與隊列無關(guān)。 二叉樹 是一個有限的結(jié)點集合， 二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點， 與隊列無關(guān)。設(shè)有棧 S 和隊列 Q，初始狀態(tài)均為空。首先依次將 A,B,C,D,E,F入棧，然后從棧中退出三 個元素依次入隊

21、，再將 X,Y,Z 入棧后，將棧中所有元素退出并依次入隊，最后將隊列中所有元素退出，則退隊元素的順序為DEFXYZABCFEDZYXCBAFEDXYZCBADEFZYXABC B【解析】棧是一種特殊的線性表，它所有的插入與刪除都限定在表的同一端進行。隊列是 指允許在一端進行插入， 而在另一端進行刪除的線性表。 將 A,B,C,D,E,F入棧后， 棧中元素為 ABCDEF，退出三個元素入隊，隊列元素為FED，將 X,Y,Z 入棧后棧中元素為 ABCXYZ，退棧全部入隊后，隊列元素為 FEDZYXCB。A下列敘述中正確的是循環(huán)隊列是順序存儲結(jié)構(gòu)循環(huán)隊列是鏈式存儲結(jié)構(gòu)循環(huán)隊列空的條件是隊頭指針與隊尾

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

23、數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的， 并且 各結(jié)點在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致， 故頭指針和尾指針或棧頂指針無法決 定鏈表長度。循環(huán)隊列的存儲空間為 Q(1:50)，初始狀態(tài)為 front=rear=50 。經(jīng)過一系列正常的入隊與退 隊操作后， front=rear=25 ，此后又插入一個元素，則循環(huán)隊列中的元素個數(shù)為1，或 50 且產(chǎn)生上溢錯誤51262A【解析】在循環(huán)隊列運轉(zhuǎn)起來后，當 front=rear=25 時可知隊列空或者隊列滿，此后又插入 了一個元素， 如果之前隊列為空， 插入操作之后隊列里只有一個元素； 如果插入之前隊列已 滿(50 個元素 )，執(zhí)行插入則會產(chǎn)生溢出錯誤。

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

25、 front=rear=1 ，此后又正常地插入了兩個元素。最后該隊列中的元素個數(shù)為31252C【解析】在循環(huán)隊列運轉(zhuǎn)起來后，由front=rear=1 可知隊列空或者隊列滿 , 此后又可以正常地插入了兩個元素說明插入前隊列為空，則插入后隊列元素個數(shù)為2。設(shè)循環(huán)隊列的存儲空間為 Q(1:m) ，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作 后， front=m ， rear=m-1，此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為m-1m-201B【解析】 在循環(huán)隊列運轉(zhuǎn)起來后， 如果 rear-front0 ，則隊列中的元素個數(shù)為 rear -front 個； 如果 rear-front

26、0 ，則隊列中的元素個數(shù)為 rear-front+m 。該題中 m-1m，即 rear -front0 ， 則該循環(huán)隊列中的元素個數(shù)為( m-1) -m+m=m -1。此后從該循環(huán)隊列中刪除一個元素，則 隊列中的元素個數(shù)為 m -1-1=m- 2。 /m ，即 rear-front0 ，則該循環(huán)隊列中的元素 個數(shù)為( m-1) -m+m=m-1。此后從該循環(huán)隊列中刪除一個元素，則隊列中的元素個數(shù)為 m-1-1=m-2。 設(shè)循環(huán)隊列的存儲空間為 Q(1:m) ，初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊與退隊操作 后， front=m -1，rear=m ，此后再向該循環(huán)隊列中插入一個元素，則隊列中的

27、元素個數(shù)為mm-112D【解析】該題中 m-10，則該循環(huán)隊列中的元素個數(shù)為 m-( m-1)=1。此后從該循環(huán)隊列中 插入一個元素，則隊列中的元素個數(shù)為1+1=2。設(shè)循環(huán)隊列為 Q(1:m) ，其初始狀態(tài)為 front=rear=m 。經(jīng)過一系列入隊與退隊運算后， front=30 ，rear=10。現(xiàn)要在該循環(huán)隊列中作順序查找，最壞情況下需要比較的次數(shù)為1920m-19m-20D【解析】 front=30 ， rear=10， frontrear ，則隊列中有 10-30+m=m-20 個元素，在作順序查 找時，最壞情況下(最后一個元素才是要找的元素或沒有要查找的元素)比較次數(shù)為 m-20

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

29、 rear-front=front -1-front0，則該循環(huán)隊列中的元素個數(shù)為 rear-front=rear - (rear-1)=1。因隊列中只有 1 個元素，故尋找值最大的元素不需要進行比較，即比較次數(shù) 為 0。5.線性鏈表線性表的鏈式存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈式存儲結(jié)構(gòu)的優(yōu)點有節(jié)省存儲空間插入與刪除運算效率高便于查找排序時減少元素的比較次數(shù) B【解析】線性表的順序存儲結(jié)構(gòu)稱為順序表，線性表的鏈式存儲結(jié)構(gòu)稱為鏈表，兩者的優(yōu) 缺點如下表所示。下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈式存儲的是A）雙向鏈表B）循環(huán)隊列C）二叉鏈表D）二維數(shù)組 A【解析】雙向鏈表也叫雙鏈表，是鏈表（采用鏈式存儲結(jié)構(gòu)）的

30、一種，它的每個數(shù)據(jù)結(jié)點 中都有兩個指針， 分別指向直接后繼和直接前驅(qū)。 循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。 叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。在線性表的鏈式存儲結(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)系。下列敘述中正確的是A）結(jié)點中具有兩個指針域的鏈

31、表一定是二叉鏈表B）結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C）循環(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)。帶鏈的棧與順序存儲的棧相比，其優(yōu)點是A）入棧與退棧操作方便B）可以省略棧底指針C）入棧操作時不會受棧存儲空間的限制而發(fā)生溢出D）所占存儲空間相同 C【解析】帶鏈的棧就是用一個線性鏈表來表示的棧，線性鏈表不受存儲空間大小的限制， 因此入棧操作

32、時不會受棧存儲空間的限制而發(fā)生溢出（不需考慮棧滿的問題） 。下列敘述中正確的是帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列為空若帶鏈隊列的隊頭指針與隊尾指針相同，則隊列中至少有一個元素不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的 A【解析】由于帶鏈棧利用的是計算機存儲空間中的所有空閑存儲結(jié)點，因此隨棧的操作棧 頂棧底指針動態(tài)變化。帶鏈的隊列中若只有一個元素，則頭指針與尾指針相同。帶鏈?？盏臈l件是top=bottom=NULLtop=-1 且 bottom=NULLtop=NULL 且 bottom= -1top=bottom= -1A【解

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

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

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

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

37、與非空表運算的統(tǒng)一B【解析】循環(huán)鏈表是指在單鏈表的第一個結(jié)點前增加一個表頭結(jié)點，隊頭指針指向表頭結(jié) 點，最后一個結(jié)點的指針域的值由NULL 改為指向表頭結(jié)點。循環(huán)鏈表是線性表的一種鏈式存儲結(jié)構(gòu)，循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。從表中任何一個結(jié)點位置出發(fā)就可以不重復地訪問到表中其他所有結(jié)點的鏈表是A）循環(huán)鏈表B）雙向鏈表C）單向鏈表D）二叉鏈表A【解析】在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈，只要指出表中任何一個結(jié)點 的位置，就可以從它出發(fā)不重復地訪問到表中其他所有結(jié)點。非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構(gòu)A）有根結(jié)點也有葉子結(jié)點B）沒有根結(jié)點但有葉子結(jié)點C）有根結(jié)點但沒有葉子結(jié)點D）沒有根結(jié)點

38、也沒有葉子結(jié)點A【解析】循環(huán)鏈表表頭結(jié)點為根結(jié)點，鏈表的最后一個結(jié)點為葉子節(jié)點，雖然它含有一個 指向表頭結(jié)點的指針，但是表頭結(jié)點并不是它的一個后件。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)系具有明顯的層次特性。某棵樹中共有 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

39、個；又根據(jù)樹中的結(jié)點數(shù) =樹中所有結(jié)點的度之和 +1，設(shè)度為 3 的結(jié)點數(shù)為 n,則 3n+1=25, 得 n=8。兩種方式得到的度為 3 的結(jié)點數(shù)不同，故不存在這樣的樹。某棵樹的度為 4，且度為 4、3、2、1 的結(jié)點個數(shù)分別為 1、2、3、4，則該樹中的葉子結(jié) 點數(shù)為A）11B）9C）10D）8A【解析】設(shè)葉子結(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。設(shè)一棵樹的度為 3，共有 27 個結(jié)點，其中度為 3，2，0 的結(jié)點數(shù)分別為 4，1，10。該樹 中度為 1 的結(jié)點數(shù)為111213

40、不可能有這樣的樹B【解析】 設(shè)度為 1 的結(jié)點數(shù)為 n，根據(jù)樹中的結(jié)點數(shù) =樹中所有結(jié)點的度之和 +1，得 3 4+2 1+1 n+0 10+1=27，則 n=12。設(shè)一棵度為 3 的樹，其中度為 2，1， 0 的結(jié)點數(shù)分別為 3， 1， 6。該樹中度為 3 的結(jié)點 數(shù)為123不可能有這樣的樹A【解析】設(shè)樹的結(jié)點數(shù)為 n，則度為 3 的結(jié)點數(shù)為 n-3-1-6=n-10 ，根據(jù)樹中的結(jié)點數(shù) =樹中 所有結(jié)點的度之和 +1，得 3(n-10)+23+11+06+1=n，解得 n=11，則度為 3 的結(jié)點 數(shù)為 n-10=11-10=1。設(shè)一棵樹的度為 3，其中沒有度為 2 的結(jié)點，且葉子結(jié)點數(shù)為

41、 5。該樹中度為 3 的結(jié)點數(shù) 為312不可能有這樣的樹C【解析】設(shè)樹的結(jié)點數(shù)為 m ，度為 3 的結(jié)點數(shù)為 n，則度為 1 的結(jié)點數(shù)為 m-n-5, 根據(jù)樹中 的結(jié)點數(shù) =樹中所有結(jié)點的度之和 +1，得 3n+1( m-n-5)+50+1=m，則 n=2。度為 3 的一棵樹共有 30 個結(jié)點，其中度為 3,1 的結(jié)點個數(shù)分別為 3,4 。則該樹中的葉子 結(jié)點數(shù)為141516不可能有這樣的樹B【解析】設(shè)葉子結(jié)點數(shù)為 n，則度為 2 的結(jié)點數(shù)為 30-3-4-n=23-n，根據(jù)樹中的結(jié)點數(shù) =樹中 所有結(jié)點的度之和 +1，得 33+2( 23-n)+14+0n+1=30，則 n=15。設(shè)某棵樹的

42、度為 3，其中度為 2,1,0 的結(jié)點個數(shù)分別為 3,4,15 。則該樹中總結(jié)點數(shù)為不可能有這樣的樹302235A【解析】設(shè)樹的總結(jié)點數(shù)為n ，則度為 3 的結(jié)點數(shù)為 n-3-4-15=n-22，根據(jù)樹中的結(jié)點數(shù) = 樹中所有結(jié)點的度之和 +1，得 3( n-22)+23+14+0 15+1=n，則 n=27.5，求出的結(jié)點 數(shù)不為整數(shù)，故不可能有這樣的樹存在。某二叉樹共有 845 個結(jié)點，其中葉子結(jié)點有 45 個，則度為 1 的結(jié)點數(shù)為400754756不確定C【解析】葉子結(jié)點有 45 個，根據(jù)在二叉樹中度為 0 的結(jié)點(葉子結(jié)點)總比度為 2 的結(jié) 點多一個，則度為 2 的結(jié)點數(shù)為 44

43、個，因此度為 1 的結(jié)點數(shù)為 845-45-44=756 個。某二叉樹中有 15 個度為 1 的結(jié)點， 16 個度為 2 的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為32464849C【解析】根據(jù)在二叉樹中度為 0 的結(jié)點(葉子結(jié)點)總比度為 2 的結(jié)點多一個，得度為 0 的結(jié)點數(shù)為 16+1=17 個，故總的結(jié)點數(shù) =17+15+16=48 個。某二叉樹共有 730 個結(jié)點，其中度為 1 的結(jié)點有 30 個，則葉子結(jié)點個數(shù)為1351350不存在這樣的二叉樹D【解析】設(shè)葉子結(jié)點數(shù)為 n，根據(jù)在二叉樹中度為 0 的結(jié)點(葉子結(jié)點)總比度為 2 的結(jié) 點多一個，則度為 2 的結(jié)點數(shù)為 n-1,n+n-1+30

44、=730，得 n=350.5。由于結(jié)點數(shù)只能為整數(shù)， 所以不存在這樣的二叉樹。某二叉樹中共有 350 個結(jié)點，其中 200 個為葉子結(jié)點，則該二叉樹中度為 2 的結(jié)點數(shù)為不可能有這樣的二叉樹150199149A【解析】葉子結(jié)點數(shù)為 200，根據(jù)在二叉樹中度為 0 的結(jié)點(葉子結(jié)點)總比度為 2 的結(jié) 點多一個，則度為 2 的結(jié)點數(shù)為 199， 199+200350，故不存在這樣的二叉樹。某二叉樹的深度為 7，其中有 64 個葉子結(jié)點，則該二叉樹中度為 1 的結(jié)點數(shù)為01263A【解析】葉子結(jié)點有 64 個，根據(jù)在二叉樹中度為 0 的結(jié)點(葉子結(jié)點)總比度為 2 的結(jié) 點多一個，則度為 2 的結(jié)

45、點數(shù)為 63 個；又深度為 m 的二叉樹最多有 2m-1 個結(jié)點，則該二 叉樹最多有 27-1=127 個結(jié)點。 64+63=127，因此該樹不存在度為 1 的結(jié)點。深度為 7 的二叉樹共有 127 個結(jié)點，則下列說法中錯誤的是該二叉樹是滿二叉樹該二叉樹有一個度為 1 的結(jié)點該二叉樹是完全二叉樹該二叉樹有 64 個葉子結(jié)點B【解析】滿二叉樹滿足深度為 m 的二叉樹最多有 2m-1 個結(jié)點，本題中二叉樹深度為 7 且 有 127 個結(jié)點，滿足 27-1=127，達到最大值，故此二叉樹為滿二叉樹，也是完全二叉樹。 滿二叉樹第 k 層上有 2k-1 結(jié)點，則該二叉樹的葉子結(jié)點數(shù)為 27-1=64 個

46、。滿二叉樹不存在 度為 1 的結(jié)點。深度為 5 的完全二叉樹的結(jié)點數(shù)不可能是15161718A【解析】設(shè)完全二叉樹的結(jié)點數(shù)為 n，根據(jù)深度為 k 的二叉樹至多有 2k-1 個結(jié)點，再根據(jù) 完全二叉樹的定義可知， 2k-1-1n 2k-1。本題中完全二叉樹的深度為 5，則 25-1-1n25-1， 15n31。因此，結(jié)點數(shù)不能為 15。/n 31。因此，結(jié)點數(shù)不能為 15 。/n 2/n 2某完全二叉樹共有 256 個結(jié)點，則該完全二叉樹的深度為78910C【解析】根據(jù)完全二叉樹的性質(zhì)：具有n 個結(jié)點的完全二叉樹的深度為 log2n+1 。本題中完全二叉樹共有 256 個結(jié)點，則深度為 log2

47、256+1=8+1=9 。深度為的完全二叉樹中共有 125 個結(jié)點，則該完全二叉樹中的葉子結(jié)點數(shù)為62636465B【解析】在滿二叉樹的第 k 層上有 2k-1 個結(jié)點、且深度為 m 的滿二叉樹有 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é)點) 。因此，該完全二叉樹中共有葉子

48、結(jié)點 62+1=63 個。在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為nn+1n-1D）n/2A【解析】由二叉樹的定義可知，樹中必定存在度為0 的結(jié)點和度為 2 的結(jié)點，設(shè)度為 0 結(jié)點有 a 個，根據(jù)度為 0 的結(jié)點（即葉子結(jié)點）總比度為 2 的結(jié)點多一個， 得度為 2 的結(jié)點有 a-1 個。再根據(jù)完全二叉樹的定義，度為 1 的結(jié)點有 0 個或 1 個，假設(shè)度 1 結(jié)點為 0 個， a+0+a-1=2n ，得 2a=2n-1，由于結(jié)點個數(shù)必須為整數(shù)，假設(shè)不成立；當度為1 的結(jié)點為 1 個時， a+1+a- 1=2n，得 a=n，即葉子結(jié)點個數(shù)為 n。下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A）二

49、叉鏈表B）循環(huán)隊列C）循環(huán)鏈表D）雙向鏈表 A【解析】二叉樹的鏈式存儲結(jié)構(gòu)也稱為二叉鏈表，二叉樹是樹的一種，屬于非線性結(jié)構(gòu)。下列敘述中正確的是A）非完全二叉樹可以采用順序存儲結(jié)構(gòu)B）有兩個指針域的鏈表就是二叉鏈表C）有的二叉樹也能用順序存儲結(jié)構(gòu)表示D）順序存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C【解析】 在計算機中， 二叉樹通常采用鏈式存儲結(jié)構(gòu)， 但對于滿二叉樹和完全二叉樹來說， 可以按層進行順序存儲。因此 A項錯誤， C項正確。雖然滿二叉樹和完全二叉樹可以采用順 序存儲結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此 D 項錯誤。雙向鏈表也有兩個指針域，因此 B 項錯誤。76.有二叉樹如下圖所示：則前序序列為A）ABDEG

50、CFHB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH A【解析】前序遍歷首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子 樹時，仍然先訪問根結(jié)點， 然后遍歷左子樹， 最后遍歷右子樹。 故本題前序序列是 ABDEGCFH。 中序遍歷首先遍歷左子樹，然后訪問跟結(jié)點，最后遍歷右子樹；在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問跟結(jié)點，最后遍歷右子樹。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點；在遍歷左、右子樹時，仍然 先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。故本題的后序序列是DGEBHFCA。設(shè)二叉樹的前序序列為 A

51、BDEGHCFI，J 中序序列為 DBGEHACIF。J 則后序序列為JIHGFEDCBADGHEBIJFCAGHIJDEFBCAABCDEFGHIJB【解析】二叉樹的前序序列為 ABDEGHCFI，J 由于前序遍歷首先訪問根結(jié)點，可以確定該二 叉樹的根結(jié)點是 A。再由中序序列為 DBGEHACIF，J可以得到結(jié)點 D、B、G、E、H 位于根結(jié) 點的左子樹上，結(jié)點 C、I、 F、 J 位于根結(jié)點的右子樹上。由于中序遍歷和后序遍歷都是先 遍歷左子樹，故本題后序遍歷首先訪問 D 結(jié)點；再由后序遍歷是最后訪問根結(jié)點，故本題 后序遍歷最后訪問的結(jié)點是根結(jié)點A。采用排除法可知，后續(xù)序列為DGHEBIJF

52、CA。某二叉樹的中序遍歷序列為 CBADE，后序遍歷序列為 CBEDA，則前序遍歷序列為CBADECBEDAABCDEEDCBAC【解析】二叉樹的后序遍歷序列為CBEDA，由于后序遍歷最后訪問根結(jié)點，可以確定該二叉樹的根結(jié)點是 A。再由中序遍歷序列為 CBADE，可以得到子序列( CB)一定在左子樹中， 子序列( DE)一定在右子樹中。結(jié)點 C、B 在中序序列和后序序列中順序未變，說明結(jié)點B是結(jié)點 C的父結(jié)點；結(jié)點 D、E在中序序列和后序序列中順序相反，說明結(jié)點D 是結(jié)點 E的父結(jié)點。因此該二叉樹的前序遍歷序列為ABCDE。某二叉樹的前序序列為 ABCDEFG，中序序列為 DCBAEFG，則該

53、二叉樹的深度 (根結(jié)點在 第 1 層)為2345C【解析】二叉樹的前序序列為 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。設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為ABCDHGFEDCBAHGFEEFGHABCDHGFEDCBAD【解析】二叉樹的前序序列與中序序列均

54、為ABCDEFGH，可知二叉樹根結(jié)點為 A，且根結(jié) 點 A 只有右子樹，沒有左子樹。同理，可以推出結(jié)點 B 只有右子樹無左子樹。依此類推， 該二叉樹除葉子結(jié)點外，每個結(jié)點只有右子樹無左子樹。因此該二叉樹的后序序列為 HGFEDCBA。某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出(同一層從左到右)的序列為CBAFEDFEDCBADEFCBAABCDEFB【解析】該二叉樹的后序遍歷序列與中序遍歷序列均為ABCDEF，則根結(jié)點為 F；根結(jié)點 F只有左子樹，右子樹為空。即 ABCDE是根結(jié)點 F 的左子樹集合。這樣問題就轉(zhuǎn)化為就后序 遍歷序列與中序遍歷序列均為 ABCDE的

55、子樹， 同理可得左子樹集合的根結(jié)點為E，且根結(jié)點E 只有左子樹無右子樹。 依次類推， 該二叉樹除葉子結(jié)點外， 每個結(jié)點只有左子樹無右子樹， 結(jié)構(gòu)如下：按層次輸出(同一層從左到右)的序列為FEDCBA。某二叉樹的前序序列為 ABDFHCEG，中序序列為 HFDBACEG。該二叉樹按層次輸出(同一 層從左到右)的序列為HGFEDCBAHFDBGECAABCDEFGHACEGBDFHC【解析】二叉樹的前序序列為ABDFHCEG，可以確定這個二叉樹的根結(jié)點是A；再由中序序列 HFDBACEG，可以得到 HFDB為根結(jié)點 A的左子樹， CEG為根結(jié)點 A 的右子樹。同理依 次對左子樹 HFDB 和右子樹

56、 CEG進行同樣的推理，得到該二叉樹的結(jié)構(gòu)如下：該二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。某完全二叉樹按層次輸出 （同一層從左到右） 的序列為 ABCDEFGH。該完全二叉樹的前序 序列為A）ABCDEFGHB）ABDHECFGC）HDBEAFCGD）HDEBFGCAB【解析】完全二叉樹的特點是除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一 層上只缺少右邊的若干結(jié)點。根據(jù)這一特點，再根據(jù)題意輸出序列為ABCDEFGH，可以得到該二叉樹的結(jié)構(gòu)如下：故此完全二叉樹的前序序列為 ABDHECFG。設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點值均小于根結(jié)點值，而右子樹上的結(jié)點

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

58、，左子樹為空，二叉樹的深度為n；若該二叉樹的后序序列與中序序列相同， 則說明該二叉樹只有左子樹， 右子樹為空， 二叉樹的深度為 n。 故本題中二叉樹的深度為 15。7查找技術(shù)在長度為 n 的順序表中查找一個元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn) 在表中每個位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為n/4n3n/4(n+1)/2D【解析】在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個元素才是要找的元素，則比較次數(shù)為n。則平均比較次數(shù)： ( 1+2+n )/n=(n(n+1)/2)/n=(n+1)/2 。在長度為 n 的順序表中查

59、找一個元素，假設(shè)需要查找的元素有一半的機會在表中，并且 如果元素在表中 ,則出現(xiàn)在表中每個位置上的可能性是相同的。則在平均情況下需要比較的 次數(shù)大約為n3n/4n/2n/4B【解析】在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個元素才是要找的元素，則比較次數(shù)為n 。這是找到元素的情況。如果沒有找到元素，則要比較 n 次。因此，平均需要比較：下列算法中均以比較作為基本運算，則平均情況與最壞情況下的時間復雜度相同的是在順序存儲的線性表中尋找最大項在順序存儲的線性表中進行順序查找在順序存儲的有序表中進行對分查找在鏈式存儲的有序表中進行查找A【解析】 尋找

60、最大項， 無論如何都要查看所有的數(shù)據(jù)， 與數(shù)據(jù)原始排列順序沒有多大關(guān)系， 無所謂最壞情況和最好情況， 或者說平均情況與最壞情況下的時間復雜度是相同的。 而查找 無論是對分查找還是順序查找， 都與要找的數(shù)據(jù)和原始的數(shù)據(jù)排列情況有關(guān)， 最好情況是第 1 次查看的一個數(shù)據(jù)恰好是要找的數(shù)據(jù)， 只需要比較 1 次；如果沒有找到再查看下一個數(shù)據(jù)， 直到找到為止， 最壞情況下是最后一次查看的數(shù)據(jù)才是要找的， 順序查找和對分查找在最壞 情況下比較次數(shù)分別是 n 和 log2n ，平均情況則是 1最壞情況的平均，因而是不同的。線性表的長度為 n。在最壞情況下，比較次數(shù)為 n-1 的算法是A）順序查找B）同時尋找