數據結構必過復習測試附答案

第頁數據結構必過復習測試附答案1.32.以下（）方法可用于求無向圖的連通分量。A、遍歷B、拓撲排序C、Dijkstra算法D、Prim算法【正確答案】：A解析：

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

線性表是具有n（n≥0）個數據元素的有限序列，本題答案為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次，總的探測次數=1+2+…+k=k(k+1)/2?！菊_答案】：為D。5.8.順序表具有隨機存取特性，指的是（）。A、查找值為x的元素與順序表中元素個數n無關B、查找值為x的元素與順序表中元素個數n有關C、查找序號為i的元素與順序表中元素個數n無關D、查找序號為i的元素與順序表中元素個數n有關【正確答案】：C解析：

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

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

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

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

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

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

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

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

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

外排序過程主要分為兩個階段：生成初始歸并段和對初始歸并段進行歸并，這兩個步驟中都涉及文件的讀寫操作。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網的關鍵路徑，以下敘述（）是正確的。A、任何一個關鍵活動提前完成，則整個工程一定會提前完成B、完成整個工程的最短時間是從源點到匯點的最短路徑長度C、一個AOE網的關鍵路徑一定是唯一的D、任何一個活動持續(xù)時間的改變可能影響關鍵路徑的改變【正確答案】：D解析：

AOE網中的關鍵路徑是從源點到匯點的最長路徑，其長度為完成整個工程的最短時間。一個AOE網可能存在多條關鍵路徑，若提前完成所有關鍵路徑都包含的關鍵活動則整個工程一定會提前完成，但改變任何一個活動的持續(xù)時間可能影響關鍵路徑的改變（因為此時關鍵路徑可能發(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解析：

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

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

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

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

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

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

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

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

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

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

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

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

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

若含有n個元素的線性表a采用順序表存儲，每個元素的類型為ElemType，則第i個元素ai時間內找到該元素值，這是一種隨機存取的存儲結構。而順序存取是一種讀寫方式，不是存儲方式，有別于順序存儲。45.25.設一個棧的輸入序列是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.數據結構課程中討論的數據一般具有內在的聯(lián)系，這是指（）。A、數據和數據之間存在一種或多種特定關系B、數據元素和數據元素之間存在一種或多種特定關系C、數據項和數據項之間存在一種或多種特定關系D、同一數據中的所有數據元素值之間存在一種或多種特定關系【正確答案】：B解析：

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

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

順序查找可以從前向后或從后向前依次查找，既適合于順序存儲結構也適合于鏈式存儲結構。49.16.哈希表中出現(xiàn)的哈希沖突是指()。A、兩個元素具有相同的序號B、兩個元素的關鍵字不同，而其他屬性相同C、數據元素過多D、兩個元素的關鍵字不同，而對應的哈希函數值相同【正確答案】：D解析：

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

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

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

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

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

基數排序中隊列的個數僅與基數相關，這里基數為10。【正確答案】：為A。58.速排序Ⅳ.二路歸并排序A、僅ⅠB、僅Ⅰ、ⅡC、僅Ⅰ、ⅢD、僅Ⅱ、Ⅳ【正確答案】：B解析：

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

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

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

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

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

這樣的有向圖中只有頂點i到頂點j（i<j）可能有邊，而頂點j到頂點i一定沒有邊，也就是說這樣的有向圖中一定沒有回路，所以可以產生拓撲序列，但拓撲序列不一定唯一?！菊_答案】：為C。64.25.n個頂點的連通圖的生成樹有（）條邊。A、nB、n-1C、n+1D、不確定【正確答案】：B65.叉排序樹，若希望高度最小，則應該選擇哪個序列插入（）。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個選項對應的關鍵字序列構造的4棵二叉排序樹如圖A.32所示，T2是一棵高度為3的滿二叉樹，高度最小?！菊_答案】：為B。66.有序段。A、1B、2C、3D、5【正確答案】：C解析：

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

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

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

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

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

在一棵m階B樹中每個內部結點的關鍵字個數為m/2-1～m-1，刪除一個關鍵字會引起合并，則該結點中關鍵字個數一定是最少的情況?！菊_答案】：為C。73.16.在數據結構中，與所使用的計算機無關的是數據的（）結構。A、邏輯B、存儲C、邏輯和存儲D、物理【正確答案】：A解析：

邏輯結構與存儲結構無關，也就是與使用的計算機無關。74.27.設有13個權值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個結點。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、串的長度相等且對應的字符相同【正確答案】：D77.60.內排序方法的穩(wěn)定性是指（）。A、該排序算法不允許有相同關鍵字的元素B、該排序算法允許有相同關鍵字的元素C、平均時間為O(nlog2n)的排序方法D、以上都不對【正確答案】：D78.59.以下不屬于內排序方法的是（）。A、二路歸并排序B、拓撲排序C、堆排序D、直接插入排序【正確答案】：B解析：

拓撲排序是一種產生拓撲序列的方法，不屬內排序方法。79.19.一個鏈隊中，由front和rear分別指向隊頭和隊尾結點，它不具有的功能是()。A、可以實現(xiàn)元素進隊操作B、可以由隊頭指針和隊尾指針直接求出隊列中的元素個數C、可以實現(xiàn)元素出隊操作D、可以由隊頭指針和隊尾指針確定隊列為空【正確答案】：B解析：

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

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

哈希表通過哈希函數和沖突解決函數確定存儲地址的，適合關鍵字集合與地址集合之間存在著某種對應關系的數據集的存儲與查找?！菊_答案】：為D。83.17.在含有n（n>2）個數據結點的數據結構中，開始結點是指（）的結點。A、沒有前趨結點B、含有一個或多個前趨結點C、沒有后繼結點D、含有一個或多個后繼結點【正確答案】：A解析：

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

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

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

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

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

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

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

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

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

圖中頂點之間是多對多的相鄰關系。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.設目標串為s，模式串為t，在KMP模式匹配中，next[4]=2的含義是()。A、表示t4字符前面最多有2個字符和開頭的2個字符相同B、表示s4字符前面最多有2個字符和開頭的2個字符相同C、表示目標串匹配失敗的位置是i=4D、表示模式串匹配失敗的位置是j=2【正確答案】：A解析：

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

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

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

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

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

分塊查找的數據組織方式為：數據表+索引表，數據表分塊，塊間有序，塊內無序?！菊_答案】：為B。7.17.棧具有先進后出的特點，其中數據的邏輯結構是任意的。A、正確B、錯誤【正確答案】：B解析：

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

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

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

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

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

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

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

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

哈希表發(fā)生沖突是由于選取的哈希函數不合適造成的。20.5.順序查找法適用于存儲結構為順序或鏈式存儲的線性表。A、正確B、錯誤【正確答案】：A21.9.棧和隊列都是限制存取端的線性表。A、正確B、錯誤【正確答案】：A解析：

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

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

當線性表采用鏈式存儲結構時，其邏輯順序與物理順序可能不一致。24.徑。A、正確B、錯誤【正確答案】：A解析：

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

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

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

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

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

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

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

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

數據的邏輯結構與存儲結構無關。42.列是不可能相同的。A、正確B、錯誤【正確答案】：B解析：

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

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

冒泡排序在初始數據正序時元素移動的次數為0。91、30.冒泡排序中，關鍵字比較的次數與初始數據序列有關，而元素移動的次數與初始數據序列無47.37.基數排序只適用于以數字為關鍵字的情況，不適用以字符串為關鍵字的情況。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的初始歸并段，采用3路歸并，在其最佳歸并樹中49.間復雜度的主要因素。正確錯誤A、正確B、錯誤【正確答案】：B解析：

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

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

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

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

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

棧的定義不涉及數據的存儲結構，棧中數據元素的邏輯關系屬于線性關系，所以棧的定義涉及64.序的時間。A、正確B、錯誤【正確答案】：B解析：

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

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

采用多路平衡歸并方法可以減少歸并的趟數。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解析：

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

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

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

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

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

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

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

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

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

線性表的順序存儲結構和鏈式存儲結構各有優(yōu)缺點。83.錄，則總共需要396次關鍵字比較。A、正確B、錯誤【正確答案】：B解析：

歸并趟數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)線性關系，但它們插入和刪除操作有別于線性表。87.10.二叉樹是一種特殊的樹。A、正確B、錯誤【正確答案】：B88.2.線性表中的結點按前趨、后繼關系可以排成一個線性序列。A、正確B、錯誤【正確答案】：A解析：

線性表是有限個相同性