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

1、1下列敘述中正確的是 )所謂算法就是計(jì)算方法）程序可以作為算法的一種描述方法)算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果)算法設(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ò)誤的是 )算法強(qiáng)調(diào)動(dòng)態(tài)的執(zhí)行過(guò)程，不同于靜態(tài)的計(jì)算公式b）算法必須能在

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

3、述中正確的是)算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)b)算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)c）算法的時(shí)間復(fù)雜度與算法程序中的語(yǔ)句條數(shù)成正比)算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)【解析】為了能夠比較客觀地反映出一個(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)解決同一個(gè)問(wèn)題的不同算法的時(shí)間

4、復(fù)雜度一般是不同的b)解決同一個(gè)問(wèn)題的不同算法的時(shí)間復(fù)雜度必定是相同的)對(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.下列敘述中正確的是）算法的空間復(fù)雜度是指算法程序中指令的條數(shù)b)壓縮數(shù)據(jù)存儲(chǔ)空間不會(huì)降低算法的空間復(fù)雜度)算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲(chǔ)空間有關(guān)d）算法的

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

6、來(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é)果的可靠性【解析】在許多實(shí)際問(wèn)題中，為了減少算法所占的存儲(chǔ)空間，通產(chǎn)采用壓縮存儲(chǔ)技術(shù),以便盡量減少不必要的額外空間。9.下列敘述中正確的是a)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)會(huì)影響算法的效率b)算法設(shè)計(jì)只需考慮結(jié)果的可靠性)算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度d)算法復(fù)雜度是用算法中指令的條數(shù)來(lái)度量的a【解析】采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此,在進(jìn)行數(shù)據(jù)處

7、理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)很重要。0.下列敘述中錯(cuò)誤的是 ）數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu))數(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é)構(gòu)?？諗?shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)。

8、非空數(shù)據(jù)結(jié)構(gòu)可以沒(méi)有根結(jié)點(diǎn)，如非性線結(jié)構(gòu)“圖”就沒(méi)有根結(jié)點(diǎn)。.下列敘述中正確的是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)【解析】如果一個(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)。.下列敘述中錯(cuò)誤的是a)向量是線性結(jié)構(gòu)b)非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有前件c）非空線性

9、結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒(méi)有后件)具有兩個(gè)以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)【解析】雙向鏈表每個(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)。1.設(shè)數(shù)據(jù)結(jié)構(gòu)b=(d,r），其中 d=，b,c,d,e,f r=(f,a),(,b),(，)，（,e）,(a，c) 該數(shù)據(jù)結(jié)構(gòu)為 a）線性結(jié)構(gòu)b)循環(huán)隊(duì)列）循環(huán)鏈表d)非線性結(jié)構(gòu)a【解析】數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素:一是數(shù)據(jù)元素的集合

10、，通常記為d;二是d上的關(guān)系,它反映了中各數(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,）表示a是b的前件,b是a的后件。本題中中的根結(jié)點(diǎn)為,元素順序?yàn)閒aed,滿足線性結(jié)構(gòu)的條件。14.設(shè)數(shù)據(jù)集合為d,2,3,4,5。下列數(shù)據(jù)結(jié)構(gòu)b(d,r)中為非線性結(jié)構(gòu)的是 )=（2,5）,(5,），（3，1)，（4，3)b）(,2),（,3),(3,4),(4,5)c）r=(1，）,(,3),(4,),(3,)d)r=（5，4),（4，),(3，

11、2),（,1)c【解析】項(xiàng)中,r=(2,5），(5,4),(3,),(4,3),2為根結(jié)點(diǎn)，元素順序?yàn)?5431,屬于線性結(jié)構(gòu);同理b項(xiàng)為根結(jié)點(diǎn),元素順序?yàn)?45，d項(xiàng)5為跟結(jié)點(diǎn),元素順序?yàn)?4321，均為線性結(jié)構(gòu)。c項(xiàng)中，元素3有兩個(gè)前件，屬于非線性結(jié)構(gòu)。5下列敘述中正確的是a)矩陣是非線性結(jié)構(gòu)b）數(shù)組是長(zhǎng)度固定的線性表c)對(duì)線性表只能作插入與刪除運(yùn)算d）線性表中各元素的數(shù)據(jù)類(lèi)型可以不同【解析】矩陣也是線性表,只不過(guò)是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類(lèi)型必須相同。在線性表中,不僅可以做插入與刪除運(yùn)算，還可以進(jìn)行查找或?qū)€性表進(jìn)行排序等操作。16在線性表的順序存儲(chǔ)結(jié)構(gòu)中,其存儲(chǔ)空間連續(xù)，

12、各個(gè)元素所占的字節(jié)數(shù) a不同，但元素的存儲(chǔ)順序與邏輯順序一致)不同,且其元素的存儲(chǔ)順序可以與邏輯順序不一致)相同，元素的存儲(chǔ)順序與邏輯順序一致d)相同，但其元素的存儲(chǔ)順序可以與邏輯順序不一致【解析】在線性表的順序存儲(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))循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)b【解析】所有的線性結(jié)構(gòu)都可以用數(shù)組保存，即都可以采用順序存儲(chǔ)結(jié)構(gòu)。而反過(guò)來(lái)不可以,完全二叉樹(shù)也能用數(shù)組保存（按層次依次存放到數(shù)

13、據(jù)元素中）,但完全二叉樹(shù)不屬于非線性結(jié)構(gòu)。雙向鏈表具有兩個(gè)以上的指針,但屬于線性結(jié)構(gòu)。循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。1下列敘述中正確的是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【解析】在棧中,通常用指針op來(lái)指示棧頂?shù)奈恢?用指針botto指向棧底。棧頂指針op動(dòng)態(tài)反應(yīng)了棧中元素的變化情況。在循環(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ǔ)空間中的位

14、置關(guān)系與邏輯關(guān)系也不一致,故頭指針和尾指針或棧頂指針無(wú)法決定鏈表長(zhǎng)度。19.設(shè)棧的順序存儲(chǔ)空間為s(1:)，初始狀態(tài)為o。現(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后，topm+，則棧中的元素個(gè)數(shù)為a) 0 b）mc）不可能d)m+【解析】棧為空時(shí),棧頂指針tp=,經(jīng)過(guò)入棧和退棧運(yùn)算，指針始終指向棧頂元素。初始狀態(tài)為op=0,當(dāng)棧滿時(shí)t=,無(wú)法繼續(xù)入棧，to值不可能為m+1。20.設(shè)棧的存儲(chǔ)空間為s(：50),初始狀態(tài)為top=-?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后,op30,則棧中的元素個(gè)數(shù)為a)20b)19c)3d【解析】棧的初始狀態(tài)為p=-表示棧為空(沒(méi)有規(guī)定棧中棧底必須是0），經(jīng)過(guò)一系列正常的入

15、棧與退棧操作后top=3,則空間(1:3)中插入了元素，共30個(gè)。2設(shè)棧的順序存儲(chǔ)空間為s（1:m）,初始狀態(tài)為tp=m+1,則棧中的數(shù)據(jù)元素個(gè)數(shù)為 a)t-1）m-p+1)m-topd)tp-mb【解析】棧的初始狀態(tài)top=+1,說(shuō)明棧空時(shí)tp=+1(m在棧底，1是開(kāi)口向上的）,入棧時(shí)棧頂指針是減操作(p=to-1),退棧時(shí)棧頂指針是加操作（top=top+1）。本題可以假設(shè)棧中有個(gè)元素,當(dāng)=0時(shí),也就是棧中沒(méi)有元素,則top=+1;當(dāng)=m時(shí)，也就是棧滿,則tp，由此可以得出top=m1-x,繼而得出x=top-m+1。22設(shè)棧的順序存儲(chǔ)空間為s(1：），初始狀態(tài)為top=m+1?，F(xiàn)經(jīng)過(guò)一系

16、列正常的入棧與退棧操作后，top=0，則棧中的元素個(gè)數(shù)為a)b)c）m+)不可能d【解析】棧的初始狀態(tài)為op=+1，說(shuō)明?？諘r(shí)op+1，入棧時(shí)棧頂指針是減操作(topto-),退棧時(shí)棧頂指針是加操作(top=to+)。棧滿時(shí)top=1，說(shuō)明棧中不能再進(jìn)行入棧操作,op=0的情況不會(huì)出現(xiàn)。23設(shè)棧的存儲(chǔ)空間為s(1:),初始狀態(tài)為to=+1。經(jīng)過(guò)一系列入棧與退棧操作后,top=1?，F(xiàn)又要將一個(gè)元素進(jìn)棧，棧頂指針top值變?yōu)閍）0 b)發(fā)生棧滿的錯(cuò)誤）md)2【解析】棧的初始狀態(tài)為to=m+1，說(shuō)明棧空時(shí)top1,入棧時(shí)棧頂指針是減操作(tp=to-1),退棧時(shí)棧頂指針是加操作(top=top1）

17、。棧滿時(shí)t=1，說(shuō)明棧中不能再進(jìn)行入棧操作（“上溢”錯(cuò)誤）。24.設(shè)棧的存儲(chǔ)空間為s（1:m),初始狀態(tài)為op=m+1。經(jīng)過(guò)一系列入棧與退棧操作后,p?，F(xiàn)又在棧中退出一個(gè)元素后，棧頂指針top值為a）)m-1c)m1d)產(chǎn)生?？斟e(cuò)誤【解析】棧的順序存儲(chǔ)空間為s(1:m)，初始狀態(tài)top=m1,所以這個(gè)棧是m在棧底，1是開(kāi)口向上的。經(jīng)過(guò)一系列入棧與退棧操作后top=m,則棧中有1個(gè)元素,若現(xiàn)在又退出一個(gè)元素,那么棧頂指針下移一位,回到m的位置。25.設(shè)棧的存儲(chǔ)空間為s（1:5)，初始狀態(tài)為t=51?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后,to=0，則棧中的元素個(gè)數(shù)為a）31b)0)1d)0【解析】棧

18、的初始狀態(tài)t51，故本棧是1在棧底，入棧時(shí)棧頂指針是減操作(top=tp-),退棧時(shí)棧頂指針是加操作(tp=tp+1）。當(dāng)op0時(shí),元素存儲(chǔ)在(0:5)空間中，因此共有520+1=31個(gè)元素。26.下列處理中與隊(duì)列有關(guān)的是 a）二叉樹(shù)的遍歷b）操作系統(tǒng)中的作業(yè)調(diào)度c)執(zhí)行程序中的過(guò)程調(diào)用）執(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ì)列的

19、過(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è)有限的結(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,e,f入棧,然后從棧中退出三個(gè)元素依次入隊(duì)，再將x,y,z入棧后,將棧中所有元素退出并依次入隊(duì),最后將隊(duì)列中所有元素退出,則退隊(duì)元素的順序?yàn)閍）dfxyzabcb)fedyxcbac)fxycba)dfzybcb【解析】棧是一種特殊的線性表，它所有的插入與刪除都限定在

20、表的同一端進(jìn)行。隊(duì)列是指允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表。將a,b,d，e,入棧后，棧中元素為abcde，退出三個(gè)元素入隊(duì)，隊(duì)列元素為fed,將x，y,z入棧后棧中元素為abcxyz，退棧全部入隊(duì)后,隊(duì)列元素為fdzyxc。28.下列敘述中正確的是 ）循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)b)循環(huán)隊(duì)列是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)c）循環(huán)隊(duì)列空的條件是隊(duì)頭指針與隊(duì)尾指針相同)循環(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.下列敘述中正確

21、的是a)在循環(huán)隊(duì)列中,隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度）在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度c）在帶鏈的隊(duì)列中,隊(duì)頭指針與隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長(zhǎng)度d)在帶鏈的棧中,棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)【解析】在循環(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ǔ)空間為 （:50)，初始狀態(tài)為 nt=rear=50。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，font=ra

22、r=25,此后又插入一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為a)1，或5且產(chǎn)生上溢錯(cuò)誤)51c)26d)【解析】循環(huán)隊(duì)列長(zhǎng)度為0，由初始狀態(tài)為frontre=50可知此時(shí)循環(huán)隊(duì)列為空。入隊(duì)運(yùn)算時(shí)，首先隊(duì)尾指針ear進(jìn)(即rea1），然后在隊(duì)尾指針ear指向的位置插入新元素。當(dāng)隊(duì)尾指針rear=51時(shí)，置a=1。退隊(duì)運(yùn)算時(shí),排頭指針fnt進(jìn)1（即frn+1），然后刪除font指針指向的位置上的元素,當(dāng)排頭指針front=50+時(shí)，置ron=1。當(dāng)frt=ear=時(shí)可知隊(duì)列空或者隊(duì)列滿,此后又插入了一個(gè)元素,如果之前隊(duì)列為空，插入操作之后隊(duì)列里只有一個(gè)元素；如果插入之前隊(duì)列已滿(0個(gè)元素),執(zhí)行插入則會(huì)

23、產(chǎn)生溢出錯(cuò)誤。31循環(huán)隊(duì)列的存儲(chǔ)空間為 q(1:40),初始狀態(tài)為 font=ear=0。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后,fron=rar15,此后又退出一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為a) b）15c)0d)39,或0且產(chǎn)生下溢錯(cuò)誤d【解析】當(dāng)front=ear=1時(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ǔ)空間為(1:0)，初始狀態(tài)為on=ea=50。現(xiàn)經(jīng)過(guò)一系列入隊(duì)與退隊(duì)操作后，frot=re=1,此后又正常地插入了兩個(gè)元素。最后該隊(duì)列中

24、的元素個(gè)數(shù)為a)b)c)2d)5c【解析】由fronrear=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ì)操作后，frontm,rea=m-,此后從該循環(huán)隊(duì)列中刪除一個(gè)元素,則隊(duì)列中的元素個(gè)數(shù)為a)-1b）-2c)0d)1b【解析】從排頭指針fnt指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。如果rea-fo,則隊(duì)列中的元素個(gè)數(shù)為rar-fon個(gè)；如果rea-ront0,則隊(duì)列中的元素個(gè)數(shù)為e-rntm。該題中m-m,即re

25、r-fron0,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為(-）-mm=m-。此后從該循環(huán)隊(duì)列中刪除一個(gè)元素,則隊(duì)列中的元素個(gè)數(shù)為m1-=m2。3.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為q(1:m），初始狀態(tài)為空?，F(xiàn)經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后，fot=-,rear=m,此后再向該循環(huán)隊(duì)列中插入一個(gè)元素,則隊(duì)列中的元素個(gè)數(shù)為a) b)-1c)1d)2d【解析】該題中-1rear，則隊(duì)列中有10-+m=m20個(gè)元素,在作順序查找時(shí),最壞情況下(最后一個(gè)元素才是要找的元素或沒(méi)有要查找的元素）比較次數(shù)為m20次。6.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為（:），初始狀態(tài)為rotear=m。經(jīng)過(guò)一系列正常的操作后,frnt=,rea=m。為了在

26、該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為）0b)1)m-2)m-1c【解析】該題中,即rear-front0,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為m-1。此在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為m1=m-。37.設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為(:0)，初始狀態(tài)為n=e=0。經(jīng)過(guò)一系列正常的操作后,front1=ar。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為a)8b)49c）1d）0a【解析】該題中rear-fron=frot- font,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為er-frnt=rr（rear-1）=。因隊(duì)列中只有個(gè)元素,故尋找值最大的元素不需要進(jìn)行比較，即比

27、較次數(shù)為0。9.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有 a)節(jié)省存儲(chǔ)空間b)插入與刪除運(yùn)算效率高c)便于查找)排序時(shí)減少元素的比較次數(shù)【解析】線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表,兩者的優(yōu)缺點(diǎn)如下表所示。類(lèi)型優(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)元素()存儲(chǔ)空間易于擴(kuò)充并且方便空間的動(dòng)態(tài)分配需要額外的空間（指針域)來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系,存儲(chǔ)

28、密度比順序表低40.下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)的是a)雙向鏈表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ō)法均不正確【解析】在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號(hào)是不連續(xù)的，并且各結(jié)

29、點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致,因此前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)與后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)之間不存在大小關(guān)系。2.下列敘述中正確的是 a）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一定是二叉鏈表）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)）循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))循環(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)。.帶鏈的棧與順序存儲(chǔ)的棧相比，其優(yōu)點(diǎn)是 a)入棧與退棧操作方便)可以省略棧底指針c)入棧操作時(shí)不

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

31、的條件是）p=bottoullb)to=-且bom=null)topnul且tom=-1d)to=otm-a【解析】在帶鏈的棧中，只會(huì)出現(xiàn)?？蘸头强諆煞N狀態(tài)。當(dāng)棧為空時(shí),有topboom=nl;當(dāng)棧非空時(shí),top指向鏈表的第一個(gè)結(jié)點(diǎn)(棧頂）。6.在帶鏈棧中，經(jīng)過(guò)一系列正常的操作后,如果to=ottom，則棧中的元素個(gè)數(shù)為)0或1）0c）1d)棧滿a【解析】帶鏈棧就是沒(méi)有附加頭結(jié)點(diǎn)、運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底指針指向的存儲(chǔ)單元中存有一個(gè)元素，則當(dāng)tobotto時(shí),棧中的元素個(gè)數(shù)為；如果棧底指針指向的存儲(chǔ)單元中沒(méi)有元素,則當(dāng)top=bttom時(shí)，棧中的元素個(gè)數(shù)為0。47.

32、某帶鏈棧的初始狀態(tài)為top=btom=nll,經(jīng)過(guò)一系列正常的入棧與退棧操作后,toboto=20。該棧中的元素個(gè)數(shù)為 a)0b）1c）20d)不確定b【解析】帶鏈的棧就是用一個(gè)單鏈表來(lái)表示的棧，棧中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)。棧為空時(shí)，頭指針和尾指針都為nu;棧中只有一個(gè)元素時(shí),頭指針和尾指針都指向這個(gè)元素。48.某帶鏈棧的初始狀態(tài)為top=bottomll，經(jīng)過(guò)一系列正常的入棧與退棧操作后，tp=0，ottom=2。該棧中的元素個(gè)數(shù)為 a）0 )1）10d)不確定d【解析】帶鏈的棧使用了鏈表來(lái)表示棧,而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中,因此當(dāng)top10,bottom20時(shí),不能確定棧

33、中元素的個(gè)數(shù)。49.帶鏈隊(duì)列空的條件是 )frontear=ulb）frot=-1且rer=nllc)frnt=null且rear=1d)frn=ra-1a【解析】帶鏈的隊(duì)列就是用一個(gè)單鏈表來(lái)表示的隊(duì)列，隊(duì)列中的每一個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)。隊(duì)列空時(shí)，頭指針和尾指針都為null。5在帶鏈隊(duì)列中,經(jīng)過(guò)一系列正常的操作后,如果fron=,則隊(duì)列中的元素個(gè)數(shù)為 a）b）1)或1d)隊(duì)列滿c【解析】帶鏈隊(duì)列空時(shí),頭指針和尾指針都為null；隊(duì)列中只有一個(gè)元素時(shí),頭指針和尾指針都指向這個(gè)元素。51.某帶鏈的隊(duì)列初始狀態(tài)為frot=ar=ll。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后,ront=ear=10。該

34、隊(duì)列中的元素個(gè)數(shù)為a)0)）或0d）不確定【解析】帶鏈隊(duì)列空時(shí),頭指針和尾指針都為null；隊(duì)列中只有一個(gè)元素時(shí),頭指針和尾指針都指向這個(gè)元素。5某帶鏈的隊(duì)列初始狀態(tài)為ron=rrn。經(jīng)過(guò)一系列正常的入隊(duì)與退隊(duì)操作后,frnt=10，rear。該隊(duì)列中的元素個(gè)數(shù)為）4 b)c)d）不確定d【解析】帶鏈的隊(duì)列使用了鏈表來(lái)表示隊(duì)列,而鏈表中的元素存儲(chǔ)在不連續(xù)的地址中，因此當(dāng)front=0,er=5時(shí),不能確定隊(duì)列中元素的個(gè)數(shù)。5.下列敘述中錯(cuò)誤的是a)循環(huán)鏈表中有一個(gè)表頭結(jié)點(diǎn))循環(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)了空表與非空

35、表運(yùn)算的統(tǒng)一b【解析】循環(huán)鏈表是指在單鏈表的第一個(gè)結(jié)點(diǎn)前增加一個(gè)表頭結(jié)點(diǎn)，隊(duì)頭指針指向表頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域的值由ll改為指向表頭結(jié)點(diǎn)。循環(huán)鏈表是線性表的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。5.從表中任何一個(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)狀鏈，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)不重復(fù)地訪問(wèn)到表中其他所有結(jié)點(diǎn)。55.非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構(gòu) ）有根結(jié)點(diǎn)也有葉子結(jié)點(diǎn)b)沒(méi)有根結(jié)點(diǎn)但有葉子結(jié)點(diǎn))有根結(jié)點(diǎn)但沒(méi)有葉子結(jié)點(diǎn))沒(méi)有根結(jié)點(diǎn)也沒(méi)有葉子

36、結(jié)點(diǎn)【解析】循環(huán)鏈表表頭結(jié)點(diǎn)為根結(jié)點(diǎn),鏈表的最后一個(gè)結(jié)點(diǎn)為葉子節(jié)點(diǎn)，雖然它含有一個(gè)指向表頭結(jié)點(diǎn)的指針,但是表頭結(jié)點(diǎn)并不是它的一個(gè)后件。6.下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是a)樹(shù)b)向量c)二維表)矩陣a【解析】由定義可以知道，樹(shù)為一種簡(jiǎn)單的非線性結(jié)構(gòu)。在數(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。7某棵樹(shù)中共有2個(gè)結(jié)點(diǎn)，且只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn),其中葉子結(jié)點(diǎn)有個(gè)，則該樹(shù)中度為3的結(jié)點(diǎn)數(shù)為a）6b）7c)不存在這樣的樹(shù)d【解析】根據(jù)題意,樹(shù)中只有度為的結(jié)點(diǎn)和葉子結(jié)點(diǎn)（個(gè)),則度為的結(jié)點(diǎn)有-7=18個(gè);又根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和,設(shè)度為的結(jié)點(diǎn)數(shù)為n,則n+125，得n8

37、。兩種方式得到的度為的結(jié)點(diǎn)數(shù)不同，故不存在這樣的樹(shù)。58.某棵樹(shù)的度為,且度為4、3、2、1的結(jié)點(diǎn)個(gè)數(shù)分別為、2、,則該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為a)11b）c)0)8a【解析】設(shè)葉子結(jié)點(diǎn)數(shù)為n,根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，得1+32+2+140121,則n2-1-4=11。59.設(shè)一棵樹(shù)的度為3,共有27個(gè)結(jié)點(diǎn)，其中度為3，0的結(jié)點(diǎn)數(shù)分別為4,10。該樹(shù)中度為1的結(jié)點(diǎn)數(shù)為 ) 1） c) 1d）不可能有這樣的樹(shù)b【解析】設(shè)度為1的結(jié)點(diǎn)數(shù)為n，根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+，得4+211+01=2，則n=12。0.設(shè)一棵度為的樹(shù),其中度為2，的結(jié)點(diǎn)數(shù)分別為3，6。該樹(shù)中度為3

38、的結(jié)點(diǎn)數(shù)為a)2c)d)不可能有這樣的樹(shù)【解析】設(shè)樹(shù)的結(jié)點(diǎn)數(shù)為，則度為3的結(jié)點(diǎn)數(shù)為-3-1-6=-1,根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和,得3(n10）3+11+6+=，解得n=1,則度為的結(jié)點(diǎn)數(shù)為-1=11-10=1。6.設(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ù)【解析】設(shè)樹(shù)的結(jié)點(diǎn)數(shù)為m，度為3的結(jié)點(diǎn)數(shù)為，則度為1的結(jié)點(diǎn)數(shù)為m-n-5, 根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1，得3+1（m-5)+0+1=m，則n=2。62.度為的一棵樹(shù)共有30個(gè)結(jié)點(diǎn)，其中度為，1的結(jié)點(diǎn)個(gè)數(shù)分別為3,4。則該樹(shù)中的葉子結(jié)點(diǎn)

39、數(shù)為a） 14b） 1c) 16)不可能有這樣的樹(shù)b【解析】設(shè)葉子結(jié)點(diǎn)數(shù)為n,則度為2的結(jié)點(diǎn)數(shù)為30-3-4n23-n,根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和1,得3+2(3-n）+4+0n+1=30，則n=15。63.設(shè)某棵樹(shù)的度為3,其中度為2,1,0的結(jié)點(diǎn)個(gè)數(shù)分別為，4,1。則該樹(shù)中總結(jié)點(diǎn)數(shù)為a)不可能有這樣的樹(shù)b）3c)22d)5【解析】設(shè)樹(shù)的總結(jié)點(diǎn)數(shù)為,則度為3的結(jié)點(diǎn)數(shù)為n-3-1=n-2,根據(jù)樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+，得3（n22)+23+14+15+1=n，則n275,求出的結(jié)點(diǎn)數(shù)不為整數(shù),故不可能有這樣的樹(shù)存在。64.某二叉樹(shù)共有845個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)有45個(gè),

40、則度為1的結(jié)點(diǎn)數(shù)為 )400b)754）756)不確定c【解析】葉子結(jié)點(diǎn)有45個(gè)，根據(jù)在二叉樹(shù)中度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè),則度為的結(jié)點(diǎn)數(shù)為44個(gè),因此度為1的結(jié)點(diǎn)數(shù)為845-4544756個(gè)。65.某二叉樹(shù)中有15個(gè)度為1的結(jié)點(diǎn)，1個(gè)度為的結(jié)點(diǎn),則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為 a）32b）48d)49c【解析】根據(jù)在二叉樹(shù)中度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)，得度為0的結(jié)點(diǎn)數(shù)為61=1個(gè)，故總的結(jié)點(diǎn)數(shù)171516=4個(gè)。6.某二叉樹(shù)共有730個(gè)結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有0個(gè),則葉子結(jié)點(diǎn)個(gè)數(shù)為）b)351c)35d)不存在這樣的二叉樹(shù)d【解析】設(shè)葉子結(jié)點(diǎn)數(shù)為n，根據(jù)在二

41、叉樹(shù)中度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)多一個(gè),則度為2的結(jié)點(diǎn)數(shù)為n1,n+n-1+30=73，得n=30.5。由于結(jié)點(diǎn)數(shù)只能為整數(shù),所以不存在這樣的二叉樹(shù)。67.某二叉樹(shù)中共有30個(gè)結(jié)點(diǎn),其中200個(gè)為葉子結(jié)點(diǎn)，則該二叉樹(shù)中度為2的結(jié)點(diǎn)數(shù)為）不可能有這樣的二叉樹(shù)b)10c)19d）9a【解析】葉子結(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+20350,故不存在這樣的二叉樹(shù)。68某二叉樹(shù)的深度為7,其中有64個(gè)葉子結(jié)點(diǎn),則該二叉樹(shù)中度為的結(jié)點(diǎn)數(shù)為 a)0b)1)63a【解析】葉子結(jié)點(diǎn)有6個(gè)，根據(jù)在二叉樹(shù)中度為的結(jié)點(diǎn)（葉子

42、結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)，則度為2的結(jié)點(diǎn)數(shù)為63個(gè);又深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn),則該二叉樹(shù)最多有27-27個(gè)結(jié)點(diǎn)。4+63=7,因此該樹(shù)不存在度為的結(jié)點(diǎn)。69.深度為的二叉樹(shù)共有2個(gè)結(jié)點(diǎn),則下列說(shuō)法中錯(cuò)誤的是 a)該二叉樹(shù)是滿二叉樹(shù)b)該二叉樹(shù)有一個(gè)度為的結(jié)點(diǎn)c)該二叉樹(shù)是完全二叉樹(shù))該二叉樹(shù)有64個(gè)葉子結(jié)點(diǎn)b【解析】滿二叉樹(shù)滿足深度為的二叉樹(shù)最多有2m1個(gè)結(jié)點(diǎn)，本題中二叉樹(shù)深度為7且有17個(gè)結(jié)點(diǎn)，滿足7-1=17，達(dá)到最大值，故此二叉樹(shù)為滿二叉樹(shù)，也是完全二叉樹(shù)。滿二叉樹(shù)第k層上有2-結(jié)點(diǎn),則該二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為2-1=64個(gè)。滿二叉樹(shù)不存在度為1的結(jié)點(diǎn)。70.深度為5的完

43、全二叉樹(shù)的結(jié)點(diǎn)數(shù)不可能是 )15b)16)17d)18a【解析】設(shè)完全二叉樹(shù)的結(jié)點(diǎn)數(shù)為n,根據(jù)深度為的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)，再根據(jù)完全二叉樹(shù)的定義可知，k11n2k-1。本題中完全二叉樹(shù)的深度為5，則2-1-1n251，1531。因此,結(jié)點(diǎn)數(shù)不能為15。71.某完全二叉樹(shù)共有個(gè)結(jié)點(diǎn),則該完全二叉樹(shù)的深度為 a)b）8c）9d)0c【解析】根據(jù)完全二叉樹(shù)的性質(zhì)：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為lo2n+1。本題中完全二叉樹(shù)共有256個(gè)結(jié)點(diǎn),則深度為og256+1=81=9。72.深度為7的完全二叉樹(shù)中共有15個(gè)結(jié)點(diǎn),則該完全二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 ）62)63c)4d）6b【解析】在滿二叉

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

45、2的結(jié)點(diǎn)有個(gè)。再根據(jù)完全二叉樹(shù)的定義，度為1的結(jié)點(diǎn)有0個(gè)或個(gè),假設(shè)度1結(jié)點(diǎn)為0個(gè)，a+0-1=2n,得2=2n,由于結(jié)點(diǎn)個(gè)數(shù)必須為整數(shù)，假設(shè)不成立;當(dāng)度為1的結(jié)點(diǎn)為1個(gè)時(shí),a+1a-2,得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.下列敘述中正確的是)非完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)）有兩個(gè)指針域的鏈表就是二叉鏈表c)有的二叉樹(shù)也能用順序存儲(chǔ)結(jié)構(gòu)表示d)順序存儲(chǔ)結(jié)構(gòu)一定是線性結(jié)構(gòu)c【解析】在計(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)，因此項(xiàng)錯(cuò)誤。雙向鏈表也有兩個(gè)指針域,因此b項(xiàng)錯(cuò)誤。7.有二叉樹(shù)如下圖所示:則前序序列為a)abdegchb)dbgeafhcc)dgebfca)cdgh【解析】前序遍歷首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù);在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn),然后遍歷左子樹(shù),最后遍歷右子樹(shù)。故本題前序序列是abegcf。中序遍歷首先遍歷左子樹(shù),然后訪問(wèn)跟結(jié)點(diǎn)，最后遍歷右子樹(shù);在遍歷左、右子樹(shù)時(shí),仍然先遍歷左子樹(shù),然后訪問(wèn)跟結(jié)點(diǎn),最后遍歷右子樹(shù)。故本