（1）對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n－1)/2的排序方法是:

【堆排序】

*編者注：各種排序方法中最壞情況下需要比較的次數(shù)分別為：冒泡排序n(n-1)/2、快速排序n(n-1)/2、簡單插入排序n(n-1)/2、希爾排序O(n1.5)、簡單選擇排序n(n-1)/2、堆排序O(nlog2n)。

（2）下列關(guān)于棧的敘述正確的是:

【棧按“先進(jìn)后出”組織數(shù)據(jù)】

*編者注：棧是限定在一端進(jìn)行插入和刪除的線性表，允許進(jìn)行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。

（3）某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是:

【6】

*編者注：根據(jù)二叉樹的性質(zhì)，在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。

（4）下列敘述中正確的是:

【算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度】

（5）下列敘述中正確的是:

【循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同指定】

（6）在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是:

【O（log2n）】

（7）下列敘述中正確的是:

【順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的】

（8）對于循環(huán)隊(duì)列，下列敘述中正確的是:

【隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針】

（9）算法的空間復(fù)雜度是指:

【算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間】

（10）一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是:

【EDCBA54321】

*編者注：棧組織數(shù)據(jù)的方式是“先進(jìn)后出”。

（11）支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是:

【棧】

*編者注：在主函數(shù)調(diào)用子函數(shù)時(shí)，要首先保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，把子函數(shù)的運(yùn)行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時(shí)的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點(diǎn)。

（12）算法的有窮性是指:

【算法程序的運(yùn)行時(shí)間是有限的】

（13）下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是:

【二叉樹】

（14）下列敘述中正確的是:

【有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)】

（15）下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是:

【?！?/p>

*編者注：“先進(jìn)后出”（FILO），“后進(jìn)先出”（LIFO）。

（16）下列敘述中正確的是:

【線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)】

（17）下列敘述中正確的是:

【棧和隊(duì)列都是線性結(jié)構(gòu)】

（18）一棵完全二叉樹共有360個(gè)結(jié)點(diǎn)，則在該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為:

【1】

*編者注：對于一個(gè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為[log2n]+1。本題中這個(gè)二叉樹的深度為[log2360]+1=8+1=9。根據(jù)滿二叉樹的性質(zhì)，深度為8的滿二叉樹其結(jié)點(diǎn)數(shù)為256-1=255。這個(gè)完全二叉樹的第9層的結(jié)點(diǎn)數(shù)為360-255=105。完全二叉樹的性質(zhì)非葉子結(jié)點(diǎn)的子結(jié)點(diǎn)都為2，105除以2其商為52余數(shù)為1。

（19）算法的時(shí)間復(fù)雜度是指:

【執(zhí)行該算法時(shí)所需要的基本運(yùn)算次數(shù)】

（20）下列關(guān)于棧敘述正確的是:

【棧頂元素最先能被刪除】

（21）下列敘述中正確的是:

【在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化】

（22）某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為（假設(shè)根結(jié)點(diǎn)在第1層）:

【7】

*編者注：根據(jù)二叉樹的性質(zhì)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0。

（23）設(shè)循環(huán)隊(duì)列存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列入隊(duì)和退隊(duì)操作后，front=rear=25，則該循環(huán)隊(duì)列中元素個(gè)數(shù)為:

【0或50】

*編者注：在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置。因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素為隊(duì)列中的元素。在循環(huán)隊(duì)列動(dòng)態(tài)變化過程中，當(dāng)循環(huán)隊(duì)列滿時(shí)有front=rear，而當(dāng)循環(huán)隊(duì)列空時(shí)也有front=rear。

（24）下列敘述中正確的是:

【設(shè)計(jì)算法時(shí)要考慮時(shí)間復(fù)雜度和空間復(fù)雜度】

（25）下列敘述中正確的是:

【只有一個(gè)根節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)】

*編者注：樹這類的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)根結(jié)點(diǎn)，但它不是線性結(jié)構(gòu)。

（26）下列關(guān)于二叉樹的敘述中，正確的是:

【葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)】

（27）下列各組的排序方法中，最壞情況下比較次數(shù)相同的是:

【冒泡排序和快速排序】

*編者注：壞情況下冒泡排序需要比較n(n-1)/2次，即序列逆序的情況?？焖倥判颍顗那闆r退化為冒泡排序，需要比較n(n-1)/2次。

（28）下列敘述中正確的是:

【循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)】

（29）下列關(guān)于線性鏈表的敘述中，正確的是:

【進(jìn)行插入或刪除時(shí)，不需要移動(dòng)表中的元素】

（30）一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為:

【16】

*編者注：度為1的結(jié)點(diǎn)個(gè)數(shù)=總結(jié)點(diǎn)數(shù)-葉子節(jié)點(diǎn)數(shù)-度為2的節(jié)點(diǎn)數(shù)=25-5-4=16。

（31）設(shè)循環(huán)隊(duì)列存儲(chǔ)空間為Q(1:50)。初始狀態(tài)為front=rear=50。經(jīng)過一系列入隊(duì)和退隊(duì)操作后，front=14，rear=19，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為:

【5】

（32）下列鏈表中，其邏輯結(jié)構(gòu)屬于非線性結(jié)構(gòu)的是:

【二叉鏈表】

（33）設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:35)，初始狀態(tài)為front=rear=35。現(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=15，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為:

【0或35】

（34）設(shè)二叉樹共有150個(gè)結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有10個(gè)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為:

【不可能有這樣的二叉樹】

*編者注：在任意一顆二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。即有n0=n2+1。這題中度為2的結(jié)點(diǎn)個(gè)數(shù)無法確定。

（35）下列敘述中正確的是:

【程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)】

（36）下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是:

【先到先服務(wù)的作業(yè)調(diào)度】

*編者注：隊(duì)列中最先插入的元素將最先被刪除，最后插入的元素將最后被刪除。

（37）對如下圖所示的二叉樹進(jìn)行前序遍歷的結(jié)果為:

【ABDYECFXZ】

（38）下列敘述中正確的是:

【算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系】

（39）一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為:

【229】

*編者注：在任意二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)，故總結(jié)點(diǎn)數(shù)=葉子節(jié)點(diǎn)數(shù)+度為2的節(jié)點(diǎn)數(shù)+度為1的節(jié)點(diǎn)數(shù)=80+79+70=229。

（40）對長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為:

【45】

*編者注：最壞情況下冒泡排序需要比較的次數(shù)為n(n-1)/2。

（41）下列敘述中正確的是:

【算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量】

（42）下列敘述中正確的是:

【線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的】

（43）某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為（根結(jié)點(diǎn)在第1層）:

【12】

*編者注：題目中的二叉樹的葉子結(jié)點(diǎn)為1，因此度為2的結(jié)點(diǎn)的數(shù)目為0，故該二叉樹為12層，每層只有一個(gè)結(jié)點(diǎn)。

（44）對長度為n的線性表作快速排序，在最壞情況下，比較次數(shù)為:

【n(n-1)/2】

（45）下列敘述中正確的是:

【有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)】

*編者注：具有一個(gè)根節(jié)點(diǎn)的樹。

（46）下列敘述中錯(cuò)誤的是:

【在線性單鏈表中，可以從任何一個(gè)結(jié)點(diǎn)開始直接遍歷到所有結(jié)點(diǎn)】

*編者注：對線性隊(duì)列的遍歷只能從隊(duì)列的頭開始，從中間的結(jié)點(diǎn)開始不能夠遍歷到所有的結(jié)點(diǎn)。

（47）某二叉樹共有13個(gè)結(jié)點(diǎn)，其中有4個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為:

【5】

（48）設(shè)棧的順序存儲(chǔ)空間為S(1:50)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列入棧與退棧運(yùn)算后，top=20，則當(dāng)前棧中的元素個(gè)數(shù)為:

【20】

*編者注：通常用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。對棧的操作有入棧和退棧兩種。入棧運(yùn)算：首先將棧頂指針進(jìn)一（即top+1），然后將新元素插入到棧頂指針指向的位置。退棧運(yùn)算：首先將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針退一（即top-1）。

（49）下列敘述中正確的是:

【循環(huán)隊(duì)列是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)】

（50）設(shè)某二叉樹的前序序列為ABC，中序序列為CBA，則該二叉樹的后序序列為:

【CBA】

*編者注：二叉樹的前序遍歷的順序?yàn)槭紫仍L問根結(jié)點(diǎn)，再依次訪問左結(jié)點(diǎn)和右結(jié)點(diǎn)。中序遍歷的順序?yàn)槭紫仍L問左結(jié)點(diǎn)，然后依次訪問根結(jié)點(diǎn)和右結(jié)點(diǎn)。后序遍歷的順序?yàn)槭紫仍L問左結(jié)點(diǎn)，然后依次訪問右結(jié)點(diǎn)和根結(jié)點(diǎn)。

（51）下列排序方法中，最壞情況下時(shí)間復(fù)雜度最小的是:

【堆排序】

*編者注：

（52）為了對有序表進(jìn)行對分查找，則要求有序表:

【只能順序存儲(chǔ)】

（53）下列敘述中正確的是:

【帶鏈的棧和隊(duì)列是線性結(jié)構(gòu)】

（54）算法時(shí)間復(fù)雜度的度量方法是:

【執(zhí)行算法所需要的基本運(yùn)算次數(shù)】

（55）在最壞情況下:

【希爾排序的時(shí)間復(fù)雜度比直接插入排序的時(shí)間復(fù)雜度要小】

（56）在深度為7的滿二叉樹中，度為2的結(jié)點(diǎn)個(gè)數(shù)為:

【63】

（57）設(shè)棧的順序存儲(chǔ)空間為S(1:m)，初始狀態(tài)為top=m+1。現(xiàn)經(jīng)過一系列入棧與退棧運(yùn)算后，top=20，則當(dāng)前棧中的元素個(gè)數(shù)為:

【m-19】

*編者注：TOP指針指向m+1-2=m-1；......；以此類推，當(dāng)壓入第N個(gè)元素時(shí)，TOP指針指向m+1-N=20；則N=m+1-20=m-19。

（58）算法空間復(fù)雜度的度量方法是:

【執(zhí)行算法所需要的存儲(chǔ)空間】

（59）設(shè)循環(huán)隊(duì)列為Q(1:m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15，rear=20?，F(xiàn)要在該循環(huán)隊(duì)列中尋找最大值的元素，最壞情況下需要比較的次數(shù)為:

【4】

*編者注：此時(shí)隊(duì)列中有5個(gè)元素，而查找最大項(xiàng)至少要比較n-1次，就是4次。

（60）下列敘述中正確的是:

【有的非線性結(jié)構(gòu)也可以采用順序存儲(chǔ)結(jié)構(gòu)】

（61）某二叉樹中有n個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)數(shù)為:

【n-1】

（62）設(shè)棧的順序存儲(chǔ)空間為S(0:49)，棧底指針bottom=49，棧頂指針top=30（指向棧頂元素）。則棧中的元素個(gè)數(shù)為:

【20】

*編者注：棧中的元素個(gè)數(shù)為：棧底-棧頂+1=49-30+1=20。

（63）某二叉樹的前序序列為ABCDEFG，中序序列為DCBAEFG，則該二叉樹的深度（根結(jié)點(diǎn)在第1層）為:

【4】

（64）下列敘述中正確的是:

【具有兩個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)】

（65）下列敘述中正確的是:

【帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，且隊(duì)頭指針可以大于也可以小于隊(duì)尾指針】

（66）設(shè)循環(huán)隊(duì)列為Q(1:m)，其初始狀態(tài)為front=rear=m。經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=20，rear=15?，F(xiàn)要在該循環(huán)隊(duì)列中尋找最小值的元素，最壞情況下需要比較的次數(shù)為:

【m-6】

*編者注：在循環(huán)隊(duì)列中元素的個(gè)數(shù)為“(rear-front+M)%M”，式中rear為隊(duì)尾指針，front為隊(duì)首指針，M為存儲(chǔ)容量，%為取余符號。對于找最小值的最壞情況下的比較次數(shù)，為循環(huán)隊(duì)列中元素值個(gè)數(shù)減1。

（67）下列敘述中正確的是:

【在鏈表中，如果有兩個(gè)結(jié)點(diǎn)的同一個(gè)指針域的值相等，則該鏈表一定是非線性結(jié)構(gòu)】

（68）下列敘述中錯(cuò)誤的是:

【在帶鏈棧中，棧頂指針和棧底指針都是在動(dòng)態(tài)變化的】

*編者注：在帶鏈棧中，棧頂指針是在動(dòng)態(tài)變化的，但棧底指針是不變的。

（69）設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}，則滿足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是:

【R={(1,3),(4,1),(3,2),(5,4)}】

（70）下列敘述中正確的是:

【鏈表結(jié)點(diǎn)中具有兩個(gè)指針域的數(shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)】

*編者注：例如雙向鏈表就具有兩個(gè)指針，也屬于線性結(jié)構(gòu)。

（71）個(gè)棧的初始狀態(tài)為空，現(xiàn)將元素A、B、C、D、E依次入棧，然后依次退棧三次，并將退棧的三個(gè)元素依次入隊(duì)（原隊(duì)列為空），最后將隊(duì)列中的元素全部退出。則元素退隊(duì)的順序?yàn)?

【EDC】

（72）下列敘述中正確的是:

【程序可以做為算法的一種描述方法】

（73）下列各序列中不是堆的是:

【(47,91,53,85,30,12,24,36)】

（74）深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是:

【15】

*編者注：滿二叉樹的結(jié)點(diǎn)數(shù)為2^(5-1)=16。

（75）有二叉樹如下圖所示，則前序序列為:

【ABDEGCFH】

（76）下列敘述中正確的是:

【沒有根結(jié)點(diǎn)或沒有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)】

（77）下列關(guān)于算法的描述中錯(cuò)誤的是:

【算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境】

*編者注：算法的優(yōu)劣取決自身的運(yùn)行效率，時(shí)間和空間復(fù)雜度高低，并不取決于運(yùn)行算法程序的環(huán)境。

（78）設(shè)有二叉樹如下圖所示，則中序序列為:

【DBGEAFHC】

（79）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)有:

【插入和刪除運(yùn)算效率高】

（80）深度為7的完全二叉樹中共有125個(gè)結(jié)點(diǎn)，則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為:

【63】

（81）下列敘述中正確的是:

【有序表可以用鏈接存儲(chǔ)方式存儲(chǔ)在不連續(xù)的存儲(chǔ)空間內(nèi)】

（82）設(shè)有二叉樹如下圖所示，則后序序列為:

【DGEBHFCA】

（83）帶鏈的棧與順序存儲(chǔ)的棧相比，其優(yōu)點(diǎn)是:

【入棧操作時(shí)不會(huì)受棧存儲(chǔ)空間的限制而發(fā)生溢出】

（84）某二叉樹的前序序列為ABCD，中序序列為DCBA，則后序序列為:

【DCBA】

（85）下列敘述中正確的是:

【算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)】

（86）某二叉樹共有399個(gè)結(jié)點(diǎn)，其中有199個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為:

【200】

（87）在長度為n的順序表中查找一個(gè)元素，假設(shè)需要查找的元素一定在表中，并且元素出現(xiàn)在表中每個(gè)位置上的可能性是相同的，則在平均情況下需要比較的次數(shù)為:

【(n+1)/2】

（88）設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值，而右子樹上的結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是:

【中序序列】

（89）循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25，此后又插入一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為:

【1或50且產(chǎn)生上溢錯(cuò)誤】

（90）下列算法中均以比較作為基本運(yùn)算，則平均情況與最壞情況下的時(shí)間復(fù)雜度相同的是:

【在順序存儲(chǔ)的線性表中尋找最大項(xiàng)】

（91）在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為:

【n】

（92）下列敘述中正確的是:

【在棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)】

（93）循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:40)，初始狀態(tài)為front=rear=40。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=15，此后又退出一個(gè)元素，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為:

【39或0且產(chǎn)生下溢錯(cuò)誤】

（94）某二叉樹的中序遍歷序列為CBADE，后序遍歷序列為CBADE，則前序遍歷序列為:

【EDABC】

（95）在長度為n的順序表中查找一個(gè)元素，假設(shè)需要查找的元素有一半的機(jī)會(huì)在表中，并且如果元素在表中，則出現(xiàn)在表中每個(gè)位置上的可能性是相同的。則在平均情況下需要比較的次數(shù)大約為:

【(3+n)/4】

*編者注：在平均情況下需要比較的次數(shù)大約為((1+n)/2+1)/2=(3＋n)/4。

（96）設(shè)一棵樹的度為3，其中度為3，2，1的結(jié)點(diǎn)個(gè)數(shù)分別為4，1，3。則該棵樹中的葉子結(jié)點(diǎn)數(shù)為:

【10】

*編者注：任一棵樹中,結(jié)點(diǎn)總數(shù)＝總分支數(shù)目＋1。

（97）設(shè)棧的存儲(chǔ)空間為S(1:50)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=51，則棧中的元素個(gè)數(shù)為:

【不可能】

*編者注：此時(shí)發(fā)生下溢錯(cuò)誤。

（98）設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)等于n(n-1)/2的是:

【快速排序】

（99）設(shè)表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是:

【二分查找法】

（100）下列敘述中錯(cuò)誤的是:

【循環(huán)鏈表是循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)】

*編者注：循環(huán)隊(duì)列屬于邏輯結(jié)構(gòu)，其實(shí)質(zhì)還是順序存儲(chǔ)，只是使用指針進(jìn)行首尾的聯(lián)結(jié)，其實(shí)現(xiàn)的存儲(chǔ)方式可分為：分散的鏈表和連續(xù)的線性表，與其邏輯結(jié)構(gòu)實(shí)現(xiàn)功能無關(guān)。

（101）設(shè)一棵樹的度為4，其中度為4，3，2，1的結(jié)點(diǎn)個(gè)數(shù)分別為2，3，3，0。則該棵樹中的葉子結(jié)點(diǎn)數(shù)為:

【16】

（102）設(shè)順序表的長度為n。下列算法中，最壞情況下比較次數(shù)小于n的是:

【尋找最大項(xiàng)】

（103）設(shè)棧的順序存儲(chǔ)空間為S(1:m)，初始狀態(tài)為top=m+1?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=0，則棧中的元素個(gè)數(shù)為:

【不可能】

*編者注：top的值在棧滿時(shí)最小，為1。

（104）某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出（同一層從左到右）的序列為:

【FEDCBA】

（105）設(shè)棧的順序存儲(chǔ)空間為S(1:m)，初始狀態(tài)為top=0?，F(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個(gè)數(shù)為:

【不可能】

*編者注：第一個(gè)元素入棧即發(fā)生下溢錯(cuò)誤。

（106）下列敘述中正確的是:

【對數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)會(huì)降低算法的空間復(fù)雜度】

（107）設(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)為:

【非線性結(jié)構(gòu)】

*編者注：結(jié)構(gòu)中的各結(jié)點(diǎn)之間形成一個(gè)循環(huán)鏈。

（108）下列排序法中，每經(jīng)過一次元素的交換會(huì)產(chǎn)生新的逆序的是:

【快速排序】

（109）某帶鏈的隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=10。該隊(duì)列中的元素個(gè)數(shù)為:

【1】

*編者注：循環(huán)隊(duì)列用數(shù)組A[0;m-1]存放其元素值，已知其頭尾指針分別是front和rear。

（110）某完全二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該完全二叉樹的前序序列為:

【ABDHECFG】

（111）下列敘述中正確的是:

【有的二叉樹也能用順序存儲(chǔ)結(jié)構(gòu)表示】

（112）某帶鏈隊(duì)列初始狀態(tài)為front=rear=NULL。經(jīng)過一系列正常入隊(duì)與退隊(duì)操作后，front=10，rear=5。該隊(duì)列中的元素個(gè)數(shù)為:

【不確定】

（113）某帶鏈棧初始狀態(tài)為top=bottom=NULL，經(jīng)過一系列正常的入棧與退棧操作后，top=10，bottom=20。該棧中的元素個(gè)數(shù)為:

【不確定】

*編者注：對于鏈棧而言，使用了鏈表來實(shí)現(xiàn)棧，鏈表中的元素存儲(chǔ)在不連續(xù)的地址。

（114）設(shè)表的長度為15。則在最壞情況下，快速排序所需要的比較次數(shù)為:

【105】

（115）設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:100)，初始狀態(tài)為空。現(xiàn)經(jīng)過一系列正常操作后，front=49，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為:

【不確定】

*編者注：rear的值未知。

（116）下列敘述中正確的是:

【解決一個(gè)問題可以有不同的算法，且它們的時(shí)間復(fù)雜度可以是不同的】

（117）設(shè)表的長度為n。下列查找算法中，在最壞情況下，比較次數(shù)最少的是:

【有序表的二分查找】

（118）下列敘述中錯(cuò)誤的是:

【算法的時(shí)間復(fù)雜度與問題規(guī)模無關(guān)】

（119）設(shè)表的長度為20。則在最壞情況下，冒泡排序的比較次數(shù)為:

【190】

（120）在帶鏈棧中，經(jīng)過一系列正常的操作后，如果top=bottom，則棧中的元素個(gè)數(shù)為:

【0或1】

*編者注：鏈棧就是沒有附加頭結(jié)點(diǎn)的、運(yùn)算受限的單鏈表。

（121）設(shè)一棵樹的度為3，共有27個(gè)結(jié)點(diǎn)，其中度為3，2，0的結(jié)點(diǎn)數(shù)分別為4，1，10。該樹中度為1的結(jié)點(diǎn)數(shù)為:

【12】

（122）設(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)為:

【線性結(jié)構(gòu)】

（123）下列敘述中錯(cuò)誤的是:

【循環(huán)隊(duì)列空的條件是隊(duì)頭指針和隊(duì)尾指針相同】

*編者注：初始化建空隊(duì)時(shí)，令front=rear=0，當(dāng)隊(duì)空時(shí)：front=rear；當(dāng)隊(duì)滿時(shí)：front=rear也成立。

（124）帶鏈?？盏臈l件是:

【top=bottom=NULL】

（125）設(shè)一棵度為3的樹，其中度為2，1，0的結(jié)點(diǎn)數(shù)分別為3，1，6。該樹中度為3的結(jié)點(diǎn)數(shù)為:

【1】

（126）下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲(chǔ)結(jié)構(gòu)的是:

【非完全二叉樹】

（127）設(shè)二叉樹共有375個(gè)結(jié)點(diǎn)，其中度為2的結(jié)點(diǎn)有187個(gè)。則度為1的結(jié)點(diǎn)個(gè)數(shù)是:

【0】

（128）設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為5。該樹中度為3的結(jié)點(diǎn)數(shù)為:

【2】

（129）設(shè)二叉樹共有500個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)有250個(gè)。則度為2的結(jié)點(diǎn)個(gè)數(shù)是:

【249】

（130）下列敘述中正確的是:

【帶鏈棧的棧底指針是隨棧的操作而動(dòng)態(tài)變化的】

（131）設(shè)一棵樹的度為3，其中沒有度為2的結(jié)點(diǎn)，且葉子結(jié)點(diǎn)數(shù)為6。該樹中度為3的結(jié)點(diǎn)數(shù)為:

【不可能有這樣的樹】

（132）下列敘述中正確的是:

【循環(huán)隊(duì)列是線性結(jié)構(gòu)】

（133）設(shè)某棵樹的度為3，其中度為3、2、1的結(jié)點(diǎn)個(gè)數(shù)分別為3、0、4。則該樹中的葉子結(jié)點(diǎn)數(shù)為:

【7】

（134）設(shè)有一個(gè)棧與一個(gè)隊(duì)列的初始狀態(tài)均為空?，F(xiàn)有一個(gè)序列A,B,C,D,E,F,G,H。先分別將序列中的前4個(gè)元素依次入棧，后4個(gè)元素依次入隊(duì)；然后分別將棧中的元素依次退棧，再將隊(duì)列中的元素依次退隊(duì)。最后得到的序列為:

【DCBAEFGH】

（135）下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)的是:

【雙向鏈表】

（136）度為3的一棵樹共有30個(gè)結(jié)點(diǎn)，其中度為3、1的結(jié)點(diǎn)個(gè)數(shù)分別為3、4。則該樹中的葉子結(jié)點(diǎn)數(shù)為:

【15】

（137）在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為:

【7】

（138）下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是:

【二維數(shù)組】

*編者注：線性結(jié)構(gòu)是一個(gè)有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊(duì)列，雙隊(duì)列，數(shù)組，串；常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹（二叉樹等），圖。

（139）從表中任何一個(gè)結(jié)點(diǎn)位置出發(fā)就可以不重復(fù)地訪問到表中其他所有結(jié)點(diǎn)的鏈表是:

【循環(huán)鏈表】

（140）設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為:

【HGFEDCBA】

（141）設(shè)某棵樹的度為3，其中度為3、1、0的結(jié)點(diǎn)個(gè)數(shù)分別為3、4、15。則該樹中總結(jié)點(diǎn)數(shù)為:

【30】

（142）下列敘述中正確的是:

【數(shù)組的長度固定的線性表】

（143）在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換（或移動(dòng)）后:

【能消除多個(gè)逆序】

*編者注：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

（144）在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后:

【能消除多個(gè)逆序】

（145）下列敘述中正確的是:

【所有的線性結(jié)構(gòu)都能采用順序存儲(chǔ)結(jié)構(gòu)】

（146）設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出（從上到下，同一層從左到右）的序列為:

【ABCDEFGHIJ】

（147）設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front-1=rear。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為:

【48】

（148）設(shè)順序表的長度為40，對該表進(jìn)行冒泡排序。在最壞情況下需要的比較次數(shù)為:

【780】

（149）設(shè)表的長度為n。在下列算法中，最壞情況下時(shí)間復(fù)雜度最高的是:

【希爾排序】

（150）設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear-1。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為:

【0】

*編者注：front指定隊(duì)頭位置，刪除一個(gè)元素就將front順時(shí)針移動(dòng)一位；rear指尾指針，指向元素要插入的位置，插入一個(gè)元素就將rear順時(shí)針移動(dòng)一位；操作后，循環(huán)隊(duì)列的隊(duì)頭指針等于尾指針-1，說明此時(shí)隊(duì)列已經(jīng)是空隊(duì)列。

（151）設(shè)順序表的長度為16，對該表進(jìn)行簡單插入排序。在最壞情況下需要的比較次數(shù)為:

【120】

（152）下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是:

【樹】

（153）設(shè)表的長度為n。在下列結(jié)構(gòu)所對應(yīng)的算法中，最壞情況下時(shí)間復(fù)雜度最低的是:

【循環(huán)鏈表中尋找最大項(xiàng)】

（154）設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:m)，初始狀態(tài)為front=rear=m。經(jīng)過一系列正常的操作后，front=1，rear=m。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為:

【m-2】

（155）某完全二叉樹有256個(gè)結(jié)點(diǎn)，則該二叉樹的深度為

【9】

（156）循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=rear=25。后又成功地將一個(gè)元素退隊(duì)，此時(shí)隊(duì)列中的元素個(gè)數(shù)為：

【49】

（157）設(shè)二叉樹中有20個(gè)葉子結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為：

【44】

（158）設(shè)棧與隊(duì)列初始狀態(tài)為空。首先A,B,C,D,E依次入棧，再F,G,H,I,J依次入隊(duì)；然后依次退隊(duì)至隊(duì)空，再依次出棧至?？铡t輸出序列為：

【FGHIJEDCBA】

（159）樹的度為3，且有9個(gè)度為3的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，但沒有度為2的結(jié)點(diǎn)。則該樹總的結(jié)點(diǎn)數(shù)為：

【33】

（160）設(shè)二叉樹的中序序列為BCDA，前序序列為ABCD，則后序序列為：

【DCBA】

（161）樹的度為3，且有9個(gè)度為3的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，但沒有度為2的結(jié)點(diǎn)。則該樹中的葉子結(jié)點(diǎn)數(shù)為：

【19】

（162）下列敘述中正確的是：

【循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)】

（163）下列算法中，最壞情況下時(shí)間復(fù)雜度最低的是：

【有序表的對分查找】

（164）對長度為8的數(shù)組進(jìn)行快速排序，最多需要的比較次數(shù)為：

【28】

（165）設(shè)線性表的長度為12。最壞情況下冒泡排序需要的比較次數(shù)為：

【66】

（166）循環(huán)隊(duì)列的存儲(chǔ)空間為Q(0:59)，初始狀態(tài)為空。經(jīng)過一系列正常的入隊(duì)與退隊(duì)操作后，front=25，rear=24。循環(huán)隊(duì)列中的元素個(gè)數(shù)為：

【59】