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

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

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

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

4、復(fù)雜度一般是不同的b)解決同一個問題的不同算法的時間復(fù)雜度必定是相同的)對同一批數(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ù)據(jù)作同一種處理或者不同處理，數(shù)據(jù)存儲結(jié)構(gòu)相同或者不同，算法的時間復(fù)雜度都可能相同或者不同。6.下列敘述中正確的是）算法的空間復(fù)雜度是指算法程序中指令的條數(shù)b)壓縮數(shù)據(jù)存儲空間不會降低算法的空間復(fù)雜度)算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲空間有關(guān)d）算法的

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

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

7、理時，選擇合適的存儲結(jié)構(gòu)很重要。0.下列敘述中錯誤的是 ）數(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)可以沒有根結(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é)點最多有一個前件，也最多有一個后件的非空的數(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)可以沒有根結(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)【解析】如果一個非空的數(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)。.下列敘述中錯誤的是a)向量是線性結(jié)構(gòu)b)非空線性結(jié)構(gòu)中只有一個結(jié)點沒有前件c）非空線性

9、結(jié)構(gòu)中只有一個結(jié)點沒有后件)具有兩個以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)【解析】雙向鏈表每個結(jié)點有兩個指針，一個為左指針，用于指向其前件結(jié)點；一個為右指針，用于指向其后件結(jié)點，再加上頭指針,具有兩個以上的指針，但雙向鏈表屬于線性結(jié)構(gòu)。非空線性結(jié)構(gòu)中第一個結(jié)點沒有前件,最后一個結(jié)點無后件,其余結(jié)點最多有一個前件，也最多有一個后件。向量也滿足這個條件，屬于線性結(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)隊列）循環(huán)鏈表d)非線性結(jié)構(gòu)a【解析】數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素:一是數(shù)據(jù)元素的集合

10、，通常記為d;二是d上的關(guān)系,它反映了中各數(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,）表示a是b的前件,b是a的后件。本題中中的根結(jié)點為,元素順序為faed,滿足線性結(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【解析】項中,r=(2,5），(5,4),(3,),(4,3),2為根結(jié)點，元素順序為25431,屬于線性結(jié)構(gòu);同理b項為根結(jié)點,元素順序為245，d項5為跟結(jié)點,元素順序為54321，均為線性結(jié)構(gòu)。c項中，元素3有兩個前件，屬于非線性結(jié)構(gòu)。5下列敘述中正確的是a)矩陣是非線性結(jié)構(gòu)b）數(shù)組是長度固定的線性表c)對線性表只能作插入與刪除運算d）線性表中各元素的數(shù)據(jù)類型可以不同【解析】矩陣也是線性表,只不過是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類型必須相同。在線性表中,不僅可以做插入與刪除運算，還可以進行查找或?qū)€性表進行排序等操作。16在線性表的順序存儲結(jié)構(gòu)中,其存儲空間連續(xù)，

12、各個元素所占的字節(jié)數(shù) a不同，但元素的存儲順序與邏輯順序一致)不同,且其元素的存儲順序可以與邏輯順序不一致)相同，元素的存儲順序與邏輯順序一致d)相同，但其元素的存儲順序可以與邏輯順序不一致【解析】在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù),各個元素所占的字節(jié)數(shù)相同，在存儲空間中是按邏輯順序依次存放的。17下列敘述中正確的是 a)能采用順序存儲的必定是線性結(jié)構(gòu)b)所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)c)具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu))循環(huán)隊列是隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)b【解析】所有的線性結(jié)構(gòu)都可以用數(shù)組保存，即都可以采用順序存儲結(jié)構(gòu)。而反過來不可以,完全二叉樹也能用數(shù)組保存（按層次依次存放到數(shù)

13、據(jù)元素中）,但完全二叉樹不屬于非線性結(jié)構(gòu)。雙向鏈表具有兩個以上的指針,但屬于線性結(jié)構(gòu)。循環(huán)隊列是隊列的順序存儲結(jié)構(gòu)。1下列敘述中正確的是a)在棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)b)在循環(huán)隊列中,隊尾指針的動態(tài)變化決定隊列的長度c)在循環(huán)鏈表中,頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度d)在線性鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度a【解析】在棧中,通常用指針op來指示棧頂?shù)奈恢?用指針botto指向棧底。棧頂指針op動態(tài)反應(yīng)了棧中元素的變化情況。在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度。鏈?zhǔn)酱鎯Y(jié)構(gòu)中,各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的,并且各結(jié)點在存儲空間中的位

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

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

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

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

18、的初始狀態(tài)t51，故本棧是1在棧底，入棧時棧頂指針是減操作(top=tp-),退棧時棧頂指針是加操作(tp=tp+1）。當(dāng)op0時,元素存儲在(0:5)空間中，因此共有520+1=31個元素。26.下列處理中與隊列有關(guān)的是 a）二叉樹的遍歷b）操作系統(tǒng)中的作業(yè)調(diào)度c)執(zhí)行程序中的過程調(diào)用）執(zhí)行程序中的循環(huán)控制b【解析】隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。由于最先進入隊列的元素將最先出隊,所以隊列具有“先進先出”的特性,體現(xiàn)了“先來先服務(wù)”的原則。操作系統(tǒng)中的作業(yè)調(diào)度是指根據(jù)一定信息，按照一定的算法,從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進程插入就緒隊列的

19、過程。執(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é)點集合,二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點,與隊列無關(guān)。27設(shè)有棧s和隊列q,初始狀態(tài)均為空。首先依次將a,b,c,e,f入棧,然后從棧中退出三個元素依次入隊，再將x,y,z入棧后,將棧中所有元素退出并依次入隊,最后將隊列中所有元素退出,則退隊元素的順序為a）dfxyzabcb)fedyxcbac)fxycba)dfzybcb【解析】棧是一種特殊的線性表，它所有的插入與刪除都限定在

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

21、的是a)在循環(huán)隊列中,隊尾指針的動態(tài)變化決定隊列的長度）在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度c）在帶鏈的隊列中,隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度d)在帶鏈的棧中,棧頂指針的動態(tài)變化決定棧中元素的個數(shù)【解析】在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度。帶鏈的棧和帶鏈的隊列均采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，而在這種結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的,并且各結(jié)點在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。30.循環(huán)隊列的存儲空間為 （:50)，初始狀態(tài)為 nt=rear=50。經(jīng)過一系列正常的入隊與退隊操作后，font=ra

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

23、產(chǎn)生溢出錯誤。31循環(huán)隊列的存儲空間為 q(1:40),初始狀態(tài)為 font=ear=0。經(jīng)過一系列正常的入隊與退隊操作后,fron=rar15,此后又退出一個元素，則循環(huán)隊列中的元素個數(shù)為a) b）15c)0d)39,或0且產(chǎn)生下溢錯誤d【解析】當(dāng)front=ear=1時可知隊列空或者隊列滿,此后又退出一個元素，如果之前隊列為空,退出操作會產(chǎn)生錯誤,隊列里有0個元素；如果退出之前隊列已滿(40個元素),執(zhí)行退出后，隊列里還有39個元素。32.設(shè)循環(huán)隊列的存儲空間為(1:0)，初始狀態(tài)為on=ea=50?，F(xiàn)經(jīng)過一系列入隊與退隊操作后，frot=re=1,此后又正常地插入了兩個元素。最后該隊列中

24、的元素個數(shù)為a)b)c)2d)5c【解析】由fronrear=1可知隊列空或者隊列滿,此后又可以正常地插入了兩個元素說明插入前隊列為空,則插入后隊列元素個數(shù)為2。33.設(shè)循環(huán)隊列的存儲空間為q(1：m），初始狀態(tài)為空。現(xiàn)經(jīng)過一系列正常的入隊與退隊操作后，frontm,rea=m-,此后從該循環(huán)隊列中刪除一個元素,則隊列中的元素個數(shù)為a)-1b）-2c)0d)1b【解析】從排頭指針fnt指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。如果rea-fo,則隊列中的元素個數(shù)為rar-fon個；如果rea-ront0,則隊列中的元素個數(shù)為e-rntm。該題中m-m,即re

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

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

27、較次數(shù)為0。9.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比,鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點有 a)節(jié)省存儲空間b)插入與刪除運算效率高c)便于查找)排序時減少元素的比較次數(shù)【解析】線性表的順序存儲結(jié)構(gòu)稱為順序表,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈表,兩者的優(yōu)缺點如下表所示。類型優(yōu)點 缺點順序表(1)可以隨機存取表中的任意結(jié)點（2）無需為表示結(jié)點間的邏輯關(guān)系額外增加存儲空間（1)插入和刪除運算效率低(2）存儲空間不便于擴充（3）不便于對存儲空間的動態(tài)分配鏈表(1)在進行插入和刪除運算時,只需要改變指針即可，不需要移動元素()存儲空間易于擴充并且方便空間的動態(tài)分配需要額外的空間（指針域)來表示數(shù)據(jù)元素之間的邏輯關(guān)系,存儲

28、密度比順序表低40.下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯Φ氖莂)雙向鏈表b)循環(huán)隊列c)二叉鏈表d）二維數(shù)組a【解析】雙向鏈表也叫雙鏈表,是鏈表(采用鏈?zhǔn)酱鎯Y(jié)構(gòu)）的一種,它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。二叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。41在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，其存儲空間一般是不連續(xù)的,并且 a）前件結(jié)點的存儲序號小于后件結(jié)點的存儲序號b)前件結(jié)點的存儲序號大于后件結(jié)點的存儲序號c)前件結(jié)點的存儲序號可以小于也可以大于后件結(jié)點的存儲序號d）以上三種說法均不正確【解析】在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，并且各結(jié)

29、點在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致,因此前件結(jié)點的存儲序號與后件結(jié)點的存儲序號之間不存在大小關(guān)系。2.下列敘述中正確的是 a）結(jié)點中具有兩個指針域的鏈表一定是二叉鏈表）結(jié)點中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)）循環(huán)鏈表是循環(huán)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu))循環(huán)鏈表是非線性結(jié)構(gòu)b【解析】結(jié)點中具有兩個指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表,雙向鏈表是線性結(jié)構(gòu),二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式,屬于線性結(jié)構(gòu),采用鏈?zhǔn)酱鎯Y(jié)構(gòu),而循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu)。.帶鏈的棧與順序存儲的棧相比，其優(yōu)點是 a)入棧與退棧操作方便)可以省略棧底指針c)入棧操作時不

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45、2的結(jié)點有個。再根據(jù)完全二叉樹的定義，度為1的結(jié)點有0個或個,假設(shè)度1結(jié)點為0個，a+0-1=2n,得2=2n,由于結(jié)點個數(shù)必須為整數(shù)，假設(shè)不成立;當(dāng)度為1的結(jié)點為1個時,a+1a-2,得a=n,即葉子結(jié)點個數(shù)為n。74下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是 a)二叉鏈表b)循環(huán)隊列c）循環(huán)鏈表d)雙向鏈表a【解析】二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表,二叉樹是樹的一種，屬于非線性結(jié)構(gòu)。75.下列敘述中正確的是)非完全二叉樹可以采用順序存儲結(jié)構(gòu)）有兩個指針域的鏈表就是二叉鏈表c)有的二叉樹也能用順序存儲結(jié)構(gòu)表示d)順序存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)c【解析】在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu),但對于滿二叉樹和完全二叉樹來說，可以按層進行順序存儲。因此a項錯誤，c項正確。雖然滿二叉樹和完全二叉樹可以采用順序存儲結(jié)構(gòu)，但仍是一種非線性結(jié)構(gòu)，因此項錯誤。雙向鏈表也有兩個指針域,因此b項錯誤。7.有二叉樹如下圖所示:則前序序列為a)abdegchb)dbgeafhcc)dgebfca)cdgh【解析】前序遍歷首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹;在遍歷左、右子樹時，仍然先訪問根結(jié)點,然后遍歷左子樹,最后遍歷右子樹。故本題前序序列是abegcf。中序遍歷首先遍歷左子樹,然后訪問跟結(jié)點，最后遍歷右子樹;在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問跟結(jié)點,最后遍歷右子樹。故本