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

第頁數(shù)據(jù)結(jié)構(gòu)必過復(fù)習(xí)試題含答案1.拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條邊<a，b>A、僅ⅠB、僅Ⅰ、ⅢC、僅Ⅱ、ⅢD、Ⅰ、Ⅱ和ⅢE、圖的遍歷是從給定的初始點(diǎn)出發(fā)訪問每個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)僅訪問一次F、圖的深度優(yōu)先遍歷適合無向圖G、圖的深度優(yōu)先遍歷不適合有向圖H、圖的深度優(yōu)先遍歷是一個(gè)遞歸過程【正確答案】：A解析：

在一個(gè)有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，圖中不一定有邊<a，b>。【正確答案】：為A。10、10.以下敘述中錯(cuò)誤的是（）。【正確答案】：C圖的深度優(yōu)先遍歷適合無向圖和有向圖。【正確答案】：為C。2.21.采用順序查找方法查找長度為n的線性表時(shí)，成功查找的平均查找長度為（）。A、nB、n/2C、(n+1)/2D、(n-1)/2【正確答案】：C解析：

解：順序查找時(shí)，元素ai需i次比較，成功查找的平均查找長度=(1+2+…+n)/n=(n+1)/2。3.移方式是（）。A、i=next[j]B、i不變C、j不變D、j=next[j]【正確答案】：B解析：

在KMP算法中，當(dāng)tj≠si時(shí)，i位置不改變。4.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。5.1.若某非空二叉樹的中序序列和后序序列正好相反，則該二叉樹的形態(tài)是（）。A、只有一個(gè)根結(jié)點(diǎn)B、所有分支結(jié)點(diǎn)都有左右孩子C、所有結(jié)點(diǎn)沒有左子樹D、所有結(jié)點(diǎn)沒有右子樹【正確答案】：C6.()來保存這些數(shù)據(jù)。A、線性表B、隊(duì)列C、棧D、單鏈表【正確答案】：B解析：

隊(duì)列具有先進(jìn)先出的特點(diǎn)?！菊_答案】：為B。7.20.在數(shù)據(jù)結(jié)構(gòu)中，以下說法中不正確的是（）。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位B、數(shù)據(jù)項(xiàng)是不可分割的最小可標(biāo)識(shí)單位C、數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D、數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成【正確答案】：D解析：

數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，而數(shù)據(jù)項(xiàng)不能再拆分，否則就沒有意義了。8.≤i≤m）。一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)為該結(jié)點(diǎn)的（）。A、權(quán)B、維數(shù)C、次數(shù)（或度）D、序【正確答案】：C9.值為()。A、一定是2B、一定是1C、不可能是1D、以上都不對(duì)【正確答案】：C解析：

若出棧序列中p1=3，說明1、2先進(jìn)棧，次棧頂為2，此時(shí)可以出棧2（p2=2），或者4進(jìn)棧再出棧（p2=4），或者4、5進(jìn)棧再出棧5（p2=5），…，總之p2可能是除了1外的其他整數(shù)?！菊_答案】：為C。10.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。11.13.若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有向圖()。A、是個(gè)有根有向圖B、是個(gè)強(qiáng)連通圖C、含有多個(gè)入度為0的頂點(diǎn)D、含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量【正確答案】：D解析：

該圖中存在回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量的一部分或全部?！菊_答案】：為D。12.()。A、5B、6C、7D、8【正確答案】：D13.27.n個(gè)頂點(diǎn)的連通圖的生成樹有（）個(gè)頂點(diǎn)。A、n-1B、nC、n+1D、不確定【正確答案】：B14.45.以下（）方法在數(shù)據(jù)基本有序時(shí)效率最好。A、快速排序B、冒泡排序C、堆排序D、希爾排序【正確答案】：B15.51.以下排序方法中，穩(wěn)定的排序方法是（）。A、快速排序B、堆排序C、希爾排序D、基數(shù)排序【正確答案】：D解析：

基數(shù)排序是一種穩(wěn)定的排序方法。16.8.下面（）算法適合用于構(gòu)造一個(gè)稠密圖的最小生成樹。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法【正確答案】：B解析：

Prim算法和Kruskal算法用于構(gòu)造一個(gè)帶權(quán)連通圖（頂點(diǎn)個(gè)數(shù)為n，邊數(shù)為e）的最小生成樹，前者的時(shí)間復(fù)雜度為O(n2)，后者的時(shí)間復(fù)雜度為O(elog2e)。【正確答案】：為B。17.隊(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可能比front多跑一圈，所以其元素個(gè)數(shù)=(rear-front+N)％N?！菊_答案】：為D。18.33.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹中度為0的結(jié)點(diǎn)個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1B、二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于0C、完全二叉樹中任何結(jié)點(diǎn)的度為0或2D、二叉樹的度為2【正確答案】：A19.5.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）。（1≤i≤n）的存儲(chǔ)地址為LOC(a0)+i×sizeof(ElemType)，也就是說，對(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ǔ)。20.個(gè)數(shù)據(jù)遞增排序，最好的時(shí)間復(fù)雜度為()。A、O(nloB、2n)C、O(nloD、2k)E、O(kloF、2n)G、O(kloH、2k)【正確答案】：B解析：

每個(gè)組內(nèi)k個(gè)元素采用基于比較的排序方法排序最好時(shí)間復(fù)雜度為O(klog2k)，整個(gè)元素序列排序的最好時(shí)間復(fù)雜度為O(klog2k)×n/k=O(nlog2k)?！菊_答案】：為B。21.53.就排序算法所用的輔助空間而言，堆排序、快速排序和歸并排序的關(guān)系是（）。A、堆排序<快速排序<歸并排序A、堆排序<歸并排序<快速排序B、堆排序>歸并排序>快速排序C、堆排序>快速排序>歸并排序【正確答案】：A解析：

歸并排序的空間復(fù)雜度為O(n)，快速排序的空間復(fù)雜度為O(log2n)，堆排序的空間復(fù)雜度為O(1)。22.{0，2，3，4}，下一步選取的目標(biāo)頂點(diǎn)可能是()。A、頂點(diǎn)2B、頂點(diǎn)3C、頂點(diǎn)4D、頂點(diǎn)7【正確答案】：D解析：

Dijkstra算法執(zhí)行中，一旦某個(gè)頂點(diǎn)v添加到S中，后面不再調(diào)整源點(diǎn)到v的最短路徑。【正確答案】：為D。23.31.二叉樹中所有結(jié)點(diǎn)的度之和等于結(jié)點(diǎn)數(shù)加（）。A、1B、-1C、2【正確答案】：B24.到一維數(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=37。25.4.采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()。A、遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)【正確答案】：D解析：

快速排序?qū)⒁粋€(gè)無序序列劃分為兩個(gè)無序子序列，這兩個(gè)無序子序列的排序是獨(dú)立的，先排序哪一個(gè)都可以。【正確答案】：為D。26.17.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是()。A、插入、刪除操作更簡單B、可以進(jìn)行隨機(jī)訪問C、可以省略表頭指針或表尾指針D、訪問前后相鄰結(jié)點(diǎn)更方便【正確答案】：D解析：

單鏈表只能通過指針向后遍歷，而雙鏈表可以通過前后指針雙向遍歷，所以訪問前后相鄰結(jié)點(diǎn)更方便。答案為D。27.17.設(shè)有100個(gè)元素的有序表，用折半查找時(shí)，不成功時(shí)最大的比較次數(shù)是（）。A、25B、50C、10D、7【正確答案】：D解析：

不成功時(shí)最大的比較次數(shù)=log2(n+1)=7。【正確答案】：為D。28.叉排序樹，若希望高度最小，則應(yīng)該選擇哪個(gè)序列插入（）。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個(gè)選項(xiàng)對(duì)應(yīng)的關(guān)鍵字序列構(gòu)造的4棵二叉排序樹如圖A.32所示，T2是一棵高度為3的滿二叉樹，高度最小?！菊_答案】：為B。29.的排序方法是（）。A、簡單選擇排序B、快速排序C、冒泡排序D、直接插入排序【正確答案】：A解析：

從數(shù)據(jù)排列次序的變化過程看到，每一趟都從無序區(qū)中選一個(gè)最小的元素歸位。30.14.設(shè)s表示串"abcd"，s1表示串"123"，則執(zhí)行語句s2=InsStr(s,2,s1)后，s2串為（）。A、"123abcd"B、"a123bcd"C、"ab123cd"D、"abc123d"【正確答案】：B31.17.在含有n（n>2）個(gè)數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，開始結(jié)點(diǎn)是指（）的結(jié)點(diǎn)。A、沒有前趨結(jié)點(diǎn)B、含有一個(gè)或多個(gè)前趨結(jié)點(diǎn)C、沒有后繼結(jié)點(diǎn)D、含有一個(gè)或多個(gè)后繼結(jié)點(diǎn)【正確答案】：A解析：

開始結(jié)點(diǎn)是沒有任何前趨結(jié)點(diǎn)的。32.35.二叉樹若用順序存儲(chǔ)結(jié)構(gòu)表示，則下列4種運(yùn)算中的（）最容易實(shí)現(xiàn)。A、先序遍歷二叉樹B、中序遍歷二叉樹C、層次遍歷二叉樹D、根據(jù)結(jié)點(diǎn)的值查找其存儲(chǔ)位置【正確答案】：C33.≤i≤m）。一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)為該結(jié)點(diǎn)的次數(shù)（或度）。A、有0個(gè)或1個(gè)B、有0個(gè)或多個(gè)C、有且只有1個(gè)D、有1個(gè)或1個(gè)以上【正確答案】：A34.種要求的排序方法是（）。A、先按k1值進(jìn)行直接插入排序，再按k2值進(jìn)行簡單選擇排序B、先按k2值進(jìn)行直接插入排序，再按k1值進(jìn)行簡單選擇排序C、先按k1值進(jìn)行簡單選擇排序，再按k2值進(jìn)行直接插入排序D、先按k2值進(jì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)定性，簡單選擇排序是不穩(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)定的排序方法。綜合起來應(yīng)該先按k2值進(jìn)行簡單選擇排序，再按k1值進(jìn)行插入排序。本題【正確答案】：為D。35.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)系。36.趟。38、38.在一般情況下，以下排序算法中元素移動(dòng)次數(shù)最少的（）。A、直接插入排序B、冒泡排序C、簡單選擇排序D、都一樣【正確答案】：C解析：

簡單選擇排序移動(dòng)元素的次數(shù)為0～3(n-1)，在一般情況下，比直接插入排序和冒泡排序移動(dòng)元素次數(shù)要少。37.32.將10個(gè)元素散列到大小為10000的哈希表中，（）產(chǎn)生沖突。A、一定會(huì)B、一定不會(huì)C、仍可能會(huì)D、以上都不對(duì)【正確答案】：C解析：

無論裝填因子大還是小，哈希表仍可能發(fā)生沖突。38.13.在長度為n（n≥1）的雙鏈表L中，在p結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)s的時(shí)間復(fù)雜度為（）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)【正確答案】：A解析：

雙鏈表中給定p結(jié)點(diǎn)后，可以直接找到其前驅(qū)結(jié)點(diǎn)pre，再在pre結(jié)點(diǎn)和p結(jié)點(diǎn)之間插入結(jié)點(diǎn)s。答案為A。39.8.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序段的時(shí)間復(fù)雜度為()。x=1whilex<=n:x=5*xA、O(loB、5n)C、O(n)D、O(nloE、5n)F、O(n5)【正確答案】：A解析：

設(shè)while循環(huán)的次數(shù)為m，x從1開始每次循環(huán)按5倍遞增，有x=5m≤n，即m≤log5n=O(log5n)。答案為A。40.操作是（）。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]一端生長。在第一個(gè)元素x進(jìn)棧時(shí)，先執(zhí)行top-=1，這樣top指向s的有效下標(biāo)，再執(zhí)行s[top]=x?！菊_答案】：為C。41.69，88）則所采用的排序方法是（）。A、快速排序B、簡單選擇排序C、直接插入排序D、二路歸并排序【正確答案】：A解析：

從元素序列的變化情況看，不可能是簡單選擇排序（因?yàn)榍昂鬀]有產(chǎn)生全局有序區(qū)），不可能是直接插入排序（因?yàn)榍昂鬀]有產(chǎn)生局部有序區(qū)），也不可能是二路歸并排序。【正確答案】：為A。42.6.在一棵非空二叉樹的先序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系()。A、不一定相同A、都相同B、都不相同C、互為逆序【正確答案】：B43.18.關(guān)于串的敘述，正確的是（）。A、串是含有一個(gè)或多個(gè)字符的有窮序列B、空串是只含有空格字符的串C、空串是含有零個(gè)字符或含有空格字符的串D、串是含有零個(gè)或多個(gè)字符的有窮序列【正確答案】：D44.4.關(guān)于線性表的正確說法是（）。A、每個(gè)元素都有一個(gè)前趨和一個(gè)后繼元素B、線性表中至少有一個(gè)元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素有且僅有一個(gè)前趨和一個(gè)后繼元素【正確答案】：D解析：

線性表屬典型的線性結(jié)構(gòu)。45.50.以下排序方法中，（）不需要進(jìn)行關(guān)鍵字的比較。A、快速排序B、歸并排序C、基數(shù)排序D、堆排序【正確答案】：C解析：

在本章介紹的各種排序方法中，基數(shù)排序是唯一不基于關(guān)鍵字比較的排序方法。46.57.初始數(shù)據(jù)序列中有兩個(gè)相同關(guān)鍵字的元素，通過不穩(wěn)定的排序方法排序后，（）。A、這兩個(gè)元素的前后位置不發(fā)生變化B、這兩個(gè)元素的前后位置一定發(fā)生變化C、這兩個(gè)元素的位置不發(fā)生變化D、這兩個(gè)元素的前后位置可能發(fā)生變化【正確答案】：D47.6.在KMP算法中，模式串"ababaabab"的next數(shù)組值為（）。A、-1,0,0,1,2,3,1,2,3B、-1,0,0,1,2,1,1,2,3C、-1,0,0,1,2,3,4,1,2D、-1,0,0,1,2,3,1,2,2【正確答案】：A解析：

求模式串"ababaabab"的next數(shù)組的過程如表A.1所示?！菊_答案】：為A。48.11.對(duì)于有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(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解析：

最小生成樹是圖中所有頂點(diǎn)構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小。【正確答案】：為D。題型：49.16.哈希表中出現(xiàn)的哈希沖突是指()。A、兩個(gè)元素具有相同的序號(hào)B、兩個(gè)元素的關(guān)鍵字不同，而其他屬性相同C、數(shù)據(jù)元素過多D、兩個(gè)元素的關(guān)鍵字不同，而對(duì)應(yīng)的哈希函數(shù)值相同【正確答案】：D解析：

哈希沖突也稱為同義詞沖突，是指兩個(gè)元素的關(guān)鍵字不同，而對(duì)應(yīng)的哈希函數(shù)值相同。【正確答案】：為D。50.24.一個(gè)棧的輸入序列為1、2、3、4、5，則下列序列中不可能是棧的輸出序列的是（）。A、2、3、4、1、5B、5、4、1、3、2C、2、3、1、4、5D、1、5、4、3、2【正確答案】：B解析：

當(dāng)出棧序列的第一個(gè)元素為5時(shí)，只有唯一的出棧序列5、4、3、2、1，不可能有5、4、1、3、2的出棧序列。本題【正確答案】：為B。51.22.對(duì)于AOE網(wǎng)的關(guān)鍵路徑，以下敘述（）是正確的。A、任何一個(gè)關(guān)鍵活動(dòng)提前完成，則整個(gè)工程一定會(huì)提前完成B、完成整個(gè)工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最短路徑長度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)的最長路徑，其長度為完成整個(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。52.29.在一個(gè)無向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（）倍。A、1/2B、1C、2D、4【正確答案】：C解析：

在無向圖中，一條邊計(jì)入兩個(gè)頂點(diǎn)的度數(shù)。53.排序確定A、外排序所花時(shí)間=內(nèi)排序時(shí)間+外存信息讀寫時(shí)間+內(nèi)部歸并所花時(shí)間B、外排序并不涉及文件的讀寫操作C、外排序完全可以由內(nèi)排序來替代【正確答案】：B解析：

外排序過程主要分為兩個(gè)階段：生成初始?xì)w并段和對(duì)初始?xì)w并段進(jìn)行歸并，這兩個(gè)步驟中都涉及文件的讀寫操作。54.56.下列排序方法中，（）在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A、簡單選擇排序B、冒泡排序C、歸并排序D、堆排序【正確答案】：C解析：

因?yàn)闅w并排序每趟并不一定產(chǎn)生全局有序區(qū)。55.42.冒泡排序最少元素移動(dòng)的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A56.31.給定一個(gè)空棧，若元素10、20、23、13依次進(jìn)棧，然后有兩個(gè)數(shù)出棧，又有3個(gè)數(shù)進(jìn)棧，第一次進(jìn)棧的元素23現(xiàn)在（）。A、已出棧B、從棧底算起第3個(gè)C、處于棧頂D、從棧底算起第4個(gè)【正確答案】：A解析：

本題的操作是：元素10、20、23、13依次進(jìn)棧，然后出棧13和23，再進(jìn)棧3個(gè)元素，第一次進(jìn)棧的元素23已出棧了。57.15.適合于折半查找的數(shù)據(jù)組織方式是()。A、以鏈表存儲(chǔ)的線性表B、以順序表存儲(chǔ)的任意線性表C、以鏈表存儲(chǔ)的有序線性表D、以順序表存儲(chǔ)的有序線性表【正確答案】：D解析：

折半查找的元素序列一定是有序的，并且采用具有隨機(jī)存取特性的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。【正確答案】：為D。58.32.以下（）方法可用于求無向圖的連通分量。A、遍歷B、拓?fù)渑判駽、Dijkstra算法D、Prim算法【正確答案】：A解析：

從圖中某個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，可將與該頂點(diǎn)相連通的所有頂點(diǎn)全部訪問，也就找到了該頂點(diǎn)所在的連通分量。59.14.一棵高度為h（h≥1）的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)。A、2h-1B、2hC、2h+1D、2h-1+1【正確答案】：A60.16.以下排序方法中，()在初始序列已基本有序的情況下，排序效率最高。A、二路歸并排序B、快速排序C、直接插入排序D、堆排序【正確答案】：C解析：

二路歸并排序和堆排序的效率用初始序列分布無關(guān)，而在初始序列已基本有序的情況下快速排序的效率最差?！菊_答案】：為C。61.10.將10階對(duì)稱矩陣A壓縮存儲(chǔ)到一維數(shù)組B中，則數(shù)組B的長度最少為_()。A、100B、40C、80D、55【正確答案】：D解析：

n階對(duì)稱矩陣壓縮存儲(chǔ)時(shí)需要存儲(chǔ)的元素個(gè)數(shù)=n(n+1)/2，n=10時(shí)結(jié)果為55。62.次探測。A、k-1B、kC、k+1D、k(k+1)/2【正確答案】：D解析：

最少探測的情況是，第一個(gè)同義詞放在哈希表ha[d]位置，探測1次，第2個(gè)同義詞放在哈希表ha[d+1]位置，探測2次，以此類推，第k個(gè)同義詞放在哈希表ha[d+k-1]位置，探測k次，總的探測次數(shù)=1+2+…+k=k(k+1)/2?！菊_答案】：為D。63.26.k階最佳歸并樹是一棵（）。A、k階平衡樹B、平衡二叉樹C、k階哈夫曼樹D、以上都不對(duì)【正確答案】：C解析：

k階最佳歸并樹是一棵k階哈夫曼樹，不一定是k階平衡樹。64.28.設(shè)有一棵哈夫曼樹的結(jié)點(diǎn)總數(shù)為35，則該哈夫曼樹共有（）個(gè)葉子結(jié)點(diǎn)。A、18B、20C、35D、30【正確答案】：A65.21.設(shè)連通圖有n個(gè)頂點(diǎn)e條邊（e，n>0），若滿足（），則圖中一定有回路。A、e≥nB、e<nC、e=n-1D、2e≥n【正確答案】：A解析：

一個(gè)有n個(gè)頂點(diǎn)e條邊的無向圖，若e=n-1時(shí)構(gòu)成一個(gè)樹圖，若en-1則一定存在回路。【正確答案】：為A。66.18.快速排序在()情況下最不利于發(fā)揮其長處。A、排序的數(shù)據(jù)量太大B、排序的數(shù)據(jù)中含有多個(gè)相同值C、排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D、排序的數(shù)據(jù)已基本有序【正確答案】：D解析：

當(dāng)排序的數(shù)據(jù)已基本有序，快速排序的時(shí)間復(fù)雜度會(huì)變?yōu)镺(n2)?！菊_答案】：為D。67.8.一棵高度為h、結(jié)點(diǎn)個(gè)數(shù)為n的m（m≥3）次樹中，其分支數(shù)是（）。A、nhB、n+hC、n-1D、h-1【正確答案】：C68.3.以下不屬于存儲(chǔ)結(jié)構(gòu)是()。A、棧B、二叉鏈C、哈希表D、雙鏈表【正確答案】：A解析：

二叉鏈?zhǔn)嵌鏄涞囊环N存儲(chǔ)結(jié)構(gòu)，哈希表是一種適合特定數(shù)據(jù)（關(guān)鍵字與地址之間存在某種關(guān)系）快速查找的存儲(chǔ)結(jié)構(gòu)，雙鏈表是線性表的一種存儲(chǔ)結(jié)構(gòu)，而棧是一種邏輯結(jié)構(gòu)，可以采用順序?；蛘哝湕４鎯?chǔ)。答案為A。69.8.一個(gè)稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲(chǔ)相比會(huì)失去（）特性。A、順序存儲(chǔ)B、隨機(jī)存取C、輸入輸出D、以上都不對(duì)【正確答案】：B解析：

稀疏矩陣采用三元組或者十字鏈表壓縮后均不再具有隨機(jī)存取特性。70.5.以下數(shù)據(jù)結(jié)構(gòu)中()屬非線性結(jié)構(gòu)。A、棧B、串C、隊(duì)列D、平衡二叉樹【正確答案】：D解析：

棧、隊(duì)列和串中元素的邏輯關(guān)系都是線性關(guān)系，平衡二叉樹是一種二叉樹，而二叉樹屬于非線性結(jié)構(gòu)。答案為D。71.10.設(shè)有100個(gè)元素的有序順序表，采用折半查找方法，不成功時(shí)最大的比較次數(shù)是（）。A、25B、50C、10D、7【正確答案】：D解析：

不成功時(shí)最大比較次數(shù)為log2(n+1)=log2101=7?！菊_答案】：為D。72.25.n個(gè)頂點(diǎn)的連通圖的生成樹有（）條邊。A、nB、n-1C、n+1D、不確定【正確答案】：B73.25.二叉排序中，最大關(guān)鍵字結(jié)點(diǎn)的（）。A、沒有左孩子結(jié)點(diǎn)B、沒有右孩子結(jié)點(diǎn)C、一定沒有左右孩子結(jié)點(diǎn)D、一定存在左右孩子結(jié)點(diǎn)【正確答案】：B解析：

在二叉排序中，最大關(guān)鍵字結(jié)點(diǎn)是中序序列的最后結(jié)點(diǎn)，即根結(jié)點(diǎn)的最右下結(jié)點(diǎn)。74.速排序Ⅳ.二路歸并排序A、僅ⅠB、僅Ⅰ、ⅡC、僅Ⅰ、ⅢD、僅Ⅱ、Ⅳ【正確答案】：B解析：

當(dāng)初始數(shù)據(jù)基本正序時(shí)，直接插入排序和起泡排序的時(shí)間復(fù)雜度為O(n)?！菊_答案】：為B。75.12.數(shù)據(jù)結(jié)構(gòu)是指（）。A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、一組性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合【正確答案】：D解析：

數(shù)據(jù)結(jié)構(gòu)通常指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。答案為D。76.（）。A、冒泡排序B、希爾排序C、歸并排序D、基數(shù)排序【正確答案】：A77.46.冒泡排序最少關(guān)鍵字比較的次數(shù)是（）。A、nB、n-1C、3n(n-1)/2【正確答案】：C78.同IV.若v不是T1的葉子結(jié)點(diǎn)，則T1與T3相同A、僅I、IIIB、僅I、IVC、僅II、IIID、僅II、IV【正確答案】：C解析：

在一棵二叉排序樹中刪除一個(gè)結(jié)點(diǎn)后再將此結(jié)點(diǎn)插入到二叉排序樹中，如果刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么在插入結(jié)點(diǎn)后，后來的二叉排序樹與刪除結(jié)點(diǎn)之前相同。如果刪除的結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，那么再插入這個(gè)結(jié)點(diǎn)后，后來的二叉樹可能發(fā)生變化，不再相同?！菊_答案】：為C。79.32.采用敗者樹進(jìn)行k路平衡歸并的外排序算法中，總的關(guān)鍵字比較次數(shù)與k（）。A、成正比B、成反比C、無關(guān)D、以上都不對(duì)【正確答案】：C解析：

采用敗者樹進(jìn)行k路平衡歸并的外排序算法中，總的關(guān)鍵字比較次數(shù)=(u-1)log2m，其中u為歸并的記錄個(gè)數(shù)，m是初始?xì)w并段的個(gè)數(shù)，從而看出與k無關(guān)。80.為節(jié)儉排序算法，以下算法中是節(jié)儉排序算法的有_（）。A、直接插入排序B、簡單選擇排序C、堆排序D、所有選項(xiàng)都不對(duì)【正確答案】：A解析：

直接插入排序中沒有同一對(duì)元素被比較過兩次或以上。【正確答案】：為A。81.31.哈希查找的基本思想是根據(jù)（）來決定元素的存儲(chǔ)地址。A、元素的序號(hào)B、元素個(gè)數(shù)C、關(guān)鍵字值D、非關(guān)鍵字屬性值【正確答案】：C82.37.采用排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（）。A、直接插入和快速B、冒泡和快速C、簡單選擇和直接插入D、簡單選擇和冒泡【正確答案】：C解析：

簡單選擇和直接插入肯定要進(jìn)行n-1趟排序，冒泡排序?yàn)?～n-1趟，快速排序?yàn)閘og2n～n-183.35.m個(gè)初始?xì)w并進(jìn)行k路平衡歸并時(shí)，所需趟數(shù)（）。A、logkmB、logkm+1C、logk(m+1)D、logmk【正確答案】：A84.4.數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是()算法的兩趟排序后的結(jié)果。A、簡單選擇排序B、冒泡排序C、直接插入排序D、堆排序【正確答案】：C解析：

簡單選擇排序、冒泡排序和堆排序每一趟產(chǎn)生的有序區(qū)都是全局有序區(qū)，而（8，9，10，4，85.4.下面關(guān)于哈夫曼樹的說法，不正確的是()。A、對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹可能不唯一B、哈夫曼樹具有最小帶權(quán)路徑長度C、哈夫曼樹中沒有度為1的結(jié)點(diǎn)D、哈夫曼樹中除了度為2的結(jié)點(diǎn)外，還有度為1的結(jié)點(diǎn)和葉結(jié)點(diǎn)【正確答案】：D86.2.以下序列不是堆的是（）。A、（100，85，98，77，80，60，82，40，20，10，66）B、（100，98，85，82，80，77，66，60，40，20，10）C、（10，20，40，60，66，77，80，82，85，98，100）D、（100，85，40，77，80，60，66，98，82，10，20）【正確答案】：D解析：

畫出各個(gè)序列對(duì)應(yīng)的完全二叉樹，再對(duì)每個(gè)分支結(jié)點(diǎn)逐個(gè)判斷。本題【正確答案】：為D。87.36.外排序和內(nèi)排序的主要區(qū)別是（）。A、內(nèi)排序速度快，而外排序速度慢B、內(nèi)排序不涉及內(nèi)、外存數(shù)據(jù)交換，而外排序涉及內(nèi)、外存數(shù)據(jù)交換C、內(nèi)排序所需內(nèi)存小，而外排序所需內(nèi)存大D、內(nèi)排序的數(shù)據(jù)量小，而外排序的數(shù)據(jù)量大【正確答案】：B88.前一位置，r指向隊(duì)尾元素），元素x出隊(duì)的操作是（）;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指向隊(duì)首元素的前一位置，r指向隊(duì)尾元素，所以出隊(duì)操作先循環(huán)移動(dòng)f?！菊_答案】：為D。89.排序后的結(jié)果，則該排序算法只能是()。A、冒泡排序B、直接插入排序C、簡單選擇排序D、二路歸并排序【正確答案】：B解析：

從第二趟排序后結(jié)果看出，先后沒有全局有序區(qū)，不可能是冒泡排序和簡單選擇排序，又發(fā)現(xiàn)了并非兩兩有序，所以不是二路歸并排序?！菊_答案】：為B。90.27.若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧的操作交替進(jìn)行，但不允許連續(xù)3次退棧工作，則不可能得到的出棧序列是（）。A、dcebfaB、cbdaefC、bcaefdD、afedcb【正確答案】：D解析：

選項(xiàng)A操作：a進(jìn)，b進(jìn)，c進(jìn)，d進(jìn)，d出，c出，e進(jìn)，e出，b出，f進(jìn)，f出，a出。選項(xiàng)B操作：a進(jìn)，b進(jìn)，c進(jìn)，c出，b出，d進(jìn)，d出，a出，e進(jìn)，e出，f進(jìn)，f出。選項(xiàng)C操作：a進(jìn)，b進(jìn)，b出，c進(jìn)，c出，a出，d進(jìn)，e進(jìn)，e出，f進(jìn)，f出，d出。選項(xiàng)D操作：a進(jìn)，a出，b進(jìn)，c進(jìn)，d進(jìn)，e進(jìn)，f進(jìn)，f出，e出，d出，c出，b出。從中看到，選項(xiàng)D中最后連續(xù)出棧5次，不符合要求。本題答案：為D。91.18.在含有n（n>2）個(gè)數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，終端結(jié)點(diǎn)是指（）的結(jié)點(diǎn)。A、沒有前趨結(jié)點(diǎn)B、含有一個(gè)或多個(gè)前趨結(jié)點(diǎn)C、沒有后繼結(jié)點(diǎn)D、含有一個(gè)或多個(gè)后繼結(jié)點(diǎn)【正確答案】：C解析：

終端結(jié)點(diǎn)是沒有任何后繼結(jié)點(diǎn)的。92.60.內(nèi)排序方法的穩(wěn)定性是指（）。A、該排序算法不允許有相同關(guān)鍵字的元素B、該排序算法允許有相同關(guān)鍵字的元素C、平均時(shí)間為O(nlog2n)的排序方法D、以上都不對(duì)【正確答案】：D93.23.如果一個(gè)表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，則可采用（）。A、有序表B、線性表C、哈希表D、二叉平衡樹【正確答案】：D解析：

滿足這種條件的表為樹表，各選項(xiàng)中只有二叉平衡樹是一種樹表。94.31.在一個(gè)圖中，每個(gè)頂點(diǎn)的前趨頂點(diǎn)和后繼頂點(diǎn)數(shù)可以有（）。A、1個(gè)B、2個(gè)C、任意多個(gè)D、0個(gè)【正確答案】：C解析：

圖中頂點(diǎn)之間是多對(duì)多的相鄰關(guān)系。95.20.引入線索二叉樹的目的是（）。A、加快查找結(jié)點(diǎn)的前趨或后繼結(jié)點(diǎn)的速度B、為了能在二叉樹中方便插入和刪除C、為了能方便找到雙親D、使二叉樹的遍歷結(jié)果唯一【正確答案】：A96.29.對(duì)于棧操作數(shù)據(jù)的原則是（）。A、先進(jìn)先出B、后進(jìn)先出C、后進(jìn)后出D、不分順序【正確答案】：B解析：

棧操作數(shù)據(jù)的原則是先進(jìn)后出或后進(jìn)先出。97.28.在含有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找某關(guān)鍵字的結(jié)點(diǎn)時(shí)，最多進(jìn)行（）次比較。A、n/2B、log2nC、log2n+1D、n【正確答案】：D解析：

n個(gè)結(jié)點(diǎn)的二叉排序樹的高度可能為n。98.22.查找效率低的數(shù)據(jù)結(jié)構(gòu)是（）。A、有序順序表B、二叉排序樹C、堆D、二叉平衡樹【正確答案】：C解析：

堆查找的時(shí)間復(fù)雜度為O(n)，所以效率最低。99.3.以下4個(gè)線性表中，最適合采用基數(shù)排序的是()。A、10000個(gè)實(shí)數(shù)B、1000個(gè)由字母、數(shù)字和其他字符組成的字符串C、1000個(gè)int類型的整數(shù)D、10000個(gè)100以內(nèi)的正整數(shù)【正確答案】：D解析：

這里是要求選擇最適合基數(shù)排序的數(shù)據(jù)，顯然實(shí)數(shù)序列不如整數(shù)序列，含負(fù)整數(shù)的序列不如僅100.13.設(shè)森林F中有4棵樹，第1、2、3、4棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為a、b、c、d，將森林F轉(zhuǎn)換為一顆二叉樹B，則二叉樹B中根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)個(gè)數(shù)是()。A、a-1B、aC、a+b+cD、b+c+d【正確答案】：A1.9.二叉樹中每個(gè)度為2的結(jié)點(diǎn)的兩棵子樹都是有序的。A、正確B、錯(cuò)誤【正確答案】：A2.6.線性表的長度是線性表占用的存儲(chǔ)空間的大小。A、正確B、錯(cuò)誤【正確答案】：B解析：

線性表的長度是指表中元素個(gè)數(shù)，屬邏輯結(jié)構(gòu)的概念，與線性表占用的存儲(chǔ)空間大小無關(guān)。3.14.在外排序過程中，一個(gè)記錄的讀入內(nèi)存的次數(shù)和寫到外存的次數(shù)必定相等。A、正確B、錯(cuò)誤【正確答案】：A4.45.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。A、正確B、錯(cuò)誤【正確答案】：B5.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ù)序列無6.后移動(dòng)。A、正確B、錯(cuò)誤【正確答案】：B7.15.棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們的數(shù)據(jù)元素的邏輯關(guān)系也不同。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們的數(shù)據(jù)元素的邏輯關(guān)系都是線性關(guān)系。8.9.數(shù)據(jù)對(duì)象就是一組任意數(shù)據(jù)元素的集合。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)對(duì)象是指具有相同性質(zhì)的有限個(gè)數(shù)據(jù)元素的集合。9.20.k路最佳歸并樹一定是一棵k路平衡樹。A、正確B、錯(cuò)誤【正確答案】：B解析：

k路最佳歸并樹不一定是一棵k路平衡樹。10.2.線性表中的結(jié)點(diǎn)按前趨、后繼關(guān)系可以排成一個(gè)線性序列。A、正確B、錯(cuò)誤【正確答案】：A解析：

線性表是有限個(gè)相同性質(zhì)的元素的序列。11.4.在隊(duì)空間大小為n的循環(huán)隊(duì)列中，最多只能進(jìn)行n次進(jìn)隊(duì)操作。A、正確B、錯(cuò)誤【正確答案】：B解析：

在循環(huán)隊(duì)列中，元素出隊(duì)后，其位置空了出來，可以讓其他元素進(jìn)隊(duì)，所以理論上講可以進(jìn)隊(duì)任意次。12.15.任何一個(gè)圖，一旦指定源點(diǎn)，其深度優(yōu)先遍歷序列是唯一的。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷序列不一定是唯一的。13.1.線性表中所有元素的數(shù)據(jù)類型必須相同。A、正確B、錯(cuò)誤【正確答案】：A解析：

線性表中所有元素具有相同性質(zhì)，在設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)時(shí)，它們對(duì)應(yīng)的數(shù)據(jù)類型也必然相同。14.1.一種邏輯結(jié)構(gòu)的數(shù)據(jù)只有一種對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：B15.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)，不能是樹形結(jié)構(gòu)或圖形結(jié)構(gòu)。16.16.非空二叉樹的中序序列的第一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B17.5.樹中元素之間是多對(duì)多的關(guān)系。A、正確B、錯(cuò)誤【正確答案】：B18.7.n個(gè)元素進(jìn)隊(duì)的順序和出隊(duì)的順序總是一致的。A、正確B、錯(cuò)誤【正確答案】：A解析：

后進(jìn)隊(duì)的元素后出隊(duì)，先進(jìn)隊(duì)的元素先出隊(duì)。19.6.哈夫曼樹中沒有度為1的結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：A20.1.給定一棵樹T，將其轉(zhuǎn)換成二叉樹B后，它們的結(jié)點(diǎn)個(gè)數(shù)相同。A、正確B、錯(cuò)誤【正確答案】：A21.5.線性表中每個(gè)元素都有一個(gè)前趨元素和一個(gè)后繼元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

開始元素沒有前趨元素，終端元素沒有后繼元素。22.數(shù)據(jù)的邏輯結(jié)構(gòu)。50、19.棧是一種特殊的線性表，其特殊之處在于棧的存儲(chǔ)結(jié)構(gòu)比較特殊。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對(duì)線性表的操作做了限制。23.35.基數(shù)排序與初始數(shù)據(jù)的次序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：A24.子。A、正確B、錯(cuò)誤【正確答案】：A解析：

二叉排序樹的任意一棵子樹也是二叉排序樹。25.18.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧的定義不涉及數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，棧中數(shù)據(jù)元素的邏輯關(guān)系屬于線性關(guān)系，所以棧的定義涉及26.4.在一個(gè)含有n（n≥1）個(gè)元素的線性表中，所有元素值不能相同。A、正確B、錯(cuò)誤【正確答案】：B解析：

在線性表中允許存在元素值相同的元素，但它們的位置是不同。27.個(gè)比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯(cuò)誤【正確答案】：A解析：

歸并趟數(shù)s=log55=1，5個(gè)記錄選取最小記錄需比較4次，所以總共需要(100-1)×4×1=396次關(guān)鍵字比較。28.25.簡單選擇排序是一種不穩(wěn)定的排序方法。A、正確B、錯(cuò)誤【正確答案】：A29.2.對(duì)于無向圖生成樹，從同一頂點(diǎn)出發(fā)所得到的生成樹一定是相同的。A、正確B、錯(cuò)誤【正確答案】：B解析：

無向圖的生成樹可能有多棵，從同一頂點(diǎn)出發(fā)所得到的生成樹也不一定相同。30.接插入排序。為把所有記錄排好序，需做6趟歸并排序。A、正確B、錯(cuò)誤【正確答案】：B解析：

內(nèi)排序采用直接插入排序時(shí)，可以產(chǎn)生375000/600=625個(gè)初始?xì)w并段，5路平衡歸并排序的趟數(shù)=log5625=4。所以需做4趟歸并排序。31.樹。A、正確B、錯(cuò)誤【正確答案】：B解析：

對(duì)于二叉排序樹，左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根記錄的關(guān)鍵字；右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根記錄的關(guān)鍵字。而不是僅僅與左、右孩子的關(guān)鍵字進(jìn)行比較。32.14.圖的遍歷就是訪問圖中所有頂點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的遍歷是指以某種順序訪問圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問一次。33.列是不可能相同的。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的兩種遍歷序列可能相同。34.42.二路歸并排序算法的時(shí)間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：A35.17.由二叉樹某種遍歷方式產(chǎn)生的結(jié)果是一個(gè)線性序列。A、正確B、錯(cuò)誤【正確答案】：A36.1.k路最佳歸并樹在外排序中的作用是產(chǎn)生初始?xì)w并段。A、正確B、錯(cuò)誤【正確答案】：B37.14.棧是一種特殊的線性表，線性表的所有運(yùn)算都可以施加在棧上。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對(duì)線性表的插入和刪除操作做了限制，所以不能將線性表的所有運(yùn)算都施加在棧上。38.2.數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計(jì)算機(jī)中如何存儲(chǔ)有關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)無關(guān)。39.39.n個(gè)元素采用二路歸并排序算法，總的趟數(shù)為n。A、正確B、錯(cuò)誤【正確答案】：B解析：

n個(gè)元素采用二路歸并排序算法，總的趟數(shù)為log2n。40.2.給定一棵樹T，可以找到唯一的一棵二叉樹B與之對(duì)應(yīng)。A、正確B、錯(cuò)誤【正確答案】：A41.31.冒泡排序在最好情況下的時(shí)間復(fù)雜度也是O(n2)。A、正確B、錯(cuò)誤【正確答案】：B解析：

冒泡排序在最好情況下的時(shí)間復(fù)雜度為O(n)。42.最后一個(gè)結(jié)點(diǎn)A、正確B、錯(cuò)誤【正確答案】：A43.26.n個(gè)元素采用簡單選擇排序進(jìn)行排序，關(guān)鍵字比較的次數(shù)總是n(n-1)/2。A、正確B、錯(cuò)誤【正確答案】：A44.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ì)列操作的次序。45.12.哈希表中所有的哈希地址是連續(xù)的。A、正確B、錯(cuò)誤【正確答案】：A46.22.內(nèi)排序過程在數(shù)據(jù)量很大時(shí)就變成了外排序過程。A、正確B、錯(cuò)誤【正確答案】：B47.15.為了提高外排序的速度，在外排序中必須選用最快的內(nèi)排序算法。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序的第二階段只能采用歸并排序算法。48.1.順序隊(duì)采用數(shù)組存放隊(duì)中元素，數(shù)組具有隨機(jī)存取特性，所以順序隊(duì)中可以隨機(jī)存取元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

順序隊(duì)采用數(shù)組存放隊(duì)中元素，盡管數(shù)組具有隨機(jī)存取特性，但隊(duì)列的操作特性是順序存取，只能存取兩端的元素。49.7.采用多路平衡歸并方法可以減少初始?xì)w并段的個(gè)數(shù)。A、正確B、錯(cuò)誤【正確答案】：B解析：

采用多路平衡歸并方法可以減少歸并的趟數(shù)。50.3.對(duì)于無向圖生成樹，其深度優(yōu)先生成樹和廣度優(yōu)先生成樹一定不相同。A、正確B、錯(cuò)誤【正確答案】：B解析：

不一定，如果一個(gè)無向圖的生成樹唯一，從同一頂點(diǎn)出發(fā)構(gòu)造的深度優(yōu)先生成樹和廣度優(yōu)先生成樹也是相同的。51.13.二叉樹就是度為2的有序樹。A、正確B、錯(cuò)誤【正確答案】：B52.16.通常外排序采用多路歸并排序方法，實(shí)際上也可以用其他內(nèi)排序方法代替歸并排序方法。A、正確B、錯(cuò)誤【正確答案】：B53.16.棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。A、正確B、錯(cuò)誤【正確答案】：A解析：

棧和隊(duì)列中元素都呈現(xiàn)線性關(guān)系，但它們插入和刪除操作有別于線性表。54.9.k路平衡歸并中，敗者樹的主要作用是減少歸并的趟數(shù)。A、正確B、錯(cuò)誤【正確答案】：B解析：

敗者樹的主要作用是加速從k個(gè)記錄中選取最小記錄，并不能減少歸并的趟數(shù)。55.13.空棧是指棧中元素沒有賦值。A、正確B、錯(cuò)誤【正確答案】：B解析：

空棧是指棧中沒有元素。56.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)。57.間復(fù)雜度的主要因素。正確錯(cuò)誤A、正確B、錯(cuò)誤【正確答案】：B解析：

影響算法時(shí)間復(fù)雜度的主要因素是移動(dòng)元素的次數(shù)和關(guān)鍵字比較的次數(shù)。58.19.外排序中沒有關(guān)鍵字比較。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序中需要關(guān)鍵字比較。59.10.二叉樹是一種特殊的樹。A、正確B、錯(cuò)誤【正確答案】：B60.37.基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。A、正確B、錯(cuò)誤【正確答案】：B61.成樹。A、正確B、錯(cuò)誤【正確答案】：B解析：

這樣的子圖不一定是連通的。62.5.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯?chǔ)的線性表。A、正確B、錯(cuò)誤【正確答案】：A63.徑。A、正確B、錯(cuò)誤【正確答案】：A解析：

頂點(diǎn)i和頂點(diǎn)j屬一個(gè)連通分量，而頂點(diǎn)k屬另一個(gè)連通分量，所以頂點(diǎn)i到頂點(diǎn)k沒有路徑。64.11.有n個(gè)不同的元素通過一個(gè)棧，產(chǎn)生的所有出棧序列恰好構(gòu)成這n個(gè)元素的全排列。A、正確B、錯(cuò)誤【正確答案】：B65.8.n個(gè)元素通過一個(gè)隊(duì)列，其出隊(duì)序列是唯一的。A、正確B、錯(cuò)誤【正確答案】：A解析：

后進(jìn)隊(duì)的元素后出隊(duì)，先進(jìn)隊(duì)的元素先出隊(duì)，所以出隊(duì)序列與進(jìn)隊(duì)序列相同。66.36.基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的大小無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

基數(shù)排序與初始數(shù)據(jù)中關(guān)鍵字的位數(shù)有關(guān)，也就與關(guān)鍵字的大小有關(guān)。67.12.相同的n個(gè)元素的不同序列通過一個(gè)棧一定不會(huì)得到相同的出棧序列。A、正確B、錯(cuò)誤【正確答案】：B解析：

相同的n個(gè)元素的不同序列通過一個(gè)?？赡軙?huì)得到相同的出棧序列。例如，進(jìn)棧序列1、2、3和68.41.對(duì)于不同的初始數(shù)據(jù)序列，二路歸并排序算法中關(guān)鍵字比較次數(shù)有所不同。A、正確B、錯(cuò)誤【正確答案】：A解析：

二路歸并排序算法的時(shí)間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)，但關(guān)鍵字比較次數(shù)是相關(guān)的。69.23.從時(shí)間性能看，堆排序總是優(yōu)于簡單選擇排序。A、正確B、錯(cuò)誤【正確答案】：A解析：

堆排序的最好、最壞和平均時(shí)間復(fù)雜度均為O(nlog2n)，而簡單選擇排序的最好、最壞和平均時(shí)間復(fù)雜度均為O(n2)。70.3.非線性結(jié)構(gòu)中，每個(gè)元素最多只有一個(gè)前趨元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

非線性結(jié)構(gòu)中，每個(gè)元素可能有多個(gè)前趨元素。71.9.二叉排序樹可以是一棵空樹。A、正確B、錯(cuò)誤【正確答案】：A72.17.影響外排序的時(shí)間因素主要是內(nèi)存與外存交換信息的次數(shù)。A、正確B、錯(cuò)誤【正確答案】：A73.查找、折半查找和分塊查找。A、正確B、錯(cuò)誤【正確答案】：B解析：

在順序存儲(chǔ)的物理介質(zhì)如磁帶上，只能進(jìn)行順序查找，即便文件有序，也不能進(jìn)行折半查找。74.3.將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化。A、正確B、錯(cuò)誤【正確答案】：A75.關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

關(guān)鍵字比較的次數(shù)與元素移動(dòng)的次數(shù)都與初始數(shù)據(jù)序列有關(guān)。76.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ù)。77.值。A、正確B、錯(cuò)誤【正確答案】：A78.3.對(duì)于不同的存儲(chǔ)結(jié)構(gòu)，應(yīng)采用不同的查找方法。A、正確B、錯(cuò)誤【正確答案】：A79.徑。A、正確B、錯(cuò)誤【正確答案】：A解析：

如果頂點(diǎn)j到頂點(diǎn)k有路徑，則頂點(diǎn)i有一條通過頂點(diǎn)j到達(dá)頂點(diǎn)k的路徑，與題中條件矛盾。80.8.一個(gè)圖中的簡單路徑是指該路徑上的邊不重復(fù)出現(xiàn)。A、正確B、錯(cuò)誤【正確答案】：B解析：

一個(gè)圖中的簡單路徑是指該路徑上的頂點(diǎn)不重復(fù)出現(xiàn)。81.15.非空二叉樹的中序序列的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B82.13.外排序的k路平衡歸并中，采用敗者樹時(shí)，歸并效率與k無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序的k路平衡歸并中，采用敗者樹時(shí)，總的關(guān)鍵字比較次數(shù)與k無關(guān)。83.33.快速排序、簡單選擇排序和堆排序都與初始序列次序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

快速排序與初始序列次序無關(guān)。84.5.一個(gè)連通圖的生成樹是唯一的。A、正確B、錯(cuò)誤【正確答案】：B解析：

一個(gè)連通圖的生成樹可能有多棵。85.24.簡單選擇排序中，每趟產(chǎn)生的有序區(qū)中所有元素在以后的排序中不再改變位置。A、正確B、錯(cuò)誤【正確答案】：A86.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次。87.40.二路歸并排序算法是穩(wěn)定的。A、正確B、錯(cuò)誤【正確答案】：A88.14.非空二叉樹的后序序列的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：A89.7