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

第頁數(shù)據(jù)結(jié)構(gòu)必過復(fù)習(xí)試題附答案1.49.以下四個(gè)線性表中，最適合采用基數(shù)排序的是（）。A、10000個(gè)實(shí)數(shù)B、1000個(gè)由字母、數(shù)字和其他字符組成的字符串C、1000個(gè)int類型的整數(shù)D、10000個(gè)100以內(nèi)的正整數(shù)【正確答案】：D解析：

選項(xiàng)C中有可能出現(xiàn)負(fù)整數(shù)，這樣不適合基數(shù)排序。2.11.在一棵m階B樹中插入一個(gè)關(guān)鍵字會(huì)引起分裂，則該結(jié)點(diǎn)原有()個(gè)關(guān)鍵字。A、1B、mC、m-1D、m/2【正確答案】：C解析：

在一棵m階B樹中每個(gè)內(nèi)部結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)為m/2-1～m-1，插入一個(gè)關(guān)鍵字會(huì)引起分裂，則該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)一定是最多的情況?！菊_答案】：為C。3.9.根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（）。A、000，001，010，011，1B、0000，0001，001，01，1C、000，001，01，10，11D、00，100，101，110，111【正確答案】：D4.17.設(shè)有100個(gè)元素的有序表，用折半查找時(shí)，不成功時(shí)最大的比較次數(shù)是（）。A、25B、50C、10D、7【正確答案】：D解析：

不成功時(shí)最大的比較次數(shù)=log2(n+1)=7?！菊_答案】：為D。5.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。6.同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。7.19.對(duì)有n個(gè)元素的排序表進(jìn)行直接插入排序，在最好情況下需比較()次關(guān)鍵字。A、n-1B、n+1C、n/2D、n(n-1)/2【正確答案】：A解析：

直接插入排序中，若初始排序表正序時(shí)性能最好，僅需要n-1次關(guān)鍵字比較，沒有元素移動(dòng)。【正確答案】：為A。8.7.二分查找和二叉排序樹查找的時(shí)間性能（）。A、完全相同B、有時(shí)不同C、完全不同D、數(shù)量級(jí)都是O(loE、2n)【正確答案】：B解析：

問題規(guī)模為n時(shí)，二分查找的時(shí)間復(fù)雜度為O(log2n)，而二叉排序樹查找與樹高相關(guān)，介于O(log2n)～O(n)，所以二分查找和二叉排序樹查找的時(shí)間性能不是完全相同，也不是完全不同，只能說有時(shí)不同?！菊_答案】：為B。9.26.樹最適合用來表示（）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)【正確答案】：C10.38.以下關(guān)于二叉樹遍歷的說法中，錯(cuò)誤的是（）。A、一棵二叉樹中，若每個(gè)結(jié)點(diǎn)最多只有左孩子，沒有右孩子，則先序和后序序列相同B、一棵二叉樹中，若每個(gè)結(jié)點(diǎn)最多只有左孩子，沒有右孩子，則中序和后序序列相同C、一棵二叉樹中，若每個(gè)結(jié)點(diǎn)最多只有左孩子，沒有右孩子，則先序和層次序列相同D、一棵二叉樹中，若每個(gè)結(jié)點(diǎn)最多只有右孩子，沒有左孩子，則先序和中序序列相同【正確答案】：A11.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。12.為節(jié)儉排序算法，以下算法中是節(jié)儉排序算法的有_（）。A、直接插入排序B、簡(jiǎn)單選擇排序C、堆排序D、所有選項(xiàng)都不對(duì)【正確答案】：A解析：

直接插入排序中沒有同一對(duì)元素被比較過兩次或以上?！菊_答案】：為A。13.9.棧和隊(duì)列的共同點(diǎn)是（）。A、都是先進(jìn)后出B、都是后進(jìn)先出C、只允許在端點(diǎn)處插入和刪除元素D、沒有共同點(diǎn)【正確答案】：C解析：

棧和隊(duì)列的共同點(diǎn)是，數(shù)據(jù)元素的邏輯關(guān)系都是線性關(guān)系，都只能在端點(diǎn)處進(jìn)行插入和刪除操作?！菊_答案】：為C。14.59.以下不屬于內(nèi)排序方法的是（）。A、二路歸并排序B、拓?fù)渑判駽、堆排序D、直接插入排序【正確答案】：B解析：

拓?fù)渑判蚴且环N產(chǎn)生拓?fù)湫蛄械姆椒?，不屬?nèi)排序方法。15.29.對(duì)于棧操作數(shù)據(jù)的原則是（）。A、先進(jìn)先出B、后進(jìn)先出C、后進(jìn)后出D、不分順序【正確答案】：B解析：

棧操作數(shù)據(jù)的原則是先進(jìn)后出或后進(jìn)先出。16.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已出棧了。17.51.以下排序方法中，穩(wěn)定的排序方法是（）。A、快速排序B、堆排序C、希爾排序D、基數(shù)排序【正確答案】：D解析：

基數(shù)排序是一種穩(wěn)定的排序方法。18.個(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。19.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ù)元素的集合。20.排序確定A、外排序所花時(shí)間=內(nèi)排序時(shí)間+外存信息讀寫時(shí)間+內(nèi)部歸并所花時(shí)間B、外排序并不涉及文件的讀寫操作C、外排序完全可以由內(nèi)排序來替代【正確答案】：B解析：

外排序過程主要分為兩個(gè)階段：生成初始?xì)w并段和對(duì)初始?xì)w并段進(jìn)行歸并，這兩個(gè)步驟中都涉及文件的讀寫操作。21.35.圖的遍歷是指（）。A、訪問圖的所有頂點(diǎn)B、以某種次序訪問圖的所有頂點(diǎn)C、從一個(gè)頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)且每個(gè)頂點(diǎn)只能訪問一次D、從一個(gè)頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)但每個(gè)頂點(diǎn)可以訪問多次【正確答案】：C解析：

圖的遍歷是從給定的初始點(diǎn)出發(fā)訪問每個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)僅訪問一次。22.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è)有序段，所以一般來講，m與數(shù)據(jù)序列、內(nèi)存工作區(qū)可容納的記錄個(gè)數(shù)w和n都有關(guān)，但并不是A、B、C選項(xiàng)所指的直接關(guān)系。23.（）__。A、堆排序B、冒泡排序C、直接插入排序D、簡(jiǎn)單選擇排序E、滿二叉樹F、二叉判定樹G、平衡二叉樹H、完全二叉樹【正確答案】：C解析：

堆排序、冒泡排序和簡(jiǎn)單選擇排序中，每一趟產(chǎn)生的有序區(qū)都是全局有序的?！菊_答案】：為C。9、9.堆的形狀是一棵_（）__?！菊_答案】：D堆的形狀是一棵完全二叉樹?！菊_答案】：為D。24.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。25.19.假設(shè)某個(gè)帶頭結(jié)點(diǎn)單鏈表的頭結(jié)點(diǎn)為head，則判定該表為空表的條件是（）。A、head==NoneB、heaC、next==headD、next==NoneE、head!=None【正確答案】：B解析：

帶頭結(jié)點(diǎn)單鏈表的頭結(jié)點(diǎn)總是存在的，其next屬性指向首結(jié)點(diǎn)，首結(jié)點(diǎn)為空表示單鏈表是空表。26.是()。A、存在，且唯一B、存在、且不唯一C、存在，可能不唯一D、無法確定是否存在【正確答案】：C解析：

這樣的有向圖中只有頂點(diǎn)i到頂點(diǎn)j（i<j）可能有邊，而頂點(diǎn)j到頂點(diǎn)i一定沒有邊，也就是說這樣的有向圖中一定沒有回路，所以可以產(chǎn)生拓?fù)湫蛄?，但拓?fù)湫蛄胁灰欢ㄎㄒ??！菊_答案】：為C。27.27.設(shè)有13個(gè)權(quán)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個(gè)結(jié)點(diǎn)。A、13B、12C、26D、25【正確答案】：D28.儲(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。29.2.設(shè)矩陣a的元素ai,j（1≤i，j≤10）滿足ai,j≠0（i≤j）和ai,j=0（i>j）。若將a的所有非零元素以行優(yōu)先存放在首地址為2000的存儲(chǔ)空間中，每個(gè)元素占4個(gè)單元，則元素a5,9的首地址是（）。A、2340B、2152C、2220D、2160【正確答案】：B解析：

該矩陣是一個(gè)上三角矩陣（下三角部分為常量0），采用以行優(yōu)先存放時(shí)，對(duì)于上三角中的元素a5,9，前面有第1行～第4行，共計(jì)10+9+8+7=34個(gè)元素，第5行前有4個(gè)元素（a5,5～a5,8），則LOC(a5,9)=LOC(a1,1)+(34+4)×4=2000+152=2152?！菊_答案】：為B。30.到'*'時(shí)，運(yùn)算數(shù)棧（從棧頂?shù)綏５状涡颍椋ǎ、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。31.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。32.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【正確答案】：A33.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)。34.8.順序表具有隨機(jī)存取特性，指的是（）。A、查找值為x的元素與順序表中元素個(gè)數(shù)n無關(guān)B、查找值為x的元素與順序表中元素個(gè)數(shù)n有關(guān)C、查找序號(hào)為i的元素與順序表中元素個(gè)數(shù)n無關(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)元素值。35.排序，需要分配和收集()趟。A、3B、4C、5D、8【正確答案】：A解析：

這組關(guān)鍵字中最長(zhǎng)的位數(shù)是3，所以采用基數(shù)排序方法時(shí)需要進(jìn)行3趟分配和收集過程?！菊_答案】：為A。36.24.由m個(gè)初始?xì)w并段構(gòu)建的k階最佳歸并樹中，總共有（）個(gè)結(jié)點(diǎn)。A、(mk-1)/kB、(mk-1)/(k-1)C、mk/(k-1)D、無法確定【正確答案】：B解析：

設(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)。37.8.在（）_中將會(huì)用到棧結(jié)構(gòu)。A、遞歸調(diào)用B、圖深度優(yōu)先遍歷C、表達(dá)式求值D、以上場(chǎng)景都有【正確答案】：D解析：

在遞歸調(diào)用、圖的深度優(yōu)先遍歷和表達(dá)式求值中均使用棧。【正確答案】：為D。38.13.數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容不涉及（）。A、數(shù)據(jù)如何組織B、數(shù)據(jù)如何存儲(chǔ)C、數(shù)據(jù)運(yùn)算如何實(shí)現(xiàn)D、算法用什么語言來描述【正確答案】：D解析：

數(shù)據(jù)結(jié)構(gòu)涉及三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)（對(duì)應(yīng)選項(xiàng)A），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（對(duì)應(yīng)選項(xiàng)B）和運(yùn)算（運(yùn)算包括運(yùn)算描述和運(yùn)算實(shí)現(xiàn)，后者對(duì)應(yīng)選項(xiàng)C）。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.6.算法的平均時(shí)間復(fù)雜度取決于（）。A、問題的規(guī)模B、待處理數(shù)據(jù)的初始狀態(tài)C、A和BD、計(jì)算機(jī)的配【正確答案】：A解析：

算法的時(shí)間復(fù)雜度分為最好、最壞和平均時(shí)間復(fù)雜度，最好和最壞時(shí)間復(fù)雜度是考慮若干種實(shí)例得到的結(jié)果，與初始狀態(tài)有關(guān)，而平均時(shí)間復(fù)雜度是考慮所有實(shí)例的結(jié)果，與初始狀態(tài)無關(guān)。答案為A。41.收集后得到的關(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ù)字來排序的，第二趟排序是按然十位數(shù)字的大小進(jìn)行排序的。【正確答案】：為C。42.有序段。A、1B、2C、3D、5【正確答案】：C解析：

產(chǎn)生的有序段是{4,5}，{2,3}，{1}，共3個(gè)有序段。43.19.哈希查找方法一般適用于（）情況下的查找。A、查找表為鏈表B、查找表為有序表C、關(guān)鍵字集合比地址集合大得多D、關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系?！菊_答案】：D解析：

哈希表通過哈希函數(shù)和沖突解決函數(shù)確定存儲(chǔ)地址的，適合關(guān)鍵字集合與地址集合之間存在著某種對(duì)應(yīng)關(guān)系的數(shù)據(jù)集的存儲(chǔ)與查找?！菊_答案】：為D。44.4.采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()。A、遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B、每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)【正確答案】：D解析：

快速排序?qū)⒁粋€(gè)無序序列劃分為兩個(gè)無序子序列，這兩個(gè)無序子序列的排序是獨(dú)立的，先排序哪一個(gè)都可以?！菊_答案】：為D。45.)。A、完全圖B、連通圖才C、有回路D、一棵樹【正確答案】：B解析：

從無向圖的某個(gè)頂點(diǎn)v出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點(diǎn)，則說明v到該圖的每個(gè)頂點(diǎn)都有路徑，這樣的無向圖一定是連通圖?！菊_答案】：為B。46.的數(shù)據(jù)結(jié)構(gòu)為（）。A、數(shù)組B、樹C、圖D、線性表【正確答案】：B47.7.某算法的時(shí)間復(fù)雜度為O(n2)，表明該算法的（）。A、問題規(guī)模是n2B、執(zhí)行時(shí)間等于n2C、執(zhí)行時(shí)間與n2成正比D、問題規(guī)模與n2成正比【正確答案】：C解析：

算法的時(shí)間復(fù)雜度為O(n2)，表示執(zhí)行時(shí)間與問題規(guī)模呈平方關(guān)系，問題規(guī)模仍然是n。答案為C。48.實(shí)際元素個(gè)數(shù)的變量count，則該隊(duì)中最多可以存放的元素個(gè)數(shù)是（）。A、n-1B、nC、(rear+n)%nD、(n-rear)%n【正確答案】：B解析：

這樣設(shè)計(jì)的隊(duì)列的隊(duì)滿條件為count==n，隊(duì)列中可以放置n個(gè)元素?！菊_答案】：為B。49.17.以下（）是"abcd321ABCD"串的子串。A、abcdB、321ABC、"abcABC"D、"21AB"【正確答案】：D50.的排序方法是（）。A、簡(jiǎn)單選擇排序B、快速排序C、冒泡排序D、直接插入排序【正確答案】：A解析：

從數(shù)據(jù)排列次序的變化過程看到，每一趟都從無序區(qū)中選一個(gè)最小的元素歸位。51.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。52.15.在一個(gè)雙鏈表中，刪除p所指結(jié)點(diǎn)（非首、尾結(jié)點(diǎn)）的操作是()。A、p.prior.next=p.next;p.next.prior=p.priorB、p.prior=p.prior.prior;p.prior.prior=pC、p.next.prior=p;p.next=p.next.nextD、p.next=p.prior.prior;p.prior=p.prior.prior【正確答案】：A解析：

在雙鏈表中刪除結(jié)點(diǎn)p的過程如圖A.24所示，訪問兩步（順序可以任意），答案為A。53.2.線性表是（）。A、一個(gè)有限序列，可以為空B、一個(gè)有限序列，不可以為空C、一個(gè)無限序列，可以為空D、一個(gè)無限序列，不可以為空【正確答案】：A解析：

線性表的定義有三點(diǎn)，即所有元素類型相同、元素個(gè)數(shù)有限、元素之間為線性關(guān)系（序列是指線性關(guān)系），另外線性表中元素個(gè)數(shù)可以為0，即空表。54.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。55.1.若某非空二叉樹的中序序列和后序序列正好相反，則該二叉樹的形態(tài)是（）。A、只有一個(gè)根結(jié)點(diǎn)B、所有分支結(jié)點(diǎn)都有左右孩子C、所有結(jié)點(diǎn)沒有左子樹D、所有結(jié)點(diǎn)沒有右子樹【正確答案】：C56.操作是（）。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.21.線索二叉樹中的線索是指（）。A、左孩子B、右孩子C、指針D、標(biāo)識(shí)【正確答案】：C58.56.下列排序方法中，（）在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A、簡(jiǎn)單選擇排序B、冒泡排序C、歸并排序D、堆排序【正確答案】：C解析：

因?yàn)闅w并排序每趟并不一定產(chǎn)生全局有序區(qū)。59.18.以下關(guān)于有向圖的說法中，正確的是()。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。60.28.在一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖中至少有（）條邊。A、nB、n+lC、n-1D、n/2【正確答案】：C61.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。62.6.在一棵非空二叉樹的先序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系()。A、不一定相同A、都相同B、都不相同C、互為逆序【正確答案】：B63.5.以下數(shù)據(jù)結(jié)構(gòu)中()屬非線性結(jié)構(gòu)。A、棧B、串C、隊(duì)列D、平衡二叉樹【正確答案】：D解析：

棧、隊(duì)列和串中元素的邏輯關(guān)系都是線性關(guān)系，平衡二叉樹是一種二叉樹，而二叉樹屬于非線性結(jié)構(gòu)。答案為D。64.5.設(shè)棧s和隊(duì)列q的初始狀態(tài)都為空，元素a、b、c、d、e和f依次通過棧s，一個(gè)元素出棧后即進(jìn)入隊(duì)列q，若6個(gè)元素出隊(duì)的序列是b、d、c、f、e、a，則棧s的容量（存放的元素個(gè)數(shù)）至少是()。A、2B、3C、4D、5【正確答案】：B解析：

一個(gè)序列通過一個(gè)隊(duì)列不會(huì)改變其順序，本題相當(dāng)于由a、b、c、d、e、f通過棧s得到出棧序列b、d、c、f、e、a，棧s的容量至少是多少，直接模擬該過程，棧中元素最多的情況是f、e、a，共3個(gè)元素。【正確答案】：為B。65.叉排序樹，若希望高度最小，則應(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。66.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。67.）個(gè)虛段。A、uB、k-uC、k-1-uD、u-1【正確答案】：C68.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【正確答案】：A69.30.一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（）條邊。A、nB、n(n-1)C、n(n-1)/2D、2n【正確答案】：C解析：

當(dāng)為完全無向圖時(shí)邊數(shù)最多。70.4.以下算法的時(shí)間復(fù)雜度為()。deffun(n):i,s=0,0whiles<=n:i+=1s+=iA、O(n)B、O(√nn)C、O(nloD、2n)E、O(loF、2n)【正確答案】：B解析：

設(shè)while循環(huán)執(zhí)行的次數(shù)為m，i從0開始，每次循環(huán)增加1，則s=1+2+…+m=m(m+1)/2≤n，可以推出m=O(n)。答案為B。71.9.在長(zhǎng)度為n的順序表中插入一個(gè)元素，對(duì)應(yīng)算法的時(shí)間復(fù)雜度為()。A、O(1)B、O(log2n)C、O(n)D、O(n2)【正確答案】：C解析：

在長(zhǎng)度為n的順序表中插入一個(gè)元素，平均需要移動(dòng)一半的元素，時(shí)間復(fù)雜度為O(n)。答案為C。72.個(gè)數(shù)是（）。A、10B、nC、5D、2【正確答案】：A解析：

基數(shù)排序中建立隊(duì)列個(gè)數(shù)等于進(jìn)制數(shù)。73.11.順序表和鏈表相比存儲(chǔ)密度較大，這是因?yàn)?)。A、順序表的存儲(chǔ)空間是預(yù)先分配的B、順序表不需要增加指針來表示元素之間的邏輯關(guān)系C、鏈表中所有結(jié)點(diǎn)的地址是連續(xù)的D、順序表中所有元素的存儲(chǔ)地址是不連續(xù)的【正確答案】：B解析：

由于順序表中邏輯上相鄰的兩個(gè)元素在物理上也相鄰，不需要增加指針來表示元素之間的邏輯關(guān)系，所以存儲(chǔ)密度為1，而鏈表的存儲(chǔ)密度總是小于1。答案為B。74.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。75.14.一棵高度為h（h≥1）的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)。A、2h-1B、2hC、2h+1D、2h-1+1【正確答案】：A76.45.以下（）方法在數(shù)據(jù)基本有序時(shí)效率最好。A、快速排序B、冒泡排序C、堆排序D、希爾排序【正確答案】：B77.5.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）。（1≤i≤n）的存儲(chǔ)地址為L(zhǎng)OC(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ǔ)。78.30.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。A、3B、4C、5D、6【正確答案】：C79.19.數(shù)據(jù)結(jié)構(gòu)通常采用二元組表示：B=(D,R)，其中R表示（）的集合。A、數(shù)據(jù)項(xiàng)B、數(shù)據(jù)元素C、數(shù)據(jù)元素關(guān)系D、數(shù)據(jù)類型【正確答案】：C解析：

二元組(D,R)是數(shù)據(jù)邏輯結(jié)構(gòu)的一種通用描述方法，其中D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)元素關(guān)系的集合，在D上可以多種關(guān)系，每個(gè)關(guān)系用序偶來表示。80.26.一個(gè)無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的（）。A、極小連通子圖B、極小子圖C、極大連通子圖D、極大子圖【正確答案】：A81.10.由權(quán)值分別為9、2、7、5的4個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為_()。A、23B、44C、37D、27【正確答案】：B82.27.n個(gè)頂點(diǎn)的連通圖的生成樹有（）個(gè)頂點(diǎn)。A、n-1B、nC、n+1D、不確定【正確答案】：B83.18.高度為h（h>0）的滿二叉樹對(duì)應(yīng)的森林由（）棵樹構(gòu)成。A、1B、loC、2hD、h/2E、h【正確答案】：D84.25，25，49（最終狀態(tài)）可以斷定，所采用的排序方法是（）排序。A、直接插入B、冒泡C、二路歸并D、簡(jiǎn)單選擇【正確答案】：D解析：

共有6個(gè)元素，即使有序也不結(jié)束，從排序過程可以斷定是簡(jiǎn)單選擇排序。85.前一位置，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。86.20.一個(gè)含有n（n>0）個(gè)頂點(diǎn)的連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是（）。A、對(duì)稱矩陣B、非對(duì)稱矩陣C、稀疏矩陣D、稠密矩陣【正確答案】：A解析：

連通圖是指任意兩個(gè)頂點(diǎn)之間存在路徑的無向圖，其鄰接矩陣一定是對(duì)稱矩陣?！菊_答案】：為A。87.24.如果具有n個(gè)頂點(diǎn)的圖恰好是一個(gè)環(huán)，則它有（）棵生成樹。A、n-1B、nC、n+1D、2n【正確答案】：D解析：

如果圖恰好是一個(gè)環(huán)，對(duì)于圖中每個(gè)頂點(diǎn)，都有順時(shí)針和逆時(shí)針方向兩棵生成樹，總計(jì)2n棵生成樹。88.12.以下關(guān)于哈希查找的敘述中正確的是()_。A、哈希查找中不需要任何關(guān)鍵字的比較B、采用拉鏈法解決沖突時(shí)，查找每個(gè)元素的時(shí)間是相同的C、哈希表在查找成功時(shí)的平均查找長(zhǎng)度僅僅與表長(zhǎng)有關(guān)D、哈希表的裝填因子等于表中填入的元素個(gè)數(shù)除以哈希表的長(zhǎng)度【正確答案】：D解析：

裝填因子等于表中填入的元素個(gè)數(shù)n除以哈希表的長(zhǎng)度m。【正確答案】：為D。89.拓?fù)湫蛄兄?，若頂點(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ù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，圖中不一定有邊<a，b>?！菊_答案】：為A。10、10.以下敘述中錯(cuò)誤的是（）?！菊_答案】：C圖的深度優(yōu)先遍歷適合無向圖和有向圖。【正確答案】：為C。90.25.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)是指（）。A、數(shù)據(jù)類型B、指針類型C、數(shù)據(jù)元素之間的邏輯關(guān)系D、數(shù)據(jù)元素之間的物理關(guān)系【正確答案】：C解析：

數(shù)據(jù)元素之間的邏輯關(guān)系構(gòu)成了數(shù)據(jù)的邏輯結(jié)構(gòu)。91.4.關(guān)于線性表的正確說法是（）。A、每個(gè)元素都有一個(gè)前趨和一個(gè)后繼元素B、線性表中至少有一個(gè)元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素有且僅有一個(gè)前趨和一個(gè)后繼元素【正確答案】：D解析：

線性表屬典型的線性結(jié)構(gòu)。92.15.一個(gè)循環(huán)隊(duì)列中元素的排列順序()_。A、與隊(duì)頭和隊(duì)尾指針的取值有關(guān)B、與元素值的大小有關(guān)C、由元素進(jìn)隊(duì)的先后順序確定D、與存放隊(duì)中元素的數(shù)組大小有關(guān)【正確答案】：C解析：

循環(huán)隊(duì)列中元素的排列順序主要是由元素進(jìn)隊(duì)的先后順序確定?！菊_答案】：為C。93.≤i≤m）。一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)為該結(jié)點(diǎn)的次數(shù)（或度）。A、互不相交B、允許相交C、允許葉結(jié)點(diǎn)相交D、允許樹枝結(jié)點(diǎn)相交【正確答案】：A94.12.若串str="Software"，其子串的數(shù)目是（）。A、8B、9C、36D、37【正確答案】：D95._。A、直接插入排序B、冒泡排序C、二路歸并排序D、希爾排序【正確答案】：B解析：

冒泡排序只需要做10趟就可以了，其他排序方法需要全部排序?！菊_答案】：為B。96.5.一個(gè)有向無環(huán)圖G的拓?fù)湫蛄袨椤瑅i，…，vj，…，則不可能出現(xiàn)的情形是()。A、G中有邊<vi，vj>B、G中有一條從vi到vj的路徑C、G中沒有邊<vi，vj>D、G中有一條從vj到vi的路徑【正確答案】：D解析：

拓?fù)湫蛄袨椤?，vi，…，vj，…，則vi到vj有邊或者路徑，如果存在從vj到vi的路徑，則存在回路?！菊_答案】：為D。97.值為()。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。98.42.冒泡排序最少元素移動(dòng)的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A99.16.以下排序方法中，()在初始序列已基本有序的情況下，排序效率最高。A、二路歸并排序B、快速排序C、直接插入排序D、堆排序【正確答案】：C解析：

二路歸并排序和堆排序的效率用初始序列分布無關(guān)，而在初始序列已基本有序的情況下快速排序的效率最差。【正確答案】：為C。100.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)镈先出來，說明A，B，C，D均在棧中，在棧中順序應(yīng)為D，C，B，A，出棧的順序只能是D，C，B，A，如圖3.3所示。所以本題【正確答案】：為D。1.12.n（n>2）個(gè)結(jié)點(diǎn)的二叉樹中至少有一個(gè)度為2的結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B2.6.置換-選擇排序算法的作用是由一個(gè)無序文件生成若干個(gè)有序的子文件。A、正確B、錯(cuò)誤【正確答案】：A3.18.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧的定義不涉及數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，棧中數(shù)據(jù)元素的邏輯關(guān)系屬于線性關(guān)系，所以棧的定義涉及4.8.一個(gè)圖中的簡(jiǎn)單路徑是指該路徑上的邊不重復(fù)出現(xiàn)。A、正確B、錯(cuò)誤【正確答案】：B解析：

一個(gè)圖中的簡(jiǎn)單路徑是指該路徑上的頂點(diǎn)不重復(fù)出現(xiàn)。5.11.哈希沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)不同的哈希地址。A、正確B、錯(cuò)誤【正確答案】：B解析：

哈希沖突是指多個(gè)不同一個(gè)關(guān)鍵字對(duì)應(yīng)相同的哈希地址。6.數(shù)據(jù)的邏輯結(jié)構(gòu)。50、19.棧是一種特殊的線性表，其特殊之處在于棧的存儲(chǔ)結(jié)構(gòu)比較特殊。A、正確B、錯(cuò)誤【正確答案】：B解析：

棧是一種特殊的線性表，其特殊之處在于對(duì)線性表的操作做了限制。7.1.順序隊(duì)采用數(shù)組存放隊(duì)中元素，數(shù)組具有隨機(jī)存取特性，所以順序隊(duì)中可以隨機(jī)存取元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

順序隊(duì)采用數(shù)組存放隊(duì)中元素，盡管數(shù)組具有隨機(jī)存取特性，但隊(duì)列的操作特性是順序存取，只能存取兩端的元素。8.值。A、正確B、錯(cuò)誤【正確答案】：A9.19.外排序中沒有關(guān)鍵字比較。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序中需要關(guān)鍵字比較。10.14.圖的遍歷就是訪問圖中所有頂點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的遍歷是指以某種順序訪問圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問一次。11.42.二路歸并排序算法的時(shí)間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：A12.14.非空二叉樹的后序序列的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：A13.2.對(duì)于無向圖生成樹，從同一頂點(diǎn)出發(fā)所得到的生成樹一定是相同的。A、正確B、錯(cuò)誤【正確答案】：B解析：

無向圖的生成樹可能有多棵，從同一頂點(diǎn)出發(fā)所得到的生成樹也不一定相同。14.13.空棧是指棧中元素沒有賦值。A、正確B、錯(cuò)誤【正確答案】：B解析：

空棧是指棧中沒有元素。15.35.基數(shù)排序與初始數(shù)據(jù)的次序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：A16.9.二叉樹中每個(gè)度為2的結(jié)點(diǎn)的兩棵子樹都是有序的。A、正確B、錯(cuò)誤【正確答案】：A17.31.冒泡排序在最好情況下的時(shí)間復(fù)雜度也是O(n2)。A、正確B、錯(cuò)誤【正確答案】：B解析：

冒泡排序在最好情況下的時(shí)間復(fù)雜度為O(n)。18.3.非線性結(jié)構(gòu)中，每個(gè)元素最多只有一個(gè)前趨元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

非線性結(jié)構(gòu)中，每個(gè)元素可能有多個(gè)前趨元素。19.13.外排序的k路平衡歸并中，采用敗者樹時(shí)，歸并效率與k無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序的k路平衡歸并中，采用敗者樹時(shí)，總的關(guān)鍵字比較次數(shù)與k無關(guān)。20.7.n個(gè)元素進(jìn)隊(duì)的順序和出隊(duì)的順序總是一致的。A、正確B、錯(cuò)誤【正確答案】：A解析：

后進(jìn)隊(duì)的元素后出隊(duì)，先進(jìn)隊(duì)的元素先出隊(duì)。21.11.圖的深度優(yōu)先遍歷算法僅對(duì)無向圖適用。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷算法對(duì)無向圖和有向圖都適用。22.15.為了提高外排序的速度，在外排序中必須選用最快的內(nèi)排序算法。A、正確B、錯(cuò)誤【正確答案】：B解析：

外排序的第二階段只能采用歸并排序算法。23.5.一個(gè)連通圖的生成樹是唯一的。A、正確B、錯(cuò)誤【正確答案】：B解析：

一個(gè)連通圖的生成樹可能有多棵。24.1.k路最佳歸并樹在外排序中的作用是產(chǎn)生初始?xì)w并段。A、正確B、錯(cuò)誤【正確答案】：B25.43.內(nèi)排序方法要求數(shù)據(jù)一定以順序表方式存儲(chǔ)。A、正確B、錯(cuò)誤【正確答案】：B解析：

有些內(nèi)排序方法也適合數(shù)據(jù)采用鏈表方式存儲(chǔ)的情況。26.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ì)任意次。27.徑。A、正確B、錯(cuò)誤【正確答案】：A解析：

如果頂點(diǎn)j到頂點(diǎn)k有路徑，則頂點(diǎn)i有一條通過頂點(diǎn)j到達(dá)頂點(diǎn)k的路徑，與題中條件矛盾。28.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ù)序列無29.27.簡(jiǎn)單選擇排序在初始數(shù)據(jù)正序時(shí)，其時(shí)間復(fù)雜度為O(n)。A、正確B、錯(cuò)誤【正確答案】：B30.23.從時(shí)間性能看，堆排序總是優(yōu)于簡(jiǎn)單選擇排序。A、正確B、錯(cuò)誤【正確答案】：A解析：

堆排序的最好、最壞和平均時(shí)間復(fù)雜度均為O(nlog2n)，而簡(jiǎn)單選擇排序的最好、最壞和平均時(shí)間復(fù)雜度均為O(n2)。31.5.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯?chǔ)的線性表。A、正確B、錯(cuò)誤【正確答案】：A32.5.樹中元素之間是多對(duì)多的關(guān)系。A、正確B、錯(cuò)誤【正確答案】：B33.41.對(duì)于不同的初始數(shù)據(jù)序列，二路歸并排序算法中關(guān)鍵字比較次數(shù)有所不同。A、正確B、錯(cuò)誤【正確答案】：A解析：

二路歸并排序算法的時(shí)間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)，但關(guān)鍵字比較次數(shù)是相關(guān)的。34.9.k路平衡歸并中，敗者樹的主要作用是減少歸并的趟數(shù)。A、正確B、錯(cuò)誤【正確答案】：B解析：

敗者樹的主要作用是加速從k個(gè)記錄中選取最小記錄，并不能減少歸并的趟數(shù)。35.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)。36.44.所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B37.6.線性表的長(zhǎng)度是線性表占用的存儲(chǔ)空間的大小。A、正確B、錯(cuò)誤【正確答案】：B解析：

線性表的長(zhǎng)度是指表中元素個(gè)數(shù)，屬邏輯結(jié)構(gòu)的概念，與線性表占用的存儲(chǔ)空間大小無關(guān)。38.15.非空二叉樹的中序序列的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B39.7.數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)是基于數(shù)據(jù)的邏輯結(jié)構(gòu)的。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)的運(yùn)算描述是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，而數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)與存儲(chǔ)結(jié)構(gòu)相關(guān)聯(lián)，所以數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)是基于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的。40.要(100-1)×3×1=297次關(guān)鍵字比較。73、12.減少初始?xì)w并段的個(gè)數(shù)，可以使外排序的時(shí)間縮短。A、正確B、錯(cuò)誤【正確答案】：A41.7.n個(gè)頂點(diǎn)的無向圖至多有n(n-1)條邊。A、正確B、錯(cuò)誤【正確答案】：B解析：

n個(gè)頂點(diǎn)的無向圖至多有n(n-1)/2條邊。42.1.一種邏輯結(jié)構(gòu)的數(shù)據(jù)只有一種對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)。A、正確B、錯(cuò)誤【正確答案】：B43.40.二路歸并排序算法是穩(wěn)定的。A、正確B、錯(cuò)誤【正確答案】：A44.24.簡(jiǎn)單選擇排序中，每趟產(chǎn)生的有序區(qū)中所有元素在以后的排序中不再改變位置。A、正確B、錯(cuò)誤【正確答案】：A45.8.數(shù)據(jù)的運(yùn)算就是指基本運(yùn)算，只能對(duì)數(shù)據(jù)實(shí)施基本運(yùn)算。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)的基本運(yùn)算只是數(shù)據(jù)運(yùn)算的一部分，它是常用的數(shù)據(jù)運(yùn)算，但并非就是數(shù)據(jù)運(yùn)算的全部，也可以對(duì)數(shù)據(jù)實(shí)施非基本運(yùn)算。46.10.二叉樹是一種特殊的樹。A、正確B、錯(cuò)誤【正確答案】：B47.樹。A、正確B、錯(cuò)誤【正確答案】：B解析：

對(duì)于二叉排序樹，左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根記錄的關(guān)鍵字；右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根記錄的關(guān)鍵字。而不是僅僅與左、右孩子的關(guān)鍵字進(jìn)行比較。48.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ù)。49.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)系。50.7.在二叉排序樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小。A、正確B、錯(cuò)誤【正確答案】：A51.徑。A、正確B、錯(cuò)誤【正確答案】：A解析：

頂點(diǎn)i和頂點(diǎn)j屬一個(gè)連通分量，而頂點(diǎn)k屬另一個(gè)連通分量，所以頂點(diǎn)i到頂點(diǎn)k沒有路徑。52.1.給定一棵樹T，將其轉(zhuǎn)換成二叉樹B后，它們的結(jié)點(diǎn)個(gè)數(shù)相同。A、正確B、錯(cuò)誤【正確答案】：A53.17.由二叉樹某種遍歷方式產(chǎn)生的結(jié)果是一個(gè)線性序列。A、正確B、錯(cuò)誤【正確答案】：A54.14.在外排序過程中，一個(gè)記錄的讀入內(nèi)存的次數(shù)和寫到外存的次數(shù)必定相等。A、正確B、錯(cuò)誤【正確答案】：A55.9.數(shù)據(jù)對(duì)象就是一組任意數(shù)據(jù)元素的集合。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)對(duì)象是指具有相同性質(zhì)的有限個(gè)數(shù)據(jù)元素的集合。56.39.n個(gè)元素采用二路歸并排序算法，總的趟數(shù)為n。A、正確B、錯(cuò)誤【正確答案】：B解析：

n個(gè)元素采用二路歸并排序算法，總的趟數(shù)為log2n。57.8.線性表的邏輯順序總與其物理順序一致。A、正確B、錯(cuò)誤【正確答案】：B解析：

當(dāng)線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其邏輯順序與物理順序可能不一致。58.5.線性表中每個(gè)元素都有一個(gè)前趨元素和一個(gè)后繼元素。A、正確B、錯(cuò)誤【正確答案】：B解析：

開始元素沒有前趨元素，終端元素沒有后繼元素。59.2.給定一棵樹T，可以找到唯一的一棵二叉樹B與之對(duì)應(yīng)。A、正確B、錯(cuò)誤【正確答案】：A60.18.非空二叉樹的先序序列的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：A61.16.棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。A、正確B、錯(cuò)誤【正確答案】：A解析：

棧和隊(duì)列中元素都呈現(xiàn)線性關(guān)系，但它們插入和刪除操作有別于線性表。62.7.采用多路平衡歸并方法可以減少初始?xì)w并段的個(gè)數(shù)。A、正確B、錯(cuò)誤【正確答案】：B解析：

采用多路平衡歸并方法可以減少歸并的趟數(shù)。63.13.二叉樹就是度為2的有序樹。A、正確B、錯(cuò)誤【正確答案】：B64.20.k路最佳歸并樹一定是一棵k路平衡樹。A、正確B、錯(cuò)誤【正確答案】：B解析：

k路最佳歸并樹不一定是一棵k路平衡樹。65.接插入排序。為把所有記錄排好序，需做6趟歸并排序。A、正確B、錯(cuò)誤【正確答案】：B解析：

內(nèi)排序采用直接插入排序時(shí)，可以產(chǎn)生375000/600=625個(gè)初始?xì)w并段，5路平衡歸并排序的趟數(shù)=log5625=4。所以需做4趟歸并排序。66.37.基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。A、正確B、錯(cuò)誤【正確答案】：B67.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ì)列操作的次序。68.11.有n個(gè)不同的元素通過一個(gè)棧，產(chǎn)生的所有出棧序列恰好構(gòu)成這n個(gè)元素的全排列。A、正確B、錯(cuò)誤【正確答案】：B69.8.哈夫曼樹中結(jié)點(diǎn)個(gè)數(shù)可以偶數(shù)也可以是奇數(shù)。A、正確B、錯(cuò)誤【正確答案】：B70.12.相同的n個(gè)元素的不同序列通過一個(gè)棧一定不會(huì)得到相同的出棧序列。A、正確B、錯(cuò)誤【正確答案】：B解析：

相同的n個(gè)元素的不同序列通過一個(gè)?？赡軙?huì)得到相同的出棧序列。例如，進(jìn)棧序列1、2、3和71.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)。72.2.順序查找方法只能從順序表的前端向后端查找。A、正確B、錯(cuò)誤【正確答案】：B解析：

順序查找方法可以從順序表的前端向后端查找，也可以從順序表的后端向前端查找。73.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次。74.個(gè)比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯(cuò)誤【正確答案】：A解析：

歸并趟數(shù)s=log55=1，5個(gè)記錄選取最小記錄需比較4次，所以總共需要(100-1)×4×1=396次關(guān)鍵字比較。75.1.線性表中所有元素的數(shù)據(jù)類型必須相同。A、正確B、錯(cuò)誤【正確答案】：A解析：

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

后進(jìn)隊(duì)的元素后出隊(duì)，先進(jìn)隊(duì)的元素先出隊(duì)，所以出隊(duì)序列與進(jìn)隊(duì)序列相同。77.5.一個(gè)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素值發(fā)生改變，則它的邏輯結(jié)構(gòu)也隨之改變。A、正確B、錯(cuò)誤【正確答案】：B解析：

數(shù)據(jù)的邏輯結(jié)構(gòu)主要指數(shù)據(jù)元素之間的相鄰關(guān)系，與元素值無關(guān)。78.間復(fù)雜度的主要因素。正確錯(cuò)誤A、正確B、錯(cuò)誤【正確答案】：B解析：

影響算法時(shí)間復(fù)雜度的主要因素是移動(dòng)元素的次數(shù)和關(guān)鍵字比較的次數(shù)。79.15.任何一個(gè)圖，一旦指定源點(diǎn)，其深度優(yōu)先遍歷序列是唯一的。A、正確B、錯(cuò)誤【正確答案】：B解析：

圖的深度優(yōu)先遍歷序列不一定是唯一的。80.33.快速排序、簡(jiǎn)單選擇排序和堆排序都與初始序列次序無關(guān)。A、正確B、錯(cuò)誤【正確答案】：B解析：

快速排序與初始序列次序無關(guān)。81.干塊，每塊中的數(shù)據(jù)個(gè)數(shù)必須相同A、正確B、錯(cuò)誤【正確答案】：B解析：

分塊查找的數(shù)據(jù)組織方式為：數(shù)據(jù)表+索引表，數(shù)據(jù)表分塊，塊間有序，塊內(nèi)無序?！菊_答案】：為B。82.4.在一個(gè)含有n（n≥1）個(gè)元素的線性表中，所有元素值不能相同。A、正確B、錯(cuò)誤【正確答案】：B解析：

在線性表中允許存在元素值相同的元素，但它們的位置是不同。83.后移動(dòng)。A、正確B、錯(cuò)誤【正確答案】：B84.4.樹中每個(gè)結(jié)點(diǎn)都有唯一的前趨結(jié)點(diǎn)。A、正確B、錯(cuò)誤【正確答案】：B85.12.哈希表中所有的哈希地址是連續(xù)的。A、正確B、錯(cuò)誤【正確答案】：A86.9.棧和隊(duì)列都是限制存取端的線性表。A、正確B、錯(cuò)誤【正確答案】：A解析：