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

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

只有簡(jiǎn)單回路才是起始頂點(diǎn)和終止頂點(diǎn)相同的簡(jiǎn)單路徑。存儲(chǔ)稀疏圖，用鄰接表比鄰接矩陣更省空間。若有向圖中存在拓?fù)湫蛄校ò宽旤c(diǎn)），則該圖不存在回路?！菊_答案】：為C。2.35.圖的遍歷是指（）。A、訪問(wèn)圖的所有頂點(diǎn)B、以某種次序訪問(wèn)圖的所有頂點(diǎn)C、從一個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中所有頂點(diǎn)且每個(gè)頂點(diǎn)只能訪問(wèn)一次D、從一個(gè)頂點(diǎn)出發(fā)訪問(wèn)圖中所有頂點(diǎn)但每個(gè)頂點(diǎn)可以訪問(wèn)多次【正確答案】：C解析：

圖的遍歷是從給定的初始點(diǎn)出發(fā)訪問(wèn)每個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)僅訪問(wèn)一次。3.果是_（）__。A、0，1，2，3，4B、0，1，2，4，3C、0，1，3，4，2D、0，1，4，2，3【正確答案】：A解析：

直接從頂點(diǎn)0出發(fā)進(jìn)行深度優(yōu)先遍歷，得到的DFS序列為0，1，2，3，4?！菊_答案】：為A。4.15.一棵含有n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，其線索個(gè)數(shù)為（）。A、2nB、n-1C、n+1D、n【正確答案】：C5.14.由n個(gè)無(wú)序的元素創(chuàng)建一個(gè)有序單鏈表的算法的時(shí)間復(fù)雜度是（）。A、O(nlog2n)B、O(n)C、O(1)D、以上都不對(duì)【正確答案】：A解析：

創(chuàng)建有序單鏈表需要排序，而排序的可以采用時(shí)間復(fù)雜度為O(nlog2n)的算法。6.29.對(duì)于采用置換-選擇算法產(chǎn)生的歸并段，以下含有3個(gè)初始?xì)w并段的組是（）有序段。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)生的歸并段一定是有序段，選項(xiàng)A錯(cuò)誤。而前一個(gè)歸并段的最后一個(gè)關(guān)鍵字一定大于下一個(gè)歸并段的第一個(gè)關(guān)鍵字，選項(xiàng)B、D錯(cuò)誤。7.21.線索二叉樹(shù)中的線索是指（）。A、左孩子B、右孩子C、指針D、標(biāo)識(shí)【正確答案】：C8.=1，則pi（1≤i≤n-1）的值是()。A、n-i+1B、n-iC、iD、有多種可能【正確答案】：A解析：

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

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

不成功時(shí)最大的比較次數(shù)=log2(n+1)=7?！菊_答案】：為D。11.10.某算法的空間復(fù)雜度為O(1)，則()。A、該算法執(zhí)行不需要任何輔助空間B、該算法執(zhí)行所需輔助空間大小與問(wèn)題規(guī)模n無(wú)關(guān)C、該算法執(zhí)行不需要任何空間D、該算法執(zhí)行所需全部空間大小與問(wèn)題規(guī)模n無(wú)關(guān)【正確答案】：B解析：

一個(gè)算法的空間復(fù)雜度為O(1)，只能說(shuō)明其輔助空間大小與問(wèn)題規(guī)模n無(wú)關(guān)，并不是說(shuō)該算法不需要空間。答案為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ù)排序的第一趟排序是按照個(gè)位數(shù)字來(lái)排序的，第二趟排序是按然十位數(shù)字的大小進(jìn)行排序的?！菊_答案】：為C。13.9.以下數(shù)據(jù)結(jié)構(gòu)中元素之間為非線性關(guān)系的是()。A、棧B、隊(duì)列C、線性表D、以上都不是【正確答案】：D解析：

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

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

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

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

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

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

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

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

在一個(gè)有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，圖中不一定有邊<a，b>。【正確答案】：為A。10、10.以下敘述中錯(cuò)誤的是（）。【正確答案】：C圖的深度優(yōu)先遍歷適合無(wú)向圖和有向圖。【正確答案】：為C。26.34.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的（）算法。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷【正確答案】：A解析：

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

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

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

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

B樹(shù)中成功的查找會(huì)落在某個(gè)內(nèi)部結(jié)點(diǎn)中，失敗的查找會(huì)落在某個(gè)外部結(jié)點(diǎn)中?！菊_答案】：為B。35.8.一棵高度為h、結(jié)點(diǎn)個(gè)數(shù)為n的m（m≥3）次樹(shù)中，其分支數(shù)是（）。A、nhB、n+hC、n-1D、h-1【正確答案】：C36.1.若某非空二叉樹(shù)的中序序列和后序序列正好相反，則該二叉樹(shù)的形態(tài)是（）。A、只有一個(gè)根結(jié)點(diǎn)B、所有分支結(jié)點(diǎn)都有左右孩子C、所有結(jié)點(diǎn)沒(méi)有左子樹(shù)D、所有結(jié)點(diǎn)沒(méi)有右子樹(shù)【正確答案】：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解析：

當(dāng)出棧序列的第一個(gè)元素為4時(shí)，只有唯一的出棧序列4、3、2、1，不可能有4、3、1、2的出棧序列。本題【正確答案】：為C。39.2.以下算法的時(shí)間復(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開(kāi)始每循環(huán)一次按3倍遞增，有i=3m≤n，m≤log3n=O(log2n)。答案為D。40.19.哈希查找方法一般適用于（）情況下的查找。A、查找表為鏈表B、查找表為有序表C、關(guān)鍵字集合比地址集合大得多D、關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系?！菊_答案】：D解析：

哈希表通過(guò)哈希函數(shù)和沖突解決函數(shù)確定存儲(chǔ)地址的，適合關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系的數(shù)據(jù)集的存儲(chǔ)與查找。【正確答案】：為D。41.57.初始數(shù)據(jù)序列中有兩個(gè)相同關(guān)鍵字的元素，通過(guò)不穩(wěn)定的排序方法排序后，（）。A、這兩個(gè)元素的前后位置不發(fā)生變化B、這兩個(gè)元素的前后位置一定發(fā)生變化C、這兩個(gè)元素的位置不發(fā)生變化D、這兩個(gè)元素的前后位置可能發(fā)生變化【正確答案】：D42.的排序方法是（）。A、簡(jiǎn)單選擇排序B、快速排序C、冒泡排序D、直接插入排序【正確答案】：A解析：

從數(shù)據(jù)排列次序的變化過(guò)程看到，每一趟都從無(wú)序區(qū)中選一個(gè)最小的元素歸位。43.11.以下算法的時(shí)間復(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階對(duì)稱矩陣A壓縮存儲(chǔ)到一維數(shù)組B中，則數(shù)組B的長(zhǎng)度最少為_(kāi)()。A、100B、40C、80D、55【正確答案】：D解析：

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

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

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

最小生成樹(shù)是圖中所有頂點(diǎn)構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小。【正確答案】：為D。題型：48.5.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）。（1≤i≤n）的存儲(chǔ)地址為L(zhǎng)OC(a0)+i×sizeof(ElemType)，也就是說(shuō)，對(duì)于給定的序號(hào)i，在O(1)的A、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B、順序存取的存儲(chǔ)結(jié)構(gòu)C、索引存取的存儲(chǔ)結(jié)構(gòu)D、散列存取的存儲(chǔ)結(jié)構(gòu)【正確答案】：A解析：

若含有n個(gè)元素的線性表a采用順序表存儲(chǔ)，每個(gè)元素的類型為ElemType，則第i個(gè)元素ai時(shí)間內(nèi)找到該元素值，這是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。而順序存取是一種讀寫方式，不是存儲(chǔ)方式，有別于順序存儲(chǔ)。49.4.以下最適合用作鏈隊(duì)的不帶頭結(jié)點(diǎn)的鏈表是（）。A、只帶首結(jié)點(diǎn)指針的循環(huán)單鏈表B、只帶尾結(jié)點(diǎn)指針的單鏈表C、只帶首結(jié)點(diǎn)指針的單鏈表D、只帶尾結(jié)點(diǎn)指針的循環(huán)單鏈表【正確答案】：D解析：

只帶尾結(jié)點(diǎn)指針的循環(huán)單鏈表的進(jìn)隊(duì)操作和出隊(duì)操作時(shí)間復(fù)雜度為O(1)?！菊_答案】：為D。50.30.棧的“先進(jìn)后出”特性是指（）。A、最后進(jìn)棧的元素總是最先出棧B、當(dāng)同時(shí)進(jìn)行進(jìn)棧和出棧操作時(shí)，總是進(jìn)棧優(yōu)先C、每當(dāng)有出棧操作時(shí)，總要先進(jìn)行一次進(jìn)棧操作D、每次出棧的元素總是最先進(jìn)棧的元素【正確答案】：A51.44.以下穩(wěn)定的排序方法是（）。A、直接插入排序和快速排序B、直接插入排序和冒泡排序C、簡(jiǎn)單選擇排序和歸并排序D、歸并排序和冒泡排序【正確答案】：B52.1.某遞歸算法的時(shí)間遞推式如下：T(1)=1T(n)=T(n/2)+n當(dāng)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)于哈夫曼樹(shù)的說(shuō)法，不正確的是()。A、對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹(shù)可能不唯一B、哈夫曼樹(shù)具有最小帶權(quán)路徑長(zhǎng)度C、哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)D、哈夫曼樹(shù)中除了度為2的結(jié)點(diǎn)外，還有度為1的結(jié)點(diǎn)和葉結(jié)點(diǎn)【正確答案】：D54.到'*'時(shí)，運(yùn)算數(shù)棧（從棧頂?shù)綏５状涡颍椋ǎ?。A、861B、581C、321D、361【正確答案】：C解析：

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

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

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

這樣的有向圖中只有頂點(diǎn)i到頂點(diǎn)j（i<j）可能有邊，而頂點(diǎn)j到頂點(diǎn)i一定沒(méi)有邊，也就是說(shuō)這樣的有向圖中一定沒(méi)有回路，所以可以產(chǎn)生拓?fù)湫蛄?，但拓?fù)湫蛄胁灰欢ㄎㄒ弧！菊_答案】：為C。60.隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置），則其元素個(gè)數(shù)為（）。A、rear-frontB、rear-front-1C、(rear-front)％N+1D、(rear-front+N)％N【正確答案】：D解析：

在非循環(huán)隊(duì)列中rear總是跑在front的前面，其元素個(gè)數(shù)=rear-front，在循環(huán)隊(duì)列中rear可能比f(wàn)ront多跑一圈，所以其元素個(gè)數(shù)=(rear-front+N)％N。【正確答案】：為D。61.31.哈希查找的基本思想是根據(jù)（）來(lái)決定元素的存儲(chǔ)地址。A、元素的序號(hào)B、元素個(gè)數(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ù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在一種或多種特定關(guān)系D、同一數(shù)據(jù)中的所有數(shù)據(jù)元素值之間存在一種或多種特定關(guān)系【正確答案】：B解析：

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。63.30.n個(gè)記錄采用置換-選擇算法產(chǎn)生m個(gè)有序段，m和n的關(guān)系是（）。A、m與n成正比B、m與n成反比C、m=log2nD、以上都不對(duì)【正確答案】：D解析：

如w=1時(shí)，記錄序列{1,2,3,4,5}產(chǎn)生一個(gè)有序段，而{5,4,3,2,1}產(chǎn)生5個(gè)有序段，所以一般來(lái)講，m與數(shù)據(jù)序列、內(nèi)存工作區(qū)可容納的記錄個(gè)數(shù)w和n都有關(guān)，但并不是A、B、C選項(xiàng)所指的直接關(guān)系。64.42.冒泡排序最少元素移動(dòng)的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A65.的數(shù)據(jù)結(jié)構(gòu)為（）。A、數(shù)組B、樹(shù)C、圖D、線性表【正確答案】：B66.種要求的排序方法是（）。A、先按k1值進(jìn)行直接插入排序，再按k2值進(jìn)行簡(jiǎn)單選擇排序B、先按k2值進(jìn)行直接插入排序，再按k1值進(jìn)行簡(jiǎn)單選擇排序C、先按k1值進(jìn)行簡(jiǎn)單選擇排序，再按k2值進(jìn)行直接插入排序D、先按k2值進(jìn)行簡(jiǎn)單選擇排序，再按k1值進(jìn)行直接插入排序【正確答案】：D解析：

從題中看出，k1數(shù)據(jù)項(xiàng)較k2數(shù)據(jù)項(xiàng)的權(quán)重，結(jié)合基數(shù)排序的情況，如在對(duì)若干兩位的十進(jìn)制數(shù)進(jìn)行基數(shù)遞增排序時(shí)，十位數(shù)較個(gè)位數(shù)權(quán)重，所以先按個(gè)位數(shù)排序，再按十位數(shù)排序，否則結(jié)果是錯(cuò)誤的，因此應(yīng)先按k2數(shù)據(jù)項(xiàng)排序，再按k1數(shù)據(jù)項(xiàng)排序。再考慮排序算法的穩(wěn)定性，簡(jiǎn)單選擇排序是不穩(wěn)定的，直接插入排序是穩(wěn)定的，如果對(duì)k1數(shù)據(jù)項(xiàng)采用不穩(wěn)定的排序方法，則可能出現(xiàn)相同k1值、k2值不同的元素改變相對(duì)次序，即可能出現(xiàn)k1值相同、k2大的在前小的在后，這顯然不符合題意，所以應(yīng)對(duì)最后的k1采用穩(wěn)定的排序方法。綜合起來(lái)應(yīng)該先按k2值進(jìn)行簡(jiǎn)單選擇排序，再按k1值進(jìn)行插入排序。本題【正確答案】：為D。67.時(shí)，()。A、僅修改隊(duì)頭指針B、僅修改隊(duì)尾指針C、隊(duì)頭、隊(duì)尾指針一定都會(huì)修改D、隊(duì)頭、隊(duì)尾指針可能都會(huì)修改【正確答案】：D解析：

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

在無(wú)向圖中，一條邊計(jì)入兩個(gè)頂點(diǎn)的度數(shù)。69.8.順序表具有隨機(jī)存取特性，指的是（）。A、查找值為x的元素與順序表中元素個(gè)數(shù)n無(wú)關(guān)B、查找值為x的元素與順序表中元素個(gè)數(shù)n有關(guān)C、查找序號(hào)為i的元素與順序表中元素個(gè)數(shù)n無(wú)關(guān)D、查找序號(hào)為i的元素與順序表中元素個(gè)數(shù)n有關(guān)【正確答案】：C解析：

一種存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存取特性指的是，對(duì)于給定的序號(hào)i，在O(1)時(shí)間內(nèi)找到對(duì)應(yīng)元素值。70.11.最不適合用作鏈隊(duì)的鏈表是（）。A、只帶頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表B、只帶隊(duì)首結(jié)點(diǎn)指針的循環(huán)雙鏈表C、只帶隊(duì)尾結(jié)點(diǎn)指針的循環(huán)雙鏈表D、以上都不適合【正確答案】：A解析：

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

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

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

設(shè)樹(shù)中結(jié)點(diǎn)個(gè)數(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.在長(zhǎng)度為n（n≥1）的循環(huán)雙鏈表L中，在尾結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。A、O(n2)B、O(n)C、O(1)D、O(nlog2n)【正確答案】：C解析：

循環(huán)雙鏈表可以O(shè)(1)時(shí)間找到尾結(jié)點(diǎn)p，再在結(jié)點(diǎn)p的后面插入新結(jié)點(diǎn)s，時(shí)間也是O(1)。答案為C。77.20.關(guān)于串的的敘述，不正確的是（）。A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、替換是串的一種重要運(yùn)算D、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)【正確答案】：B78.23.計(jì)算機(jī)所處理的數(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ù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系【正確答案】：B解析：

數(shù)據(jù)結(jié)構(gòu)中討論的數(shù)據(jù)是由數(shù)據(jù)元素構(gòu)成的，這些數(shù)據(jù)元素之間存在某種關(guān)系。79.3，4}，下一步選取的目標(biāo)頂點(diǎn)可能是（）。A、頂點(diǎn)2B、頂點(diǎn)3C、頂點(diǎn)4D、頂點(diǎn)7【正確答案】：D解析：

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

圖的深度優(yōu)先遍歷算法既適合無(wú)向圖也適合有向圖的遍歷。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算法求最小生成樹(shù)時(shí)，U={1，2，3}，V-U={4，5，…}，候選邊只能是這兩個(gè)頂點(diǎn)集之間的邊?！菊_答案】：為C。82.12.若串str="Software"，其子串的數(shù)目是（）。A、8B、9C、36D、37【正確答案】：D83.50.以下排序方法中，（）不需要進(jìn)行關(guān)鍵字的比較。A、快速排序B、歸并排序C、基數(shù)排序D、堆排序【正確答案】：C解析：

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

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

順序查找可以從前向后或從后向前依次查找，既適合于順序存儲(chǔ)結(jié)構(gòu)也適合于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。87.26.數(shù)據(jù)結(jié)構(gòu)是指（）的集合以及它們之間的關(guān)系。A、數(shù)據(jù)元素B、計(jì)算方法C、邏輯存儲(chǔ)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)于二叉樹(shù)的說(shuō)法中正確的是（）。A、二叉樹(shù)就是度為2的樹(shù)B、二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)C、二叉樹(shù)就是有序樹(shù)D、二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2【正確答案】：B89.12.設(shè)有5個(gè)元素進(jìn)棧序列是a、b、c、d、e，其輸出序列是c、e、d、b、a，則該棧的容量至少是（）。A、1B、2C、3D、4【正確答案】：D解析：

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

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

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

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

兩個(gè)棧構(gòu)成共享?xiàng)?，元素進(jìn)棧時(shí)迎面生長(zhǎng)，這樣可節(jié)省存儲(chǔ)空間，降低上溢出發(fā)生的機(jī)率。答案：為B。97.次探測(cè)。A、k-1B、kC、k+1D、k(k+1)/2【正確答案】：D解析：

最少探測(cè)的情況是，第一個(gè)同義詞放在哈希表ha[d]位置，探測(cè)1次，第2個(gè)同義詞放在哈希表ha[d+1]位置，探測(cè)2次，以此類推，第k個(gè)同義詞放在哈希表ha[d+k-1]位置，探測(cè)k次，總的探測(cè)次數(shù)=1+2+…+k=k(k+1)/2?！菊_答案】：為D。98.4.關(guān)于線性表的正確說(shuō)法是（）。A、每個(gè)元素都有一個(gè)前趨和一個(gè)后繼元素B、線性表中至少有一個(gè)元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素有且僅有一個(gè)前趨和一個(gè)后繼元素【正確答案】：D解析：

線性表屬典型的線性結(jié)構(gòu)。99.22.對(duì)于AOE網(wǎng)的關(guān)鍵路徑，以下敘述（）是正確的。A、任何一個(gè)關(guān)鍵活動(dòng)提前完成，則整個(gè)工程一定會(huì)提前完成B、完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最短路徑長(zhǎng)度C、一個(gè)AOE網(wǎng)的關(guān)鍵路徑一定是唯一的D、任何一個(gè)活動(dòng)持續(xù)時(shí)間的改變可能影響關(guān)鍵路徑的改變【正確答案】：D解析：

AOE網(wǎng)中的關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑，其長(zhǎng)度為完成整個(gè)工程的最短時(shí)間。一個(gè)AOE網(wǎng)可能存在多條關(guān)鍵路徑，若提前完成所有關(guān)鍵路徑都包含的關(guān)鍵活動(dòng)則整個(gè)工程一定會(huì)提前完成，但改變?nèi)魏我粋€(gè)活動(dòng)的持續(xù)時(shí)間可能影響關(guān)鍵路徑的改變（因?yàn)榇藭r(shí)關(guān)鍵路徑可能發(fā)生改變）。答案：為D。100.16.在含有n個(gè)結(jié)點(diǎn)的單鏈表中查找第i個(gè)結(jié)點(diǎn)的平均時(shí)間復(fù)雜度是()。A、O(log2n)B、O(1)C、O(n2)D、O(n)【正確答案】：D解析：

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

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

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

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

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

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

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

空棧是指棧中沒(méi)有元素。9.5.一個(gè)連通圖的生成樹(shù)是唯一的。A、正確B、錯(cuò)誤【正確答案】：B解析：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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