[單選題]1.下列敘述中正確的是（

）。A.程序可以作為算法的一種描述方法B.算法設(shè)計可以忽略算法的運(yùn)算時間C.所謂算法就是計算方法D.算法設(shè)計只需考慮得到計算結(jié)果答案：A解析：解析：算法可以用程序、偽代碼、流程圖來描述，故A選項(xiàng)正確。算法要求執(zhí)行過程中所需要的基本運(yùn)算次數(shù)和時間最少，即時間復(fù)雜度最低，故B選項(xiàng)錯誤。算法是一組有窮指令集，是解題方案的準(zhǔn)確而完整的描述，故C選項(xiàng)錯誤。算法設(shè)計時要考慮算法的復(fù)雜度，問題規(guī)模越大越是如此，故D選項(xiàng)錯誤。2.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是（

）。A.17B.16C.15D.18答案：C解析：解析：根據(jù)二叉樹的性質(zhì)，除最后一層，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，所以前4層共有25-1-1=15個結(jié)點(diǎn)，而第5層至少有一個葉子結(jié)點(diǎn)，所以總結(jié)點(diǎn)數(shù)至少16，不可能是15，故本題答案為C。3.有二叉樹如下圖所示：?則前序序列為（

）。A.A、ABDEGCFHB.B、DBGEAFHCC.C、DGEBHFCAD.D、ABCDEFGH答案：A解析：解析：前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹；在遍歷左、右子樹時，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，故本題答案為A。4.下列敘述中正確的是（

）。A.循環(huán)隊(duì)列是鏈?zhǔn)酱鎯Y(jié)構(gòu)B.循環(huán)隊(duì)列是順序存儲結(jié)構(gòu)C.循環(huán)隊(duì)列的插入運(yùn)算不會發(fā)生溢出現(xiàn)象D.循環(huán)隊(duì)列是非線性結(jié)構(gòu)答案：B解析：解析：在順序隊(duì)列中,由于數(shù)組空間不夠而產(chǎn)生的溢出叫真溢出；順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲空間但不能進(jìn)行入隊(duì)列操作的溢出稱為假溢出；假溢出是由于隊(duì)尾rear的值和隊(duì)頭front的值不能由所定義數(shù)組下界值自動轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的，解決的辦法是把順序隊(duì)列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊(duì)列，故A選項(xiàng)錯誤，B選項(xiàng)正確。循環(huán)隊(duì)列雖然能解決由于假溢出，卻不能解決在順序隊(duì)列中,由于數(shù)組空間不夠而產(chǎn)生的溢出的真溢出，故選項(xiàng)C錯誤。循環(huán)隊(duì)列屬于隊(duì)列的特例，和棧同屬于線性結(jié)構(gòu)，D選項(xiàng)錯誤。5.下列敘述中正確的是（

）。A.沒有根結(jié)點(diǎn)或沒有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)B.所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）C.所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點(diǎn)D.只有一個根結(jié)點(diǎn)，且只有一個葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)答案：A解析：解析：只有一個空節(jié)點(diǎn)的結(jié)構(gòu)也屬數(shù)據(jù)結(jié)構(gòu)，所以B、C選項(xiàng)錯誤；有且只有一個根結(jié)點(diǎn)，每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件的數(shù)據(jù)結(jié)構(gòu)才屬于線性結(jié)構(gòu)，故D選項(xiàng)錯誤。故本題答案為A。6.下列關(guān)于算法的描述中錯誤的是（

）。A.算法強(qiáng)調(diào)動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式B.算法必須能在有限個步驟之后終止C.算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境D.算法設(shè)計必須考慮算法的復(fù)雜度答案：C解析：解析：算法的優(yōu)劣取決自身的運(yùn)行效率，時間和空間復(fù)雜度高低，并不取決于運(yùn)行算法程序的環(huán)境，故本題答案為C。7.設(shè)有二叉樹如下圖所示：?則中序序列為（

）。A.A、DGEBHFCAB.B、ABCDEFGHC.C、DBGEAFHCD.D、ABDEGCFH答案：C解析：解析：中序遍歷首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹，故本題答案為C。8.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)有（

）。A.節(jié)省存儲空間B.排序時減少元素的比較次數(shù)C.便于查找D.插入與刪除運(yùn)算效率高答案：D解析：解析：順序存儲時，所有元素所占的存儲空間是連續(xù)的（邏輯與物理統(tǒng)一），優(yōu)點(diǎn)是存儲空間利用率高，缺點(diǎn)是插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)的指針，這樣的優(yōu)點(diǎn)是插入或刪除元素時效率高，缺點(diǎn)是需要額外的空間（指針域）來表示數(shù)據(jù)之間的邏輯關(guān)系，存儲空間利用率低。故本題答案為D。9.深度為7的完全二叉樹中共有125個結(jié)點(diǎn)，則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.65B.64C.62D.63答案：D解析：解析：深度為6的滿二叉樹，結(jié)點(diǎn)個數(shù)為26-1=63，則第7層共有125-63=62個葉子結(jié)點(diǎn)，分別掛在第6層的左邊62個結(jié)點(diǎn)上，加上第6層的最后1個葉子結(jié)點(diǎn)，共有63個葉子結(jié)點(diǎn)，故本題答案為D。10.下列敘述中正確的是（

）。A.所謂有序表是指在順序存儲空間內(nèi)連續(xù)存放的元素序列B.任何存儲方式的有序表均能采用二分法進(jìn)行查找C.有序表可以用鏈接存儲方式存儲在不連續(xù)的存儲空間內(nèi)D.有序表只能順序存儲在連續(xù)的存儲空間內(nèi)答案：C解析：解析：有序是指元素按遞增/遞減順序排列，與空間無關(guān)，A選項(xiàng)錯誤。能使用二分法查找的線性表必須滿足是有序的順序存儲結(jié)構(gòu)，B選項(xiàng)錯誤。有序表可以順序存儲也可以鏈?zhǔn)酱鎯Γ珼選項(xiàng)錯誤。故本題答案為C。11.設(shè)有二叉樹如下圖所示：?則后序序列為（

）。A.A、DGEBHFCAB.B、ABCDEFGHC.C、ABDEGCFHD.D、DBGEAFHC答案：A解析：解析：后序遍歷首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)，故本題答案為A。12.下列敘述中正確的是（

）。A.二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)B.循環(huán)鏈表是非線性結(jié)構(gòu)C.結(jié)點(diǎn)中具有兩個指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)D.結(jié)點(diǎn)中具有兩個指針域的鏈表一定是二叉鏈表答案：C解析：解析：二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也可采用順序存儲結(jié)構(gòu)，故A選項(xiàng)錯誤；循環(huán)鏈表是線性結(jié)構(gòu)，故B選項(xiàng)錯誤；雙向鏈表是線性結(jié)構(gòu)，二叉樹為非線性結(jié)構(gòu)，二者結(jié)點(diǎn)中均有兩個指針域，C選項(xiàng)正確；具有兩個指針域的鏈表可能是雙向鏈表，D選項(xiàng)錯誤13.設(shè)某二叉樹中共有140個結(jié)點(diǎn)，其中有40個度為1的結(jié)點(diǎn)。則（

）。A.該二叉樹中有50個度為2的結(jié)點(diǎn)B.該二叉樹中有51個葉子結(jié)點(diǎn)C.該二叉樹中有50個葉子結(jié)點(diǎn)D.不可能有這樣的二叉樹答案：D解析：解析：在二叉樹中，只存在度為0、1、2的結(jié)點(diǎn)，度為1的結(jié)點(diǎn)為40，所以度為0和度為2的結(jié)點(diǎn)總數(shù)為100，而根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個，所以不可能出現(xiàn)兩者相加為100的情況，故不存在這樣的二叉樹。14.帶鏈的棧與順序存儲的棧相比，其優(yōu)點(diǎn)是（

）。A.入棧與退棧操作方便B.可以省略棧底指針C.入棧操作時不會受棧存儲空間的限制而發(fā)生溢出D.以上說法均不正確答案：C解析：解析：帶鏈的棧與順序存儲的棧相比優(yōu)點(diǎn)是不受連續(xù)存儲空間大小的限制，即不需考慮棧滿的問題，故本題答案為C。15.某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為（

）。A.A、CDABB.B、BADCC.C、ABCDD.D、DCBA答案：D解析：解析：根據(jù)前序序列為ABCD，可知A為根結(jié)點(diǎn)；再由中序序列為DCBA可知DCB是A的左子樹。根據(jù)前序序列可知B是CD的根結(jié)點(diǎn)。再根據(jù)中序序列可知DC是結(jié)點(diǎn)B的左子樹。根據(jù)前序序列可知，C是D的根結(jié)點(diǎn)，故后序序列為DCBA，D選項(xiàng)正確。16.下列關(guān)于算法復(fù)雜度敘述正確的是（

）。A.最壞情況下的時間復(fù)雜度一定高于平均情況的時間復(fù)雜度B.對同一個問題，采用不同的算法，則它們的時間復(fù)雜度是相同的C.時間復(fù)雜度與采用的算法描述語言有關(guān)D.時間復(fù)雜度與所用的計算工具無關(guān)答案：D解析：解析：算法程序執(zhí)行的具體時間受到所使用的計算機(jī)、程序設(shè)計語言以及算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)所影響，但算法的時間復(fù)雜度與這些因素?zé)o關(guān)，故D選項(xiàng)正確，C選項(xiàng)錯誤；最壞情況下的時間復(fù)雜度可以與平均情況的時間復(fù)雜度相同(比如冒泡排序)，A選項(xiàng)錯誤；不同的算法時間復(fù)雜度一般不相同，B選項(xiàng)錯誤。17.設(shè)有棧S和隊(duì)列Q，初始狀態(tài)均為空。首先依次將A,B,C,D,E,F入棧，然后從棧中退出三個元素依次入隊(duì)，再將X,Y,Z入棧后，將棧中所有元素退出并依次入隊(duì)，最后將隊(duì)列中所有元素退出，則退隊(duì)元素的順序?yàn)椋?/p>

）。A.A、FEDZYXCBAB.B、DEFZYXABCC.C、FEDXYZCBAD.D、DEFXYZABC答案：A解析：解析：棧稱為“后進(jìn)先出”表或“先進(jìn)后出”的線性表；隊(duì)列稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表。A,B,C,D,E,F依次入棧，然后前三個元素出棧順序?yàn)镕,E,D，后續(xù)X,Y,Z入棧后重新全部出棧，順序?yàn)閆,Y,X,D,C,B,A，按照出棧順序入隊(duì)，隊(duì)列順序?yàn)镕,E,D,Z,Y,X,D,C,B,A，因?yàn)殛?duì)列是先進(jìn)先出的，退隊(duì)順序和入隊(duì)順序相同，所有退隊(duì)元素的順序?yàn)镕EDZYXCBA。故本題答案為A。18.下列敘述中正確的是（

）。A.帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表B.結(jié)點(diǎn)中具有多個指針域的鏈表稱為多重鏈表C.有兩個指針域的鏈表稱為二叉鏈表D.循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)答案：B解析：解析：雙重鏈表的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)，而棧中雖然存在棧頂指針和棧底指針，但每個棧元素只有一個指針域，故A選項(xiàng)錯誤；結(jié)點(diǎn)中具有多個指針域的鏈表就稱為多重鏈表，B選項(xiàng)正確；雙向鏈表中的結(jié)點(diǎn)也有兩個指針域，但它并不屬于二叉鏈表，故C選項(xiàng)錯誤；循環(huán)鏈表屬于存儲結(jié)構(gòu)的概念，循環(huán)隊(duì)列是屬于邏輯結(jié)構(gòu)的概念，循環(huán)隊(duì)列既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?，兩者沒有必然關(guān)聯(lián)。故D選項(xiàng)不正確。19.某二叉樹共有845個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有45個，則度為1的結(jié)點(diǎn)數(shù)為（

）。A.400B.754C.756D.不確定答案：C解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，即度為2的結(jié)點(diǎn)有44個，所以度為1的結(jié)點(diǎn)個數(shù)為845-45-44=756個。20.設(shè)數(shù)據(jù)元素的集合D={1，3，5，7，9}，D上的關(guān)系為R，下列數(shù)據(jù)結(jié)構(gòu)B=（D，R）中為非線性結(jié)構(gòu)的是（

）。A.R={(5,1),(7,9),(1,7),(9,3)}B.R={(1,3),(3,5),(5,9)}C.R={(9,7),(1,3),(7,1),(3,5)}D.R={(1,9),(9,7),(7,5),(5,3)}答案：B解析：解析：線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)只有一個前件也只有一個后件。A選項(xiàng)的結(jié)構(gòu)可以寫成5→1→7→9→3，B選項(xiàng)是1→3→5→9，元素7沒有前件和后件，C選項(xiàng)是9→7→1→3→5，D選項(xiàng)是1→9→7→5→3.三者都是線性結(jié)構(gòu)，故本題答案為B。21.深度為7的二叉樹共有127個結(jié)點(diǎn)，則下列說法中錯誤的是（

）。A.該二叉樹有64個葉子結(jié)點(diǎn)B.該二叉樹是完全二叉樹C.該二叉樹是滿二叉樹D.該二叉樹有一個度為1的結(jié)點(diǎn)答案：D解析：解析：根據(jù)二叉樹的性質(zhì)，深度為m的二叉樹最多有2m-1個結(jié)點(diǎn)，由題意可知，該二叉樹的結(jié)點(diǎn)數(shù)27-1=127已達(dá)到最大值，所以該樹是滿二叉樹，滿二叉樹沒有度為1的結(jié)點(diǎn)，有64個葉子結(jié)點(diǎn)，故本題答案為D。22.下列敘述中正確的是（

）。A.非線性結(jié)構(gòu)只能用多重鏈表表示B.有的非線性結(jié)構(gòu)也能采用順序存儲結(jié)構(gòu)C.所有數(shù)據(jù)結(jié)構(gòu)既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D.非線性結(jié)構(gòu)只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)答案：B解析：解析：鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)，非線性結(jié)構(gòu)也可以用連續(xù)存儲空間順序存儲。所以A、D選項(xiàng)錯誤，在所有的數(shù)據(jù)結(jié)構(gòu)中并非所有的結(jié)構(gòu)都能用順序存儲結(jié)構(gòu)和采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示，所以C選項(xiàng)也錯誤，故本題答案為B。23.某二叉樹的中序序列為BDCA，后序序列為DCBA，則前序序列為（

）。A.A、BADCB.B、ABCDC.C、BDCAD.D、DCBA答案：B解析：解析：從二叉樹后序遍歷為DCBA中可知A是根節(jié)點(diǎn)，在前序遍歷中根結(jié)點(diǎn)位于首位，故本題答案為B。24.設(shè)有序線性表的長度為n，則在有序線性表中進(jìn)行二分查找，最壞情況下的比較次數(shù)為（

）。A.n(n-1)/2B.nlog2nC.C、nD.log2n答案：D解析：解析：對于長度為n的有序線性表，最壞情況需要比較log2n次，故本題答案為D。25.某完全二叉樹有256個結(jié)點(diǎn)，則該二叉樹的深度為（

）。A.7B.8C.10D.9答案：D解析：解析：根據(jù)深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)，二叉樹的第i層至多有2i-1個結(jié)點(diǎn)；因?yàn)榍鞍藢拥慕Y(jié)點(diǎn)就有28-1=255個，所以第九層的結(jié)點(diǎn)數(shù)是256-255=1個，故本題答案為D。26.設(shè)序列長度為n，在最壞情況下比較次數(shù)低于O(n2)的排序方法是（

）。A.直接插入排序B.希爾排序C.冒泡排序D.快速排序答案：B解析：解析：最壞情況下，冒泡排序、快速排序、直接插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)。27.某二叉樹的前序序列為ABCD，中序序列為BDCA，則該二叉樹的深度為（

）。A.3B.2C.4D.不確定答案：C解析：解析：先由前序遍歷可知A是根結(jié)點(diǎn)，再由中序遍歷可知BDC是左子樹，沒有右子樹；對于子樹BDC，由前序序列可知B是子樹的根節(jié)點(diǎn)，所以DC是B的右子樹。據(jù)此畫出二叉樹圖形后，可知該二叉樹的深度為4，故本題答案為C。28.設(shè)循環(huán)隊(duì)列為Q(1:m)，初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)一系列入隊(duì)與退隊(duì)操作后，front=rear=m-1，則（

）。A.該循環(huán)隊(duì)列已滿B.該循環(huán)隊(duì)列已空C.該循環(huán)隊(duì)列中有1個元素D.該循環(huán)隊(duì)列已空或已滿答案：D解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，循環(huán)隊(duì)列為空或滿，故本題答案為D。29.設(shè)序列長度為n，在最壞情況下，時間復(fù)雜度為O(log2n)的算法是（

）。A.二分法查找B.哈希查找C.分塊查找D.順序查找答案：A解析：解析：二分法查找只適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次，而順序查找需要比較n次。故本題答案為A。30.某二叉樹的深度為7，其中有64個葉子結(jié)點(diǎn)，則該二叉樹中度為1的結(jié)點(diǎn)數(shù)為（

）。A.1B.0C.2D.63答案：B解析：解析：根據(jù)二叉樹的性質(zhì)，該樹的第7層的節(jié)點(diǎn)數(shù)是27-1=64，已達(dá)到最大值，所以除了葉子結(jié)點(diǎn)，每個結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)，即每個結(jié)點(diǎn)都是度為2的，所以不存在度為1的結(jié)點(diǎn)，故本題答案為B。31.堆排序最壞情況下的時間復(fù)雜度為（

）。A.O(n1.5)B.O(log2n)C.O(nlog2n)D.O(n(n-1)/2)答案：C解析：解析：堆排序的平均和最壞情況時間復(fù)雜度都為O(nlog2n)，故本題答案為C。32.在線性表的鏈?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.以上說法均不正確答案：B解析：解析：鏈?zhǔn)酱鎯Y(jié)構(gòu)使得節(jié)點(diǎn)在內(nèi)存中不受位置的限制，結(jié)點(diǎn)存儲號可以是任意的，故本題答案為B。33.設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}，則滿足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是（

）。A.R={(1,3),(4,1),(3,2),(5,4)}B.R={(1,2),(2,4),(4,5),(2,3)}C.R={(1,2),(3,2),(5,1),(4,5)}D.R={(1,3),(2,4),(3,5),(1,2)}答案：A解析：解析：線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)只有一個前件也只有一個后件。B選項(xiàng)2的后面有4、3兩個數(shù)值，C選項(xiàng)2的前面有1、3兩個數(shù)值，D選項(xiàng)1的后面有3、2兩個數(shù)值，所以B、C、D選項(xiàng)是非線性結(jié)構(gòu)，故本題答案為A。34.某二叉樹中有15個度為1的結(jié)點(diǎn)，16個度為2的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（

）。A.32B.46C.48D.49答案：C解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，所以度為0的一共有17個，總的結(jié)點(diǎn)數(shù)即17+15+16=48個。35.下列敘述中正確的是（

）。A.每一個結(jié)點(diǎn)有兩個指針域的鏈表一定是非線性結(jié)構(gòu)B.循環(huán)鏈表是循環(huán)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)C.所有結(jié)點(diǎn)的指針域都為非空的鏈表一定是非線性結(jié)構(gòu)D.線性結(jié)構(gòu)的存儲結(jié)點(diǎn)也可以有多個指針答案：D解析：解析：當(dāng)結(jié)點(diǎn)中兩個指針分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)是為線性結(jié)構(gòu)，當(dāng)指向兩個不同的前驅(qū)或后繼結(jié)點(diǎn)時為非線性結(jié)構(gòu)，指針域?yàn)榉强盏逆湵硪部梢允蔷€性結(jié)構(gòu)，鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。故A、B、C選項(xiàng)不完全正確。線性結(jié)構(gòu)的存儲結(jié)點(diǎn)可以由多個指針只有保證有且只有指向一個前驅(qū)結(jié)點(diǎn)和一個后繼結(jié)點(diǎn)就是線性結(jié)構(gòu)。故本題答案為D。36.在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)（

）。A.相同，元素的存儲順序與邏輯順序一致B.不同，但元素的存儲順序與邏輯順序一致C.不同，且其元素的存儲順序可以與邏輯順序不一致D.相同，但其元素的存儲順序可以與邏輯順序不一致答案：A解析：解析：線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)：(1)線性表中所有元素所占的存儲空間是連續(xù)的;(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。另在線性表中數(shù)據(jù)元素所占的字節(jié)數(shù)都是一致的，故本題答案為A。37.設(shè)循環(huán)隊(duì)列為Q(1:m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=30，rear=10?，F(xiàn)要在該循環(huán)隊(duì)列中作順序查找，最壞情況下需要比較的次數(shù)為（

）。A.m-19B.19C.m-20D.20答案：C解析：解析：循環(huán)隊(duì)列為Q(1:m)，其初始狀態(tài)為front=rear=m，則節(jié)點(diǎn)個數(shù)為m-(front-rear),且順序查找的比較次數(shù)與實(shí)際節(jié)點(diǎn)個數(shù)一致，故本題答案為C。38.某二叉樹中共有935個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有435個，則該二叉樹中度為2的結(jié)點(diǎn)個數(shù)為（

）。A.434B.64C.436D.66答案：A解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，故本題答案為A。39.非空循環(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)答案：B解析：解析：循環(huán)鏈表的第一個結(jié)點(diǎn)就是根結(jié)點(diǎn)，最后一個結(jié)點(diǎn)就是葉子結(jié)點(diǎn)，故本題答案為B。40.某棵樹只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，其中度為3的結(jié)點(diǎn)有8個，則該樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.15B.17C.不存在這樣的樹D.16答案：B解析：解析：在樹結(jié)構(gòu)中，樹中的結(jié)點(diǎn)數(shù)即為樹中所有結(jié)點(diǎn)的度數(shù)之和再加1。本題中該樹總度數(shù)為3×8=24，所以結(jié)點(diǎn)總數(shù)為25個，則該樹中葉子結(jié)點(diǎn)個數(shù)為25-8=17，故本題答案為B。41.某循環(huán)隊(duì)列的存儲空間為Q(1:m)，初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)過一系列的入隊(duì)操作和退隊(duì)操作后，front=m，rear=m-1，則該循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.1B.B、mC.m-1D.0答案：C解析：解析：由于存儲空間可以存儲m個結(jié)點(diǎn)，而頭指針指向m，所以第一個結(jié)點(diǎn)就在第1個位置上，而最后一個結(jié)點(diǎn)在m-1的位置上，所以該循環(huán)隊(duì)列共有m-1個結(jié)點(diǎn)。42.在排序過程中，每一次數(shù)據(jù)元素的移動會產(chǎn)生新的逆序的排序方法是（

）。A.快速排序B.冒泡排序C.簡單插入排序D.以上說法均不正確答案：A解析：解析：在數(shù)據(jù)元素的序列中，對于某個元素，如果其后存在一個元素小于它，則稱之為存在一個逆序。冒泡排序只交換相鄰元素，不是每次移動都產(chǎn)生新的逆序。簡單插入排序每一次比較后最多移掉一個逆序?？焖倥判蚴沁x出一個結(jié)點(diǎn)，然后將大于該結(jié)點(diǎn)的數(shù)據(jù)移到后面，將小于該結(jié)點(diǎn)的數(shù)據(jù)移到前面，所以會產(chǎn)生一個新的逆序，當(dāng)不會有新的逆序產(chǎn)生時，本輪比較結(jié)束。43.某循環(huán)隊(duì)列的存儲空間為Q(1:m)，初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)過一系列的入隊(duì)操作和退隊(duì)操作后，front=m-1，rear=m，則該循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.A、mB.1C.m-1D.0答案：B解析：解析：設(shè)循環(huán)隊(duì)列的存儲空間為Q(1:m)，初始狀態(tài)為空。在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后，如果rear-front>0，則隊(duì)列中的元素個數(shù)為rear-front個；如果rear-front0，則元素個數(shù)為m-(m-1)=1。44.某棵樹中共有25個結(jié)點(diǎn)，且只有度為3的結(jié)點(diǎn)和葉子結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有7個，則該樹中度為3的結(jié)點(diǎn)數(shù)為（

）。A.7B.8C.6D.不存在這樣的樹答案：D解析：解析：如果葉子結(jié)點(diǎn)有7個，那么度為3的結(jié)點(diǎn)數(shù)是25-7=18個，但如果度為3的結(jié)點(diǎn)有18個，因?yàn)闃渲械慕Y(jié)點(diǎn)數(shù)即為樹中所有結(jié)點(diǎn)的度數(shù)之和再加1，那么該樹的總結(jié)點(diǎn)數(shù)是18*3+1=55個，與題目相矛盾，故本題答案為D。45.在最壞情況下，二分查找法的時間復(fù)雜度為（

）。A.A、nB.(n/2)log2nC.n/2D.log2n答案：D解析：解析：最壞情況下，二分法查找的時間復(fù)雜度是log2n。46.下列序列中不滿足堆條件的是（

）。A.(98,95,93,94,89,90,76,80,55,49)B.(98,95,93,94,89,90,76,64,55,49)C.(98,95,93,96,89,85,76,64,55,49)D.(98,95,93,94,89,85,76,64,55,49)答案：C解析：解析：若有n個元素的序列，將元素按順序組成一棵完全二叉樹，當(dāng)且僅當(dāng)滿足下列條件時稱為堆：大根堆，所有結(jié)點(diǎn)的值大于或等于其左右子結(jié)點(diǎn)的值；小根堆，所有結(jié)點(diǎn)的值小于或等于其左右子結(jié)點(diǎn)的值。A、B、D選項(xiàng)屬于大根堆。C選項(xiàng)由于98>95，判斷屬于大根堆，但9547.下列敘述中正確的是（

）。A.算法的復(fù)雜度用于衡量算法的控制結(jié)構(gòu)B.算法的效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)C.程序可以作為算法的一種表達(dá)方式D.算法的有窮性是指算法的規(guī)模不能太大答案：C解析：解析：算法可以用程序、偽代碼、流程圖來描述；而算法的有窮性是指算法能夠在有限時間內(nèi)完成，即執(zhí)行有限步驟后能夠終止；算法的復(fù)雜度用來衡量算法的好壞；算法的效率與數(shù)據(jù)的存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)都有關(guān)，故本題答案為C。48.某棵樹的度為4，且度為4、3、2、1的結(jié)點(diǎn)個數(shù)分別為1、2、3、4，則該樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.8B.10C.9D.11答案：D解析：解析：在樹結(jié)構(gòu)中，樹中的結(jié)點(diǎn)數(shù)即為樹中所有結(jié)點(diǎn)的度數(shù)之和再加1。本題中該樹總度數(shù)為4*1+3*2+2*3+1*4=20，所以結(jié)點(diǎn)總數(shù)為21個，則該樹中葉子結(jié)點(diǎn)個數(shù)為21-1-2-3-4=11個，故本題答案為D。49.設(shè)二叉樹中共有15個結(jié)點(diǎn)，其中的結(jié)點(diǎn)值互不相同。如果該二叉樹的前序序列與中序序列相同，則該二叉樹的深度為（

）。A.6B.15C.4D.不存在這樣的二叉樹答案：B解析：解析：如果該二叉樹前序序列與中序序列相同，說明該二叉樹沒有左子結(jié)點(diǎn)，只有右子結(jié)點(diǎn)，即所有結(jié)點(diǎn)結(jié)成一串，所以該二叉樹深度為15，故本題答案為B。50.設(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.52C.1D.2答案：D解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，此時如果正常地插入兩個元素，說明隊(duì)列為空（為滿的話插入元素會產(chǎn)生溢出錯誤），所以插入后元素個數(shù)為2，故本題答案為D。51.設(shè)數(shù)據(jù)元素集合為{A，B，C，D，E，F(xiàn)}，下列關(guān)系為線性結(jié)構(gòu)的是（

）。A.A、R={(D,F),(E,C),(B,C),(A,B),(C,F)}B.B、R={(D,E),(E,A),(B,C),(F,B),(C,F)}C.C、R={(A,B),(C,D),(B,A),(E,F),(F,A)}D.D、R={(D,E),(E,A),(B,C),(A,B),(C,F)}答案：D解析：解析：線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)只有一個前件也只有一個后件。對各個選項(xiàng)分析可以得出D選項(xiàng)符合要求，故本題答案為D。52.下列處理中與隊(duì)列有關(guān)的是（

）。A.執(zhí)行程序中的過程調(diào)用B.操作系統(tǒng)中的作業(yè)調(diào)度C.執(zhí)行程序中的循環(huán)控制D.以上說法均不正確答案：B解析：解析：在計算機(jī)系統(tǒng)中，如果一次只能執(zhí)行一個程序，則在多個用戶程序需要執(zhí)行時，這些用戶程序必須按照到來的順序進(jìn)行排隊(duì)等待。即操作系統(tǒng)中的作業(yè)調(diào)度使用的是隊(duì)列的先進(jìn)先出思想，故本題答案為B。53.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（

）。A.雙向鏈表B.二叉鏈表C.循環(huán)隊(duì)列D.循環(huán)鏈表答案：B解析：解析：樹是簡單的非線性結(jié)構(gòu)，所以二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)，而二叉鏈表是二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，故本題答案為B。54.設(shè)二叉樹中共有31個結(jié)點(diǎn)，其中的結(jié)點(diǎn)值互不相同。如果該二叉樹的后序序列與中序序列相同，則該二叉樹的深度為（

）。A.16B.17C.5D.31答案：D解析：解析：如果該二叉樹后序序列與中序序列相同，說明該二叉樹沒右子結(jié)點(diǎn)，只有左子結(jié)點(diǎn)，即所有結(jié)點(diǎn)結(jié)成一串，所以該二叉樹深度為31，故本題答案為D。55.下列敘述中錯誤的是（

）。A.空數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素不能是另一數(shù)據(jù)結(jié)構(gòu)D.非空數(shù)據(jù)結(jié)構(gòu)可以沒有根結(jié)點(diǎn)答案：C解析：解析：數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另外一種數(shù)據(jù)結(jié)構(gòu)，故本題答案為C。56.為了降低算法的空間復(fù)雜度，要求算法盡量采用原地工作(inplace)。所謂原地工作是指（

）。A.執(zhí)行算法時所使用的額外空間固定（即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化）B.執(zhí)行算法時不使用任何存儲空間C.執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化D.執(zhí)行算法時不使用額外空間答案：A解析：解析：原地工作原理是執(zhí)行算法時使用固定的額外空間，降低了算法的空間復(fù)雜度，故本題答案為A。57.設(shè)棧的存儲空間為S(1:m)，初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后，top=1。現(xiàn)又要將一個元素進(jìn)棧，棧頂指針top值變?yōu)椋?/p>

）。A.A、mB.發(fā)生棧滿的錯誤C.2D.0答案：B解析：解析：初始狀態(tài)為top=m+1，說明棧底是m，棧頂是1，當(dāng)top=1時，指針已經(jīng)指向棧頂，棧已經(jīng)滿了，再增加就會產(chǎn)生溢出錯誤，故本題答案為B。58.設(shè)某二叉樹的后序序列與中序序列均為ABCDEFGH，則該二叉樹的前序序列為（

）。A.A、DCBAHGFEB.B、EFGHABCDC.C、HGFEDCBAD.D、ABCDEFGH答案：C解析：解析：當(dāng)二叉樹的后序遍歷與中序遍歷相同時，說明該二叉樹各結(jié)點(diǎn)都是只有左子結(jié)點(diǎn)，所以前序遍歷的結(jié)果與后序遍歷的結(jié)果正好相反，故本題答案為C。59.設(shè)棧的存儲空間為S(1:m)，初始狀態(tài)為top=m+1。經(jīng)過一系列入棧與退棧操作后，top=m?，F(xiàn)又在棧中退出一個元素后，棧頂指針top值為（

）。A.m-1B.產(chǎn)生?？斟e誤C.m+1D.0答案：C解析：解析：在該棧中，初始狀態(tài)是空棧，經(jīng)過若干次操作后，指針指向m，意味著棧中還有一個元素，如果此時退出一個元素，那么再次成為空棧，所以top=m+1，故本題答案為C。60.下列敘述中正確的是（

）。A.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素只能是另一種線性結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素只能是另一種非線性結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一種數(shù)據(jù)結(jié)構(gòu)D.以上說法均不正確答案：C解析：解析：數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另外一種數(shù)據(jù)結(jié)構(gòu)，故本題答案為C。61.下列敘述中正確的是（

）。A.二分查找法適用于有序雙向鏈表B.二分查找法只適用于順序存儲的有序線性表C.二分查找法適用于有序循環(huán)鏈表D.二分查找法適用于任何存儲結(jié)構(gòu)的有序線性表答案：B解析：解析：二分查找法只適用于順序存儲的有序線性表，故本題答案為B。62.設(shè)某二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為（

）。A.A、HGFEDCBAB.B、ABCDEFGHC.C、EFGHABCDD.D、DCBAHGFE答案：A解析：解析：當(dāng)二叉樹的前序遍歷與中序遍歷相同時，說明該二叉樹各結(jié)點(diǎn)都是只有右子結(jié)點(diǎn)，所以前序遍歷的結(jié)果與后序遍歷的結(jié)果正好相反，故本題答案為A。63.設(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.0B.1C.m-2D.m-1答案：C解析：解析：由于存儲空間可以存儲m個結(jié)點(diǎn)，而頭指針指向m，所以第一個結(jié)點(diǎn)就在第1個位置上，而最后一個結(jié)點(diǎn)在m-1的位置上，所以該循環(huán)隊(duì)列共有m-1個結(jié)點(diǎn)，此后又刪除一個元素，所以最后隊(duì)列中元素個數(shù)為m-2，故本題答案為C。64.某二叉樹共有730個結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有30個，則葉子結(jié)點(diǎn)個數(shù)為（

）。A.351B.不存在這樣的二叉樹C.350D.1答案：B解析：解析：在二叉樹中，只存在度為0、1、2的結(jié)點(diǎn)，度為1的結(jié)點(diǎn)為30，所以度為0和度為2的結(jié)點(diǎn)總數(shù)為700，而根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個，所以不可能出現(xiàn)兩者相加為700的情況，故不存在這樣的二叉樹。65.能從任意一個結(jié)點(diǎn)開始沒有重復(fù)地掃描到所有結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是（

）。A.循環(huán)鏈表B.雙向鏈表C.二叉鏈表D.有序鏈表答案：A解析：解析：循環(huán)列表可以實(shí)現(xiàn)不重復(fù)地掃描到所有結(jié)點(diǎn)，故本題答案為A。66.若某二叉樹中的所有結(jié)點(diǎn)值均大于其左子樹上的所有結(jié)點(diǎn)值，且小于右子樹上的所有結(jié)點(diǎn)值，則該二叉樹遍歷序列中有序的是（

）。A.前序序列B.中序序列C.后序序列D.以上答案均不正確答案：B解析：解析：該二叉樹中，根結(jié)點(diǎn)大于左子結(jié)點(diǎn)，而小于右子結(jié)點(diǎn)，所以只要先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子，即可滿足有序，也就是中序遍歷，故本題答案為B。67.設(shè)循環(huán)隊(duì)列的存儲空間為Q(1:m)，初始狀態(tài)為空。現(xiàn)經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=m-1，rear=m，此后再向該循環(huán)隊(duì)列中插入一個元素，則隊(duì)列中的元素個數(shù)為（

）。A.2B.1C.m-1D.D、m答案：A解析：解析：設(shè)循環(huán)隊(duì)列的存儲空間為Q(1:m)，初始狀態(tài)為空。在循環(huán)隊(duì)列運(yùn)轉(zhuǎn)起來后，如果rear-front>0，則隊(duì)列中的元素個數(shù)為rear-front個；如果rear-front0，則元素個數(shù)為m-(m-1)=1，此后又插入一個元素，則循環(huán)隊(duì)列中共有2個元素，故本題答案為A。68.某二叉樹共有530個結(jié)點(diǎn)，其中度為2的結(jié)點(diǎn)有250個，則度為1的結(jié)點(diǎn)數(shù)為（

）。A.251B.30C.249D.29答案：D解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，即度為0的結(jié)點(diǎn)有251個，所以度為1的結(jié)點(diǎn)個數(shù)為530-250-251=29個。69.下列敘述中正確的是（

）。A.對同一批數(shù)據(jù)作同一種處理，如果數(shù)據(jù)存儲結(jié)構(gòu)不同，不同算法的時間復(fù)雜度肯定相同B.解決同一個問題的不同算法的時間復(fù)雜度必定是相同的C.解決同一個問題的不同算法的時間復(fù)雜度一般是不同的D.對同一批數(shù)據(jù)作不同的處理，如果數(shù)據(jù)存儲結(jié)構(gòu)相同，不同算法的時間復(fù)雜度肯定相同答案：C解析：解析：一般來說，不同算法的時間復(fù)雜度是不同的，而且時間復(fù)雜度也受數(shù)據(jù)的存儲結(jié)構(gòu)影響，故本題答案為C。70.在最壞情況下，堆排序的時間復(fù)雜度是（

）。A.O(n1.5)B.O(nlog2n)C.O(log2n)D.O(n2)答案：B解析：解析：堆排序的平均和最壞情況時間復(fù)雜度都為O(nlog2n)，故本題答案為B。71.下列敘述中正確的是（

）。A.壓縮數(shù)據(jù)存儲空間不會降低算法的空間復(fù)雜度B.算法的空間復(fù)雜度是指算法程序控制結(jié)構(gòu)的復(fù)雜程度C.算法的空間復(fù)雜度與算法所處理的數(shù)據(jù)存儲空間有關(guān)D.算法的空間復(fù)雜度是指算法程序中指令的條數(shù)答案：C解析：解析：算法的空間復(fù)雜度是執(zhí)行算法所需的內(nèi)存空間，它與算法所處理的數(shù)據(jù)存儲空間有關(guān)，故本題答案為C。72.下列各組排序法中，最壞情況下比較次數(shù)相同的是（

）。A.簡單插入排序與希爾排序B.簡單選擇排序與堆排序C.希爾排序與堆排序D.冒泡排序與快速排序答案：D解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)。73.設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}。下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為非線性結(jié)構(gòu)的是（

）。A.R={(1,2),(2,3),(3,4),(4,5)}B.R={(1,2),(2,3),(4,3),(3,5)}C.R={(5,4),(4,3),(3,2),(2,1)}D.R={(2,5),(5,4),(3,2),(4,3)}答案：B解析：解析：線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)只有一個前件也只有一個后件。分析各個選項(xiàng)可知只有B選項(xiàng)是非線性結(jié)構(gòu)，故本題答案為B。74.某二叉樹共有400個結(jié)點(diǎn)，其中有100個度為1的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.150B.149C.不存在這樣的二叉樹D.151答案：C解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，由題意可知，葉子結(jié)點(diǎn)和度為2的結(jié)點(diǎn)個數(shù)總和為400-100=300，無法滿足該性質(zhì)，故不存在這樣的二叉樹。所以本題答案為C。75.設(shè)棧的存儲空間為S(1:50)，初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=20，則棧中的元素個數(shù)為（

）。A.21B.20C.30D.31答案：D解析：解析：初始狀態(tài)為top=51，說明棧底的地址為50，棧頂?shù)奈恢脼?，經(jīng)過一系列操作后，top=20，則說明20-50位置都有元素，共計31個，故本題答案為D。76.下列敘述中正確的是（

）。A.有多個指針域的鏈表一定是非線性結(jié)構(gòu)B.只有一個根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)C.有多個指針域的鏈表有可能是線性結(jié)構(gòu)D.有兩個指針域的鏈表一定是二叉樹的存儲結(jié)構(gòu)答案：C解析：解析：線性結(jié)構(gòu)應(yīng)滿足：(1)有且只有一個根結(jié)點(diǎn)；(2)每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件；那么該結(jié)構(gòu)就是線性結(jié)構(gòu)，與結(jié)點(diǎn)有幾個指針域沒有必然關(guān)系，結(jié)點(diǎn)在有多個指針域的情況下，只要滿足只有一個指針域有具體的值，其他都為空，那么仍然可以構(gòu)成線性結(jié)構(gòu)，故本題答案為C。77.某二叉樹共有150個結(jié)點(diǎn)，其中有50個度為1的結(jié)點(diǎn)，則（

）。A.該二叉樹有49個葉子結(jié)點(diǎn)B.該二叉樹有51個葉子結(jié)點(diǎn)C.該二叉樹有50個葉子結(jié)點(diǎn)D.不存在這樣的二叉樹答案：D解析：解析：在二叉樹中，只存在度為0、1、2的結(jié)點(diǎn)，度為1的結(jié)點(diǎn)為50，所以度為0和度為2的結(jié)點(diǎn)總數(shù)為100，而根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個，所以不可能出現(xiàn)兩者相加為100的情況，故不存在這樣的二叉樹。78.循環(huán)隊(duì)列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25，此后又正常地插入了一個元素，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.49B.50C.51D.1答案：D解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，此時如果正常地插入一個元素，說明隊(duì)列為空（為滿的話插入元素會產(chǎn)生溢出錯誤），插入后元素個數(shù)為1，故本題答案為D。79.某二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為CBADE，則后序遍歷序列為（

）。A.A、EDCBAB.B、CBADEC.C、CBEDAD.D、EDABC答案：C解析：解析：由前序遍歷可以得出A是根結(jié)點(diǎn)，結(jié)合中序遍歷知道CB是左子樹，DE是右子樹；再回到前序遍歷，CB這棵左子樹B是根結(jié)點(diǎn)，由中序遍歷知道C是B的左子結(jié)點(diǎn)；同理可得出DE右子樹的情況；還原出此二叉樹的原形后，再進(jìn)行后序遍歷，可以得出后序遍歷的順序是CBEDA，故本題答案為C。80.下列敘述中正確的是（

）。A.循環(huán)隊(duì)列是隊(duì)列的一種存儲結(jié)構(gòu)B.所有二叉樹均不適合用順序存儲結(jié)構(gòu)C.二分查找適用于任何存儲方式的有序表D.有兩個指針域的鏈表一定是二叉樹的存儲結(jié)構(gòu)答案：A解析：解析：循環(huán)隊(duì)列是隊(duì)列的一種順序存儲結(jié)構(gòu)，A選項(xiàng)正確。并不是所有二叉樹都要采用鏈?zhǔn)酱鎯Γ訠選項(xiàng)錯誤。二分法查找適用于順序存儲的有序表，所以C選項(xiàng)錯誤。一個數(shù)據(jù)結(jié)構(gòu)是不是二叉樹，并不是由結(jié)點(diǎn)包含幾個指針域決定的，而是有幾個后件決定的，所以D選項(xiàng)錯誤。81.下列敘述中正確的是（

）。A.算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度B.算法設(shè)計只需考慮結(jié)果的可靠性C.算法復(fù)雜度是用算法中指令的條數(shù)來度量的D.數(shù)據(jù)的存儲結(jié)構(gòu)會影響算法的效率答案：D解析：解析：算法的復(fù)雜度有時間復(fù)雜度、空間復(fù)雜度，兩者分別表示執(zhí)行算法所需要的計算工作量、執(zhí)行算法所需的內(nèi)存空間，故A選項(xiàng)和C選項(xiàng)錯誤。算法設(shè)計時要考慮算法的復(fù)雜度，問題規(guī)模越大越是如此，故B選項(xiàng)錯誤。算法的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都會影響算法的效率，故本題答案為D。82.循環(huán)隊(duì)列的存儲空間為Q(1:40)，初始狀態(tài)為front=rear=40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=15，此后又正常地退出了一個元素，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.14B.16C.39D.9答案：C解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，此時如果正常退出一個元素，說明當(dāng)時是隊(duì)滿，隊(duì)滿的情況下，此循環(huán)隊(duì)列可以有40個元素，退出1個后，還有39個，故本題答案為C。83.某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBEDA，則前序遍歷序列為（

）。A.A、CBADEB.B、ABCDEC.C、CBEDAD.D、EDCBA答案：B解析：解析：先由后序遍歷可知A是根結(jié)點(diǎn)，再由中序遍歷可知CB是左子樹，DE是右子樹；再根據(jù)后序遍歷可知B和D分別是左右子樹中的根結(jié)點(diǎn)，由中序遍歷可知C是B的左子結(jié)點(diǎn)，E是D的右子結(jié)點(diǎn)，據(jù)此畫出二叉樹圖形后，再進(jìn)行前序遍歷，可得到ABCDE，故本題答案為B。84.下列敘述中正確的是（

）。A.沒有根結(jié)點(diǎn)的一定是非線性結(jié)構(gòu)B.只有一個根結(jié)點(diǎn)的必定是線性結(jié)構(gòu)或二叉樹C.只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)的必定是線性結(jié)構(gòu)D.非線性結(jié)構(gòu)可以為空答案：D解析：解析：一個空的數(shù)據(jù)結(jié)構(gòu)既可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)，所以D選項(xiàng)正確，A選項(xiàng)錯誤。線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，并且中間結(jié)點(diǎn)有且只有一個前件和一個后件，所以B選項(xiàng)和C選項(xiàng)錯誤，故本題答案為D。85.設(shè)棧的存儲空間為S(1:60)，初始狀態(tài)為top=61?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=25，則棧中的元素個數(shù)為（

）。A.36B.25C.35D.26答案：A解析：解析：初始狀態(tài)為top=61,說明?？諘rtop=61；入棧時棧頂指針是減操作，即每入棧一個元素，棧頂指針top的值減1，則入棧元素的個數(shù)等于61-top；當(dāng)top的值為25時，棧中元素的個數(shù)為36，故本題答案為A。86.下列排序方法中，最壞情況下時間復(fù)雜度（即比較次數(shù)）最低的是（

）。A.快速排序B.冒泡排序C.希爾排序D.簡單插入排序答案：C解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)，故本題答案為C。87.下列敘述中錯誤的是（

）。A.非線性結(jié)構(gòu)中至少有一個根結(jié)點(diǎn)B.有一個以上葉子結(jié)點(diǎn)的必定是非線性結(jié)構(gòu)C.有一個以上根結(jié)點(diǎn)的必定是非線性結(jié)構(gòu)D.非線性結(jié)構(gòu)中可以沒有根結(jié)點(diǎn)與葉子結(jié)點(diǎn)答案：A解析：解析：線性結(jié)構(gòu)應(yīng)滿足：(1)有且只有一個根結(jié)點(diǎn)；(2)每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件；所以B、C選項(xiàng)正確，一個空的數(shù)據(jù)結(jié)構(gòu)既可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)，所以D選項(xiàng)正確，A選項(xiàng)錯誤。88.某二叉樹中共有350個結(jié)點(diǎn)，其中200個為葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)數(shù)為（

）。A.不可能有這樣的二叉樹B.150C.149D.199答案：A解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，葉子結(jié)點(diǎn)有200個，那么度為0的結(jié)點(diǎn)就應(yīng)該有199個，總數(shù)已經(jīng)超過350個，與題意矛盾，故本題答案為A。89.下列排序方法中，最壞情況下時間復(fù)雜度（即比較次數(shù)）低于O(n2)的是（

）。A.冒泡排序B.快速排序C.堆排序D.簡單插入排序答案：C解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)，故本題答案為C。90.下列算法中，最壞情況下時間復(fù)雜度最低的是（

）。A.順序查找法B.堆排序C.二分查找法D.快速排序答案：C解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)，故本題答案為C。91.下列敘述中錯誤的是（

）。A.所有二叉樹都只能用二叉鏈表表示B.有多個指針域的鏈表也有可能是線性結(jié)構(gòu)C.二分查找法只適用于順序存儲的線性有序表D.循環(huán)隊(duì)列是隊(duì)列的存儲結(jié)構(gòu)答案：A解析：解析：一般來說，二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，但由于完全二叉樹的特點(diǎn)，采用順序存儲也能方便地訪問其中的每一個元素。故A選項(xiàng)錯誤。92.某二叉樹共有400個結(jié)點(diǎn)，其中有99個度為1的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.151B.149C.不可能有這樣的二叉樹D.150答案：A解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，由題意可知，葉子結(jié)點(diǎn)和度為2的結(jié)點(diǎn)個數(shù)總和為400-99=301，所以葉子結(jié)點(diǎn)個數(shù)為151個，度為2的結(jié)點(diǎn)個數(shù)為150個，故本題答案為A。93.循環(huán)隊(duì)列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.49B.0或50C.26D.25答案：B解析：解析：當(dāng)隊(duì)頭和隊(duì)尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，故本題答案為B。94.設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5,6}。下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為線性結(jié)構(gòu)的是（

）。A.R={(1,2),(2,3),(6,5),(3,6),(5,4)}B.R={(5,4),(3,4),(3,2),(4,3),(5,6)}C.R={(1,2),(2,3),(3,4),(4,5),(6,5)}D.R={(1,2),(2,3),(4,3),(4,5),(5,6)}答案：A解析：解析：線性結(jié)構(gòu)要求只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)，除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)只有一個前件也只有一個后件。B選項(xiàng)5的后面有4、6兩個數(shù)值，C選項(xiàng)5的前面有4、6兩個數(shù)值，D選項(xiàng)4的后面有3、5兩個數(shù)值，所以B、C、D選項(xiàng)是非線性結(jié)構(gòu)，故本題答案為A。95.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=m+1，則棧中的數(shù)據(jù)元素個數(shù)為（

）。A.A、m-topB.m-top+1C.C、top-mD.top-m+1答案：B解析：解析：棧的初始狀態(tài)top=m+1，說明棧空時top=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。96.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則前序遍歷序列為（

）。A.A、CBAFEDB.B、DEFCBAC.C、FEDCBAD.D、ABCDEF答案：C解析：解析：后序遍歷與中遍歷相同，說明該二叉樹除了葉子結(jié)點(diǎn)外，所有結(jié)點(diǎn)都只有左子結(jié)點(diǎn)，依據(jù)題目中的結(jié)點(diǎn)情況，可以得出其前序遍歷的結(jié)果為FEDCBA，故本題答案為C。97.在具有n個結(jié)點(diǎn)的二叉樹中，如果各結(jié)點(diǎn)值互不相同，但前序遍歷序列與中序遍歷序列相同，則該二叉樹的深度為（根結(jié)點(diǎn)在第1層）（

）。A.n-1B.n/2+1C.C、nD.n+1答案：C解析：解析：前序遍歷和中序遍歷相同說明該樹除了葉子結(jié)點(diǎn)外，每個結(jié)點(diǎn)只有右子結(jié)點(diǎn)，也就是該二叉樹是深度為n，結(jié)點(diǎn)個數(shù)為n的二叉樹，故本題答案為C。98.下列敘述中錯誤的是（

）。A.不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的B.順序棧的棧底指針在操作過程中是固定不變的C.不管是順序棧還是帶鏈的棧，在操作過程中其棧頂指針均是動態(tài)變化的D.帶鏈棧的棧底指針在操作過程中是有可能改變的答案：A解析：解析：帶鏈棧其棧底指針是動態(tài)變化的，故本題答案為A。99.某二叉樹的前序遍歷序列與中序遍歷序列相同，均為ABCDEF，則后序遍歷序列為（

）。A.A、BCDEFAB.B、FEDCBAC.C、DEFABCD.D、CDEFAB答案：B解析：解析：如果二叉樹的前序遍歷和中序遍歷相同，那么說明此二叉樹除葉子結(jié)點(diǎn)外，所有結(jié)點(diǎn)都是只有右子結(jié)點(diǎn)。根據(jù)上述說法畫出二叉樹可知，其后序遍歷序列為FEDCBA，故本題答案為B。100.下列敘述中正確的是（

）。A.堆可以用完全二叉樹表示，其中序遍歷序列是有序序列B.任何二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)C.多重鏈表必定是非線性結(jié)構(gòu)D.排序二叉樹的中序遍歷序列是有序序列答案：D解析：解析：排序二叉樹中，左子樹上的值均小于其根結(jié)點(diǎn)，右子樹上的值均大于其根結(jié)點(diǎn)，所以排序二叉樹的中序遍歷一定是有序序列，故本題答案為D。101.下列敘述中正確的是（

）。A.算法的時間復(fù)雜度與運(yùn)行算法時特定的輸入有關(guān)B.算法的時間復(fù)雜度與算法程序編制者的水平有關(guān)C.算法的時間復(fù)雜度與計算機(jī)的運(yùn)行速度有關(guān)D.算法的時間復(fù)雜度與算法程序中的語句條數(shù)成正比答案：A解析：解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法程序執(zhí)行的具體時間和算法的時間復(fù)雜度并不是一致的。算法程序執(zhí)行的具體時間受到所使用的計算機(jī)、程序設(shè)計語言以及算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)所影響，而算法的時間復(fù)雜度與這些因素?zé)o關(guān)。因此B、C、D選項(xiàng)錯誤。通常用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)還與問題的規(guī)模有關(guān)；對應(yīng)一個固定的規(guī)模，算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)。故本題答案為A。102.設(shè)棧的存儲空間為S(1:50)，初始狀態(tài)為top=51?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=50，則棧中的元素個數(shù)為（

）。A.50B.1C.0D.49答案：B解析：解析：初始狀態(tài)為top=51,說明棧空時top=51；入棧時棧頂指針是減操作，即每入棧一個元素，棧頂指針top的值減1，則入棧元素的個數(shù)等于51-top；當(dāng)top的值為50時，棧中元素的個數(shù)為1，故本題答案為B。103.某二叉樹共有399個結(jié)點(diǎn)，其中有199個度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.198B.199C.不存在這樣的二叉樹D.200答案：D解析：解析：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個，題目中度為2的結(jié)點(diǎn)為199個，則葉子結(jié)點(diǎn)為199+1=200。故本題答案為D。104.下列敘述中錯誤的是（

）。A.算法的時間復(fù)雜度與實(shí)現(xiàn)算法過程中的具體細(xì)節(jié)無關(guān)B.算法的時間復(fù)雜度與使用的計算機(jī)系統(tǒng)無關(guān)C.算法的時間復(fù)雜度與使用的程序設(shè)計語言無關(guān)D.對于各種特定的輸入,算法的時間復(fù)雜度是固定不變的答案：D解析：解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)與問題的規(guī)模有關(guān)。對于一個固定的規(guī)模，算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)，故本題答案為D。105.在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn)在表中每個位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為（

）。A.n/4B.3n/4C.C、nD.(n+1)/2答案：D解析：解析：在順序表中查找，最好情況下第一個元素就是要查找的元素，則比較次數(shù)為1；在最壞情況下，最后一個元素才是要找的元素，則比較次數(shù)為n。兩種情況平均即(1+n)/2。故本題答案為D。106.設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值，而右子樹上的結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是（

）。A.后序序列B.前序序列或后序序列C.前序序列D.中序序列答案：D解析：解析：由題目可知，根結(jié)點(diǎn)的值一定大于左子樹的結(jié)點(diǎn)，并且一定小于右子樹的結(jié)點(diǎn)，所以要想排序，只能是先左子樹，再根結(jié)點(diǎn)，再右子樹，即采用中序遍歷，故本題答案為D。107.循環(huán)隊(duì)列的存儲空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25，此后又插入一個元素，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.26B.51C.1，或50且產(chǎn)生上溢錯誤D.2答案：C解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，此時如果插入一個元素，若隊(duì)列為滿時產(chǎn)生溢出錯誤，若隊(duì)列為空則成功插入一個元素，故本題答案為C。108.下列算法中均以比較作為基本運(yùn)算，則平均情況與最壞情況下的時間復(fù)雜度相同的是（

）。A.在順序存儲的線性表中尋找最大項(xiàng)B.在順序存儲的有序表中進(jìn)行對分查找C.在順序存儲的線性表中進(jìn)行順序查找D.在鏈?zhǔn)酱鎯Φ挠行虮碇羞M(jìn)行查找答案：A解析：解析：在順序存儲的線性表中查找最大項(xiàng)時，最壞情況下比較次數(shù)為n-1，順序查找的平均情況時間復(fù)雜度為O(n)，故本題答案為A。109.在具有2n個結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個數(shù)為（

）。A.A、nB.n+1C.n/2D.n-1答案：A解析：解析：關(guān)于完全二叉樹的特殊性質(zhì)：假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)（即葉子結(jié)點(diǎn)數(shù)），n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，則n=n0+n1+n2（其中n為完全二叉樹的結(jié)點(diǎn)總數(shù)）；又因?yàn)槎鏄涞幕拘再|(zhì)（n0=n2+1）,所以得n=2*n0+n1-1，由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0=n/2或n0=(n+1)/2。簡便來算，就是n0=n/2（n為奇數(shù)時結(jié)果向上取整）。由題可知，結(jié)點(diǎn)總數(shù)為2n，故n0=2n/2=n，本題答案為A。110.下列敘述中正確的是（

）。A.在循環(huán)鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度B.在線性鏈表中，頭指針和鏈尾指針的動態(tài)變化決定鏈表的長度C.在棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)D.在循環(huán)隊(duì)列中，隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度答案：C解析：解析：在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針都是動態(tài)變化的，所以循環(huán)隊(duì)列中的元素個數(shù)由隊(duì)頭指針和隊(duì)尾指針共同決定；在循環(huán)鏈表中，前一個結(jié)點(diǎn)指向后一個結(jié)點(diǎn)，而最后一個結(jié)點(diǎn)指向頭結(jié)點(diǎn)，只有頭結(jié)點(diǎn)是固定的；線性鏈表中，由于前一個結(jié)點(diǎn)包含下一個結(jié)點(diǎn)的指針，尾結(jié)點(diǎn)指針為空，要插入刪除元素，只需要改變相應(yīng)位置的結(jié)點(diǎn)指針即可，頭指針和尾指針無法決定鏈表長度；在棧中，棧底保持不變，有元素入棧，棧頂指針增加；有元素出棧，棧頂指針減小。故本題答案為C。111.循環(huán)隊(duì)列的存儲空間為Q(1:40)，初始狀態(tài)為front=rear=40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=15，此后又退出一個元素，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.40B.39，或0且產(chǎn)生下溢錯誤C.14D.15答案：B解析：解析：當(dāng)頭指針和尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，此時執(zhí)行退出元素操作，若隊(duì)列為滿時40個元素減去1個還剩39個，若隊(duì)列為空則產(chǎn)生下溢錯誤，故本題答案為B。112.某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBADE，則前序遍歷序列為（

）。A.A、EDABCB.B、EDCBAC.C、CBEDAD.D、CBADE答案：A解析：解析：先由后序遍歷可知E是根結(jié)點(diǎn)，再由中序遍歷可知CBAD都是左子樹；再根據(jù)后序遍歷可知D是左子樹CBAD中的根結(jié)點(diǎn)，同理根據(jù)中序遍歷可知CBA都是左子樹，再根據(jù)后序遍歷可知A是第三層根節(jié)點(diǎn)，同理往下判斷CB，據(jù)此畫出二叉樹圖形后，再進(jìn)行前序遍歷，可得到EDABC，故本題答案為A。113.下列敘述中正確的是（

）。A.在循環(huán)隊(duì)列中，隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度B.在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)C.在帶鏈的隊(duì)列中，隊(duì)頭指針與隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度D.在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動態(tài)變化決定隊(duì)列的長度答案：D解析：解析：在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針都是動態(tài)變化的，所以循環(huán)隊(duì)列中的元素個數(shù)由隊(duì)頭指針和隊(duì)尾指針共同決定；在循環(huán)鏈表中，前一個結(jié)點(diǎn)指向后一個結(jié)點(diǎn)，而最后一個結(jié)點(diǎn)指向頭結(jié)點(diǎn)，只有頭結(jié)點(diǎn)是固定的；線性鏈表中，由于前一個結(jié)點(diǎn)包含下一個結(jié)點(diǎn)的指針，尾結(jié)點(diǎn)指針為空，要插入刪除元素，只需要改變相應(yīng)位置的結(jié)點(diǎn)指針即可，頭指針和尾指針無法決定鏈表長度。故本題答案為D。114.設(shè)棧的存儲空間為S(1:60)，初始狀態(tài)為top=61?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=1，則棧中的元素個數(shù)為（

）。A.60B.59C.1D.0答案：A解析：解析：初始狀態(tài)為top=61,說明棧空時top=61；入棧時棧頂指針是減操作，即每入棧一個元素，棧頂指針top的值減1，則入棧元素的個數(shù)等于61-top；當(dāng)top的值為1時，棧中元素的個數(shù)為60，故本題答案為A。115.設(shè)順序表的長度為n。下列排序方法中，最壞情況下比較次數(shù)小于n(n-1)/2的是（

）。A.冒泡排序B.快速排序C.簡單插入排序D.堆排序答案：D解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為n(n-1)/2；堆排序需要的比較次數(shù)為nlog2n。故本題答案為D。116.在長度為n的順序表中查找一個元素，假設(shè)需要查找的元素有一半的機(jī)會在表中，并且如果元素在表中,則出現(xiàn)在表中每個位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為（

）。A.n/4B.3n/4C.n/2D.D、n答案：B解析：解析：因?yàn)椴檎业脑赜幸话霗C(jī)會在表中，所以二分之一的情況下平均比較次數(shù)為n/2，二分之一情況下平均比較次數(shù)為n，總的平均比較次數(shù)為(n/2+n)/2=3n/4。故本題答案為B。117.設(shè)一棵樹的度為3，其中度為3，2，1的結(jié)點(diǎn)個數(shù)分別為4，1，3。則該棵樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.10B.11C.12D.不可能有這樣的樹答案：A解析：解析：在樹結(jié)構(gòu)中，樹中的結(jié)點(diǎn)數(shù)即為樹中所有結(jié)點(diǎn)的度數(shù)之和再加1。本題中該樹總度數(shù)為3×4+2×1+1×3=17，所以結(jié)點(diǎn)總數(shù)為18個，則該樹中葉子結(jié)點(diǎn)個數(shù)為18-4-1-3=10，故本題答案為A。118.設(shè)棧的存儲空間為S(1:50)，初始狀態(tài)為top=0。現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=51，則棧中的元素個數(shù)為（

）。A.50B.不可能C.1D.0答案：B解析：解析：初始狀態(tài)棧頂指針top=0，存儲空間為S(1:50)，則說明1為棧底，50為棧頂，當(dāng)top=51時棧已經(jīng)溢出。故本題答案為B。119.設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)等于n(n-1)/2的是（

）。A.尋找最大項(xiàng)B.堆排序C.快速排序D.順序查找答案：C解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為n(n-1)/2；堆排序需要的比較次數(shù)為nlog2n；順序查找需要查找n次；順序表中，尋找最大項(xiàng)需要比較n-1次。故本題答案為C。120.設(shè)表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是（

）。A.堆排序B.快速排序C.順序查找法D.二分查找法答案：D解析：解析：最壞情況下，冒泡排序、快速排序、直接插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)。故本題答案為D。121.下列敘述中錯誤的是（

）。A.棧是線性結(jié)構(gòu)B.二叉鏈表是二叉樹的存儲結(jié)構(gòu)C.循環(huán)鏈表是循環(huán)隊(duì)列的存儲結(jié)構(gòu)D.循環(huán)隊(duì)列是隊(duì)列的存儲結(jié)構(gòu)答案：C解析：解析：循環(huán)隊(duì)列是隊(duì)列的順序存儲結(jié)構(gòu)，所以C選項(xiàng)說法錯誤。122.設(shè)一棵樹的度為4，其中度為4，3，2，1的結(jié)點(diǎn)個數(shù)分別為2，3，3，0。則該棵樹中的葉子結(jié)點(diǎn)數(shù)為（

）。A.不可能有這樣的樹B.16C.15D.17答案：B解析：解析：在樹結(jié)構(gòu)中，樹中的結(jié)點(diǎn)數(shù)即為樹中所有結(jié)點(diǎn)的度數(shù)之和再加1。本題中該樹總度數(shù)為4×2+3×3+2×3+1×0=23，所以結(jié)點(diǎn)總數(shù)為24個，則該樹中葉子結(jié)點(diǎn)個數(shù)為24-2-3-3=16，故本題答案為B。123.循環(huán)隊(duì)列的存儲空間為Q(1:100)，初始狀態(tài)為front=rear=100。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=99，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.2B.0或100C.99D.1答案：B解析：解析：當(dāng)隊(duì)頭和隊(duì)尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，故本題答案為B。124.設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是（

）。A.堆排序B.尋找最大項(xiàng)C.順序查找法D.快速排序答案：B解析：解析：最壞情況下，冒泡排序、快速排序、直接插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；尋找最大項(xiàng)只要比較n-1次。故本題答案為B。125.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=m+1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=0，則棧中的元素個數(shù)為（

）。A.m+1B.1C.C、mD.不可能答案：D解析：解析：初始狀態(tài)棧頂指針top=m+1，存儲空間為S(1:m)，則說明m為棧底，1為棧頂，當(dāng)top=0時棧已經(jīng)溢出。故本題答案為D。126.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為（

）。A.A、FEDCBAB.B、CBAFEDC.C、ABCDEFD.D、DEFCBA答案：A解析：解析：二叉樹的中序遍歷序列和后序遍歷序列均為ABCDEF，可知該樹只有左子樹結(jié)點(diǎn)，沒有右子樹結(jié)點(diǎn)，F(xiàn)為根結(jié)點(diǎn)。中序遍歷序列與后序遍歷序列相同說明該樹只有左子樹沒有右子樹，因此該樹有6層，從頂向下從左向右依次為FEDCBA。故本題答案為A。127.循環(huán)隊(duì)列的存儲空間為Q(1:200)，初始狀態(tài)為front=rear=200。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=1，則循環(huán)隊(duì)列中的元素個數(shù)為（

）。A.1B.2C.199D.0或200答案：D解析：解析：當(dāng)隊(duì)頭和隊(duì)尾指針指向同一個元素時，隊(duì)列為空或隊(duì)列為滿，故本題答案為D。128.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個數(shù)為（

）。A.m+1B.不可能C.0D.D、m答案：B解析：解析：初始狀態(tài)棧頂指針top=0，存儲空間為S(1:m)，則說明1為棧底，m為棧頂，當(dāng)top=m+1時棧已經(jīng)溢出。故本題答案為B。129.某二叉樹的前序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為（

）。A.A、DEFABCB.B、FEDCBAC.C、BCDEFAD.D、ABCDEF答案：D解析：解析：二叉樹的中序遍歷序列和前序遍歷序列均為ABCDEF，可知該樹只有右子樹結(jié)點(diǎn)，沒有左子樹結(jié)點(diǎn)，A為根結(jié)點(diǎn)。中序遍歷序列與前序遍歷序列相同說明該樹只有右子樹沒有左子樹，因此該樹有6層，從頂向下從左向右依次為ABCDEF。故本題答案為D。130.下列敘述中正確的是（

）。A.數(shù)值型算法只需考慮計算結(jié)果的可靠性B.算法的復(fù)雜度與問題的規(guī)模無關(guān)C.算法的優(yōu)化主要通過程序的編制技巧來實(shí)現(xiàn)D.對數(shù)據(jù)進(jìn)行壓縮存儲會降低算法的空間復(fù)雜度答案：D解析：解析：算法的空間復(fù)雜度是執(zhí)行算法所需的內(nèi)存空間。為了降低算法的空間復(fù)雜度，主要應(yīng)減少輸入數(shù)據(jù)所占的存儲空間以及額外空間，通常采用壓縮存儲技術(shù)。由于在編程時要受到計算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，因此，程序的編制通常不可能優(yōu)于算法的設(shè)計。算法執(zhí)行時所需要的計算機(jī)資源越多，算法復(fù)雜度越高，因此算法的復(fù)雜度和問題規(guī)模成正比。算法設(shè)計時要考慮算法的復(fù)雜度，問題規(guī)模越大越是如此。故本題答案為D。131.設(shè)數(shù)據(jù)結(jié)構(gòu)B=(D,R)，其中D={a,b,c,d,e,f}R={(a,b),(b,c),(c:d),(d,e),(e,f),(f,a)}該數(shù)據(jù)結(jié)構(gòu)為（

）。A.循環(huán)鏈表B.非線性結(jié)構(gòu)C.線性結(jié)構(gòu)D.循環(huán)隊(duì)列答案：B解析：解析：滿足下列兩個條件的非空數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)：1.有且只有一個根結(jié)點(diǎn)；2.每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。本題數(shù)據(jù)結(jié)構(gòu)中沒有根節(jié)點(diǎn)，因此它是非線性結(jié)構(gòu)，故本題答案為B。132.下列排序法中，每經(jīng)過一次元素的交換會產(chǎn)生新的逆序的是（

）。A.冒泡排序B.簡單選擇排序C.快速排序D.簡單插入排序答案：C解析：解析：在數(shù)據(jù)元素的序列中，對于某個元素，如果其后存在一個元素小于它，則稱之為存在一個逆序。冒泡排序只交換相鄰元素，不是每次移動都產(chǎn)生新的逆序。簡單插入排序每一次比較后最多移掉一個逆序。快速排序是選出一個結(jié)點(diǎn)，然后將大于該結(jié)點(diǎn)的數(shù)據(jù)移到后面，將小于該結(jié)點(diǎn)的數(shù)據(jù)移到前面，所以會產(chǎn)生一個新的逆序，當(dāng)不會有新的逆序產(chǎn)生時，本輪比較結(jié)束。簡單選擇排序的基本思想是先從所有n個待排序的數(shù)據(jù)元素中選擇最小的元素，將該元素與第一個元素交換，再從剩下的n-1個元素中選出最小的元素與第2個元素交換，這樣做不會產(chǎn)生逆序。故本題答案為C。133.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=10。該隊(duì)列中的元素個數(shù)為（

）。A.1或0B.1C.0D.不確定答案：B解析：解析：往隊(duì)列的隊(duì)尾插入一個元素為入隊(duì)，從隊(duì)列的排頭刪除一個元素稱為退隊(duì)。初始時front=rear=0，front總是指向隊(duì)頭元素的前一位置，入隊(duì)一次rear+1，退隊(duì)一次front+1。隊(duì)列隊(duì)頭隊(duì)尾指針相同時隊(duì)列為空。而帶鏈的隊(duì)列，由于每個元素都包含一個指針域指向下一個元素，當(dāng)帶鏈隊(duì)列為空時front=rear=NULL，插入第1個元素時，rear+1指向該元素，front+1也指向該元素，插入第2個元素時rear+1，front不變，刪除1個元素時front+1。即front=rear不為空時帶鏈的隊(duì)列中只有一個元素。故本題答案為B。134.某完全二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該完全二叉樹的前序序列為（

）。A.A、HDEBFGCAB.B、ABCDEFGHC.C、ABDHECFGD.D、HDBEAFCG答案：C解析：解析：完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。由此根據(jù)層次輸出結(jié)果畫出對應(yīng)的二叉樹，如下圖?故前序序列為ABDHECFG。135.下列敘述中正確的是（

）。A.順序存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)B.多重鏈表一定是非線性結(jié)構(gòu)C.有的二叉樹也能用順序存儲結(jié)構(gòu)表示D.有兩個指針域的鏈表就是二叉鏈表答案：C解析：解析：所有結(jié)點(diǎn)都只有一個子結(jié)點(diǎn)的特殊二叉樹可以用順序結(jié)構(gòu)存儲，故本題答案為C。136.下列各排序法中，最壞情況下時間復(fù)雜度最小的是（

）。A.希爾排序B.冒泡排序C.快速排序D.堆排序答案：D解析：解析：最壞情況下，冒泡排序、快速排序、簡單插入排序、簡單選擇排序需要的比較次數(shù)為O(n2)；希爾排序需要的比較次數(shù)為O(n1.5)；堆排序需要的比較次數(shù)為O(nlog2n)；順序查找需要的比較次數(shù)為O(n)次；二分法查找需要的比較次數(shù)為O(log2n)，故本題答案為D。137.某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=10,rear=5。該隊(duì)列中的元素個數(shù)為（

）。A.4B.不確定C.5D.6答案：B解析：解析：在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點(diǎn)有兩部分組成，一部分為數(shù)據(jù)域，一部分為指針域，當(dāng)front=rear時可判斷只有一個元素，其他情況無法判斷。故本題答案為B。138.某二叉樹的前序序列