..數(shù)據(jù)結(jié)構(gòu)與算法核心真題1.算法1.下列敘述中正確的是A>所謂算法就是計(jì)算方法B>程序可以作為算法的一種描述方法C>算法設(shè)計(jì)只需考慮得到計(jì)算結(jié)果D>算法設(shè)計(jì)可以忽略算法的運(yùn)算時間B[解析]算法是指對解題方案的準(zhǔn)確而完整的描述,算法不等于數(shù)學(xué)上的計(jì)算方法,也不等于程序。算法設(shè)計(jì)需要考慮可行性、確定性、有窮性與足夠的情報,不能只考慮計(jì)算結(jié)果。算法設(shè)計(jì)有窮性是指操作步驟有限且能在有限時間內(nèi)完成,如果一個算法執(zhí)行耗費(fèi)的時間太長,即使最終得出了正確結(jié)果,也是沒有意義的。算法在實(shí)現(xiàn)時需要用具體的程序設(shè)計(jì)語言描述,所以程序可以作為算法的一種描述方法。2.下列關(guān)于算法的描述中錯誤的是A>算法強(qiáng)調(diào)動態(tài)的執(zhí)行過程,不同于靜態(tài)的計(jì)算公式B>算法必須能在有限個步驟之后終止C>算法設(shè)計(jì)必須考慮算法的復(fù)雜度D>算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境D[解析]算法設(shè)計(jì)不僅要考慮計(jì)算結(jié)果的正確性,還要考慮算法的時間復(fù)雜度和空間復(fù)雜度。3.下列敘述中正確的是A>算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度B>算法的復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度C>算法的復(fù)雜度是指算法程序中指令的數(shù)量D>算法的復(fù)雜度是指算法所處理的數(shù)據(jù)量A[解析]算法復(fù)雜度是指算法在編寫成可執(zhí)行程序后,運(yùn)行時所需要的資源,資源包括時間資源和內(nèi)存資源。算法的復(fù)雜度包括時間復(fù)雜度與空間復(fù)雜度。算法的時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。4.下列敘述中正確的是A>算法的時間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)B>算法的時間復(fù)雜度與運(yùn)行算法時特定的輸入有關(guān)C>算法的時間復(fù)雜度與算法程序中的語句條數(shù)成正比D>算法的時間復(fù)雜度與算法程序編制者的水平有關(guān)B[解析]為了能夠比較客觀地反映出一個算法的效率,在度量一個算法的工作量時,不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān),而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此,可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)還與問題的規(guī)模有關(guān)；對應(yīng)一個固定的規(guī)模,算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)。5.下列敘述中正確的是A>解決同一個問題的不同算法的時間復(fù)雜度一般是不同的B>解決同一個問題的不同算法的時間復(fù)雜度必定是相同的C>對同一批數(shù)據(jù)作同一種處理,如果數(shù)據(jù)存儲結(jié)構(gòu)不同,不同算法的時間復(fù)雜度肯定相同D>對同一批數(shù)據(jù)作不同的處理,如果數(shù)據(jù)存儲結(jié)構(gòu)相同,不同算法的時間復(fù)雜度肯定相同A[解析]解決同一個問題的不同算法的時間復(fù)雜度,可能相同也可能不相同。算法的時間復(fù)雜度與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān),對同一批數(shù)據(jù)作同一種處理或者不同處理,數(shù)據(jù)存儲結(jié)構(gòu)相同或者不同,算法的時間復(fù)雜度都可能相同或者不同。6.下列敘述中正確的是A>算法的空間復(fù)雜度是指算法程序中指令的條數(shù)B>壓縮數(shù)據(jù)存儲空間不會降低算法的空間復(fù)雜度C>算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲空間有關(guān)D>算法的空間復(fù)雜度是指算法程序控制結(jié)構(gòu)的復(fù)雜程度C[解析]算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。算法執(zhí)行期間所需的存儲空間包括3個部分：輸入數(shù)據(jù)所占的存儲空間；程序本身所占的存儲空間；算法執(zhí)行過程中所需要的額外空間。7.為了降低算法的空間復(fù)雜度,要求算法盡量采用原地工作<inplace>。所謂原地工作是指A>執(zhí)行算法時不使用額外空間B>執(zhí)行算法時不使用任何存儲空間C>執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D>執(zhí)行算法時所使用的額外空間固定〔即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化D[解析]對于算法的空間復(fù)雜度,如果額外空間量相對于問題規(guī)模〔即輸入數(shù)據(jù)所占的存儲空間來說是常數(shù),即額外空間量不隨問題規(guī)模的變化而變化,則稱該算法是原地工作的。8.下列敘述中正確的是A>算法的復(fù)雜度與問題的規(guī)模無關(guān)B>算法的優(yōu)化主要通過程序的編制技巧來實(shí)現(xiàn)C>對數(shù)據(jù)進(jìn)行壓縮存儲會降低算法的空間復(fù)雜度D>數(shù)值型算法只需考慮計(jì)算結(jié)果的可靠性C[解析]在許多實(shí)際問題中,為了減少算法所占的存儲空間,通產(chǎn)采用壓縮存儲技術(shù),以便盡量減少不必要的額外空間。2.數(shù)據(jù)結(jié)構(gòu)的基本概念9.下列敘述中正確的是A>數(shù)據(jù)的存儲結(jié)構(gòu)會影響算法的效率B>算法設(shè)計(jì)只需考慮結(jié)果的可靠性C>算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度D>算法復(fù)雜度是用算法中指令的條數(shù)來度量的A[解析]采用不同的存儲結(jié)構(gòu),其數(shù)據(jù)處理的效率是不同的。因此,在進(jìn)行數(shù)據(jù)處理時,選擇合適的存儲結(jié)構(gòu)很重要。10.下列敘述中錯誤的是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é)點(diǎn)B[解析]數(shù)據(jù)元素是一個含義很廣泛的概念,它是數(shù)據(jù)的"基本單位",在計(jì)算機(jī)中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)元素可以是一個數(shù)據(jù)也可以是被抽象出的具有一定結(jié)構(gòu)數(shù)據(jù)集合,所以數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu)。滿足有且只有一個根結(jié)點(diǎn)并且每一個結(jié)點(diǎn)最多有一個前件,也最多有一個后件的非空的數(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)。非空數(shù)據(jù)結(jié)構(gòu)可以沒有根結(jié)點(diǎn),如非性線結(jié)構(gòu)"圖"就沒有根結(jié)點(diǎn)。11.下列敘述中正確的是A>非線性結(jié)構(gòu)可以為空B>只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)的必定是線性結(jié)構(gòu)C>只有一個根結(jié)點(diǎn)的必定是線性結(jié)構(gòu)或二叉樹D>沒有根結(jié)點(diǎn)的一定是非線性結(jié)構(gòu)A[解析]如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：①有且只有一個根結(jié)點(diǎn)；②每一個結(jié)點(diǎn)最多有一個前件,也最多有一個后件。則稱該數(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é)點(diǎn),但不論有幾個葉子結(jié)點(diǎn),樹都是非線性結(jié)構(gòu)。12.下列敘述中錯誤的是A>向量是線性結(jié)構(gòu)B>非空線性結(jié)構(gòu)中只有一個結(jié)點(diǎn)沒有前件C>非空線性結(jié)構(gòu)中只有一個結(jié)點(diǎn)沒有后件D>具有兩個以上指針域的鏈?zhǔn)浇Y(jié)構(gòu)一定屬于非線性結(jié)構(gòu)D[解析]雙向鏈表每個結(jié)點(diǎn)有兩個指針,一個為左指針,用于指向其前件結(jié)點(diǎn)；一個為右指針,用于指向其后件結(jié)點(diǎn),再加上頭指針,具有兩個以上的指針,但雙向鏈表屬于線性結(jié)構(gòu)。非空線性結(jié)構(gòu)中第一個結(jié)點(diǎn)沒有前件,最后一個結(jié)點(diǎn)無后件,其余結(jié)點(diǎn)最多有一個前件,也最多有一個后件。向量也滿足這個條件,屬于線性結(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)鏈表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é)點(diǎn)為f,元素順序?yàn)閒→a→c→e→d→b,滿足線性結(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>,<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)?→5→4→3→1,屬于線性結(jié)構(gòu)；同理B項(xiàng)1為根結(jié)點(diǎn),元素順序?yàn)?→2→3→4→5,D項(xiàng)5為跟結(jié)點(diǎn),元素順序?yàn)?→4→3→2→1,均為線性結(jié)構(gòu)。C項(xiàng)中,元素3有兩個前件,屬于非線性結(jié)構(gòu)。3．線性表及其順序存儲結(jié)構(gòu)15.下列敘述中正確的是A>矩陣是非線性結(jié)構(gòu)B>數(shù)組是長度固定的線性表C>對線性表只能作插入與刪除運(yùn)算D>線性表中各元素的數(shù)據(jù)類型可以不同B[解析]矩陣也是線性表,只不過是比較復(fù)雜的線性表。線性表中各元素的數(shù)據(jù)類型必須相同。在線性表中,不僅可以做插入與刪除運(yùn)算,還可以進(jìn)行查找或?qū)€性表進(jìn)行排序等操作。16.在線性表的順序存儲結(jié)構(gòu)中,其存儲空間連續(xù),各個元素所占的字節(jié)數(shù)A不同,但元素的存儲順序與邏輯順序一致B>不同,且其元素的存儲順序可以與邏輯順序不一致C>相同,元素的存儲順序與邏輯順序一致D>相同,但其元素的存儲順序可以與邏輯順序不一致C[解析]在線性表的順序存儲結(jié)構(gòu)中,其存儲空間連續(xù),各個元素所占的字節(jié)數(shù)相同,在存儲空間中是按邏輯順序依次存放的。17.下列敘述中正確的是A>能采用順序存儲的必定是線性結(jié)構(gòu)B>所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)C>具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)D>循環(huán)隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)B[解析]所有的線性結(jié)構(gòu)都可以用數(shù)組保存,即都可以采用順序存儲結(jié)構(gòu)。而反過來不可以,完全二叉樹也能用數(shù)組保存〔按層次依次存放到數(shù)據(jù)元素中,但完全二叉樹不屬于非線性結(jié)構(gòu)。雙向鏈表具有兩個以上的指針,但屬于線性結(jié)構(gòu)。循環(huán)隊(duì)列是隊(duì)列的順序存儲結(jié)構(gòu)。4.棧和隊(duì)列18.下列敘述中正確的是A>在棧中,棧頂指針的動態(tài)變化決定棧中元素的個數(shù)B>在循環(huán)隊(duì)列中,隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度C>在循環(huán)鏈表中,頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度D>在線性鏈表中,頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度A[解析]在棧中,通常用指針top來指示棧頂?shù)奈恢?用指針bottom指向棧底。棧頂指針top動態(tài)反應(yīng)了棧中元素的變化情況。在循環(huán)隊(duì)列中,隊(duì)頭指針和隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度。鏈?zhǔn)酱鎯Y(jié)構(gòu)中,各數(shù)據(jù)結(jié)點(diǎn)的存儲序號是不連續(xù)的,并且各結(jié)點(diǎn)在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致,故頭指針和尾指針或棧頂指針無法決定鏈表長度。19.設(shè)棧的順序存儲空間為S<1:m>,初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后,top=m+1,則棧中的元素個數(shù)為A>0B>mC>不可能D>m+1C[解析]棧為空時,棧頂指針top=0,經(jīng)過入棧和退棧運(yùn)算,指針始終指向棧頂元素。初始狀態(tài)為top=0,當(dāng)棧滿時top=m,無法繼續(xù)入棧,top值不可能為m+1。20.設(shè)棧的存儲空間為S<1:50>,初始狀態(tài)為top=-1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后,top=30,則棧中的元素個數(shù)為A>20B>19C>31D>30D[解析]棧的初始狀態(tài)為top=-1表示棧為空〔沒有規(guī)定棧中棧底必須是0,經(jīng)過一系列正常的入棧與退棧操作后top=30,則空間〔1:30中插入了元素,共30個。21.設(shè)棧的順序存儲空間為S<1:m>,初始狀態(tài)為top=m+1,則棧中的數(shù)據(jù)元素個數(shù)為A>top-m+1B>m-top+1C>m-topD>top-mB[解析]棧的初始狀態(tài)top=m+1,說明?？諘rtop=m+1〔m在棧底,1是開口向上的,入棧時棧頂指針是減操作〔top=top-1,退棧時棧頂指針是加操作〔top=top+1。本題可以假設(shè)棧中有x個元素,當(dāng)x=0時,也就是棧中沒有元素,則top=m+1；當(dāng)x=m時,也就是棧滿,則top=1,由此可以得出top=m+1-x,繼而得出x=m-top+1。22.設(shè)棧的順序存儲空間為S<1:m>,初始狀態(tài)為top=m+1。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后,top=0,則棧中的元素個數(shù)為A>1B>mC>m+1D>不可能D[解析]棧的初始狀態(tài)為top=m+1,說明棧空時top=m+1,入棧時棧頂指針是減操作〔top=top-1,退棧時棧頂指針是加操作〔top=top+1。棧滿時top=1,說明棧中不能再進(jìn)行入棧操作,top=0的情況不會出現(xiàn)。23.設(shè)棧的存儲空間為S<1:m>,初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后,top=1?，F(xiàn)又要將一個元素進(jìn)棧,棧頂指針top值變?yōu)锳>0B>發(fā)生棧滿的錯誤C>mD>2B[解析]棧的初始狀態(tài)為top=m+1,說明?？諘rtop=m+1,入棧時棧頂指針是減操作〔top=top-1,退棧時棧頂指針是加操作〔top=top+1。棧滿時top=1,說明棧中不能再進(jìn)行入棧操作〔"上溢"錯誤。24.設(shè)棧的存儲空間為S<1:m>,初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后,top=m。現(xiàn)又在棧中退出一個元素后,棧頂指針top值為A>0B>m-1C>m+1D>產(chǎn)生?？斟e誤C[解析]棧的順序存儲空間為S<1:m>,初始狀態(tài)top=m+1,所以這個棧是m在棧底,1是開口向上的。經(jīng)過一系列入棧與退棧操作后top=m,則棧中有1個元素,若現(xiàn)在又退出一個元素,那么棧頂指針下移一位,回到m+1的位置。25.設(shè)棧的存儲空間為S<1:50>,初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后,top=20,則棧中的元素個數(shù)為A>31B>30C>21D>20A[解析]棧的初始狀態(tài)top=51,故本棧是51在棧底,入棧時棧頂指針是減操作〔top=top-1,退棧時棧頂指針是加操作〔top=top+1。當(dāng)top=20時,元素存儲在<20:50>空間中,因此共有50-20+1=31個元素。26.下列處理中與隊(duì)列有關(guān)的是A>二叉樹的遍歷B>操作系統(tǒng)中的作業(yè)調(diào)度C>執(zhí)行程序中的過程調(diào)用D>執(zhí)行程序中的循環(huán)控制B[解析]隊(duì)列是指允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表。由于最先進(jìn)入隊(duì)列的元素將最先出隊(duì),所以隊(duì)列具有"先進(jìn)先出"的特性,體現(xiàn)了"先來先服務(wù)"的原則。操作系統(tǒng)中的作業(yè)調(diào)度是指根據(jù)一定信息,按照一定的算法,從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列的過程。執(zhí)行程序中的過程調(diào)用一般指函數(shù)調(diào)用,需要調(diào)用時候轉(zhuǎn)入被調(diào)用函數(shù)地址執(zhí)行程序,與隊(duì)列無關(guān)。執(zhí)行程序中的循環(huán)控制是指算法的基本控制結(jié)構(gòu),包括對循環(huán)條件的判定與執(zhí)行循環(huán)體,與隊(duì)列無關(guān)。二叉樹是一個有限的結(jié)點(diǎn)集合,二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn),與隊(duì)列無關(guān)。27.設(shè)有棧S和隊(duì)列Q,初始狀態(tài)均為空。首先依次將A,B,C,D,E,F入棧,然后從棧中退出三個元素依次入隊(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,退出三個元素入隊(duì),隊(duì)列元素為FED,將X,Y,Z入棧后棧中元素為ABCXYZ,退棧全部入隊(duì)后,隊(duì)列元素為FEDZYXCBA。28.下列敘述中正確的是A>循環(huán)隊(duì)列是順序存儲結(jié)構(gòu)B>循環(huán)隊(duì)列是鏈?zhǔn)酱鎯Y(jié)構(gòu)C>循環(huán)隊(duì)列空的條件是隊(duì)頭指針與隊(duì)尾指針相同D>循環(huán)隊(duì)列的插入運(yùn)算不會發(fā)生溢出現(xiàn)象A[解析]循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)。在循環(huán)隊(duì)列中,在隊(duì)列滿和隊(duì)列為空時,隊(duì)頭指針與隊(duì)尾指針均相同；當(dāng)需要插入的數(shù)據(jù)大于循環(huán)隊(duì)列的存儲長度,入隊(duì)運(yùn)算會覆蓋前面的數(shù)據(jù),發(fā)生溢出現(xiàn)象。29.下列敘述中正確的是A>在循環(huán)隊(duì)列中,隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度B>在循環(huán)隊(duì)列中,隊(duì)頭指針和隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度C>在帶鏈的隊(duì)列中,隊(duì)頭指針與隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度D>在帶鏈的棧中,棧頂指針的動態(tài)變化決定棧中元素的個數(shù)B[解析]在循環(huán)隊(duì)列中,隊(duì)頭指針和隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度。帶鏈的棧和帶鏈的隊(duì)列均采用鏈?zhǔn)酱鎯Y(jié)構(gòu),而在這種結(jié)構(gòu)中,各數(shù)據(jù)結(jié)點(diǎn)的存儲序號是不連續(xù)的,并且各結(jié)點(diǎn)在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致,故頭指針和尾指針或棧頂指針無法決定鏈表長度。30.循環(huán)隊(duì)列的存儲空間為Q<1:50>,初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=rear=25,此后又插入一個元素,則循環(huán)隊(duì)列中的元素個數(shù)為A>1,或50且產(chǎn)生上溢錯誤B>51C>26D>2A[解析]在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后,當(dāng)front=rear=25時可知隊(duì)列空或者隊(duì)列滿,此后又插入了一個元素,如果之前隊(duì)列為空,插入操作之后隊(duì)列里只有一個元素；如果插入之前隊(duì)列已滿<50個元素>,執(zhí)行插入則會產(chǎn)生溢出錯誤。31.循環(huán)隊(duì)列的存儲空間為Q<1:40>,初始狀態(tài)為front=rear=40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=rear=15,此后又退出一個元素,則循環(huán)隊(duì)列中的元素個數(shù)為A>14B>15C>40D>39,或0且產(chǎn)生下溢錯誤D[解析]在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后,當(dāng)front=rear=15時可知隊(duì)列空或者隊(duì)列滿,此后又退出一個元素,如果之前隊(duì)列為空,退出操作會產(chǎn)生錯誤,隊(duì)列里有0個元素；如果退出之前隊(duì)列已滿<40個元素>,執(zhí)行退出后,隊(duì)列里還有39個元素。32.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:50>,初始狀態(tài)為front=rear=50?，F(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)操作后,front=rear=1,此后又正常地插入了兩個元素。最后該隊(duì)列中的元素個數(shù)為A>3B>1C>2D>52C[解析]在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后,由front=rear=1可知隊(duì)列空或者隊(duì)列滿,此后又可以正常地插入了兩個元素說明插入前隊(duì)列為空,則插入后隊(duì)列元素個數(shù)為2。33.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:m>,初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=m,rear=m-1,此后從該循環(huán)隊(duì)列中刪除一個元素,則隊(duì)列中的元素個數(shù)為A>m-1B>m-2C>0D>1B[解析]在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后,如果rear-front>0,則隊(duì)列中的元素個數(shù)為rear-front個；如果rear-front<0,則隊(duì)列中的元素個數(shù)為rear-front+m。該題中m-1<m,即rear-front<0,則該循環(huán)隊(duì)列中的元素個數(shù)為〔m-1-m+m=m-1。此后從該循環(huán)隊(duì)列中刪除一個元素,則隊(duì)列中的元素個數(shù)為m-1-1=m-2。34.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:m>,初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=m-1,rear=m,此后再向該循環(huán)隊(duì)列中插入一個元素,則隊(duì)列中的元素個數(shù)為A>mB>m-1C>1D>2D[解析]該題中m-10,則該循環(huán)隊(duì)列中的元素個數(shù)為m-〔m-1=1。此后從該循環(huán)隊(duì)列中插入一個元素,則隊(duì)列中的元素個數(shù)為1+1=2。35.設(shè)循環(huán)隊(duì)列為Q<1:m>,其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(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,front>rear,則隊(duì)列中有10-30+m=m-20個元素,在作順序查找時,最壞情況下〔最后一個元素才是要找的元素或沒有要查找的元素比較次數(shù)為m-20次。36.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:m>,初始狀態(tài)為front=rear=m。經(jīng)過一系列正常的操作后,front=1,rear=m。為了在該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為A>0B>1C>m-2D>m-1C[解析]該題中10,則該循環(huán)隊(duì)列中的元素個數(shù)為m-1。此在該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為m-1-1=m-2。37.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:50>,初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后,front-1=rear。為了在該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為A>48B>49C>1D>0A[解析]該題中rear-front=front-1-front<0,則該循環(huán)隊(duì)列中的元素個數(shù)為rear-front+50=front-1-front+50=49。在該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為49-1=48。38.設(shè)循環(huán)隊(duì)列的存儲空間為Q<1:50>,初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后,front=rear-1。為了在該隊(duì)列中尋找值最大的元素,在最壞情況下需要的比較次數(shù)為A>1B>0C>49D>50B[解析]該題中rear-front=rear-〔rear-1>0,則該循環(huán)隊(duì)列中的元素個數(shù)為rear-front=rear-〔rear-1=1。因隊(duì)列中只有1個元素,故尋找值最大的元素不需要進(jìn)行比較,即比較次數(shù)為0。5.線性鏈表39.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比,鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)有A>節(jié)省存儲空間B>插入與刪除運(yùn)算效率高C>便于查找D>排序時減少元素的比較次數(shù)B[解析]線性表的順序存儲結(jié)構(gòu)稱為順序表,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈表,兩者的優(yōu)缺點(diǎn)如下表所示。40.下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯Φ氖茿>雙向鏈表B>循環(huán)隊(duì)列C>二叉鏈表D>二維數(shù)組A[解析]雙向鏈表也叫雙鏈表,是鏈表〔采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的一種,它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針,分別指向直接后繼和直接前驅(qū)。循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)。二叉鏈表和二維數(shù)組屬于非線性結(jié)構(gòu)。41.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中,其存儲空間一般是不連續(xù)的,并且A>前件結(jié)點(diǎn)的存儲序號小于后件結(jié)點(diǎn)的存儲序號B>前件結(jié)點(diǎn)的存儲序號大于后件結(jié)點(diǎn)的存儲序號C>前件結(jié)點(diǎn)的存儲序號可以小于也可以大于后件結(jié)點(diǎn)的存儲序號D>以上三種說法均不正確C[解析]在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中,各數(shù)據(jù)結(jié)點(diǎn)的存儲序號是不連續(xù)的,并且各結(jié)點(diǎn)在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致,因此前件結(jié)點(diǎn)的存儲序號與后件結(jié)點(diǎn)的存儲序號之間不存在大小關(guān)系。42.下列敘述中正確的是A>結(jié)點(diǎn)中具有兩個指針域的鏈表一定是二叉鏈表B>結(jié)點(diǎn)中具有兩個指針域的鏈表可以是線性結(jié)構(gòu),也可以是非線性結(jié)構(gòu)C>循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)D>循環(huán)鏈表是非線性結(jié)構(gòu)B[解析]結(jié)點(diǎn)中具有兩個指針域的鏈表既可以是雙向鏈表也可以是二叉鏈表,雙向鏈表是線性結(jié)構(gòu),二叉鏈表屬于非線性結(jié)構(gòu)。循環(huán)鏈表是線性鏈表的一種形式,屬于線性結(jié)構(gòu),采用鏈?zhǔn)酱鎯Y(jié)構(gòu),而循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)。43.帶鏈的棧與順序存儲的棧相比,其優(yōu)點(diǎn)是A>入棧與退棧操作方便B>可以省略棧底指針C>入棧操作時不會受棧存儲空間的限制而發(fā)生溢出D>所占存儲空間相同C[解析]帶鏈的棧就是用一個線性鏈表來表示的棧,線性鏈表不受存儲空間大小的限制,因此入棧操作時不會受棧存儲空間的限制而發(fā)生溢出〔不需考慮棧滿的問題。44.下列敘述中正確的是A>帶鏈棧的棧底指針是隨棧的操作而動態(tài)變化的B>若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同,則隊(duì)列為空C>若帶鏈隊(duì)列的隊(duì)頭指針與隊(duì)尾指針相同,則隊(duì)列中至少有一個元素D>不管是順序棧還是帶鏈的棧,在操作過程中其棧底指針均是固定不變的A[解析]由于帶鏈棧利用的是計(jì)算機(jī)存儲空間中的所有空閑存儲結(jié)點(diǎn),因此隨棧的操作棧頂棧底指針動態(tài)變化。帶鏈的隊(duì)列中若只有一個元素,則頭指針與尾指針相同。45.帶鏈?？盏臈l件是A>top=bottom=NULLB>top=-1且bottom=NULLC>top=NULL且bottom=-1D>top=bottom=-1A[解析]在帶鏈的棧中,只會出現(xiàn)棧空和非空兩種狀態(tài)。當(dāng)棧為空時,有top=bottom=NULL；當(dāng)棧非空時,top指向鏈表的第一個結(jié)點(diǎn)〔棧頂。46.在帶鏈棧中,經(jīng)過一系列正常的操作后,如果top=bottom,則棧中的元素個數(shù)為A>0或1B>0C>1D>棧滿A[解析]帶鏈棧就是沒有附加頭結(jié)點(diǎn)、運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底指針指向的存儲單元中存有一個元素,則當(dāng)top=bottom時,棧中的元素個數(shù)為1；如果棧底指針指向的存儲單元中沒有元素,則當(dāng)top=bottom時,棧中的元素個數(shù)為0。47.某帶鏈棧的初始狀態(tài)為top=bottom=NULL,經(jīng)過一系列正常的入棧與退棧操作后,top=bottom=20。該棧中的元素個數(shù)為A>0B>1C>20D>不確定B[解析]帶鏈的棧就是用一個單鏈表來表示的棧,棧中的每一個元素對應(yīng)鏈表中的一個結(jié)點(diǎn)。棧為空時,頭指針和尾指針都為NULL；棧中只有一個元素時,頭指針和尾指針都指向這個元素。48.某帶鏈棧的初始狀態(tài)為top=bottom=NULL,經(jīng)過一系列正常的入棧與退棧操作后,top=10,bottom=20。該棧中的元素個數(shù)為A>0B>1C>10D>不確定D[解析]帶鏈的棧使用了鏈表來表示棧,而鏈表中的元素存儲在不連續(xù)的地址中,因此當(dāng)top=10,bottom=20時,不能確定棧中元素的個數(shù)。49.帶鏈隊(duì)列空的條件是A>front=rear=NULLB>front=-1且rear=NULLC>front=NULL且rear=-1D>front=rear=-1A[解析]帶鏈的隊(duì)列就是用一個單鏈表來表示的隊(duì)列,隊(duì)列中的每一個元素對應(yīng)鏈表中的一個結(jié)點(diǎn)。隊(duì)列空時,頭指針和尾指針都為NULL。50.在帶鏈隊(duì)列中,經(jīng)過一系列正常的操作后,如果front=rear,則隊(duì)列中的元素個數(shù)為A>0B>1C>0或1D>隊(duì)列滿C[解析]帶鏈隊(duì)列空時,頭指針和尾指針都為NULL；隊(duì)列中只有一個元素時,頭指針和尾指針都指向這個元素。51.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=rear=10。該隊(duì)列中的元素個數(shù)為A>0B>1C>1或0D>不確定B[解析]帶鏈隊(duì)列空時,頭指針和尾指針都為null；隊(duì)列中只有一個元素時,頭指針和尾指針都指向這個元素。52.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后,front=10,rear=5。該隊(duì)列中的元素個數(shù)為A>4B>5C>6D>不確定D[解析]帶鏈的隊(duì)列使用了鏈表來表示隊(duì)列,而鏈表中的元素存儲在不連續(xù)的地址中,因此當(dāng)front=10,rear=5時,不能確定隊(duì)列中元素的個數(shù)。53.下列敘述中錯誤的是A>循環(huán)鏈表中有一個表頭結(jié)點(diǎn)B>循環(huán)鏈表是循環(huán)隊(duì)列的存儲結(jié)構(gòu)C>循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點(diǎn)的指針均指向表頭結(jié)點(diǎn)D>循環(huán)鏈表實(shí)現(xiàn)了空表與非空表運(yùn)算的統(tǒng)一B[解析]循環(huán)鏈表是指在單鏈表的第一個結(jié)點(diǎn)前增加一個表頭結(jié)點(diǎn),隊(duì)頭指針指向表頭結(jié)點(diǎn),最后一個結(jié)點(diǎn)的指針域的值由NULL改為指向表頭結(jié)點(diǎn)。循環(huán)鏈表是線性表的一種鏈?zhǔn)酱鎯Y(jié)構(gòu),循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)。54.從表中任何一個結(jié)點(diǎn)位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點(diǎn)的鏈表是A>循環(huán)鏈表B>雙向鏈表C>單向鏈表D>二叉鏈表A[解析]在循環(huán)鏈表中,所有結(jié)點(diǎn)的指針構(gòu)成了一個環(huán)狀鏈,只要指出表中任何一個結(jié)點(diǎn)的位置,就可以從它出發(fā)不重復(fù)地訪問到表中其他所有結(jié)點(diǎn)。55.非空循環(huán)鏈表所表示的數(shù)據(jù)結(jié)構(gòu)A>有根結(jié)點(diǎn)也有葉子結(jié)點(diǎn)B>沒有根結(jié)點(diǎn)但有葉子結(jié)點(diǎn)C>有根結(jié)點(diǎn)但沒有葉子結(jié)點(diǎn)D>沒有根結(jié)點(diǎn)也沒有葉子結(jié)點(diǎn)A[解析]循環(huán)鏈表表頭結(jié)點(diǎn)為根結(jié)點(diǎn),鏈表的最后一個結(jié)點(diǎn)為葉子節(jié)點(diǎn),雖然它含有一個指向表頭結(jié)點(diǎn)的指針,但是表頭結(jié)點(diǎn)并不是它的一個后件。6.樹與二叉樹56.下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A>樹B>向量C>二維表D>矩陣A[解析]由定義可以知道,樹為一種簡單的非線性結(jié)構(gòu)。在數(shù)這種數(shù)據(jù)結(jié)構(gòu)中,所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。57.某棵樹中共有25個結(jié)點(diǎn),且只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn),其中葉子結(jié)點(diǎn)有7個,則該樹中度為3的結(jié)點(diǎn)數(shù)為A>6B>7C>8D>不存在這樣的樹D[解析]根據(jù)題意,樹中只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn)〔7個,則度為3的結(jié)點(diǎn)有25-7=18個；又根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,設(shè)度為3的結(jié)點(diǎn)數(shù)為n,則3n+1=25,得n=8。兩種方式得到的度為3的結(jié)點(diǎn)數(shù)不同,故不存在這樣的樹。58.某棵樹的度為4,且度為4、3、2、1的結(jié)點(diǎn)個數(shù)分別為1、2、3、4,則該樹中的葉子結(jié)點(diǎn)數(shù)為A>11B>9C>10D>8A[解析]設(shè)葉子結(jié)點(diǎn)數(shù)為n,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得4×1+3×2+2×3+1×4+n×0+1=21,則n=21-1-2-3-4=11。59.設(shè)一棵樹的度為3,共有27個結(jié)點(diǎn),其中度為3,2,0的結(jié)點(diǎn)數(shù)分別為4,1,10。該樹中度為1的結(jié)點(diǎn)數(shù)為A>11B>12C>13D>不可能有這樣的樹B[解析]設(shè)度為1的結(jié)點(diǎn)數(shù)為n,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得3×4+2×1+1×n+0×10+1=27,則n=12。60.設(shè)一棵度為3的樹,其中度為2,1,0的結(jié)點(diǎn)數(shù)分別為3,1,6。該樹中度為3的結(jié)點(diǎn)數(shù)為A>1B>2C>3D>不可能有這樣的樹A[解析]設(shè)樹的結(jié)點(diǎn)數(shù)為n,則度為3的結(jié)點(diǎn)數(shù)為n-3-1-6=n-10,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得3×〔n-10+2×3+1×1+0×6+1=n,解得n=11,則度為3的結(jié)點(diǎn)數(shù)為n-10=11-10=1。61.設(shè)一棵樹的度為3,其中沒有度為2的結(jié)點(diǎn),且葉子結(jié)點(diǎn)數(shù)為5。該樹中度為3的結(jié)點(diǎn)數(shù)為A>3B>1C>2D>不可能有這樣的樹C[解析]設(shè)樹的結(jié)點(diǎn)數(shù)為m,度為3的結(jié)點(diǎn)數(shù)為n,則度為1的結(jié)點(diǎn)數(shù)為m-n-5,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得3×n+1×〔m-n-5+5×0+1=m,則n=2。62.度為3的一棵樹共有30個結(jié)點(diǎn),其中度為3,1的結(jié)點(diǎn)個數(shù)分別為3,4。則該樹中的葉子結(jié)點(diǎn)數(shù)為A>14B>15C>16D>不可能有這樣的樹B[解析]設(shè)葉子結(jié)點(diǎn)數(shù)為n,則度為2的結(jié)點(diǎn)數(shù)為30-3-4-n=23-n,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得3×3+2×〔23-n+1×4+0×n+1=30,則n=15。63.設(shè)某棵樹的度為3,其中度為2,1,0的結(jié)點(diǎn)個數(shù)分別為3,4,15。則該樹中總結(jié)點(diǎn)數(shù)為A>不可能有這樣的樹B>30C>22D>35A[解析]設(shè)樹的總結(jié)點(diǎn)數(shù)為n,則度為3的結(jié)點(diǎn)數(shù)為n-3-4-15=n-22,根據(jù)樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1,得3×〔n-22+2×3+1×4+0×15+1=n,則n=27.5,求出的結(jié)點(diǎn)數(shù)不為整數(shù),故不可能有這樣的樹存在。64.某二叉樹共有845個結(jié)點(diǎn),其中葉子結(jié)點(diǎn)有45個,則度為1的結(jié)點(diǎn)數(shù)為A>400B>754C>756D>不確定C[解析]葉子結(jié)點(diǎn)有45個,根據(jù)在二叉樹中度為0的結(jié)點(diǎn)〔葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,則度為2的結(jié)點(diǎn)數(shù)為44個,因此度為1的結(jié)點(diǎn)數(shù)為845-45-44=756個。65.某二叉樹中有15個度為1的結(jié)點(diǎn),16個度為2的結(jié)點(diǎn),則該二叉樹中總的結(jié)點(diǎn)數(shù)為A>32B>46C>48D>49C[解析]根據(jù)在二叉樹中度為0的結(jié)點(diǎn)〔葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,得度為0的結(jié)點(diǎn)數(shù)為16+1=17個,故總的結(jié)點(diǎn)數(shù)=17+15+16=48個。66.某二叉樹共有730個結(jié)點(diǎn),其中度為1的結(jié)點(diǎn)有30個,則葉子結(jié)點(diǎn)個數(shù)為A>1B>351C>350D>不存在這樣的二叉樹D[解析]設(shè)葉子結(jié)點(diǎn)數(shù)為n,根據(jù)在二叉樹中度為0的結(jié)點(diǎn)〔葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,則度為2的結(jié)點(diǎn)數(shù)為n-1,n+n-1+30=730,得n=350.5。由于結(jié)點(diǎn)數(shù)只能為整數(shù),所以不存在這樣的二叉樹。67.某二叉樹中共有350個結(jié)點(diǎn),其中200個為葉子結(jié)點(diǎn),則該二叉樹中度為2的結(jié)點(diǎn)數(shù)為A>不可能有這樣的二叉樹B>150C>199D>149A[解析]葉子結(jié)點(diǎn)數(shù)為200,根據(jù)在二叉樹中度為0的結(jié)點(diǎn)〔葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,則度為2的結(jié)點(diǎn)數(shù)為199,199+200>350,故不存在這樣的二叉樹。68.某二叉樹的深度為7,其中有64個葉子結(jié)點(diǎn),則該二叉樹中度為1的結(jié)點(diǎn)數(shù)為A>0B>1C>2D>63A[解析]葉子結(jié)點(diǎn)有64個,根據(jù)在二叉樹中度為0的結(jié)點(diǎn)〔葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,則度為2的結(jié)點(diǎn)數(shù)為63個；又深度為m的二叉樹最多有2m-1個結(jié)點(diǎn),則該二叉樹最多有27-1=127個結(jié)點(diǎn)。64+63=127,因此該樹不存在度為1的結(jié)點(diǎn)。69.深度為7的二叉樹共有127個結(jié)點(diǎn),則下列說法中錯誤的是A>該二叉樹是滿二叉樹B>該二叉樹有一個度為1的結(jié)點(diǎn)C>該二叉樹是完全二叉樹D>該二叉樹有64個葉子結(jié)點(diǎn)B[解析]滿二叉樹滿足深度為m的二叉樹最多有2m-1個結(jié)點(diǎn),本題中二叉樹深度為7且有127個結(jié)點(diǎn),滿足27-1=127,達(dá)到最大值,故此二叉樹為滿二叉樹,也是完全二叉樹。滿二叉樹第k層上有2k-1結(jié)點(diǎn),則該二叉樹的葉子結(jié)點(diǎn)數(shù)為27-1=64個。滿二叉樹不存在度為1的結(jié)點(diǎn)。70.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是A>15B>16C>17D>18A[解析]設(shè)完全二叉樹的結(jié)點(diǎn)數(shù)為n,根據(jù)深度為k的二叉樹至多有2k-1個結(jié)點(diǎn),再根據(jù)完全二叉樹的定義可知,2k-1-1<n≤2k-1。本題中完全二叉樹的深度為5,則25-1-1<n≤25-1,15<n≤31。因此,結(jié)點(diǎn)數(shù)不能為15。71.某完全二叉樹共有256個結(jié)點(diǎn),則該完全二叉樹的深度為A>7B>8C>9D>10C[解析]根據(jù)完全二叉樹的性質(zhì)：具有n個結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。本題中完全二叉樹共有256個結(jié)點(diǎn),則深度為[log2256]+1=8+1=9。72.深度為７的完全二叉樹中共有125個結(jié)點(diǎn),則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為A>62B>63C>64D>65B[解析]在滿二叉樹的第k層上有2k-1個結(jié)點(diǎn)、且深度為m的滿二叉樹有2m-1個結(jié)點(diǎn),則深度為6的滿二叉樹共有26-1=63個結(jié)點(diǎn),第6層上有26-1=32個結(jié)點(diǎn)。本題是深度為7的完全二叉樹,則前6層共有63個結(jié)點(diǎn),第7層的結(jié)點(diǎn)數(shù)為125-63=62個且全為葉子結(jié)點(diǎn)。由于第6層上有32個結(jié)點(diǎn),第7層上有62個結(jié)點(diǎn),則第6層上有1個結(jié)點(diǎn)無左右子樹〔該結(jié)點(diǎn)為葉子結(jié)點(diǎn)。因此,該完全二叉樹中共有葉子結(jié)點(diǎn)62+1=63個。73.在具有2n個結(jié)點(diǎn)的完全二叉樹中,葉子結(jié)點(diǎn)個數(shù)為A>nB>n+1C>n-1D>n/2A[解析]由二叉樹的定義可知,樹中必定存在度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn),設(shè)度為0結(jié)點(diǎn)有a個,根據(jù)度為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個,得度為2的結(jié)點(diǎn)有a-1個。再根據(jù)完全二叉樹的定義,度為1的結(jié)點(diǎn)有0個或1個,假設(shè)度1結(jié)點(diǎn)為0個,a+0+a-1=2n,得2a=2n-1,由于結(jié)點(diǎn)個數(shù)必須為整數(shù),假設(shè)不成立；當(dāng)度為1的結(jié)點(diǎn)為1個時,a+1+a-1=2n,得a=n,即葉子結(jié)點(diǎn)個數(shù)為n。74.下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是A>二叉鏈表B>循環(huán)隊(duì)列C>循環(huán)鏈表D>雙向鏈表A[解析]二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表,二叉樹是樹的一種,屬于非線性結(jié)構(gòu)。75.下列敘述中正確的是A>非完全二叉樹可以采用順序存儲結(jié)構(gòu)B>有兩個指針域的鏈表就是二叉鏈表C>有的二叉樹也能用順序存儲結(jié)構(gòu)表示D>順序存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C[解析]在計(jì)算機(jī)中,二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu),但對于滿二叉樹和完全二叉樹來說,可以按層進(jìn)行順序存儲。因此A項(xiàng)錯誤,C項(xiàng)正確。雖然滿二叉樹和完全二叉樹可以采用順序存儲結(jié)構(gòu),但仍是一種非線性結(jié)構(gòu),因此D項(xiàng)錯誤。雙向鏈表也有兩個指針域,因此B項(xiàng)錯誤。76.有二叉樹如下圖所示：則前序序列為A>ABDEGCFHB>DBGEAFHCC>DGEBHFCAD>ABCDEFGHA[解析]前序遍歷首先訪問根結(jié)點(diǎn),然后遍歷左子樹,最后遍歷右子樹；在遍歷左、右子樹時,仍然先訪問根結(jié)點(diǎn),然后遍歷左子樹,最后遍歷右子樹。故本題前序序列是ABDEGCFH。中序遍歷首先遍歷左子樹,然后訪問跟結(jié)點(diǎn),最后遍歷右子樹；在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪問跟結(jié)點(diǎn),最后遍歷右子樹。故本題的中序序列是DBGEAFHC。后序遍歷首先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點(diǎn)；在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點(diǎn)。故本題的后序序列是DGEBHFCA。77.設(shè)二叉樹的前序序列為ABDEGHCFIJ,中序序列為DBGEHACIFJ。則后序序列為A>JIHGFEDCBAB>DGHEBIJFCAC>GHIJDEFBCAD>ABCDEFGHIJB[解析]二叉樹的前序序列為ABDEGHCFIJ,由于前序遍歷首先訪問根結(jié)點(diǎn),可以確定該二叉樹的根結(jié)點(diǎn)是A。再由中序序列為DBGEHACIFJ,可以得到結(jié)點(diǎn)D、B、G、E、H位于根結(jié)點(diǎn)的左子樹上,結(jié)點(diǎn)C、I、F、J位于根結(jié)點(diǎn)的右子樹上。由于中序遍歷和后序遍歷都是先遍歷左子樹,故本題后序遍歷首先訪問D結(jié)點(diǎn)；再由后序遍歷是最后訪問根結(jié)點(diǎn),故本題后序遍歷最后訪問的結(jié)點(diǎn)是根結(jié)點(diǎn)A。采用排除法可知,后續(xù)序列為DGHEBIJFCA。78.某二叉樹的中序遍歷序列為CBADE,后序遍歷序列為CBEDA,則前序遍歷序列為A>CBADEB>CBEDAC>ABCDED>EDCBAC[解析]二叉樹的后序遍歷序列為CBEDA,由于后序遍歷最后訪問根結(jié)點(diǎn),可以確定該二叉樹的根結(jié)點(diǎn)是A。再由中序遍歷序列為CBADE,可以得到子序列〔CB一定在左子樹中,子序列〔DE一定在右子樹中。結(jié)點(diǎn)C、B在中序序列和后序序列中順序未變,說明結(jié)點(diǎn)B是結(jié)點(diǎn)C的父結(jié)點(diǎn)；結(jié)點(diǎn)D、E在中序序列和后序序列中順序相反,說明結(jié)點(diǎn)D是結(jié)點(diǎn)E的父結(jié)點(diǎn)。因此該二叉樹的前序遍歷序列為ABCDE。79.某二叉樹的前序序列為ABCDEFG,中序序列為DCBAEFG,則該二叉樹的深度〔根結(jié)點(diǎn)在第1層為A>2B>3C>4D>5C[解析]二叉樹的前序序列為ABCDEFG,則A為根結(jié)點(diǎn)；中序序列為DCBAEFG,可知結(jié)點(diǎn)D、C、B位于根結(jié)點(diǎn)的左子樹上,結(jié)點(diǎn)E、F、G位于根結(jié)點(diǎn)的右子樹上。另外,結(jié)點(diǎn)B、C、D在前序序列和中序序列中順序相反,則說明這三個結(jié)點(diǎn)依次位于前一個結(jié)點(diǎn)的左子樹上；結(jié)點(diǎn)E、F、G順序未變,則說明這三個結(jié)點(diǎn)依次位于前一個結(jié)點(diǎn)的右子樹上。故二叉樹深度為4。80.設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH,則該二叉樹的后序序列為A>ABCDHGFEB>DCBAHGFEC>EFGHABCDD>HGFEDCBAD[解析]二叉樹的前序序列與中序序列均為ABCDEFGH,可知二叉樹根結(jié)點(diǎn)為A,且根結(jié)點(diǎn)A只有右子樹,沒有左子樹。同理,可以推出結(jié)點(diǎn)B只有右子樹無左子樹。依此類推,該二叉樹除葉子結(jié)點(diǎn)外,每個結(jié)點(diǎn)只有右子樹無左子樹。因此該二叉樹的后序序列為HGFEDCBA。81.某二叉樹的后序遍歷序列與中序遍歷序列相同,均為ABCDEF,則按層次輸出〔同一層從左到右的序列為A>CBAFEDB>FEDCBAC>DEFCBAD>ABCDEFB[解析]該二叉樹的后序遍歷序列與中序遍歷序列均為ABCDEF,則根結(jié)點(diǎn)為F；根結(jié)點(diǎn)F只有左子樹,右子樹為空。即ABCDE是根結(jié)點(diǎn)F的左子樹集合。這樣問題就轉(zhuǎn)化為就后序遍歷序列與中序遍歷序列均為ABCDE的子樹,同理可得左子樹集合的根結(jié)點(diǎn)為E,且根結(jié)點(diǎn)E只有左子樹無右子樹。依次類推,該二叉樹除葉子結(jié)點(diǎn)外,每個結(jié)點(diǎn)只有左子樹無右子樹,結(jié)構(gòu)如下：按層次輸出〔同一層從左到右的序列為FEDCBA。82.某二叉樹的前序序列為ABDFHCEG,中序序列為HFDBACEG。該二叉樹按層次輸出〔同一層從左到右的序列為A>HGFEDCBAB>HFDBGECAC>ABCDEFGHD>ACEGBDFHC[解析]二叉樹的前序序列為ABDFHCEG,可以確定這個二叉樹的根結(jié)點(diǎn)是A；再由中序序列HFDBACEG,可以得到HFDB為根結(jié)點(diǎn)A的左子樹,CEG為根結(jié)點(diǎn)A的右子樹。同理依次對左子樹HFDB和右子樹CEG進(jìn)行同樣的推理,得到該二叉樹的結(jié)構(gòu)如下：該二叉樹按層次輸出〔同一層從左到右的序列為ABCDEFGH。83.某完全二叉樹按層次輸出〔同一層從左到右的序列為ABCDEFGH。該完全二叉樹的前序序列為A>ABCDEFGHB>ABDHECFGC>HDBEAFCGD>HDEBFGCAB[解析]完全二叉樹的特點(diǎn)是除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。根據(jù)這一特點(diǎn),再根據(jù)題意輸出序列為ABCDEFGH,可以得到該二叉樹的結(jié)構(gòu)如下：故此完全二叉樹的前序序列為ABDHECFG。84.設(shè)非空二叉樹的所有子樹中,其左子樹上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值,而右子樹上的結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值,則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是A>前序序列B>中序序列C>后序序列D>前序序列或后序序列B[解析]中序遍歷的次序是先遍歷左子樹,再遍歷根結(jié)點(diǎn),最后遍歷右子樹。而在排序二叉樹中,左子樹結(jié)點(diǎn)值<根結(jié)點(diǎn)值≤右子樹結(jié)點(diǎn)值,要使對排序二叉樹的遍歷結(jié)果為有序序列,只能采用中序遍歷。85.設(shè)二叉樹中共有15個結(jié)點(diǎn),其中的結(jié)點(diǎn)值互不相同。如果該二叉樹的前序序列與中序序列相同,則該二叉樹的深度為A>4B>6C>15D>不存在這樣的二叉樹C[解析]在具有n個結(jié)點(diǎn)的二叉樹中,如果各結(jié)點(diǎn)值互不相同,若該二叉樹的前序序列與中序序列相同,則說明該二叉樹只有右子樹,左子樹為空,二叉樹的深度為n；若該二叉樹的后序序列與中序序列相同,則說明該二叉樹只有左子樹,右子樹為空,二叉樹的深度為n。故本題中二叉樹的深度為15。7．查找技術(shù)86.在長度為n的順序表中查找一個元素,假設(shè)需要查找的元素一定在表中,并且元素出現(xiàn)在表中每個位置上的可能性是相同的,則在平均情況下需要比較的次數(shù)為A>n/4B>nC>3n/4D><n+1>/2D[解析]在順序表中查找,最好情況下第一個元素就是要查找的元素,則比較次數(shù)為1；在最壞情況下,最后一個元素才是要找的元素,則比較次數(shù)為n。則平均比較次數(shù)：〔1+2+┉+n/n=<n<n+1>/2>/n=<n+1>/2。87.在長度為n的順序表中查找一個元素,假設(shè)需要查找的元素有一半的機(jī)會在表中,并且如果元素在表中,則出現(xiàn)在表中每個位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為A>nB>3n/4C>n/2D>n/4B[解析]在順序表中查找,最好情況下第一個元素就是要查找的元素,則比較次數(shù)為1；在最壞情況下,最后一個元素才是要找的元素,則比較次數(shù)為n。這是找到元素的情況。如果沒有找到元素,則要比較n次。因此,平均需要比較：88.下列算法中均以比較作為基本運(yùn)算,則平均情況與最壞情況下的時間復(fù)雜度相同的是A>在順序存儲的線性表中尋找最大項(xiàng)B>在順序存儲的線性表中進(jìn)行順序查找C>在順序存儲的有序表中進(jìn)行對分查找D>在鏈?zhǔn)酱鎯Φ挠行虮碇羞M(jìn)行查找A[解析]尋找最大項(xiàng),無論如何都要查看所有的數(shù)據(jù),與數(shù)據(jù)原始排列順序沒有多大關(guān)系,無所謂最壞情況和最好情況,或者說平均情況與最壞情況下的時間復(fù)雜度是相同的。而查找無論是對分查找還是順序查找,都與要找的數(shù)據(jù)和原始的數(shù)據(jù)排列情況有關(guān),最好情況是第1次查看的一個數(shù)據(jù)恰好是要找的數(shù)據(jù),只需要比較1次；如果沒有找到再查看下一個數(shù)據(jù),直到找到為止,最壞情況下是最后一次查看的數(shù)據(jù)才是要找的,順序查找和對分查找在最壞情況下比較次數(shù)分別是n和log2n,平均情況則是1~最壞情況的平均,因而是不同的。89.線性表的長度為n。在最壞情況下,比較次數(shù)為n-1的算法是A>順序查找B>同時尋找最大項(xiàng)與最小項(xiàng)C>尋找最大項(xiàng)D>有序表的插入C[解析]順序查找要逐個查看所有元素,會比較n次。在最壞情況下,尋找最大項(xiàng)無論如何需要查看表中的所有元素,n個元素比較次數(shù)為n-1。同時尋找最大項(xiàng)和最小項(xiàng),需要為判斷較大值和較小值分別進(jìn)行比較,會有更多的比較次數(shù)。有序表的插入最壞情況下是插入到表中的最后一個元素的后面位置,則會比較n次。90.下列敘述中正確的是A>二分查找法只適用于順序存儲的有序線性表B>二分查找法適用于任何存儲結(jié)構(gòu)的有序線性表C>二分查找法適用于有序循環(huán)鏈表D>二分查找法適用于有序雙向鏈表A[解析]二分查找法〔又稱對分查找法只適用于順序存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列〔即從小到大,但允許相鄰元素值相等。91.設(shè)有序線性表的長度為n,則在有序線性表中進(jìn)行二分查找,最壞情況下的比較次數(shù)為A>n<n-1>/2B>nC>nlog2nD>log2nD[解析]有序線性表的長度為n,設(shè)被查找元素為x,則二分查找的方法如下：將x與線性表的中間項(xiàng)比較：若中間項(xiàng)的值等于x,則說明查到,查找結(jié)束；若x小于中間項(xiàng)的值,則在線性表的前半部分〔即中間項(xiàng)以前的部分以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值,則在線性表的后半部分〔即中間項(xiàng)以后的部分以相同的方法進(jìn)行查找。這個過程一直進(jìn)行到查找成功或子表長度為0〔說明線性表中沒有這個元素為止。對于長度為n的有序線性表,在最壞情況下,二分查找只需要比較log2n次。92.在長度為97的順序有序表中作二分查找,最多需要的比較次數(shù)為A>48B>96C>7D>6C[解析]對于長度為n的有序線性表,在最壞情況下,二分查找只需要比