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

第頁數(shù)據(jù)結(jié)構(gòu)必過復(fù)習測試卷附答案1.接表更省空間Ⅲ.若有向圖中存在拓撲序列，則該圖不存在回路A、僅ⅡB、僅Ⅰ、ⅡC、僅ⅢD、僅Ⅰ、Ⅲ【正確答案】：C解析：

只有簡單回路才是起始頂點和終止頂點相同的簡單路徑。存儲稀疏圖，用鄰接表比鄰接矩陣更省空間。若有向圖中存在拓撲序列（包含全部頂點），則該圖不存在回路?！菊_答案】：為C。2.35.圖的遍歷是指（）。A、訪問圖的所有頂點B、以某種次序訪問圖的所有頂點C、從一個頂點出發(fā)訪問圖中所有頂點且每個頂點只能訪問一次D、從一個頂點出發(fā)訪問圖中所有頂點但每個頂點可以訪問多次【正確答案】：C解析：

圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次。3.果是_（）__。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。4.15.一棵含有n個結(jié)點的線索二叉樹中，其線索個數(shù)為（）。A、2nB、n-1C、n+1D、n【正確答案】：C5.14.由n個無序的元素創(chuàng)建一個有序單鏈表的算法的時間復(fù)雜度是（）。A、O(nlog2n)B、O(n)C、O(1)D、以上都不對【正確答案】：A解析：

創(chuàng)建有序單鏈表需要排序，而排序的可以采用時間復(fù)雜度為O(nlog2n)的算法。6.29.對于采用置換-選擇算法產(chǎn)生的歸并段，以下含有3個初始歸并段的組是（）有序段。A、{5,6,10}，{7,8,2}，{9,5}B、{3,6,12}，{1,2,3}，{5,14}C、{5,6,10}，{7,12,15}，{2,9}D、{7,8,12}，{1,4,6}，{9,12}【正確答案】：C解析：

采用置換-選擇算法產(chǎn)生的歸并段一定是有序段，選項A錯誤。而前一個歸并段的最后一個關(guān)鍵字一定大于下一個歸并段的第一個關(guān)鍵字，選項B、D錯誤。7.21.線索二叉樹中的線索是指（）。A、左孩子B、右孩子C、指針D、標識【正確答案】：C8.=1，則pi（1≤i≤n-1）的值是()。A、n-i+1B、n-iC、iD、有多種可能【正確答案】：A解析：

當pn=1時，進棧序列是p1、p2、p3、…、1，由輸出序列可知，p1、p2、p3、…、pn依次進棧，然后依次出棧，即pn-1=2，pn-2=3，…，p1=n，也就是說pi=n-i+1。【正確答案】：為A。9.排序確定A、外排序所花時間=內(nèi)排序時間+外存信息讀寫時間+內(nèi)部歸并所花時間B、外排序并不涉及文件的讀寫操作C、外排序完全可以由內(nèi)排序來替代【正確答案】：B解析：

外排序過程主要分為兩個階段：生成初始歸并段和對初始歸并段進行歸并，這兩個步驟中都涉及文件的讀寫操作。10.17.設(shè)有100個元素的有序表，用折半查找時，不成功時最大的比較次數(shù)是（）。A、25B、50C、10D、7【正確答案】：D解析：

不成功時最大的比較次數(shù)=log2(n+1)=7。【正確答案】：為D。11.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。12.收集后得到的關(guān)鍵字序列是（）。A、007，110，119，114，911，120，122B、007，110，119，114，911，122，120C、007，110，911，114，119，120，122D、110，120，911，122，114，007，119【正確答案】：C解析：

這里基數(shù)排序的第一趟排序是按照個位數(shù)字來排序的，第二趟排序是按然十位數(shù)字的大小進行排序的?！菊_答案】：為C。13.9.以下數(shù)據(jù)結(jié)構(gòu)中元素之間為非線性關(guān)系的是()。A、棧B、隊列C、線性表D、以上都不是【正確答案】：D解析：

棧、隊列和線性表中元素之間的邏輯關(guān)系均為線性關(guān)系。答案為D。14.32.以下（）方法可用于求無向圖的連通分量。A、遍歷B、拓撲排序C、Dijkstra算法D、Prim算法【正確答案】：A解析：

從圖中某個頂點出發(fā)進行遍歷，可將與該頂點相連通的所有頂點全部訪問，也就找到了該頂點所在的連通分量。15.到一維數(shù)組B[0..m]中，則A[5][8]元素在B中的位置k是（）。A、10B、37C、45D、60【正確答案】：B解析：

A[5][8]屬于上三角部分的元素，A[5][8]前面存放的元素個數(shù)計算是，第1行有10個，第2行有9個，…，第4行有7個，在第5行中有A[5..7]計3個元素，共10+9+8+7+3=37，由于B的起始下標從0開始，所以k=37。16.13.對含有n個元素的順序表采用順序查找方法，不成功時的比較次數(shù)是()。A、1B、nC、n-1D、n+1E、4F、5G、6H、7【正確答案】：B解析：

不成功時的比較次數(shù)總是n?！菊_答案】：為B。14、14.含有20個結(jié)點的AVL樹的最大高度是()?！菊_答案】：C設(shè)Nh表示高度為h的平衡二叉樹中含有的最少結(jié)點數(shù)，有N1=1，N2=2，Nh=Nh-1+Nh-2+1，求出N6=20?！菊_答案】：為C。17.35.m個初始歸并進行k路平衡歸并時，所需趟數(shù)（）。A、logkmB、logkm+1C、logk(m+1)D、logmk【正確答案】：A18.6.（）方法可以判斷一個有向圖是否存在回路。A、求最小生成樹B、拓撲排序C、求關(guān)鍵路徑D、求最短路徑【正確答案】：B解析：

可以采用深度優(yōu)先遍歷和拓撲排序來判斷一個有向圖是否存在回路，若一個有向圖能夠成功進行拓撲排序，即拓撲排序時產(chǎn)生所有頂點的拓撲序列，則該有向圖中一定沒有回路?！菊_答案】：為B。19.24.數(shù)據(jù)結(jié)構(gòu)是具有（）的數(shù)據(jù)元素的集合。A、性質(zhì)相同B、相同物理結(jié)構(gòu)C、相互關(guān)系D、數(shù)據(jù)項【正確答案】：C20.45.以下（）方法在數(shù)據(jù)基本有序時效率最好。A、快速排序B、冒泡排序C、堆排序D、希爾排序【正確答案】：B21.18.以下關(guān)于有向圖的說法中，正確的是()。A、強連通圖中任何頂點到其他所有頂點都有邊B、完全有向圖一定是強連通圖C、有向圖中任一頂點的入度等于出度D、有向圖邊集的子集和頂點集的子集可構(gòu)成原有向圖的子圖【正確答案】：B解析：

強連通圖是任何頂點到其他所有頂點都有路徑而不一定有邊。完全有向圖中任意兩個頂點之間都存在一條邊，則一定是強連通圖。有向圖中任一頂點的入度不一定等于出度。一個有向圖邊集的子集和頂點集的子集不一定構(gòu)成一個圖?！菊_答案】：為B。22.28.設(shè)一個棧的輸入序列為A、B、C、D，則借助一個棧所得到的輸出序列不可能是（）。A,B,C,DB、D,C,B,AC、A,C,D,BD,A,B,C【正確答案】：D解析：

可以簡單地推算，容易得出D，A，B，C是不可能的，因為D先出來，說明A，B，C，D均在棧中，在棧中順序應(yīng)為D，C，B，A，出棧的順序只能是D，C，B，A，如圖3.3所示。所以本題【正確答案】：為D。23.21.采用順序查找方法查找長度為n的線性表時，成功查找的平均查找長度為（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正確答案】：C解析：

解：順序查找時，元素ai需i次比較，成功查找的平均查找長度=(1+2+…+n)/n=(n+1)/2。24.16.設(shè)一棵哈夫曼樹中有1999個結(jié)點，該哈夫曼樹用于對（）個字符進行編碼。A、999B、998C、1000D、1001【正確答案】：C25.拓撲序列中，若頂點a在頂點b之前，則圖中必有一條邊<a，b>A、僅ⅠB、僅Ⅰ、ⅢC、僅Ⅱ、ⅢD、Ⅰ、Ⅱ和ⅢE、圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次F、圖的深度優(yōu)先遍歷適合無向圖G、圖的深度優(yōu)先遍歷不適合有向圖H、圖的深度優(yōu)先遍歷是一個遞歸過程【正確答案】：A解析：

在一個有向圖的拓撲序列中，若頂點a在頂點b之前，圖中不一定有邊<a，b>?！菊_答案】：為A。10、10.以下敘述中錯誤的是（）?！菊_答案】：C圖的深度優(yōu)先遍歷適合無向圖和有向圖?！菊_答案】：為C。26.34.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）算法。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷【正確答案】：A解析：

當圖變?yōu)槎鏄鋾r，深度優(yōu)先遍歷過程是訪問起點（類似于訪問根結(jié)點），訪問起點的相鄰點，再訪問起點的相鄰點的相鄰點（類似于訪問左子樹），…，回溯回來時再訪問起點的下一個相鄰點（類似于訪問右子樹）。27.1.以下關(guān)于有向圖的說法中，正確的是（）。A、強連通圖是任何頂點到其他所有頂點都有邊B、完全有向圖一定是強連通圖C、有向圖中任一頂點的入度等于出度D、有向圖邊集的子集和頂點集的子集可構(gòu)成原有向圖的子圖【正確答案】：B解析：

完全有向圖中任意兩個頂點之間都有一條邊，一定是強連通圖?！菊_答案】：為B。28.樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是（）。A、LRNB、NRLC、RLND、RNL【正確答案】：D29.13.設(shè)森林F中有4棵樹，第1、2、3、4棵樹的結(jié)點個數(shù)分別為a、b、c、d，將森林F轉(zhuǎn)換為一顆二叉樹B，則二叉樹B中根結(jié)點的左子樹上的結(jié)點個數(shù)是()。A、a-1B、aC、a+b+cD、b+c+d【正確答案】：A30.61.內(nèi)排序方法的穩(wěn)定性是指（）。A、經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的相對位置不變B、經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的絕對位置不變C、排序算法的性能與被排序元素的數(shù)量關(guān)系不大D、排序算法的性能與被排序元素的數(shù)量關(guān)系密切【正確答案】：A31.34.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹中每個結(jié)點的度均為2B、二叉樹中至少有一個結(jié)點的度為2C、二叉樹中每個結(jié)點的度可以小于2D、二叉樹中至少有一個結(jié)點【正確答案】：C32.8.在（）_中將會用到棧結(jié)構(gòu)。A、遞歸調(diào)用B、圖深度優(yōu)先遍歷C、表達式求值D、以上場景都有【正確答案】：D解析：

在遞歸調(diào)用、圖的深度優(yōu)先遍歷和表達式求值中均使用棧?！菊_答案】：為D。33.儲地址為100，則A[2][3]的存儲地址是（）。A、122B、126C、114D、116【正確答案】：A解析：

A[2][3]前面有3列，每列3個元素，計9個元素，在列3中前面有2個元素，這樣的存儲方式中，A[2][3]前面共存儲11個元素。LOC(A[2][3])=LOC(A[0][0])+11×2=122?！菊_答案】：為A。34.8.關(guān)于m階B樹說法錯誤的是（）。A、m階B樹是一棵平衡的m叉樹B樹中的查找無論是否成功都必須找到最下層結(jié)點C、根結(jié)點最多含有m棵子樹D、根結(jié)點至少含有2棵子樹【正確答案】：B解析：

B樹中成功的查找會落在某個內(nèi)部結(jié)點中，失敗的查找會落在某個外部結(jié)點中?！菊_答案】：為B。35.8.一棵高度為h、結(jié)點個數(shù)為n的m（m≥3）次樹中，其分支數(shù)是（）。A、nhB、n+hC、n-1D、h-1【正確答案】：C36.1.若某非空二叉樹的中序序列和后序序列正好相反，則該二叉樹的形態(tài)是（）。A、只有一個根結(jié)點B、所有分支結(jié)點都有左右孩子C、所有結(jié)點沒有左子樹D、所有結(jié)點沒有右子樹【正確答案】：C37.55.下列排序方法中，輔助空間為O(n)的是（）。A、希爾選擇B、冒泡排序C、堆排序D、歸并排序【正確答案】：D解析：

這幾種排序方法中只有歸并排序的空間復(fù)雜度為O(n)，其余幾種排序方法的空間復(fù)雜度為O(1)。38.23.設(shè)棧的輸入序列是1、2、3、4，則（）不可能是其出棧序列。A、1、2、4、3B、2、1、3、4C、4、3、1、2D、3、2、1、4【正確答案】：C解析：

當出棧序列的第一個元素為4時，只有唯一的出棧序列4、3、2、1，不可能有4、3、1、2的出棧序列。本題【正確答案】：為C。39.2.以下算法的時間復(fù)雜度為()。deffun(n):i=1whilei<=n:i=i*3A、O(n)B、O(n2)C、O(nloD、2n)E、O(loF、2n)【正確答案】：D解析：

設(shè)while循環(huán)的次數(shù)為m，i從1開始每循環(huán)一次按3倍遞增，有i=3m≤n，m≤log3n=O(log2n)。答案為D。40.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。41.57.初始數(shù)據(jù)序列中有兩個相同關(guān)鍵字的元素，通過不穩(wěn)定的排序方法排序后，（）。A、這兩個元素的前后位置不發(fā)生變化B、這兩個元素的前后位置一定發(fā)生變化C、這兩個元素的位置不發(fā)生變化D、這兩個元素的前后位置可能發(fā)生變化【正確答案】：D42.的排序方法是（）。A、簡單選擇排序B、快速排序C、冒泡排序D、直接插入排序【正確答案】：A解析：

從數(shù)據(jù)排列次序的變化過程看到，每一趟都從無序區(qū)中選一個最小的元素歸位。43.11.以下算法的時間復(fù)雜度為（）。deffun(n):i=1whilei<=n:i+=1A、O(n)B、O(√nn)C、O(nloD、2n)E、O(loF、2n)【正確答案】：A解析：

設(shè)while循環(huán)的次數(shù)為m，則有2m<=n，m<=n/2=O(n)。答案為A。44.10.將10階對稱矩陣A壓縮存儲到一維數(shù)組B中，則數(shù)組B的長度最少為_()。A、100B、40C、80D、55【正確答案】：D解析：

n階對稱矩陣壓縮存儲時需要存儲的元素個數(shù)=n(n+1)/2，n=10時結(jié)果為55。45.排序，需要分配和收集()趟。A、3B、4C、5D、8【正確答案】：A解析：

這組關(guān)鍵字中最長的位數(shù)是3，所以采用基數(shù)排序方法時需要進行3趟分配和收集過程。【正確答案】：為A。46.20.中綴表達式“2*(3+4)-1”的后綴表達式是（）。A、2341*+-B、234+*1–C、234*+1–D、-+*2341【正確答案】：B解析：

對于每個選項按后綴表達式方式求解，看是否與中綴表達式“2*(3+4)-1”的計算順序一致。【正確答案】：為B。47.11.對于有n個頂點的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個（）。A、由n-1條權(quán)值最小的邊構(gòu)成的子圖B、由n-l條權(quán)值之和最小的邊構(gòu)成的子圖C、由n個頂點構(gòu)成的極大連通子圖D、由n個頂點構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小【正確答案】：D解析：

最小生成樹是圖中所有頂點構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小?！菊_答案】：為D。題型：48.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)。而順序存取是一種讀寫方式，不是存儲方式，有別于順序存儲。49.4.以下最適合用作鏈隊的不帶頭結(jié)點的鏈表是（）。A、只帶首結(jié)點指針的循環(huán)單鏈表B、只帶尾結(jié)點指針的單鏈表C、只帶首結(jié)點指針的單鏈表D、只帶尾結(jié)點指針的循環(huán)單鏈表【正確答案】：D解析：

只帶尾結(jié)點指針的循環(huán)單鏈表的進隊操作和出隊操作時間復(fù)雜度為O(1)?！菊_答案】：為D。50.30.棧的“先進后出”特性是指（）。A、最后進棧的元素總是最先出棧B、當同時進行進棧和出棧操作時，總是進棧優(yōu)先C、每當有出棧操作時，總要先進行一次進棧操作D、每次出棧的元素總是最先進棧的元素【正確答案】：A51.44.以下穩(wěn)定的排序方法是（）。A、直接插入排序和快速排序B、直接插入排序和冒泡排序C、簡單選擇排序和歸并排序D、歸并排序和冒泡排序【正確答案】：B52.1.某遞歸算法的時間遞推式如下：T(1)=1T(n)=T(n/2)+n當n>1則，T(n)=（）。A、O(1)B、O(loC、2n)D、O(n)E、O(n2)【正確答案】：C解析：

不妨設(shè)n=2k，有k=log2n，T(n)=T(n/21)+n=[T(n/22)+n/2]+n=T(n/22)+(1+1/2)n=…=T(n/2k)+(1+1/2+…+1/2k-1)n=2n+1=O(n)。答案為C。53.4.下面關(guān)于哈夫曼樹的說法，不正確的是()。A、對應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹可能不唯一B、哈夫曼樹具有最小帶權(quán)路徑長度C、哈夫曼樹中沒有度為1的結(jié)點D、哈夫曼樹中除了度為2的結(jié)點外，還有度為1的結(jié)點和葉結(jié)點【正確答案】：D54.到'*'時，運算數(shù)棧（從棧頂?shù)綏５状涡颍椋ǎ?。A、861B、581C、321D、361【正確答案】：C解析：

算術(shù)表達式“1+6/(8-5)*3”的后綴表達式是“1685-/3*+”，在求值時，遇到后綴表達式的'*'時，前面已進行了-和/運算，運算數(shù)棧中從棧頂?shù)綏５状涡驗?21?！菊_答案】：為C。55.18.有一個非空循環(huán)雙鏈表，在結(jié)點p之前插入結(jié)點q的操作是()。A、p.prior=q;q.next=p;p.prior.next=q;q.prior=p.prior;B、p.prior=q;p.prior.next=q;q.next=p;q.prior=p.prior;C、q.next=p;q.prior=p.prior;p.prior=q;p.prior.next=q;D、q.next=p;q.prior=p.prior;p.prior.next=q;p.prior=q;【正確答案】：D56.操作是（）。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的下標為0～n-1，top的初始值為n，將s[n-1]一端作為棧底，進棧中元素向s[0]一端生長。在第一個元素x進棧時，先執(zhí)行top-=1，這樣top指向s的有效下標，再執(zhí)行s[top]=x?！菊_答案】：為C。57.23.由m個初始歸并段構(gòu)建的k階最佳歸并樹中，度為k的結(jié)點個數(shù)是（）。A、(m-1)/kB、m/kC、(m-1)/(k-1)D、無法確定【正確答案】：C解析：

設(shè)樹中結(jié)點個數(shù)為n，n0=m，n-1=knk，n=n0+nk，所以有knk=m+nk-1，則nk=(m-1)/(k-1)。58.26.k階最佳歸并樹是一棵（）。A、k階平衡樹B、平衡二叉樹C、k階哈夫曼樹D、以上都不對【正確答案】：C解析：

k階最佳歸并樹是一棵k階哈夫曼樹，不一定是k階平衡樹。59.是()。A、存在，且唯一B、存在、且不唯一C、存在，可能不唯一D、無法確定是否存在【正確答案】：C解析：

這樣的有向圖中只有頂點i到頂點j（i<j）可能有邊，而頂點j到頂點i一定沒有邊，也就是說這樣的有向圖中一定沒有回路，所以可以產(chǎn)生拓撲序列，但拓撲序列不一定唯一?！菊_答案】：為C。60.隊頭元素的前一個位置，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。61.31.哈希查找的基本思想是根據(jù)（）來決定元素的存儲地址。A、元素的序號B、元素個數(shù)C、關(guān)鍵字值D、非關(guān)鍵字屬性值【正確答案】：C62.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ù)元素的集合。63.30.n個記錄采用置換-選擇算法產(chǎn)生m個有序段，m和n的關(guān)系是（）。A、m與n成正比B、m與n成反比C、m=log2nD、以上都不對【正確答案】：D解析：

如w=1時，記錄序列{1,2,3,4,5}產(chǎn)生一個有序段，而{5,4,3,2,1}產(chǎn)生5個有序段，所以一般來講，m與數(shù)據(jù)序列、內(nèi)存工作區(qū)可容納的記錄個數(shù)w和n都有關(guān)，但并不是A、B、C選項所指的直接關(guān)系。64.42.冒泡排序最少元素移動的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A65.的數(shù)據(jù)結(jié)構(gòu)為（）。A、數(shù)組B、樹C、圖D、線性表【正確答案】：B66.種要求的排序方法是（）。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。67.時，()。A、僅修改隊頭指針B、僅修改隊尾指針C、隊頭、隊尾指針一定都會修改D、隊頭、隊尾指針可能都會修改【正確答案】：D解析：

當原鏈隊為空時進隊操作會修改隊頭、隊尾指針，當原鏈隊不空時進隊操作僅修改隊尾指針?！菊_答案】：為D。68.29.在一個無向圖中，所有頂點的度之和等于邊數(shù)的（）倍。A、1/2B、1C、2D、4【正確答案】：C解析：

在無向圖中，一條邊計入兩個頂點的度數(shù)。69.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)元素值。70.11.最不適合用作鏈隊的鏈表是（）。A、只帶頭結(jié)點指針的非循環(huán)雙鏈表B、只帶隊首結(jié)點指針的循環(huán)雙鏈表C、只帶隊尾結(jié)點指針的循環(huán)雙鏈表D、以上都不適合【正確答案】：A解析：

只帶頭結(jié)點指針的非循環(huán)雙鏈表作為鏈隊時，隊頭在首部，隊尾在尾部，進隊和出隊操作的時間均為O(1)。【正確答案】：為A。71.19.下面關(guān)于串的敘述中，正確的是（）。A、串是一種特殊的線性表B、串中元素只能是字母C、空串就是空白串D、串的長度必須大于零【正確答案】：A72.5.一棵高度為h的非空平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0，則該樹共有()個結(jié)點。A、2h-1-1B、2h-1C、2h-1+1D、2h-1【正確答案】：D73.7.一個順序表所占用存儲空間的大小與（）無關(guān)。A、順序表長度B、順序表中元素的數(shù)據(jù)類型C、順序表中元素各數(shù)據(jù)項的數(shù)據(jù)類型D、順序表中各元素的存放次序【正確答案】：D解析：

對于含有n個元素類型為ElemType的順序表，所占用存儲空間的大小為n×sizeof(ElemType)，與各元素的存放次序無關(guān)。74.29.對于棧操作數(shù)據(jù)的原則是（）。A、先進先出B、后進先出C、后進后出D、不分順序【正確答案】：B解析：

棧操作數(shù)據(jù)的原則是先進后出或后進先出。75.24.由m個初始歸并段構(gòu)建的k階最佳歸并樹中，總共有（）個結(jié)點。A、(mk-1)/kB、(mk-1)/(k-1)C、mk/(k-1)D、無法確定【正確答案】：B解析：

設(shè)樹中結(jié)點個數(shù)為n，n0=m，n-1=knk，n=n0+nk，所以有knk=m+nk-1，則nk=(m-1)/(k-1)。n=n0+nk=m+(m-1)/(k-1)=(mk-1)/(k-1)。76.12.在長度為n（n≥1）的循環(huán)雙鏈表L中，在尾結(jié)點之后插入一個新結(jié)點的時間復(fù)雜度為()。A、O(n2)B、O(n)C、O(1)D、O(nlog2n)【正確答案】：C解析：

循環(huán)雙鏈表可以O(shè)(1)時間找到尾結(jié)點p，再在結(jié)點p的后面插入新結(jié)點s，時間也是O(1)。答案為C。77.20.關(guān)于串的的敘述，不正確的是（）。A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、替換是串的一種重要運算D、串既可以采用順序存儲，也可以采用鏈式存儲【正確答案】：B78.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)系。79.3，4}，下一步選取的目標頂點可能是（）。A、頂點2B、頂點3C、頂點4D、頂點7【正確答案】：D解析：

Dijkstra算法求出源點到某個頂點的最短路徑并添加到S中后，后面不再以它作為目標頂點。【正確答案】：為D。80.36.以下敘述中錯誤的是（）。A、圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次B、圖的深度優(yōu)先遍歷適合無向圖C、圖的深度優(yōu)先遍歷不適合有向圖D、圖的深度優(yōu)先遍歷是一個遞歸過程【正確答案】：C解析：

圖的深度優(yōu)先遍歷算法既適合無向圖也適合有向圖的遍歷。81.取。A、{(1，4)，(3，4)，(3，5)，(2，5)}B、{(1，5)，(2，4)，(3，5)}C、{(1，2)，(2，3)，(3，1)}D、{(1，4)，(3，5)，(2，5)，(3，4)}【正確答案】：C解析：

采用Prim算法求最小生成樹時，U={1，2，3}，V-U={4，5，…}，候選邊只能是這兩個頂點集之間的邊?！菊_答案】：為C。82.12.若串str="Software"，其子串的數(shù)目是（）。A、8B、9C、36D、37【正確答案】：D83.50.以下排序方法中，（）不需要進行關(guān)鍵字的比較。A、快速排序B、歸并排序C、基數(shù)排序D、堆排序【正確答案】：C解析：

在本章介紹的各種排序方法中，基數(shù)排序是唯一不基于關(guān)鍵字比較的排序方法。84.14.設(shè)s表示串"abcd"，s1表示串"123"，則執(zhí)行語句s2=InsStr(s,2,s1)后，s2串為（）。A、"123abcd"B、"a123bcd"C、"ab123cd"D、"abc123d"【正確答案】：B85.16.以下排序方法中，()在初始序列已基本有序的情況下，排序效率最高。A、二路歸并排序B、快速排序C、直接插入排序D、堆排序【正確答案】：C解析：

二路歸并排序和堆排序的效率用初始序列分布無關(guān)，而在初始序列已基本有序的情況下快速排序的效率最差。【正確答案】：為C。86.20.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A、哈希存儲B、順序存儲或鏈式存儲C、壓縮存儲D、索引存儲【正確答案】：B解析：

順序查找可以從前向后或從后向前依次查找，既適合于順序存儲結(jié)構(gòu)也適合于鏈式存儲結(jié)構(gòu)。87.26.數(shù)據(jù)結(jié)構(gòu)是指（）的集合以及它們之間的關(guān)系。A、數(shù)據(jù)元素B、計算方法C、邏輯存儲D、數(shù)據(jù)映像【正確答案】：A解析：

數(shù)據(jù)結(jié)構(gòu)中討論的數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的，這些數(shù)據(jù)元素之間存在某種關(guān)系，數(shù)據(jù)結(jié)構(gòu)課程中主要討論相鄰關(guān)系。88.32.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹就是度為2的樹B、二叉樹中不存在度大于2的結(jié)點C、二叉樹就是有序樹D、二叉樹中每個結(jié)點的度都為2【正確答案】：B89.12.設(shè)有5個元素進棧序列是a、b、c、d、e，其輸出序列是c、e、d、b、a，則該棧的容量至少是（）。A、1B、2C、3D、4【正確答案】：D解析：

對應(yīng)的操作是abc進棧，棧為（a，b，c），c出棧，de進棧，棧為（a，b，d，e），e出棧，d出棧，b出棧，a出棧。棧中最多4個元素?！菊_答案】：為D。90.22.以下排序方法中，（）不需要進行關(guān)鍵字的比較。A、快速排序B、歸并排序C、基數(shù)排序[].堆排序D、以上都不對【正確答案】：C解析：

在各種內(nèi)排序方法中基數(shù)排序不需要關(guān)鍵字比較?！菊_答案】：為C。91.21.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。A、數(shù)據(jù)元素具有同一特點B、不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項個數(shù)相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C、每個數(shù)據(jù)元素值都相同D、數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等【正確答案】：B解析：

因為只有同一類型的數(shù)據(jù)元素才能歸類到同一種結(jié)構(gòu)中，另外在計算機存儲器中表示數(shù)據(jù)元素時，必須為它們定義相同的數(shù)據(jù)類型。92.33.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹中度為0的結(jié)點個數(shù)等于度為2的結(jié)點個數(shù)加1B、二叉樹中結(jié)點個數(shù)必大于0C、完全二叉樹中任何結(jié)點的度為0或2D、二叉樹的度為2【正確答案】：A93.≤i≤m）。一個結(jié)點的子樹個數(shù)為該結(jié)點的（）。A、權(quán)B、維數(shù)C、次數(shù)（或度）D、序【正確答案】：C94.17.以下（）是"abcd321ABCD"串的子串。A、abcdB、321ABC、"abcABC"D、"21AB"【正確答案】：D95.5.一個有向無環(huán)圖G的拓撲序列為…，vi，…，vj，…，則不可能出現(xiàn)的情形是()。A、G中有邊<vi，vj>B、G中有一條從vi到vj的路徑C、G中沒有邊<vi，vj>D、G中有一條從vj到vi的路徑【正確答案】：D解析：

拓撲序列為…，vi，…，vj，…，則vi到vj有邊或者路徑，如果存在從vj到vi的路徑，則存在回路?！菊_答案】：為D。96.2.兩個棧采用順序存儲結(jié)構(gòu)時，共享同一個數(shù)組空間的好處是（）。A、減少存取時間，降低下溢出發(fā)生的機率B、節(jié)省存儲空間，降低上溢出發(fā)生的機率C、減少存取時間，降低上溢出發(fā)生的機率D、節(jié)省存儲空間，降低下溢出發(fā)生的機率【正確答案】：B解析：

兩個棧構(gòu)成共享棧，元素進棧時迎面生長，這樣可節(jié)省存儲空間，降低上溢出發(fā)生的機率。答案：為B。97.次探測。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。98.4.關(guān)于線性表的正確說法是（）。A、每個元素都有一個前趨和一個后繼元素B、線性表中至少有一個元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個元素和最后一個元素外，其余每個元素有且僅有一個前趨和一個后繼元素【正確答案】：D解析：

線性表屬典型的線性結(jié)構(gòu)。99.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。100.16.在含有n個結(jié)點的單鏈表中查找第i個結(jié)點的平均時間復(fù)雜度是()。A、O(log2n)B、O(1)C、O(n2)D、O(n)【正確答案】：D解析：

單鏈表不具有隨機存取特性，查找第i個結(jié)點的平均時間復(fù)雜度是O(n)。答案為D。1.5.隊列是一種對進隊、出隊操作的次序做了限制的線性表。A、正確B、錯誤【正確答案】：B解析：

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次序。2.11.圖的深度優(yōu)先遍歷算法僅對無向圖適用。A、正確B、錯誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷算法對無向圖和有向圖都適用。3.5.順序查找法適用于存儲結(jié)構(gòu)為順序或鏈式存儲的線性表。A、正確B、錯誤【正確答案】：A4.39.n個元素采用二路歸并排序算法，總的趟數(shù)為n。A、正確B、錯誤【正確答案】：B解析：

n個元素采用二路歸并排序算法，總的趟數(shù)為log2n。5.5.線性表中每個元素都有一個前趨元素和一個后繼元素。A、正確B、錯誤【正確答案】：B解析：

開始元素沒有前趨元素，終端元素沒有后繼元素。6.9.k路平衡歸并中，敗者樹的主要作用是減少歸并的趟數(shù)。A、正確B、錯誤【正確答案】：B解析：

敗者樹的主要作用是加速從k個記錄中選取最小記錄，并不能減少歸并的趟數(shù)。7.7.采用多路平衡歸并方法可以減少初始歸并段的個數(shù)。A、正確B、錯誤【正確答案】：B解析：

采用多路平衡歸并方法可以減少歸并的趟數(shù)。8.13.空棧是指棧中元素沒有賦值。A、正確B、錯誤【正確答案】：B解析：

空棧是指棧中沒有元素。9.5.一個連通圖的生成樹是唯一的。A、正確B、錯誤【正確答案】：B解析：

一個連通圖的生成樹可能有多棵。10.9.數(shù)據(jù)對象就是一組任意數(shù)據(jù)元素的集合。A、正確B、錯誤【正確答案】：B解析：

數(shù)據(jù)對象是指具有相同性質(zhì)的有限個數(shù)據(jù)元素的集合。11.徑。A、正確B、錯誤【正確答案】：A解析：

頂點i和頂點j屬一個連通分量，而頂點k屬另一個連通分量，所以頂點i到頂點k沒有路徑。12.25.簡單選擇排序是一種不穩(wěn)定的排序方法。A、正確B、錯誤【正確答案】：A13.14.非空二叉樹的后序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：A14.序的時間。A、正確B、錯誤【正確答案】：B解析：

主要取決于內(nèi)外存數(shù)據(jù)交換的次數(shù)。15.15.任何一個圖，一旦指定源點，其深度優(yōu)先遍歷序列是唯一的。A、正確B、錯誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷序列不一定是唯一的。16.29.冒泡排序在最好情況下元素移動的次數(shù)為0。A、正確B、錯誤【正確答案】：A解析：

冒泡排序在初始數(shù)據(jù)正序時元素移動的次數(shù)為0。91、30.冒泡排序中，關(guān)鍵字比較的次數(shù)與初始數(shù)據(jù)序列有關(guān)，而元素移動的次數(shù)與初始數(shù)據(jù)序列無17.12.有向圖的遍歷不可采用廣度優(yōu)先遍歷方法。A、正確B、錯誤【正確答案】：B解析：

廣度優(yōu)先遍歷算法適合于有向圖和無向圖。49、13.圖的深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法是兩種不同的算法，所以任何圖的這兩種遍歷序18.5.樹中元素之間是多對多的關(guān)系。A、正確B、錯誤【正確答案】：B19.18.非空二叉樹的先序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：A20.36.基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的大小無關(guān)。A、正確B、錯誤【正確答案】：B解析：

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

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次數(shù)。22.12.相同的n個元素的不同序列通過一個棧一定不會得到相同的出棧序列。A、正確B、錯誤【正確答案】：B解析：

相同的n個元素的不同序列通過一個?？赡軙玫较嗤某鰲Ｐ蛄?。例如，進棧序列1、2、3和23.37.基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。A、正確B、錯誤【正確答案】：B24.42.二路歸并排序算法的時間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。A、正確B、錯誤【正確答案】：A25.9.棧和隊列都是限制存取端的線性表。A、正確B、錯誤【正確答案】：A解析：

棧和隊列中元素的邏輯關(guān)系都是線性關(guān)系，僅限制在端點進行插入和刪除操作。26.14.圖的遍歷就是訪問圖中所有頂點。A、正確B、錯誤【正確答案】：B解析：

圖的遍歷是指以某種順序訪問圖中所有頂點，且每個頂點僅訪問一次。27.23.從時間性能看，堆排序總是優(yōu)于簡單選擇排序。A、正確B、錯誤【正確答案】：A解析：

堆排序的最好、最壞和平均時間復(fù)雜度均為O(nlog2n)，而簡單選擇排序的最好、最壞和平均時間復(fù)雜度均為O(n2)。28.7.在二叉排序樹中，每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小。A、正確B、錯誤【正確答案】：A29.45.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。A、正確B、錯誤【正確答案】：B30.后移動。A、正確B、錯誤【正確答案】：B31.7.哈夫曼樹是帶權(quán)路徑長度最短的二叉樹，權(quán)值越大的結(jié)點離根結(jié)點越遠。A、正確B、錯誤【正確答案】：B32.41.對于不同的初始數(shù)據(jù)序列，二路歸并排序算法中關(guān)鍵字比較次數(shù)有所不同。A、正確B、錯誤【正確答案】：A解析：

二路歸并排序算法的時間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)，但關(guān)鍵字比較次數(shù)是相關(guān)的。33.44.所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。A、正確B、錯誤【正確答案】：B34.16.通常外排序采用多路歸并排序方法，實際上也可以用其他內(nèi)排序方法代替歸并排序方法。A、正確B、錯誤【正確答案】：B35.子。A、正確B、錯誤【正確答案】：A解析：

二叉排序樹的任意一棵子樹也是二叉排序樹。36.徑。A、正確B、錯誤【正確答案】：A解析：

如果頂點j到頂點k有路徑，則頂點i有一條通過頂點j到達頂點k的路徑，與題中條件矛盾。37.干塊，每塊中的數(shù)據(jù)個數(shù)必須相同A、正確B、錯誤【正確答案】：B解析：

分塊查找的數(shù)據(jù)組織方式為：數(shù)據(jù)表+索引表，數(shù)據(jù)表分塊，塊間有序，塊內(nèi)無序?！菊_答案】：為B。38.19.外排序中沒有關(guān)鍵字比較。A、正確B、錯誤【正確答案】：B解析：

外排序中需要關(guān)鍵字比較。39.1.順序隊采用數(shù)組存放隊中元素，數(shù)組具有隨機存取特性，所以順序隊中可以隨機存取元素。A、正確B、錯誤【正確答案】：B解析：

順序隊采用數(shù)組存放隊中元素，盡管數(shù)組具有隨機存取特性，但隊列的操作特性是順序存取，只能存取兩端的元素。40.8.哈夫曼樹中結(jié)點個數(shù)可以偶數(shù)也可以是奇數(shù)。A、正確B、錯誤【正確答案】：B41.2.對于無向圖生成樹，從同一頂點出發(fā)所得到的生成樹一定是相同的。A、正確B、錯誤【正確答案】：B解析：

無向圖的生成樹可能有多棵，從同一頂點出發(fā)所得到的生成樹也不一定相同。42.17.由二叉樹某種遍歷方式產(chǎn)生的結(jié)果是一個線性序列。A、正確B、錯誤【正確答案】：A43.2.給定一棵樹T，可以找到唯一的一棵二叉樹B與之對應(yīng)。A、正確B、錯誤【正確答案】：A44.10.圖是一種結(jié)點之間無層次關(guān)系的線性結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

圖是一種非線性結(jié)構(gòu)。45.11.哈希沖突是指同一個關(guān)鍵字對應(yīng)多個不同的哈希地址。A、正確B、錯誤【正確答案】：B解析：

哈希沖突是指多個不同一個關(guān)鍵字對應(yīng)相同的哈希地址。46.1.給定一棵樹T，將其轉(zhuǎn)換成二叉樹B后，它們的結(jié)點個數(shù)相同。A、正確B、錯誤【正確答案】：A47.3.對于無向圖生成樹，其深度優(yōu)先生成樹和廣度優(yōu)先生成樹一定不相同。A、正確B、錯誤【正確答案】：B解析：

不一定，如果一個無向圖的生成樹唯一，從同一頂點出發(fā)構(gòu)造的深度優(yōu)先生成樹和廣度優(yōu)先生成樹也是相同的。48.16.非空二叉樹的中序序列的第一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤【正確答案】：B49.1.一種邏輯結(jié)構(gòu)的數(shù)據(jù)只有一種對應(yīng)的存儲結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B50.20.k路最佳歸并樹一定是一棵k路平衡樹。A、正確B、錯誤【正確答案】：B解析：

k路最佳歸并樹不一定是一棵k路平衡樹。51.11.有n個不同的元素通過一個棧，產(chǎn)生的所有出棧序列恰好構(gòu)成這n個元素的全排列。A、正確B、錯誤【正確答案】：B52.2.順序查找方法只能從順序表的前端向后端查找。A、正確B、錯誤【正確答案】：B解析：

順序查找方法可以從順序表的前端向后端查找，也可以從順序表的后端向前端查找。53.5.置換-選擇排序算法的作用是由一個無序文件生成一個全部有序的文件。A、正確B、錯誤【正確答案】：B54.43.內(nèi)排序方法要求數(shù)據(jù)一定以順序表方式存儲。A、正確B、錯誤【正確答案】：B解析：

有些內(nèi)排序方法也適合數(shù)據(jù)采用鏈表方式存儲的情況。55.31.冒泡排序在最好情況下的時間復(fù)雜度也是O(n2)。A、正確B、錯誤【正確答案】：B解析：

冒泡排序在最好情況下的時間復(fù)雜度為O(n)。56.數(shù)據(jù)的邏輯結(jié)構(gòu)。50、19.棧是一種特殊的線性表，其特殊之處在于棧的存儲結(jié)構(gòu)比較特殊。A、正確B、錯誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對線性表的操作做了限制。57.6.數(shù)據(jù)的運算描述是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的。A、正確B、錯誤【正確答案】：A解析：

數(shù)據(jù)的運算描述是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，而數(shù)據(jù)運算的具體實現(xiàn)與存儲結(jié)構(gòu)相關(guān)聯(lián)。58.26.n個元素采用簡單選擇排序進行排序，關(guān)鍵字比較的次數(shù)總是n(n-1)/2。A、正確B、錯誤【正確答案】：A59.8.線性表的邏輯順序總與其物理順序一致。A、正確B、錯誤【正確答案】：B解析：

當線性表采用鏈式存儲結(jié)構(gòu)時，其邏輯順序與物理順序可能不一致。60.關(guān)。A、正確B、錯誤【正確答案】：B解析：

關(guān)鍵字比較的次數(shù)與元素移動的次數(shù)都與初始數(shù)據(jù)序列有關(guān)。61.4.在一個含有n（n≥1）個元素的線性表中，所有元素值不能相同。A、正確B、錯誤【正確答案】：B解析：

在線性表中允許存在元素值相同的元素，但它們的位置是不同。62.22.內(nèi)排序過程在數(shù)據(jù)量很大時就變成了外排序過程。A、正確B、錯誤【正確答案】：B63.35.基數(shù)排序與初始數(shù)據(jù)的次序無關(guān)。A、正確B、錯誤【正確答案】：A64.7.n個元素進隊的順序和出隊的順序總是一致的。A、正確B、錯誤【正確答案】：A解析：

后進隊的元素后出隊，先進隊的元素先出隊。65.6.置換-選擇排序算法的作用是由一個無序文件生成若干個有序的子文件。A、正確B、錯誤【正確答案】：A66.9.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)各有優(yōu)缺點。67.6.哈夫曼樹中沒有度為1的結(jié)點。A、正確B、錯誤【正確答案】：A68.3.在隊空間大小為n的非循環(huán)隊列中，最多只能進行n次進隊操作。A、正確B、錯誤【正確答案】：A解析：

在非循環(huán)隊列，元素進隊時隊尾指針遞增，當?shù)竭_最大下標時不能再進隊，所以總計只能進隊n次。69.1.k路最佳歸并樹在外排序中的作用是產(chǎn)生初始歸并段。A、正確B、錯誤【正確答案】：B70.成樹。A、正確B、錯誤【正確答案】：B解析：

這樣的子圖不一定是連通的。71.值。A、正確B、錯誤【正確答案】：A72.17.影響外排序的時間因素主要是內(nèi)存與外存交換信息的次數(shù)。A、正確B、錯誤【正確答案】：A73.個比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯誤【正確答案】：A解析：

歸并趟數(shù)s=log55=1，5個記錄選取最小記錄需比較4次，所以總共需要(100-1)×4×1=396次關(guān)鍵字比較。74.17.棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)是任意的。A、正確B、錯誤【正確答案】：B解析：

棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)一定是線性結(jié)構(gòu)，不能是樹形結(jié)構(gòu)或圖形結(jié)構(gòu)。75.34.直接插入排序、冒泡排序和簡單選擇排序在最好情況下的時間復(fù)雜度均為O(n)。A、正確B、錯誤【正確答案】：B解析：

直接插入排序和冒泡排序在最好情況下的時間復(fù)雜度均為O(n)。76.12.n（n>2）個結(jié)點的二叉樹中至少有一個度為2的結(jié)點。A、正確B、錯誤【正確答案】：B77.16.棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。A、正確B、錯誤【正確答案】：A解析：

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

線性表是有限個相同性質(zhì)的元素的序列。79.24.簡單選擇排序中，每趟產(chǎn)生的有序區(qū)中所有元素在以后的排序中不再改變位置。A、正確B、錯誤【正確答案】：A80.6.線性表的長度是線性表占用的存儲空間的大小。A、正確B、錯誤【正確答案】：B解析：

線性表的長度是指表中元素個數(shù)，屬邏輯結(jié)構(gòu)的概念，與線性表占用的存儲空間大小無關(guān)。81.14.棧是一種特殊的線性表，線性表的所有運算都可以施加在棧上。A、正確B、錯誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對線性表的插入和刪除操作做了限制，所以不能將線性表的所有運算都施加在棧上。82.14.在外排序過程中，一個記錄的讀入內(nèi)存的次數(shù)和寫到外存的次數(shù)必定相等。A、正確B、錯誤【正確答案】：A83.1.線性表中所有元素的數(shù)據(jù)類型必須相同。A、正確B、錯誤【正確答案】：A解析：

線性表中所有元素具有相同性質(zhì)，在設(shè)計存儲結(jié)構(gòu)時，它們對應(yīng)的數(shù)據(jù)類型也必然相同。84.列是不可能相同的。A、正確B、錯誤【正確答案】：B解析：

圖的兩種遍歷序列可能相同。85.錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯誤【正確答案】：B解析：

歸并趟數(shù)s=log55=1，采用敗者樹時，5個記錄選取最小記錄需比較log25=3次，所以總共需86.間復(fù)雜度的主要因素