計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考前押題

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

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

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

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

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

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

7、其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)很重要。10.下列敘述中錯(cuò)誤的是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)可以沒(méi)有根結(jié)點(diǎn)B【解析】數(shù)據(jù)元素是一個(gè)含義很廣泛的概念，它是數(shù)據(jù)的“基本單位”，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素可以是一個(gè)數(shù)據(jù)也可以是被抽象出的具有一定結(jié)構(gòu)數(shù)據(jù)集合，所以數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu)。滿足有且只有一個(gè)根結(jié)點(diǎn)并且每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件的非空的數(shù)據(jù)結(jié)構(gòu)認(rèn)為是線性結(jié)構(gòu)，不滿足條件的結(jié)構(gòu)為非線性結(jié)

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

9、線性結(jié)構(gòu)B)非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有前件C)非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有后件D)具有兩個(gè)以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)D【解析】雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針，一個(gè)為左指針，用于指向其前件結(jié)點(diǎn)；一個(gè)為右指針，用于指向其后件結(jié)點(diǎn)，再加上頭指針，具有兩個(gè)以上的指針，但雙向鏈表屬于線性結(jié)構(gòu)。非空線性結(jié)構(gòu)中第一個(gè)結(jié)點(diǎn)沒(méi)有前件，最后一個(gè)結(jié)點(diǎn)無(wú)后件，其余結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。向量也滿足這個(gè)條件，屬于線性結(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) 該數(shù)據(jù)結(jié)構(gòu)為A)線性結(jié)構(gòu)B)循環(huán)隊(duì)列C)循環(huán)

10、鏈表D)非線性結(jié)構(gòu)A【解析】數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成B=（D,R）。其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。例如，假設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組（a,b）表示a是b的前件，b是a的后件。本題中R中的根結(jié)點(diǎn)為f，元素順序?yàn)閒acedb，滿足線性結(jié)構(gòu)的條件。14.設(shè)數(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),(

11、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項(xiàng)中，R=(2,5),(5,4),(3,1),(4,3)，2為根結(jié)點(diǎn)，元素順序?yàn)?5431，屬于線性結(jié)構(gòu)；同理B項(xiàng)1為根結(jié)點(diǎn)，元素順序?yàn)?2345，D項(xiàng)5為跟結(jié)點(diǎn)，元素順序?yàn)?4321，均為線性結(jié)構(gòu)。C項(xiàng)中，元素3有兩個(gè)前件，屬于非線性結(jié)構(gòu)。15.下列敘述中正確的是A)矩陣是非線性結(jié)構(gòu)B)數(shù)組是長(zhǎng)度固定的線性表C)對(duì)線性表只能作插入與刪除運(yùn)算D)線性表中各元素的數(shù)據(jù)類型可以不同B【解析】矩陣也是線性表，只不過(guò)是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類型必須

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、環(huán)隊(duì)列中的元素個(gè)數(shù)為m-1。此在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為m-1-1=m-2。37.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過(guò)一系列正常的操作后，front-1=rear。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為A)48B)49C)1D)0A【解析】該題中rear-front=front-1- front0，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為rear-front=rear-（rear-1）=1。因隊(duì)列中只有1個(gè)元素，故尋找值最大的元素不需要進(jìn)行比較，即比較次數(shù)為0。39.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱?/p>

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

30、向鏈表B)循環(huán)隊(duì)列C)二叉鏈表D)二維數(shù)組A【解析】雙向鏈表也叫雙鏈表，是鏈表（采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。二叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。41.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間一般是不連續(xù)的，并且A)前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)小于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)B)前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)C)前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)可以小于也可以大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)D)以上三種說(shuō)法均不正確C【解析】在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致，因此前件結(jié)點(diǎn)的

31、存儲(chǔ)序號(hào)與后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)之間不存在大小關(guān)系。42.下列敘述中正確的是A)結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表B)結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)C)循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D)循環(huán)鏈表是非線性結(jié)構(gòu)B【解析】結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表，雙向鏈表是線性結(jié)構(gòu)，二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式，屬于線性結(jié)構(gòu)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。43.帶鏈的棧與順序存儲(chǔ)的棧相比，其優(yōu)點(diǎn)是A)入棧與退棧操作方便B)可以省略棧底指針C)入棧操作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出D)所占存儲(chǔ)空間相

32、同C【解析】帶鏈的棧就是用一個(gè)線性鏈表來(lái)表示的棧，線性鏈表不受存儲(chǔ)空間大小的限制，因此入棧操作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出（不需考慮棧滿的問(wèn)題）。44.下列敘述中正確的是A)帶鏈棧的棧底指針是隨棧的操作而動(dòng)態(tài)變化的B)若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列為空C)若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同，則隊(duì)列中至少有一個(gè)元素D)不管是順序棧還是帶鏈的棧，在操作過(guò)程中其棧底指針均是固定不變的A【解析】由于帶鏈棧利用的是計(jì)算機(jī)存儲(chǔ)空間中的所有空閑存儲(chǔ)結(jié)點(diǎn)，因此隨棧的操作棧頂棧底指針動(dòng)態(tài)變化。帶鏈的隊(duì)列中若只有一個(gè)元素，則頭指針與尾指針相同。45.帶鏈?？盏臈l件是A)top=bottom=NU

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

34、ttom時(shí)，棧中的元素個(gè)數(shù)為0。47.某帶鏈棧的初始狀態(tài)為top=bottom=NULL，經(jīng)過(guò)一系列正常的入棧與退棧操作后，top=bottom=20。該棧中的元素個(gè)數(shù)為A)0B)1C)20D)不確定B【解析】帶鏈的棧就是用一個(gè)單鏈表來(lái)表示的棧，棧中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)。棧為空時(shí)，頭指針和尾指針都為NULL；棧中只有一個(gè)元素時(shí)，頭指針和尾指針都指向這個(gè)元素。48.某帶鏈棧的初始狀態(tài)為top=bottom=NULL，經(jīng)過(guò)一系列正常的入棧與退棧操作后，top=10，bottom=20。該棧中的元素個(gè)數(shù)為A)0 B)1C)10D)不確定D【解析】帶鏈的棧使用了鏈表來(lái)表示棧，而鏈表中的元素

35、存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)top=10，bottom=20時(shí)，不能確定棧中元素的個(gè)數(shù)。49.帶鏈隊(duì)列空的條件是A)front=rear=NULLB)front=-1且rear=NULLC)front=NULL且rear=-1D)front=rear=-1A【解析】帶鏈的隊(duì)列就是用一個(gè)單鏈表來(lái)表示的隊(duì)列，隊(duì)列中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)。隊(duì)列空時(shí)，頭指針和尾指針都為NULL。50.在帶鏈隊(duì)列中，經(jīng)過(guò)一系列正常的操作后，如果front=rear，則隊(duì)列中的元素個(gè)數(shù)為A)0B)1C)0或1D)隊(duì)列滿C【解析】帶鏈隊(duì)列空時(shí)，頭指針和尾指針都為NULL；隊(duì)列中只有一個(gè)元素時(shí)，頭指針和尾指針都指向

36、這個(gè)元素。51.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=10。該隊(duì)列中的元素個(gè)數(shù)為A)0B)1C)1或0D)不確定B【解析】帶鏈隊(duì)列空時(shí)，頭指針和尾指針都為null；隊(duì)列中只有一個(gè)元素時(shí)，頭指針和尾指針都指向這個(gè)元素。52.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，front=10,rear=5。該隊(duì)列中的元素個(gè)數(shù)為A)4 B)5C)6D)不確定D【解析】帶鏈的隊(duì)列使用了鏈表來(lái)表示隊(duì)列，而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)front=10,rear=5時(shí)，不能確定隊(duì)列中元素

37、的個(gè)數(shù)。53.下列敘述中錯(cuò)誤的是A)循環(huán)鏈表中有一個(gè)表頭結(jié)點(diǎn)B)循環(huán)鏈表是循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)C)循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針均指向表頭結(jié)點(diǎn)D)循環(huán)鏈表實(shí)現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一B【解析】循環(huán)鏈表是指在單鏈表的第一個(gè)結(jié)點(diǎn)前增加一個(gè)表頭結(jié)點(diǎn)，隊(duì)頭指針指向表頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域的值由NULL改為指向表頭結(jié)點(diǎn)。循環(huán)鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。54.從表中任何一個(gè)結(jié)點(diǎn)位置出發(fā)就可以不重復(fù)地訪問(wèn)到表中其他所有結(jié)點(diǎn)的鏈表是A)循環(huán)鏈表B)雙向鏈表C)單向鏈表D)二叉鏈表A【解析】在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈，只要指出表中任何

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

39、為3的結(jié)點(diǎn)數(shù)為A)6B)7C)8D)不存在這樣的樹(shù)D【解析】根據(jù)題意，樹(shù)中只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn)（7個(gè)），則度為3的結(jié)點(diǎn)有25-7=18個(gè)；又根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，設(shè)度為3的結(jié)點(diǎn)數(shù)為n,則3n+1=25,得n=8。兩種方式得到的度為3的結(jié)點(diǎn)數(shù)不同，故不存在這樣的樹(shù)。58.某棵樹(shù)的度為4，且度為4、3、2、1的結(jié)點(diǎn)個(gè)數(shù)分別為1、2、3、4，則該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為A)11B)9C)10D)8A【解析】設(shè)葉子結(jié)點(diǎn)數(shù)為n，根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，得41+32+23+14+n0+1=21,則n=21-1-2-3-4=11。59.設(shè)一棵樹(shù)的度為3，共有27個(gè)結(jié)

40、點(diǎn)，其中度為3，2，0的結(jié)點(diǎn)數(shù)分別為4，1，10。該樹(shù)中度為1的結(jié)點(diǎn)數(shù)為A) 11B) 12C) 13D)不可能有這樣的樹(shù)B【解析】設(shè)度為1的結(jié)點(diǎn)數(shù)為n，根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，得34+21+1n+010+1=27，則n=12。60.設(shè)一棵度為3的樹(shù)，其中度為2，1，0的結(jié)點(diǎn)數(shù)分別為3，1，6。該樹(shù)中度為3的結(jié)點(diǎn)數(shù)為A)1B)2C)3D)不可能有這樣的樹(shù)A【解析】設(shè)樹(shù)的結(jié)點(diǎn)數(shù)為n，則度為3的結(jié)點(diǎn)數(shù)為n-3-1-6=n-10，根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，得3（n-10）+23+11+06+1=n，解得n=11，則度為3的結(jié)點(diǎn)數(shù)為n-10=11-10=1。61.

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

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

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

44、.5。由于結(jié)點(diǎn)數(shù)只能為整數(shù)，所以不存在這樣的二叉樹(shù)。67.某二叉樹(shù)中共有350個(gè)結(jié)點(diǎn)，其中200個(gè)為葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)點(diǎn)數(shù)為A)不可能有這樣的二叉樹(shù)B)150C)199D)149A【解析】葉子結(jié)點(diǎn)數(shù)為200，根據(jù)在二叉樹(shù)中度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)，則度為2的結(jié)點(diǎn)數(shù)為199，199+200350，故不存在這樣的二叉樹(shù)。68.某二叉樹(shù)的深度為7，其中有64個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為A)0B)1C)2D)63A【解析】葉子結(jié)點(diǎn)有64個(gè)，根據(jù)在二叉樹(shù)中度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)，則度為2的結(jié)點(diǎn)數(shù)為63個(gè)；又深度為m的二叉樹(shù)最多有2m

45、-1個(gè)結(jié)點(diǎn)，則該二叉樹(shù)最多有27-1=127個(gè)結(jié)點(diǎn)。64+63=127，因此該樹(shù)不存在度為1的結(jié)點(diǎn)。69.深度為7的二叉樹(shù)共有127個(gè)結(jié)點(diǎn)，則下列說(shuō)法中錯(cuò)誤的是A)該二叉樹(shù)是滿二叉樹(shù)B)該二叉樹(shù)有一個(gè)度為1的結(jié)點(diǎn)C)該二叉樹(shù)是完全二叉樹(shù)D)該二叉樹(shù)有64個(gè)葉子結(jié)點(diǎn)B【解析】滿二叉樹(shù)滿足深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)，本題中二叉樹(shù)深度為7且有127個(gè)結(jié)點(diǎn)，滿足27-1=127，達(dá)到最大值，故此二叉樹(shù)為滿二叉樹(shù)，也是完全二叉樹(shù)。滿二叉樹(shù)第k層上有2k-1結(jié)點(diǎn)，則該二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為27-1=64個(gè)。滿二叉樹(shù)不存在度為1的結(jié)點(diǎn)。70.深度為5的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)不可能是A)15B)16C)1

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

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

48、總比度為2的結(jié)點(diǎn)多一個(gè)，得度為2的結(jié)點(diǎn)有a-1個(gè)。再根據(jù)完全二叉樹(shù)的定義，度為1的結(jié)點(diǎn)有0個(gè)或1個(gè)，假設(shè)度1結(jié)點(diǎn)為0個(gè)，a+0+a-1=2n，得2a=2n-1，由于結(jié)點(diǎn)個(gè)數(shù)必須為整數(shù)，假設(shè)不成立；當(dāng)度為1的結(jié)點(diǎn)為1個(gè)時(shí)，a+1+a-1=2n，得a=n，即葉子結(jié)點(diǎn)個(gè)數(shù)為n。74.下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A)二叉鏈表B)循環(huán)隊(duì)列C)循環(huán)鏈表D)雙向鏈表A【解析】二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表，二叉樹(shù)是樹(shù)的一種，屬于非線性結(jié)構(gòu)。75.下列敘述中正確的是A)非完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)B)有兩個(gè)指針域的鏈表就是二叉鏈表C)有的二叉樹(shù)也能用順序存儲(chǔ)結(jié)構(gòu)表示D)順序存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)C【

49、解析】在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但對(duì)于滿二叉樹(shù)和完全二叉樹(shù)來(lái)說(shuō)，可以按層進(jìn)行順序存儲(chǔ)。因此A項(xiàng)錯(cuò)誤，C項(xiàng)正確。雖然滿二叉樹(shù)和完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此D項(xiàng)錯(cuò)誤。雙向鏈表也有兩個(gè)指針域，因此B項(xiàng)錯(cuò)誤。76.有二叉樹(shù)如下圖所示：則前序序列為A)ABDEGCFHB)DBGEAFHCC)DGEBHFCAD)ABCDEFGHA【解析】前序遍歷首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。故本題前序序列是ABDEGCFH。中序遍歷首先遍歷左子樹(shù)，然后訪問(wèn)跟結(jié)點(diǎn)，最后遍歷右子樹(shù)；在遍歷左、右

50、子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪問(wèn)跟結(jié)點(diǎn)，最后遍歷右子樹(shù)。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)；在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。故本題的后序序列是DGEBHFCA。77.設(shè)二叉樹(shù)的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為A)JIHGFEDCBAB)DGHEBIJFCA C)GHIJDEFBCAD)ABCDEFGHIJB【解析】二叉樹(shù)的前序序列為ABDEGHCFIJ，由于前序遍歷首先訪問(wèn)根結(jié)點(diǎn)，可以確定該二叉樹(shù)的根結(jié)點(diǎn)是A。再由中序序列為DBGEHACIFJ，可以得到結(jié)

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

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

53、，則說(shuō)明這三個(gè)結(jié)點(diǎn)依次位于前一個(gè)結(jié)點(diǎn)的右子樹(shù)上。故二叉樹(shù)深度為4。80.設(shè)二叉樹(shù)的前序序列與中序序列均為ABCDEFGH，則該二叉樹(shù)的后序序列為A)ABCDHGFEB)DCBAHGFEC)EFGHABCDD)HGFEDCBAD【解析】二叉樹(shù)的前序序列與中序序列均為ABCDEFGH，可知二叉樹(shù)根結(jié)點(diǎn)為A，且根結(jié)點(diǎn)A只有右子樹(shù)，沒(méi)有左子樹(shù)。同理，可以推出結(jié)點(diǎn)B只有右子樹(shù)無(wú)左子樹(shù)。依此類推，該二叉樹(shù)除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有右子樹(shù)無(wú)左子樹(shù)。因此該二叉樹(shù)的后序序列為HGFEDCBA。81.某二叉樹(shù)的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為A)CBAFED

54、B)FEDCBA C)DEFCBAD)ABCDEFB【解析】該二叉樹(shù)的后序遍歷序列與中序遍歷序列均為ABCDEF，則根結(jié)點(diǎn)為F；根結(jié)點(diǎn)F只有左子樹(shù)，右子樹(shù)為空。即ABCDE是根結(jié)點(diǎn)F的右子樹(shù)集合。這樣問(wèn)題就轉(zhuǎn)化為就后序遍歷序列與中序遍歷序列均為ABCDE的子樹(shù)，同理可得左子樹(shù)集合的根結(jié)點(diǎn)為E，且根結(jié)點(diǎn)只有左子樹(shù)右子樹(shù)。依次類推，該二叉樹(shù)除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有左子樹(shù)無(wú)右子樹(shù)，結(jié)構(gòu)如下：按層次輸出（同一層從左到右）的序列為FEDCBA。82.某二叉樹(shù)的前序序列為ABDFHCEG，中序序列為HFDBACEG。該二叉樹(shù)按層次輸出（同一層從左到右）的序列為A)HGFEDCBAB)HFDBGECAC)

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