數(shù)據(jù)結(jié)構(gòu)必過復(fù)習(xí)測試附答案

第頁數(shù)據(jù)結(jié)構(gòu)必過復(fù)習(xí)測試附答案1.32.以下（）方法可用于求無向圖的連通分量。A、遍歷B、拓?fù)渑判駽、Dijkstra算法D、Prim算法【正確答案】：A解析：

從圖中某個頂點出發(fā)進行遍歷，可將與該頂點相連通的所有頂點全部訪問，也就找到了該頂點所在的連通分量。2.1.線性表是具有n個（）的有限序列。A、表元素B、字符C、數(shù)據(jù)元素D、數(shù)據(jù)項【正確答案】：C解析：

線性表是具有n（n≥0）個數(shù)據(jù)元素的有限序列，本題答案為C。3.27.n個頂點的連通圖的生成樹有（）個頂點。A、n-1B、nC、n+1D、不確定【正確答案】：B4.次探測。A、k-1B、kC、k+1D、k(k+1)/2【正確答案】：D解析：

最少探測的情況是，第一個同義詞放在哈希表ha[d]位置，探測1次，第2個同義詞放在哈希表ha[d+1]位置，探測2次，以此類推，第k個同義詞放在哈希表ha[d+k-1]位置，探測k次，總的探測次數(shù)=1+2+…+k=k(k+1)/2?！菊_答案】：為D。5.8.順序表具有隨機存取特性，指的是（）。A、查找值為x的元素與順序表中元素個數(shù)n無關(guān)B、查找值為x的元素與順序表中元素個數(shù)n有關(guān)C、查找序號為i的元素與順序表中元素個數(shù)n無關(guān)D、查找序號為i的元素與順序表中元素個數(shù)n有關(guān)【正確答案】：C解析：

一種存儲結(jié)構(gòu)具有隨機存取特性指的是，對于給定的序號i，在O(1)時間內(nèi)找到對應(yīng)元素值。6.的數(shù)據(jù)結(jié)構(gòu)為（）。A、數(shù)組B、樹C、圖D、線性表【正確答案】：B7.26.樹最適合用來表示（）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)【正確答案】：C8.結(jié)點。A、1+2b+3cB、a+2b+3cC、2b+3cD、1+b+2c【正確答案】：D9.14.對于不帶權(quán)無向圖的鄰接矩陣來說，()_。A、第i行上、第i列上非零元素總數(shù)等于頂點i的度數(shù)B、矩陣中的非零元素個數(shù)等于圖中的邊數(shù)C、第i行上的非零元素個數(shù)和第i列的非零元素個數(shù)一定相等D、鄰接矩陣中非全零行的行數(shù)等于圖中的頂點數(shù)【正確答案】：C解析：

無向圖的鄰接矩陣是一個對稱矩陣。【正確答案】：為C。10.樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是（）。A、LRNB、NRLC、RLND、RNL【正確答案】：D11.26.給定一個足夠大的空棧，有4個元素的進棧次序為A、B、C、D，則以C、D開頭的出棧序列的個數(shù)為（）。A、1B、2C、3D、4【正確答案】：A解析：

若出棧序列為CD…，則A、B、C進棧，C出棧，D進棧，D出棧，此后只有B出棧和A出棧一種情況，所以這樣的出棧序列只有CDBA一個。12.≤i≤m）。一個結(jié)點的子樹個數(shù)為該結(jié)點的次數(shù)（或度）。A、有0個或1個B、有0個或多個C、有且只有1個D、有1個或1個以上【正確答案】：A13.15.在一個雙鏈表中，刪除p所指結(jié)點（非首、尾結(jié)點）的操作是()。A、p.prior.next=p.next;p.next.prior=p.priorB、p.prior=p.prior.prior;p.prior.prior=pC、p.next.prior=p;p.next=p.next.nextD、p.next=p.prior.prior;p.prior=p.prior.prior【正確答案】：A解析：

在雙鏈表中刪除結(jié)點p的過程如圖A.24所示，訪問兩步（順序可以任意），答案為A。14.移方式是（）。A、i=next[j]B、i不變C、j不變D、j=next[j]【正確答案】：B解析：

在KMP算法中，當(dāng)tj≠si時，i位置不改變。15.（）。A、冒泡排序B、希爾排序C、歸并排序D、基數(shù)排序【正確答案】：A16.19.下面關(guān)于串的敘述中，正確的是（）。A、串是一種特殊的線性表B、串中元素只能是字母C、空串就是空白串D、串的長度必須大于零【正確答案】：A17.14.數(shù)據(jù)結(jié)構(gòu)通常采用二元組表示：B=(D,R)，其中D表示（）的集合。A、數(shù)據(jù)項B、數(shù)據(jù)元素C、數(shù)據(jù)元素關(guān)系D、數(shù)據(jù)類型【正確答案】：B解析：

二元組(D,R)是數(shù)據(jù)邏輯結(jié)構(gòu)的一種通用描述方法，其中D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)元素關(guān)系的集合，在D上可以多種關(guān)系，每個關(guān)系用序偶來表示。18.58.以下關(guān)于排序的敘述中正確的是（）。A、穩(wěn)定的排序方法優(yōu)于不穩(wěn)定的排序方法，因為穩(wěn)定的排序方法效率較高B、對同一個順序表使用不同的排序方法進行排序，得到的排序結(jié)果可能不同C、排序方法都是在順序表上實現(xiàn)的，在鏈表上無法實現(xiàn)排序方法D、在順序表上實現(xiàn)的排序方法在鏈表上也可以實現(xiàn)【正確答案】：B解析：

穩(wěn)定的排序方法的效率不一定都比不穩(wěn)定的排序方法高。有些排序方法既可以上順序表上實現(xiàn)，也可以在鏈表上實現(xiàn)，但不是所有的排序方法都如此。由于排序方法具有不同的穩(wěn)定性，所以對同一個順序表使用不同的排序方法進行排序，得到的排序結(jié)果可能不同。19.16.設(shè)一棵哈夫曼樹中有1999個結(jié)點，該哈夫曼樹用于對（）個字符進行編碼。A、999B、998C、1000D、1001【正確答案】：C20.36.以下敘述中錯誤的是（）。A、圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次B、圖的深度優(yōu)先遍歷適合無向圖C、圖的深度優(yōu)先遍歷不適合有向圖D、圖的深度優(yōu)先遍歷是一個遞歸過程【正確答案】：C解析：

圖的深度優(yōu)先遍歷算法既適合無向圖也適合有向圖的遍歷。21.8.一個稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲相比會失去（）特性。A、順序存儲B、隨機存取C、輸入輸出D、以上都不對【正確答案】：B解析：

稀疏矩陣采用三元組或者十字鏈表壓縮后均不再具有隨機存取特性。22.38.以下關(guān)于二叉樹遍歷的說法中，錯誤的是（）。A、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則先序和后序序列相同B、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則中序和后序序列相同C、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則先序和層次序列相同D、一棵二叉樹中，若每個結(jié)點最多只有右孩子，沒有左孩子，則先序和中序序列相同【正確答案】：A23.20.關(guān)于串的的敘述，不正確的是（）。A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、替換是串的一種重要運算D、串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Α菊_答案】：B24.32.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹就是度為2的樹B、二叉樹中不存在度大于2的結(jié)點C、二叉樹就是有序樹D、二叉樹中每個結(jié)點的度都為2【正確答案】：B25.排序確定A、外排序所花時間=內(nèi)排序時間+外存信息讀寫時間+內(nèi)部歸并所花時間B、外排序并不涉及文件的讀寫操作C、外排序完全可以由內(nèi)排序來替代【正確答案】：B解析：

外排序過程主要分為兩個階段：生成初始?xì)w并段和對初始?xì)w并段進行歸并，這兩個步驟中都涉及文件的讀寫操作。26.果是_（）__。A、0，1，2，3，4B、0，1，2，4，3C、0，1，3，4，2D、0，1，4，2，3【正確答案】：A解析：

直接從頂點0出發(fā)進行深度優(yōu)先遍歷，得到的DFS序列為0，1，2，3，4。【正確答案】：為A。27.22.對于AOE網(wǎng)的關(guān)鍵路徑，以下敘述（）是正確的。A、任何一個關(guān)鍵活動提前完成，則整個工程一定會提前完成B、完成整個工程的最短時間是從源點到匯點的最短路徑長度C、一個AOE網(wǎng)的關(guān)鍵路徑一定是唯一的D、任何一個活動持續(xù)時間的改變可能影響關(guān)鍵路徑的改變【正確答案】：D解析：

AOE網(wǎng)中的關(guān)鍵路徑是從源點到匯點的最長路徑，其長度為完成整個工程的最短時間。一個AOE網(wǎng)可能存在多條關(guān)鍵路徑，若提前完成所有關(guān)鍵路徑都包含的關(guān)鍵活動則整個工程一定會提前完成，但改變?nèi)魏我粋€活動的持續(xù)時間可能影響關(guān)鍵路徑的改變（因為此時關(guān)鍵路徑可能發(fā)生改變）。答案：為D。28.操作是（）。A、top+=1;s[top]=x;B、s[top]=x;top+=1C、top-=1;s[top]=x;D、s[top]=x;top-=1【正確答案】：C解析：

數(shù)組s的下標(biāo)為0～n-1，top的初始值為n，將s[n-1]一端作為棧底，進棧中元素向s[0]一端生長。在第一個元素x進棧時，先執(zhí)行top-=1，這樣top指向s的有效下標(biāo)，再執(zhí)行s[top]=x。【正確答案】：為C。29.28.在含有n個結(jié)點的二叉排序樹中查找某關(guān)鍵字的結(jié)點時，最多進行（）次比較。A、n/2B、log2nC、log2n+1D、n【正確答案】：D解析：

n個結(jié)點的二叉排序樹的高度可能為n。30.是（）的集合。A、序偶B、序列C、數(shù)據(jù)結(jié)構(gòu)D、數(shù)據(jù)類型【正確答案】：A解析：

二元組(D,R)是數(shù)據(jù)邏輯結(jié)構(gòu)的一種通用描述方法，其中D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)元素關(guān)系的集合，在D上可以多種關(guān)系，每個關(guān)系用序偶來表示。31.叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）。A、16B、15C、7D、17【正確答案】：B32.28.設(shè)有一棵哈夫曼樹的結(jié)點總數(shù)為35，則該哈夫曼樹共有（）個葉子結(jié)點。A、18B、20C、35D、30【正確答案】：A33.11.順序表和鏈表相比存儲密度較大，這是因為()。A、順序表的存儲空間是預(yù)先分配的B、順序表不需要增加指針來表示元素之間的邏輯關(guān)系C、鏈表中所有結(jié)點的地址是連續(xù)的D、順序表中所有元素的存儲地址是不連續(xù)的【正確答案】：B解析：

由于順序表中邏輯上相鄰的兩個元素在物理上也相鄰，不需要增加指針來表示元素之間的邏輯關(guān)系，所以存儲密度為1，而鏈表的存儲密度總是小于1。答案為B。34.隊頭元素的前一個位置，rear指向隊尾元素的位置），則其元素個數(shù)為（）。A、rear-frontB、rear-front-1C、(rear-front)％N+1D、(rear-front+N)％N【正確答案】：D解析：

在非循環(huán)隊列中rear總是跑在front的前面，其元素個數(shù)=rear-front，在循環(huán)隊列中rear可能比front多跑一圈，所以其元素個數(shù)=(rear-front+N)％N?！菊_答案】：為D。35.的A、采用拉鏈法解決沖突時容易引起堆積現(xiàn)象B、以上都不對【正確答案】：B解析：

若哈希地址為0～m-1，序號為i（0≤i≤m-1）的單鏈表中的結(jié)點個數(shù)可能有多個，這樣查找到任何一個關(guān)鍵字的結(jié)點的時間可能不同。拉鏈法解決沖突時不會出現(xiàn)堆積現(xiàn)象?！菊_答案】：為B。36.19.數(shù)據(jù)結(jié)構(gòu)通常采用二元組表示：B=(D,R)，其中R表示（）的集合。A、數(shù)據(jù)項B、數(shù)據(jù)元素C、數(shù)據(jù)元素關(guān)系D、數(shù)據(jù)類型【正確答案】：C解析：

二元組(D,R)是數(shù)據(jù)邏輯結(jié)構(gòu)的一種通用描述方法，其中D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)元素關(guān)系的集合，在D上可以多種關(guān)系，每個關(guān)系用序偶來表示。37.采用敗者樹進行，則總的關(guān)鍵字比較次數(shù)是（）（用時間復(fù)雜度表示）。A、log2m(u-1)(k-1)B、log2m(u-1)(k-1)/log2kC、log2m(u-1)D、log2m(k-1)【正確答案】：C38.22.查找效率低的數(shù)據(jù)結(jié)構(gòu)是（）。A、有序順序表B、二叉排序樹C、堆D、二叉平衡樹【正確答案】：C解析：

堆查找的時間復(fù)雜度為O(n)，所以效率最低。39.25.二叉排序中，最大關(guān)鍵字結(jié)點的（）。A、沒有左孩子結(jié)點B、沒有右孩子結(jié)點C、一定沒有左右孩子結(jié)點D、一定存在左右孩子結(jié)點【正確答案】：B解析：

在二叉排序中，最大關(guān)鍵字結(jié)點是中序序列的最后結(jié)點，即根結(jié)點的最右下結(jié)點。40.37.采用排序算法對n個元素進行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（）。A、直接插入和快速B、冒泡和快速C、簡單選擇和直接插入D、簡單選擇和冒泡【正確答案】：C解析：

簡單選擇和直接插入肯定要進行n-1趟排序，冒泡排序為1～n-1趟，快速排序為log2n～n-141.51.以下排序方法中，穩(wěn)定的排序方法是（）。A、快速排序B、堆排序C、希爾排序D、基數(shù)排序【正確答案】：D解析：

基數(shù)排序是一種穩(wěn)定的排序方法。42.24.靜態(tài)查找表和動態(tài)查找表的區(qū)別是（）。A、它們的邏輯結(jié)構(gòu)相同B、施加其上的操作不同C、所包含的數(shù)據(jù)元素的類型不同D、存儲實現(xiàn)不同【正確答案】：B解析：

由是否支持修改運算（或操作）來確定存放數(shù)據(jù)元素的表是靜態(tài)查找表還是動態(tài)查找表。43.13.數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容不涉及（）。A、數(shù)據(jù)如何組織B、數(shù)據(jù)如何存儲C、數(shù)據(jù)運算如何實現(xiàn)D、算法用什么語言來描述【正確答案】：D解析：

數(shù)據(jù)結(jié)構(gòu)涉及三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)（對應(yīng)選項A），數(shù)據(jù)的存儲結(jié)構(gòu)（對應(yīng)選項B）和運算（運算包括運算描述和運算實現(xiàn)，后者對應(yīng)選項C）。44.5.線性表的順序存儲結(jié)構(gòu)是一種（）。（1≤i≤n）的存儲地址為LOC(a0)+i×sizeof(ElemType)，也就是說，對于給定的序號i，在O(1)的A、隨機存取的存儲結(jié)構(gòu)B、順序存取的存儲結(jié)構(gòu)C、索引存取的存儲結(jié)構(gòu)D、散列存取的存儲結(jié)構(gòu)【正確答案】：A解析：

若含有n個元素的線性表a采用順序表存儲，每個元素的類型為ElemType，則第i個元素ai時間內(nèi)找到該元素值，這是一種隨機存取的存儲結(jié)構(gòu)。而順序存取是一種讀寫方式，不是存儲方式，有別于順序存儲。45.25.設(shè)一個棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是（）。A、5、1、2、3、4B、4、5、1、3、2C、4、3、1、2、5D、3、2、1、5、4【正確答案】：D解析：

只有選項D是合法輸出序列，其操作是：1進棧，2進棧，3進棧，3出棧，2出棧，1出棧，4進棧，5進棧，5出棧，4出棧。46.22.數(shù)據(jù)結(jié)構(gòu)課程中討論的數(shù)據(jù)一般具有內(nèi)在的聯(lián)系，這是指（）。A、數(shù)據(jù)和數(shù)據(jù)之間存在一種或多種特定關(guān)系B、數(shù)據(jù)元素和數(shù)據(jù)元素之間存在一種或多種特定關(guān)系C、數(shù)據(jù)項和數(shù)據(jù)項之間存在一種或多種特定關(guān)系D、同一數(shù)據(jù)中的所有數(shù)據(jù)元素值之間存在一種或多種特定關(guān)系【正確答案】：B解析：

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。47.6.算法的平均時間復(fù)雜度取決于（）。A、問題的規(guī)模B、待處理數(shù)據(jù)的初始狀態(tài)C、A和BD、計算機的配【正確答案】：A解析：

算法的時間復(fù)雜度分為最好、最壞和平均時間復(fù)雜度，最好和最壞時間復(fù)雜度是考慮若干種實例得到的結(jié)果，與初始狀態(tài)有關(guān)，而平均時間復(fù)雜度是考慮所有實例的結(jié)果，與初始狀態(tài)無關(guān)。答案為A。48.20.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A、哈希存儲B、順序存儲或鏈?zhǔn)酱鎯、壓縮存儲D、索引存儲【正確答案】：B解析：

順序查找可以從前向后或從后向前依次查找，既適合于順序存儲結(jié)構(gòu)也適合于鏈?zhǔn)酱鎯Y(jié)構(gòu)。49.16.哈希表中出現(xiàn)的哈希沖突是指()。A、兩個元素具有相同的序號B、兩個元素的關(guān)鍵字不同，而其他屬性相同C、數(shù)據(jù)元素過多D、兩個元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值相同【正確答案】：D解析：

哈希沖突也稱為同義詞沖突，是指兩個元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值相同?！菊_答案】：為D。50.10.由權(quán)值分別為9、2、7、5的4個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為_()。A、23B、44C、37D、27【正確答案】：B51.≤i≤m）。一個結(jié)點的子樹個數(shù)為該結(jié)點的次數(shù)（或度）。A、互不相交B、允許相交C、允許葉結(jié)點相交D、允許樹枝結(jié)點相交【正確答案】：A52.4.以下算法的時間復(fù)雜度為()。deffun(n):i,s=0,0whiles<=n:i+=1s+=iA、O(n)B、O(√nn)C、O(nloD、2n)E、O(loF、2n)【正確答案】：B解析：

設(shè)while循環(huán)執(zhí)行的次數(shù)為m，i從0開始，每次循環(huán)增加1，則s=1+2+…+m=m(m+1)/2≤n，可以推出m=O(n)。答案為B。53.18.高度為h（h>0）的滿二叉樹對應(yīng)的森林由（）棵樹構(gòu)成。A、1B、loC、2hD、h/2E、h【正確答案】：D54.55.下列排序方法中，輔助空間為O(n)的是（）。A、希爾選擇B、冒泡排序C、堆排序D、歸并排序【正確答案】：D解析：

這幾種排序方法中只有歸并排序的空間復(fù)雜度為O(n)，其余幾種排序方法的空間復(fù)雜度為O(1)。55.23.計算機所處理的數(shù)據(jù)一般具備某種內(nèi)在聯(lián)系，這是指（）。A、數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系B、元素和元素之間存在某種關(guān)系C、元素內(nèi)部具有某種結(jié)構(gòu)D、數(shù)據(jù)項和數(shù)據(jù)項之間存在某種關(guān)系【正確答案】：B解析：

數(shù)據(jù)結(jié)構(gòu)中討論的數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的，這些數(shù)據(jù)元素之間存在某種關(guān)系。56.33.哈希查找方法一般適用于（）情況下的查找。A、查找表為鏈表B、查找表為有序表C、關(guān)鍵字集合比地址集合大得多D、關(guān)鍵字集合與地址集合之間存在對應(yīng)關(guān)系【正確答案】：D解析：

關(guān)鍵字集合與地址集合之間存在對應(yīng)關(guān)系時，通過哈希函數(shù)表示這種關(guān)系，這樣查找以計算哈希函數(shù)而不是比較的方式進行查找。57.個數(shù)是()_。A、10B、nC、5D、2【正確答案】：A解析：

基數(shù)排序中隊列的個數(shù)僅與基數(shù)相關(guān)，這里基數(shù)為10?！菊_答案】：為A。58.速排序Ⅳ.二路歸并排序A、僅ⅠB、僅Ⅰ、ⅡC、僅Ⅰ、ⅢD、僅Ⅱ、Ⅳ【正確答案】：B解析：

當(dāng)初始數(shù)據(jù)基本正序時，直接插入排序和起泡排序的時間復(fù)雜度為O(n)?！菊_答案】：為B。59.11.最不適合用作鏈隊的鏈表是（）。A、只帶頭結(jié)點指針的非循環(huán)雙鏈表B、只帶隊首結(jié)點指針的循環(huán)雙鏈表C、只帶隊尾結(jié)點指針的循環(huán)雙鏈表D、以上都不適合【正確答案】：A解析：

只帶頭結(jié)點指針的非循環(huán)雙鏈表作為鏈隊時，隊頭在首部，隊尾在尾部，進隊和出隊操作的時間均為O(1)?！菊_答案】：為A。60.10.某算法的空間復(fù)雜度為O(1)，則()。A、該算法執(zhí)行不需要任何輔助空間B、該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C、該算法執(zhí)行不需要任何空間D、該算法執(zhí)行所需全部空間大小與問題規(guī)模n無關(guān)【正確答案】：B解析：

一個算法的空間復(fù)雜度為O(1)，只能說明其輔助空間大小與問題規(guī)模n無關(guān)，并不是說該算法不需要空間。答案為B。61.23.若一個具有n個頂點和e條邊的無向圖是一個森林（n>e），則該森林必有（）棵樹。A、eB、nC、n-eD、1【正確答案】：C解析：

設(shè)該森林有m棵樹，結(jié)點個數(shù)分別為n1、n2、…、nm，則總頂點數(shù)n=n1+n2+…+nm，第i棵樹的邊數(shù)=ni-1，總邊數(shù)=(n1-1)+(n2-1)+…+(nm-1)=n-m=e，所以m=n-e。62.26.用n個關(guān)鍵字構(gòu)造的一棵二叉排序樹，經(jīng)過i次關(guān)鍵字比較成功找到的元素個數(shù)最多為（）。A、iB、2iC、2i-1D、2i-1【正確答案】：C解析：

二叉排序樹中第i層最多有2i-1個結(jié)點。63.是()。A、存在，且唯一B、存在、且不唯一C、存在，可能不唯一D、無法確定是否存在【正確答案】：C解析：

這樣的有向圖中只有頂點i到頂點j（i<j）可能有邊，而頂點j到頂點i一定沒有邊，也就是說這樣的有向圖中一定沒有回路，所以可以產(chǎn)生拓?fù)湫蛄?，但拓?fù)湫蛄胁灰欢ㄎㄒ弧！菊_答案】：為C。64.25.n個頂點的連通圖的生成樹有（）條邊。A、nB、n-1C、n+1D、不確定【正確答案】：B65.叉排序樹，若希望高度最小，則應(yīng)該選擇哪個序列插入（）。A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53【正確答案】：B解析：

4個選項對應(yīng)的關(guān)鍵字序列構(gòu)造的4棵二叉排序樹如圖A.32所示，T2是一棵高度為3的滿二叉樹，高度最小?！菊_答案】：為B。66.有序段。A、1B、2C、3D、5【正確答案】：C解析：

產(chǎn)生的有序段是{4,5}，{2,3}，{1}，共3個有序段。67.5.一棵高度為h的非空平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0，則該樹共有()個結(jié)點。A、2h-1-1B、2h-1C、2h-1+1D、2h-1【正確答案】：D68.個數(shù)是（）。A、10B、nC、5D、2【正確答案】：A解析：

基數(shù)排序中建立隊列個數(shù)等于進制數(shù)。69.值為()。A、一定是2B、一定是1C、不可能是1D、以上都不對【正確答案】：C解析：

若出棧序列中p1=3，說明1、2先進棧，次棧頂為2，此時可以出棧2（p2=2），或者4進棧再出棧（p2=4），或者4、5進棧再出棧5（p2=5），…，總之p2可能是除了1外的其他整數(shù)?！菊_答案】：為C。70.47.有n個十進制整數(shù)進行基數(shù)排序，其中最大的整數(shù)為5位，則基數(shù)排序的趟數(shù)是（）。A、10B、nC、5D、2【正確答案】：C解析：

基數(shù)排序的趟數(shù)是最大的關(guān)鍵字的位數(shù)。48、48.有n個十進制整數(shù)進行基數(shù)排序，其中最大的整數(shù)為5位，則基數(shù)排序過程中臨時建立的隊數(shù)71.53.就排序算法所用的輔助空間而言，堆排序、快速排序和歸并排序的關(guān)系是（）。A、堆排序<快速排序<歸并排序A、堆排序<歸并排序<快速排序B、堆排序>歸并排序>快速排序C、堆排序>快速排序>歸并排序【正確答案】：A解析：

歸并排序的空間復(fù)雜度為O(n)，快速排序的空間復(fù)雜度為O(log2n)，堆排序的空間復(fù)雜度為O(1)。72.18.在一棵m階B樹中刪除一個關(guān)鍵字會引起合并，則該結(jié)點原有（）個關(guān)鍵字。A、1B、m/2C、m/2-1D、m/2+1【正確答案】：C解析：

在一棵m階B樹中每個內(nèi)部結(jié)點的關(guān)鍵字個數(shù)為m/2-1～m-1，刪除一個關(guān)鍵字會引起合并，則該結(jié)點中關(guān)鍵字個數(shù)一定是最少的情況。【正確答案】：為C。73.16.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A、邏輯B、存儲C、邏輯和存儲D、物理【正確答案】：A解析：

邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)無關(guān)，也就是與使用的計算機無關(guān)。74.27.設(shè)有13個權(quán)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個結(jié)點。A、13B、12C、26D、25【正確答案】：D75.21.采用順序查找方法查找長度為n的線性表時，成功查找的平均查找長度為（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正確答案】：C解析：

解：順序查找時，元素ai需i次比較，成功查找的平均查找長度=(1+2+…+n)/n=(n+1)/2。76.1.兩個字符串相等的條件是（）。A、串的長度相等B、含有相同的字符集C、都是非空串D、串的長度相等且對應(yīng)的字符相同【正確答案】：D77.60.內(nèi)排序方法的穩(wěn)定性是指（）。A、該排序算法不允許有相同關(guān)鍵字的元素B、該排序算法允許有相同關(guān)鍵字的元素C、平均時間為O(nlog2n)的排序方法D、以上都不對【正確答案】：D78.59.以下不屬于內(nèi)排序方法的是（）。A、二路歸并排序B、拓?fù)渑判駽、堆排序D、直接插入排序【正確答案】：B解析：

拓?fù)渑判蚴且环N產(chǎn)生拓?fù)湫蛄械姆椒ǎ粚賰?nèi)排序方法。79.19.一個鏈隊中，由front和rear分別指向隊頭和隊尾結(jié)點，它不具有的功能是()。A、可以實現(xiàn)元素進隊操作B、可以由隊頭指針和隊尾指針直接求出隊列中的元素個數(shù)C、可以實現(xiàn)元素出隊操作D、可以由隊頭指針和隊尾指針確定隊列為空【正確答案】：B解析：

鏈隊（由front和rear分別指向隊頭和隊尾結(jié)點）中不能直接由front和rear求出隊列中的元素個數(shù)。【正確答案】：為B。80.≤i≤m）。一個結(jié)點的子樹個數(shù)為該結(jié)點的（）。A、權(quán)B、維數(shù)C、次數(shù)（或度）D、序【正確答案】：C81.1.以下關(guān)于有向圖的說法中，正確的是（）。A、強連通圖是任何頂點到其他所有頂點都有邊B、完全有向圖一定是強連通圖C、有向圖中任一頂點的入度等于出度D、有向圖邊集的子集和頂點集的子集可構(gòu)成原有向圖的子圖【正確答案】：B解析：

完全有向圖中任意兩個頂點之間都有一條邊，一定是強連通圖?！菊_答案】：為B。82.19.哈希查找方法一般適用于（）情況下的查找。A、查找表為鏈表B、查找表為有序表C、關(guān)鍵字集合比地址集合大得多D、關(guān)鍵字集合與地址集合之間存在著某種對應(yīng)關(guān)系?！菊_答案】：D解析：

哈希表通過哈希函數(shù)和沖突解決函數(shù)確定存儲地址的，適合關(guān)鍵字集合與地址集合之間存在著某種對應(yīng)關(guān)系的數(shù)據(jù)集的存儲與查找。【正確答案】：為D。83.17.在含有n（n>2）個數(shù)據(jù)結(jié)點的數(shù)據(jù)結(jié)構(gòu)中，開始結(jié)點是指（）的結(jié)點。A、沒有前趨結(jié)點B、含有一個或多個前趨結(jié)點C、沒有后繼結(jié)點D、含有一個或多個后繼結(jié)點【正確答案】：A解析：

開始結(jié)點是沒有任何前趨結(jié)點的。84.種要求的排序方法是（）。A、先按k1值進行直接插入排序，再按k2值進行簡單選擇排序B、先按k2值進行直接插入排序，再按k1值進行簡單選擇排序C、先按k1值進行簡單選擇排序，再按k2值進行直接插入排序D、先按k2值進行簡單選擇排序，再按k1值進行直接插入排序【正確答案】：D解析：

從題中看出，k1數(shù)據(jù)項較k2數(shù)據(jù)項的權(quán)重，結(jié)合基數(shù)排序的情況，如在對若干兩位的十進制數(shù)進行基數(shù)遞增排序時，十位數(shù)較個位數(shù)權(quán)重，所以先按個位數(shù)排序，再按十位數(shù)排序，否則結(jié)果是錯誤的，因此應(yīng)先按k2數(shù)據(jù)項排序，再按k1數(shù)據(jù)項排序。再考慮排序算法的穩(wěn)定性，簡單選擇排序是不穩(wěn)定的，直接插入排序是穩(wěn)定的，如果對k1數(shù)據(jù)項采用不穩(wěn)定的排序方法，則可能出現(xiàn)相同k1值、k2值不同的元素改變相對次序，即可能出現(xiàn)k1值相同、k2大的在前小的在后，這顯然不符合題意，所以應(yīng)對最后的k1采用穩(wěn)定的排序方法。綜合起來應(yīng)該先按k2值進行簡單選擇排序，再按k1值進行插入排序。本題【正確答案】：為D。85.17.如圖7.1（a）所示的二叉樹B是由森林T轉(zhuǎn)換而來的二叉樹，那么森林T有（）個葉子結(jié)點。A、4B、5C、6D、7【正確答案】：C86.21.線索二叉樹中的線索是指（）。A、左孩子B、右孩子C、指針D、標(biāo)識【正確答案】：C87.9.以下數(shù)據(jù)結(jié)構(gòu)中元素之間為非線性關(guān)系的是()。A、棧B、隊列C、線性表D、以上都不是【正確答案】：D解析：

棧、隊列和線性表中元素之間的邏輯關(guān)系均為線性關(guān)系。答案為D。88.10.設(shè)有100個元素的有序順序表，采用折半查找方法，不成功時最大的比較次數(shù)是（）。A、25B、50C、10D、7【正確答案】：D解析：

不成功時最大比較次數(shù)為log2(n+1)=log2101=7。【正確答案】：為D。89.32.將10個元素散列到大小為10000的哈希表中，（）產(chǎn)生沖突。A、一定會B、一定不會C、仍可能會D、以上都不對【正確答案】：C解析：

無論裝填因子大還是小，哈希表仍可能發(fā)生沖突。90.42.冒泡排序最少元素移動的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A91.35.圖的遍歷是指（）。A、訪問圖的所有頂點B、以某種次序訪問圖的所有頂點C、從一個頂點出發(fā)訪問圖中所有頂點且每個頂點只能訪問一次D、從一個頂點出發(fā)訪問圖中所有頂點但每個頂點可以訪問多次【正確答案】：C解析：

圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次。92.7.二分查找和二叉排序樹查找的時間性能（）。A、完全相同B、有時不同C、完全不同D、數(shù)量級都是O(loE、2n)【正確答案】：B解析：

問題規(guī)模為n時，二分查找的時間復(fù)雜度為O(log2n)，而二叉排序樹查找與樹高相關(guān)，介于O(log2n)～O(n)，所以二分查找和二叉排序樹查找的時間性能不是完全相同，也不是完全不同，只能說有時不同?！菊_答案】：為B。93.12.以下關(guān)于哈希查找的敘述中正確的是()_。A、哈希查找中不需要任何關(guān)鍵字的比較B、采用拉鏈法解決沖突時，查找每個元素的時間是相同的C、哈希表在查找成功時的平均查找長度僅僅與表長有關(guān)D、哈希表的裝填因子等于表中填入的元素個數(shù)除以哈希表的長度【正確答案】：D解析：

裝填因子等于表中填入的元素個數(shù)n除以哈希表的長度m?！菊_答案】：為D。94.56.下列排序方法中，（）在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A、簡單選擇排序B、冒泡排序C、歸并排序D、堆排序【正確答案】：C解析：

因為歸并排序每趟并不一定產(chǎn)生全局有序區(qū)。95.31.在一個圖中，每個頂點的前趨頂點和后繼頂點數(shù)可以有（）。A、1個B、2個C、任意多個D、0個【正確答案】：C解析：

圖中頂點之間是多對多的相鄰關(guān)系。96.前一位置，r指向隊尾元素），元素x出隊的操作是（）;x=qu.data[qu.f]。A、qu.r+=1B、qu.r=(qu.r+1)%NC、qu.f+=1D、qu.f=(qu.f+1)%N【正確答案】：D解析：

這里f指向隊首元素的前一位置，r指向隊尾元素，所以出隊操作先循環(huán)移動f。【正確答案】：為D。97.11.設(shè)目標(biāo)串為s，模式串為t，在KMP模式匹配中，next[4]=2的含義是()。A、表示t4字符前面最多有2個字符和開頭的2個字符相同B、表示s4字符前面最多有2個字符和開頭的2個字符相同C、表示目標(biāo)串匹配失敗的位置是i=4D、表示模式串匹配失敗的位置是j=2【正確答案】：A解析：

KMP算法中next數(shù)組表示模式串t的部分匹配信息，next[4]=2表示字符t4前面最多有2個字符和t開頭的2個字符相同?！菊_答案】：為A。98.16.串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A、可以順序存儲B、數(shù)據(jù)元素是單個字符C、可以鏈接存儲D、數(shù)據(jù)元素可以是多個字符【正確答案】：B99.20.中綴表達(dá)式“2*(3+4)-1”的后綴表達(dá)式是（）。A、2341*+-B、234+*1–C、234*+1–D、-+*2341【正確答案】：B解析：

對于每個選項按后綴表達(dá)式方式求解，看是否與中綴表達(dá)式“2*(3+4)-1”的計算順序一致?！菊_答案】：為B。100.）個虛段。A、uB、k-uC、k-1-uD、u-1【正確答案】：C1.子。A、正確B、錯誤【正確答案】：A解析：

二叉排序樹的任意一棵子樹也是二叉排序樹。2.5.樹中元素之間是多對多的關(guān)系。A、正確B、錯誤【正確答案】：B3.22.內(nèi)排序過程在數(shù)據(jù)量很大時就變成了外排序過程。A、正確B、錯誤【正確答案】：B4.23.從時間性能看，堆排序總是優(yōu)于簡單選擇排序。A、正確B、錯誤【正確答案】：A解析：

堆排序的最好、最壞和平均時間復(fù)雜度均為O(nlog2n)，而簡單選擇排序的最好、最壞和平均時間復(fù)雜度均為O(n2)。5.7.線性表的存儲結(jié)構(gòu)大小與線性表中元素類型有關(guān)。A、正確B、錯誤【正確答案】：A解析：

線性表的存儲結(jié)構(gòu)大小等于線性表中所有元素存儲空間之和，而線性表中元素類型不同，每個元素所占用的存儲空間大小也可能不同。6.干塊，每塊中的數(shù)據(jù)個數(shù)必須相同A、正確B、錯誤【正確答案】：B解析：

分塊查找的數(shù)據(jù)組織方式為：數(shù)據(jù)表+索引表，數(shù)據(jù)表分塊，塊間有序，塊內(nèi)無序。【正確答案】：為B。7.17.棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)是任意的。A、正確B、錯誤【正確答案】：B解析：

棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)一定是線性結(jié)構(gòu)，不能是樹形結(jié)構(gòu)或圖形結(jié)構(gòu)。8.5.隊列是一種對進隊、出隊操作的次序做了限制的線性表。A、正確B、錯誤【正確答案】：B解析：

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次序。9.34.直接插入排序、冒泡排序和簡單選擇排序在最好情況下的時間復(fù)雜度均為O(n)。A、正確B、錯誤【正確答案】：B解析：

直接插入排序和冒泡排序在最好情況下的時間復(fù)雜度均為O(n)。10.8.數(shù)據(jù)的運算就是指基本運算，只能對數(shù)據(jù)實施基本運算。A、正確B、錯誤【正確答案】：B解析：

數(shù)據(jù)的基本運算只是數(shù)據(jù)運算的一部分，它是常用的數(shù)據(jù)運算，但并非就是數(shù)據(jù)運算的全部，也可以對數(shù)據(jù)實施非基本運算。11.17.影響外排序的時間因素主要是內(nèi)存與外存交換信息的次數(shù)。A、正確B、錯誤【正確答案】：A12.25.簡單選擇排序是一種不穩(wěn)定的排序方法。A、正確B、錯誤【正確答案】：A13.19.外排序中沒有關(guān)鍵字比較。A、正確B、錯誤【正確答案】：B解析：

外排序中需要關(guān)鍵字比較。14.成樹。A、正確B、錯誤【正確答案】：B解析：

這樣的子圖不一定是連通的。15.1.一種邏輯結(jié)構(gòu)的數(shù)據(jù)只有一種對應(yīng)的存儲結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B16.14.非空二叉樹的后序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：A17.3.非線性結(jié)構(gòu)中，每個元素最多只有一個前趨元素。A、正確B、錯誤【正確答案】：B解析：

非線性結(jié)構(gòu)中，每個元素可能有多個前趨元素。18.7.n個元素進隊的順序和出隊的順序總是一致的。A、正確B、錯誤【正確答案】：A解析：

后進隊的元素后出隊，先進隊的元素先出隊。19.13.哈希表發(fā)生沖突是由于選取的解決沖突的方法不當(dāng)造成的。A、正確B、錯誤【正確答案】：B解析：

哈希表發(fā)生沖突是由于選取的哈希函數(shù)不合適造成的。20.5.順序查找法適用于存儲結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯Φ木€性表。A、正確B、錯誤【正確答案】：A21.9.棧和隊列都是限制存取端的線性表。A、正確B、錯誤【正確答案】：A解析：

棧和隊列中元素的邏輯關(guān)系都是線性關(guān)系，僅限制在端點進行插入和刪除操作。22.15.為了提高外排序的速度，在外排序中必須選用最快的內(nèi)排序算法。A、正確B、錯誤【正確答案】：B解析：

外排序的第二階段只能采用歸并排序算法。23.8.線性表的邏輯順序總與其物理順序一致。A、正確B、錯誤【正確答案】：B解析：

當(dāng)線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，其邏輯順序與物理順序可能不一致。24.徑。A、正確B、錯誤【正確答案】：A解析：

如果頂點j到頂點k有路徑，則頂點i有一條通過頂點j到達(dá)頂點k的路徑，與題中條件矛盾。25.16.通常外排序采用多路歸并排序方法，實際上也可以用其他內(nèi)排序方法代替歸并排序方法。A、正確B、錯誤【正確答案】：B26.1.順序隊采用數(shù)組存放隊中元素，數(shù)組具有隨機存取特性，所以順序隊中可以隨機存取元素。A、正確B、錯誤【正確答案】：B解析：

順序隊采用數(shù)組存放隊中元素，盡管數(shù)組具有隨機存取特性，但隊列的操作特性是順序存取，只能存取兩端的元素。27.10.圖是一種結(jié)點之間無層次關(guān)系的線性結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

圖是一種非線性結(jié)構(gòu)。28.16.非空二叉樹的中序序列的第一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：B29.11.圖的深度優(yōu)先遍歷算法僅對無向圖適用。A、正確B、錯誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷算法對無向圖和有向圖都適用。30.43.內(nèi)排序方法要求數(shù)據(jù)一定以順序表方式存儲。A、正確B、錯誤【正確答案】：B解析：

有些內(nèi)排序方法也適合數(shù)據(jù)采用鏈表方式存儲的情況。31.18.非空二叉樹的先序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：A32.2.給定一棵樹T，可以找到唯一的一棵二叉樹B與之對應(yīng)。A、正確B、錯誤【正確答案】：A33.要(100-1)×3×1=297次關(guān)鍵字比較。73、12.減少初始?xì)w并段的個數(shù)，可以使外排序的時間縮短。A、正確B、錯誤【正確答案】：A34.8.一個圖中的簡單路徑是指該路徑上的邊不重復(fù)出現(xiàn)。A、正確B、錯誤【正確答案】：B解析：

一個圖中的簡單路徑是指該路徑上的頂點不重復(fù)出現(xiàn)。35.5.置換-選擇排序算法的作用是由一個無序文件生成一個全部有序的文件。A、正確B、錯誤【正確答案】：B36.9.二叉樹中每個度為2的結(jié)點的兩棵子樹都是有序的。A、正確B、錯誤【正確答案】：A37.1.線性表中所有元素的數(shù)據(jù)類型必須相同。A、正確B、錯誤【正確答案】：A解析：

線性表中所有元素具有相同性質(zhì)，在設(shè)計存儲結(jié)構(gòu)時，它們對應(yīng)的數(shù)據(jù)類型也必然相同。38.26.n個元素采用簡單選擇排序進行排序，關(guān)鍵字比較的次數(shù)總是n(n-1)/2。A、正確B、錯誤【正確答案】：A39.24.簡單選擇排序中，每趟產(chǎn)生的有序區(qū)中所有元素在以后的排序中不再改變位置。A、正確B、錯誤【正確答案】：A40.15.棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們的數(shù)據(jù)元素的邏輯關(guān)系也不同。A、正確B、錯誤【正確答案】：B解析：

棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們的數(shù)據(jù)元素的邏輯關(guān)系都是線性關(guān)系。41.2.數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。A、正確B、錯誤【正確答案】：B解析：

數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)無關(guān)。42.列是不可能相同的。A、正確B、錯誤【正確答案】：B解析：

圖的兩種遍歷序列可能相同。43.44.所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。A、正確B、錯誤【正確答案】：B44.27.簡單選擇排序在初始數(shù)據(jù)正序時，其時間復(fù)雜度為O(n)。A、正確B、錯誤【正確答案】：B45.11.哈希沖突是指同一個關(guān)鍵字對應(yīng)多個不同的哈希地址。A、正確B、錯誤【正確答案】：B解析：

哈希沖突是指多個不同一個關(guān)鍵字對應(yīng)相同的哈希地址。46.29.冒泡排序在最好情況下元素移動的次數(shù)為0。A、正確B、錯誤【正確答案】：A解析：

冒泡排序在初始數(shù)據(jù)正序時元素移動的次數(shù)為0。91、30.冒泡排序中，關(guān)鍵字比較的次數(shù)與初始數(shù)據(jù)序列有關(guān)，而元素移動的次數(shù)與初始數(shù)據(jù)序列無47.37.基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。A、正確B、錯誤【正確答案】：B48.變?yōu)椤?R[j],…,R[i],…，則該排序算法是穩(wěn)定的。A、正確B、錯誤【正確答案】：B解析：

該排序算法是不穩(wěn)定的。108、1.等有8個長度為2、5、3、10、4、7、9、18的初始?xì)w并段，采用3路歸并，在其最佳歸并樹中49.間復(fù)雜度的主要因素。正確錯誤A、正確B、錯誤【正確答案】：B解析：

影響算法時間復(fù)雜度的主要因素是移動元素的次數(shù)和關(guān)鍵字比較的次數(shù)。50.1.k路最佳歸并樹在外排序中的作用是產(chǎn)生初始?xì)w并段。A、正確B、錯誤【正確答案】：B51.42.二路歸并排序算法的時間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。A、正確B、錯誤【正確答案】：A52.36.基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的大小無關(guān)。A、正確B、錯誤【正確答案】：B解析：

基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的位數(shù)有關(guān)，也就與關(guān)鍵字的大小有關(guān)。53.6.隊列是一種對進隊、出隊操作的次數(shù)做了限制的線性表。A、正確B、錯誤【正確答案】：B解析：

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次數(shù)。54.12.n（n>2）個結(jié)點的二叉樹中至少有一個度為2的結(jié)點。A、正確B、錯誤【正確答案】：B55.13.二叉樹就是度為2的有序樹。A、正確B、錯誤【正確答案】：B56.14.在外排序過程中，一個記錄的讀入內(nèi)存的次數(shù)和寫到外存的次數(shù)必定相等。A、正確B、錯誤【正確答案】：A57.6.哈夫曼樹中沒有度為1的結(jié)點。A、正確B、錯誤【正確答案】：A58.40.二路歸并排序算法是穩(wěn)定的。A、正確B、錯誤【正確答案】：A59.8.哈夫曼樹中結(jié)點個數(shù)可以偶數(shù)也可以是奇數(shù)。A、正確B、錯誤【正確答案】：B60.12.有向圖的遍歷不可采用廣度優(yōu)先遍歷方法。A、正確B、錯誤【正確答案】：B解析：

廣度優(yōu)先遍歷算法適合于有向圖和無向圖。49、13.圖的深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法是兩種不同的算法，所以任何圖的這兩種遍歷序61.13.空棧是指棧中元素沒有賦值。A、正確B、錯誤【正確答案】：B解析：

空棧是指棧中沒有元素。62.7.哈夫曼樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值越大的結(jié)點離根結(jié)點越遠(yuǎn)。A、正確B、錯誤【正確答案】：B63.18.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

棧的定義不涉及數(shù)據(jù)的存儲結(jié)構(gòu)，棧中數(shù)據(jù)元素的邏輯關(guān)系屬于線性關(guān)系，所以棧的定義涉及64.序的時間。A、正確B、錯誤【正確答案】：B解析：

主要取決于內(nèi)外存數(shù)據(jù)交換的次數(shù)。65.7.n個頂點的無向圖至多有n(n-1)條邊。A、正確B、錯誤【正確答案】：B解析：

n個頂點的無向圖至多有n(n-1)/2條邊。66.3.對于不同的存儲結(jié)構(gòu)，應(yīng)采用不同的查找方法。A、正確B、錯誤【正確答案】：A67.7.采用多路平衡歸并方法可以減少初始?xì)w并段的個數(shù)。A、正確B、錯誤【正確答案】：B解析：

采用多路平衡歸并方法可以減少歸并的趟數(shù)。68.4.在隊空間大小為n的循環(huán)隊列中，最多只能進行n次進隊操作。A、正確B、錯誤【正確答案】：B解析：

在循環(huán)隊列中，元素出隊后，其位置空了出來，可以讓其他元素進隊，所以理論上講可以進隊任意次。69.12.哈希表中所有的哈希地址是連續(xù)的。A、正確B、錯誤【正確答案】：A70.徑。A、正確B、錯誤【正確答案】：A解析：

頂點i和頂點j屬一個連通分量，而頂點k屬另一個連通分量，所以頂點i到頂點k沒有路徑。71.6.線性表的長度是線性表占用的存儲空間的大小。A、正確B、錯誤【正確答案】：B解析：

線性表的長度是指表中元素個數(shù)，屬邏輯結(jié)構(gòu)的概念，與線性表占用的存儲空間大小無關(guān)。72.個比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯誤【正確答案】：A解析：

歸并趟數(shù)s=log55=1，5個記錄選取最小記錄需比較4次，所以總共需要(100-1)×4×1=396次關(guān)鍵字比較。73.數(shù)據(jù)的邏輯結(jié)構(gòu)。50、19.棧是一種特殊的線性表，其特殊之處在于棧的存儲結(jié)構(gòu)比較特殊。A、正確B、錯誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對線性表的操作做了限制。74.5.一個連通圖的生成樹是唯一的。A、正確B、錯誤【正確答案】：B解析：

一個連通圖的生成樹可能有多棵。75.39.n個元素采用二路歸并排序算法，總的趟數(shù)為n。A、正確B、錯誤【正確答案】：B解析：

n個元素采用二路歸并排序算法，總的趟數(shù)為log2n。76.9.數(shù)據(jù)對象就是一組任意數(shù)據(jù)元素的集合。A、正確B、錯誤【正確答案】：B解析：

數(shù)據(jù)對象是指具有相同性質(zhì)的有限個數(shù)據(jù)元素的集合。77.9.k路平衡歸并中，敗者樹的主要作用是減少歸并的趟數(shù)。A、正確B、錯誤【正確答案】：B解析：

敗者樹的主要作用是加速從k個記錄中選取最小記錄，并不能減少歸并的趟數(shù)。78.2.對于無向圖生成樹，從同一頂點出發(fā)所得到的生成樹一定是相同的。A、正確B、錯誤【正確答案】：B解析：

無向圖的生成樹可能有多棵，從同一頂點出發(fā)所得到的生成樹也不一定相同。79.45.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。A、正確B、錯誤【正確答案】：B80.17.由二叉樹某種遍歷方式產(chǎn)生的結(jié)果是一個線性序列。A、正確B、錯誤【正確答案】：A81.查找、折半查找和分塊查找。A、正確B、錯誤【正確答案】：B解析：

在順序存儲的物理介質(zhì)如磁帶上，只能進行順序查找，即便文件有序，也不能進行折半查找。82.9.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)各有優(yōu)缺點。83.錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯誤【正確答案】：B解析：

歸并趟數(shù)s=log55=1，采用敗者樹時，5個記錄選取最小記錄需比較log25=3次，所以總共需84.6.置換-選擇排序算法的作用是由一個無序文件生成若干個有序的子文件。A、正確B、錯誤【正確答案】：A85.20.k路最佳歸并樹一定是一棵k路平衡樹。A、正確B、錯誤【正確答案】：B解析：

k路最佳歸并樹不一定是一棵k路平衡樹。86.16.棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。A、正確B、錯誤【正確答案】：A解析：

棧和隊列中元素都呈現(xiàn)線性關(guān)系，但它們插入和刪除操作有別于線性表。87.10.二叉樹是一種特殊的樹。A、正確B、錯誤【正確答案】：B88.2.線性表中的結(jié)點按前趨、后繼關(guān)系可以排成一個線性序列。A、正確B、錯誤【正確答案】：A解析：

線性表是有限個相同性