計算機二級公共試題

..數(shù)據(jù)結構與算法核心真題1.算法1.下列敘述中正確的是A>所謂算法就是計算方法B>程序可以作為算法的一種描述方法C>算法設計只需考慮得到計算結果D>算法設計可以忽略算法的運算時間B[解析]算法是指對解題方案的準確而完整的描述,算法不等于數(shù)學上的計算方法,也不等于程序。算法設計需要考慮可行性、確定性、有窮性與足夠的情報,不能只考慮計算結果。算法設計有窮性是指操作步驟有限且能在有限時間內完成,如果一個算法執(zhí)行耗費的時間太長,即使最終得出了正確結果,也是沒有意義的。算法在實現(xiàn)時需要用具體的程序設計語言描述,所以程序可以作為算法的一種描述方法。2.下列關于算法的描述中錯誤的是A>算法強調動態(tài)的執(zhí)行過程,不同于靜態(tài)的計算公式B>算法必須能在有限個步驟之后終止C>算法設計必須考慮算法的復雜度D>算法的優(yōu)劣取決于運行算法程序的環(huán)境D[解析]算法設計不僅要考慮計算結果的正確性,還要考慮算法的時間復雜度和空間復雜度。3.下列敘述中正確的是A>算法的復雜度包括時間復雜度與空間復雜度B>算法的復雜度是指算法控制結構的復雜程度C>算法的復雜度是指算法程序中指令的數(shù)量D>算法的復雜度是指算法所處理的數(shù)據(jù)量A[解析]算法復雜度是指算法在編寫成可執(zhí)行程序后,運行時所需要的資源,資源包括時間資源和內存資源。算法的復雜度包括時間復雜度與空間復雜度。算法的時間復雜度是指執(zhí)行算法所需要的計算工作量；算法的空間復雜度是指算法在執(zhí)行過程中所需要的內存空間。4.下列敘述中正確的是A>算法的時間復雜度與計算機的運行速度有關B>算法的時間復雜度與運行算法時特定的輸入有關C>算法的時間復雜度與算法程序中的語句條數(shù)成正比D>算法的時間復雜度與算法程序編制者的水平有關B[解析]為了能夠比較客觀地反映出一個算法的效率,在度量一個算法的工作量時,不僅應該與所使用的計算機、程序設計語言以及程序編制者無關,而且還應該與算法實現(xiàn)過程中的許多細節(jié)無關。為此,可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運算次數(shù)還與問題的規(guī)模有關；對應一個固定的規(guī)模,算法所執(zhí)行的基本運算次數(shù)還可能與特定的輸入有關。5.下列敘述中正確的是A>解決同一個問題的不同算法的時間復雜度一般是不同的B>解決同一個問題的不同算法的時間復雜度必定是相同的C>對同一批數(shù)據(jù)作同一種處理,如果數(shù)據(jù)存儲結構不同,不同算法的時間復雜度肯定相同D>對同一批數(shù)據(jù)作不同的處理,如果數(shù)據(jù)存儲結構相同,不同算法的時間復雜度肯定相同A[解析]解決同一個問題的不同算法的時間復雜度,可能相同也可能不相同。算法的時間復雜度與數(shù)據(jù)存儲結構無關,對同一批數(shù)據(jù)作同一種處理或者不同處理,數(shù)據(jù)存儲結構相同或者不同,算法的時間復雜度都可能相同或者不同。6.下列敘述中正確的是A>算法的空間復雜度是指算法程序中指令的條數(shù)B>壓縮數(shù)據(jù)存儲空間不會降低算法的空間復雜度C>算法的空間復雜度與算法所處理的數(shù)據(jù)存儲空間有關D>算法的空間復雜度是指算法程序控制結構的復雜程度C[解析]算法的空間復雜度是指算法在執(zhí)行過程中所需要的內存空間。算法執(zhí)行期間所需的存儲空間包括3個部分：輸入數(shù)據(jù)所占的存儲空間；程序本身所占的存儲空間；算法執(zhí)行過程中所需要的額外空間。7.為了降低算法的空間復雜度,要求算法盡量采用原地工作<inplace>。所謂原地工作是指A>執(zhí)行算法時不使用額外空間B>執(zhí)行算法時不使用任何存儲空間C>執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D>執(zhí)行算法時所使用的額外空間固定〔即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化D[解析]對于算法的空間復雜度,如果額外空間量相對于問題規(guī)?！布摧斎霐?shù)據(jù)所占的存儲空間來說是常數(shù),即額外空間量不隨問題規(guī)模的變化而變化,則稱該算法是原地工作的。8.下列敘述中正確的是A>算法的復雜度與問題的規(guī)模無關B>算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)C>對數(shù)據(jù)進行壓縮存儲會降低算法的空間復雜度D>數(shù)值型算法只需考慮計算結果的可靠性C[解析]在許多實際問題中,為了減少算法所占的存儲空間,通產采用壓縮存儲技術,以便盡量減少不必要的額外空間。2.數(shù)據(jù)結構的基本概念9.下列敘述中正確的是A>數(shù)據(jù)的存儲結構會影響算法的效率B>算法設計只需考慮結果的可靠性C>算法復雜度是指算法控制結構的復雜程度D>算法復雜度是用算法中指令的條數(shù)來度量的A[解析]采用不同的存儲結構,其數(shù)據(jù)處理的效率是不同的。因此,在進行數(shù)據(jù)處理時,選擇合適的存儲結構很重要。10.下列敘述中錯誤的是A>數(shù)據(jù)結構中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結構B>數(shù)據(jù)結構中的數(shù)據(jù)元素不能是另一數(shù)據(jù)結構C>空數(shù)據(jù)結構可以是線性結構也可以是非線性結構D>非空數(shù)據(jù)結構可以沒有根結點B[解析]數(shù)據(jù)元素是一個含義很廣泛的概念,它是數(shù)據(jù)的"基本單位",在計算機中通常作為一個整體進行考慮和處理。數(shù)據(jù)元素可以是一個數(shù)據(jù)也可以是被抽象出的具有一定結構數(shù)據(jù)集合,所以數(shù)據(jù)結構中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結構。滿足有且只有一個根結點并且每一個結點最多有一個前件,也最多有一個后件的非空的數(shù)據(jù)結構認為是線性結構,不滿足條件的結構為非線性結構?？諗?shù)據(jù)結構可以是線性結構也可以是非線性結構。非空數(shù)據(jù)結構可以沒有根結點,如非性線結構"圖"就沒有根結點。11.下列敘述中正確的是A>非線性結構可以為空B>只有一個根結點和一個葉子結點的必定是線性結構C>只有一個根結點的必定是線性結構或二叉樹D>沒有根結點的一定是非線性結構A[解析]如果一個非空的數(shù)據(jù)結構滿足下列兩個條件：①有且只有一個根結點；②每一個結點最多有一個前件,也最多有一個后件。則稱該數(shù)據(jù)結構為線性結構。如果一個數(shù)據(jù)結構不是線性結構,則稱之為非線性結構。線性結構和非線性結構都可以是空的數(shù)據(jù)結構。樹只有一個根結點,但不論有幾個葉子結點,樹都是非線性結構。12.下列敘述中錯誤的是A>向量是線性結構B>非空線性結構中只有一個結點沒有前件C>非空線性結構中只有一個結點沒有后件D>具有兩個以上指針域的鏈式結構一定屬于非線性結構D[解析]雙向鏈表每個結點有兩個指針,一個為左指針,用于指向其前件結點；一個為右指針,用于指向其后件結點,再加上頭指針,具有兩個以上的指針,但雙向鏈表屬于線性結構。非空線性結構中第一個結點沒有前件,最后一個結點無后件,其余結點最多有一個前件,也最多有一個后件。向量也滿足這個條件,屬于線性結構。13.設數(shù)據(jù)結構B=<D,R>,其中

D={a,b,c,d,e,f}

R={<f,a>,<d,b>,<e,d>,<c,e>,<a,c>}

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