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

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

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

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

不成功時最大的比較次數(shù)=log2(n+1)=7?！菊_答案】：為D。5.21.設(shè)連通圖有n個頂點e條邊（e，n>0），若滿足（），則圖中一定有回路。A、e≥nB、e<nC、e=n-1D、2e≥n【正確答案】：A解析：

一個有n個頂點e條邊的無向圖，若e=n-1時構(gòu)成一個樹圖，若en-1則一定存在回路?！菊_答案】：為A。6.同IV.若v不是T1的葉子結(jié)點，則T1與T3相同A、僅I、IIIB、僅I、IVC、僅II、IIID、僅II、IV【正確答案】：C解析：

在一棵二叉排序樹中刪除一個結(jié)點后再將此結(jié)點插入到二叉排序樹中，如果刪除的結(jié)點是葉子結(jié)點，那么在插入結(jié)點后，后來的二叉排序樹與刪除結(jié)點之前相同。如果刪除的結(jié)點不是葉子結(jié)點，那么再插入這個結(jié)點后，后來的二叉樹可能發(fā)生變化，不再相同?！菊_答案】：為C。7.19.對有n個元素的排序表進行直接插入排序，在最好情況下需比較()次關(guān)鍵字。A、n-1B、n+1C、n/2D、n(n-1)/2【正確答案】：A解析：

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

問題規(guī)模為n時，二分查找的時間復(fù)雜度為O(log2n)，而二叉排序樹查找與樹高相關(guān)，介于O(log2n)～O(n)，所以二分查找和二叉排序樹查找的時間性能不是完全相同，也不是完全不同，只能說有時不同?！菊_答案】：為B。9.26.樹最適合用來表示（）。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)【正確答案】：C10.38.以下關(guān)于二叉樹遍歷的說法中，錯誤的是（）。A、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則先序和后序序列相同B、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則中序和后序序列相同C、一棵二叉樹中，若每個結(jié)點最多只有左孩子，沒有右孩子，則先序和層次序列相同D、一棵二叉樹中，若每個結(jié)點最多只有右孩子，沒有左孩子，則先序和中序序列相同【正確答案】：A11.IV.若v不是T1的葉子結(jié)點，則T1與T3相同A、僅I、IIIB、僅I、IVC、僅II、IIID、僅II、IV【正確答案】：C解析：

在一棵二叉排序樹中刪除一個結(jié)點后再將此結(jié)點插入到二叉排序樹中，如果刪除的結(jié)點是葉子結(jié)點，那么在插入結(jié)點后，后來的二叉排序樹與刪除結(jié)點之前相同。如果刪除的結(jié)點不是葉子結(jié)點，那么再插入這個結(jié)點后，后來的二叉樹可能發(fā)生變化，不再相同?！菊_答案】：為C。12.為節(jié)儉排序算法，以下算法中是節(jié)儉排序算法的有_（）。A、直接插入排序B、簡單選擇排序C、堆排序D、所有選項都不對【正確答案】：A解析：

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

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

拓撲排序是一種產(chǎn)生拓撲序列的方法，不屬內(nèi)排序方法。15.29.對于棧操作數(shù)據(jù)的原則是（）。A、先進先出B、后進先出C、后進后出D、不分順序【正確答案】：B解析：

棧操作數(shù)據(jù)的原則是先進后出或后進先出。16.31.給定一個空棧，若元素10、20、23、13依次進棧，然后有兩個數(shù)出棧，又有3個數(shù)進棧，第一次進棧的元素23現(xiàn)在（）。A、已出棧B、從棧底算起第3個C、處于棧頂D、從棧底算起第4個【正確答案】：A解析：

本題的操作是：元素10、20、23、13依次進棧，然后出棧13和23，再進棧3個元素，第一次進棧的元素23已出棧了。17.51.以下排序方法中，穩(wěn)定的排序方法是（）。A、快速排序B、堆排序C、希爾排序D、基數(shù)排序【正確答案】：D解析：

基數(shù)排序是一種穩(wěn)定的排序方法。18.個數(shù)據(jù)遞增排序，最好的時間復(fù)雜度為()。A、O(nloB、2n)C、O(nloD、2k)E、O(kloF、2n)G、O(kloH、2k)【正確答案】：B解析：

每個組內(nèi)k個元素采用基于比較的排序方法排序最好時間復(fù)雜度為O(klog2k)，整個元素序列排序的最好時間復(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ù)項和數(shù)據(jù)項之間存在一種或多種特定關(guān)系D、同一數(shù)據(jù)中的所有數(shù)據(jù)元素值之間存在一種或多種特定關(guān)系【正確答案】：B解析：

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。20.排序確定A、外排序所花時間=內(nèi)排序時間+外存信息讀寫時間+內(nèi)部歸并所花時間B、外排序并不涉及文件的讀寫操作C、外排序完全可以由內(nèi)排序來替代【正確答案】：B解析：

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

圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次。22.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)系。23.（）__。A、堆排序B、冒泡排序C、直接插入排序D、簡單選擇排序E、滿二叉樹F、二叉判定樹G、平衡二叉樹H、完全二叉樹【正確答案】：C解析：

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

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

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

該矩陣是一個上三角矩陣（下三角部分為常量0），采用以行優(yōu)先存放時，對于上三角中的元素a5,9，前面有第1行～第4行，共計10+9+8+7=34個元素，第5行前有4個元素（a5,5～a5,8），則LOC(a5,9)=LOC(a1,1)+(34+4)×4=2000+152=2152?！菊_答案】：為B。30.到'*'時，運算數(shù)棧（從棧頂?shù)綏５状涡颍椋ǎ?。A、861B、581C、321D、361【正確答案】：C解析：

算術(shù)表達式“1+6/(8-5)*3”的后綴表達式是“1685-/3*+”，在求值時，遇到后綴表達式的'*'時，前面已進行了-和/運算，運算數(shù)棧中從棧頂?shù)綏５状涡驗?21?！菊_答案】：為C。31.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。32.33.以下關(guān)于二叉樹的說法中正確的是（）。A、二叉樹中度為0的結(jié)點個數(shù)等于度為2的結(jié)點個數(shù)加1B、二叉樹中結(jié)點個數(shù)必大于0C、完全二叉樹中任何結(jié)點的度為0或2D、二叉樹的度為2【正確答案】：A33.32.采用敗者樹進行k路平衡歸并的外排序算法中，總的關(guān)鍵字比較次數(shù)與k（）。A、成正比B、成反比C、無關(guān)D、以上都不對【正確答案】：C解析：

采用敗者樹進行k路平衡歸并的外排序算法中，總的關(guān)鍵字比較次數(shù)=(u-1)log2m，其中u為歸并的記錄個數(shù)，m是初始歸并段的個數(shù)，從而看出與k無關(guān)。34.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)元素值。35.排序，需要分配和收集()趟。A、3B、4C、5D、8【正確答案】：A解析：

這組關(guān)鍵字中最長的位數(shù)是3，所以采用基數(shù)排序方法時需要進行3趟分配和收集過程。【正確答案】：為A。36.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)。37.8.在（）_中將會用到棧結(jié)構(gòu)。A、遞歸調(diào)用B、圖深度優(yōu)先遍歷C、表達式求值D、以上場景都有【正確答案】：D解析：

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

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

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

產(chǎn)生的有序段是{4,5}，{2,3}，{1}，共3個有序段。43.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。44.4.采用遞歸方式對順序表進行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()。A、遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)【正確答案】：D解析：

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

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

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

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

從數(shù)據(jù)排列次序的變化過程看到，每一趟都從無序區(qū)中選一個最小的元素歸位。51.4.以下最適合用作鏈隊的不帶頭結(jié)點的鏈表是（）。A、只帶首結(jié)點指針的循環(huán)單鏈表B、只帶尾結(jié)點指針的單鏈表C、只帶首結(jié)點指針的單鏈表D、只帶尾結(jié)點指針的循環(huán)單鏈表【正確答案】：D解析：

只帶尾結(jié)點指針的循環(huán)單鏈表的進隊操作和出隊操作時間復(fù)雜度為O(1)?！菊_答案】：為D。52.15.在一個雙鏈表中，刪除p所指結(jié)點（非首、尾結(jié)點）的操作是()。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é)點p的過程如圖A.24所示，訪問兩步（順序可以任意），答案為A。53.2.線性表是（）。A、一個有限序列，可以為空B、一個有限序列，不可以為空C、一個無限序列，可以為空D、一個無限序列，不可以為空【正確答案】：A解析：

線性表的定義有三點，即所有元素類型相同、元素個數(shù)有限、元素之間為線性關(guān)系（序列是指線性關(guān)系），另外線性表中元素個數(shù)可以為0，即空表。54.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。55.1.若某非空二叉樹的中序序列和后序序列正好相反，則該二叉樹的形態(tài)是（）。A、只有一個根結(jié)點B、所有分支結(jié)點都有左右孩子C、所有結(jié)點沒有左子樹D、所有結(jié)點沒有右子樹【正確答案】：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]一端作為棧底，進棧中元素向s[0]一端生長。在第一個元素x進棧時，先執(zhí)行top-=1，這樣top指向s的有效下標(biāo)，再執(zhí)行s[top]=x?！菊_答案】：為C。57.21.線索二叉樹中的線索是指（）。A、左孩子B、右孩子C、指針D、標(biāo)識【正確答案】：C58.56.下列排序方法中，（）在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A、簡單選擇排序B、冒泡排序C、歸并排序D、堆排序【正確答案】：C解析：

因為歸并排序每趟并不一定產(chǎn)生全局有序區(qū)。59.18.以下關(guān)于有向圖的說法中，正確的是()。A、強連通圖中任何頂點到其他所有頂點都有邊B、完全有向圖一定是強連通圖C、有向圖中任一頂點的入度等于出度D、有向圖邊集的子集和頂點集的子集可構(gòu)成原有向圖的子圖【正確答案】：B解析：

強連通圖是任何頂點到其他所有頂點都有路徑而不一定有邊。完全有向圖中任意兩個頂點之間都存在一條邊，則一定是強連通圖。有向圖中任一頂點的入度不一定等于出度。一個有向圖邊集的子集和頂點集的子集不一定構(gòu)成一個圖。【正確答案】：為B。60.28.在一個具有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解析：

畫出各個序列對應(yīng)的完全二叉樹，再對每個分支結(jié)點逐個判斷。本題【正確答案】：為D。62.6.在一棵非空二叉樹的先序序列和后序序列中，各葉子之間的相對次序關(guān)系()。A、不一定相同A、都相同B、都不相同C、互為逆序【正確答案】：B63.5.以下數(shù)據(jù)結(jié)構(gòu)中()屬非線性結(jié)構(gòu)。A、棧B、串C、隊列D、平衡二叉樹【正確答案】：D解析：

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

一個序列通過一個隊列不會改變其順序，本題相當(dāng)于由a、b、c、d、e、f通過棧s得到出棧序列b、d、c、f、e、a，棧s的容量至少是多少，直接模擬該過程，棧中元素最多的情況是f、e、a，共3個元素。【正確答案】：為B。65.叉排序樹，若希望高度最小，則應(yīng)該選擇哪個序列插入（）。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個選項對應(yīng)的關(guān)鍵字序列構(gòu)造的4棵二叉排序樹如圖A.32所示，T2是一棵高度為3的滿二叉樹，高度最小?！菊_答案】：為B。66.1.某遞歸算法的時間遞推式如下：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.）個虛段。A、uB、k-uC、k-1-uD、u-1【正確答案】：C68.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【正確答案】：A69.30.一個有n個頂點的無向圖最多有（）條邊。A、nB、n(n-1)C、n(n-1)/2D、2n【正確答案】：C解析：

當(dāng)為完全無向圖時邊數(shù)最多。70.4.以下算法的時間復(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.在長度為n的順序表中插入一個元素，對應(yīng)算法的時間復(fù)雜度為()。A、O(1)B、O(log2n)C、O(n)D、O(n2)【正確答案】：C解析：

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

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

由于順序表中邏輯上相鄰的兩個元素在物理上也相鄰，不需要增加指針來表示元素之間的邏輯關(guān)系，所以存儲密度為1，而鏈表的存儲密度總是小于1。答案為B。74.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。75.14.一棵高度為h（h≥1）的完全二叉樹至少有（）個結(jié)點。A、2h-1B、2hC、2h+1D、2h-1+1【正確答案】：A76.45.以下（）方法在數(shù)據(jù)基本有序時效率最好。A、快速排序B、冒泡排序C、堆排序D、希爾排序【正確答案】：B77.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)。而順序存取是一種讀寫方式，不是存儲方式，有別于順序存儲。78.30.按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。A、3B、4C、5D、6【正確答案】：C79.19.數(shù)據(jù)結(jié)構(gòu)通常采用二元組表示：B=(D,R)，其中R表示（）的集合。A、數(shù)據(jù)項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)系，每個關(guān)系用序偶來表示。80.26.一個無向連通圖的生成樹是含有該連通圖的全部頂點的（）。A、極小連通子圖B、極小子圖C、極大連通子圖D、極大子圖【正確答案】：A81.10.由權(quán)值分別為9、2、7、5的4個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為_()。A、23B、44C、37D、27【正確答案】：B82.27.n個頂點的連通圖的生成樹有（）個頂點。A、n-1B、nC、n+1D、不確定【正確答案】：B83.18.高度為h（h>0）的滿二叉樹對應(yīng)的森林由（）棵樹構(gòu)成。A、1B、loC、2hD、h/2E、h【正確答案】：D84.25，25，49（最終狀態(tài)）可以斷定，所采用的排序方法是（）排序。A、直接插入B、冒泡C、二路歸并D、簡單選擇【正確答案】：D解析：

共有6個元素，即使有序也不結(jié)束，從排序過程可以斷定是簡單選擇排序。85.前一位置，r指向隊尾元素），元素x出隊的操作是（）;x=qu.data[qu.f]。A、qu.r+=1B、qu.r=(qu.r+1)%NC、qu.f+=1D、qu.f=(qu.f+1)%N【正確答案】：D解析：

這里f指向隊首元素的前一位置，r指向隊尾元素，所以出隊操作先循環(huán)移動f?！菊_答案】：為D。86.20.一個含有n（n>0）個頂點的連通圖采用鄰接矩陣存儲，則該矩陣一定是（）。A、對稱矩陣B、非對稱矩陣C、稀疏矩陣D、稠密矩陣【正確答案】：A解析：

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

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

裝填因子等于表中填入的元素個數(shù)n除以哈希表的長度m?！菊_答案】：為D。89.拓撲序列中，若頂點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。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、每個元素都有一個前趨和一個后繼元素B、線性表中至少有一個元素C、表中元素的排序順序必須是由小到大或由大到小D、除第一個元素和最后一個元素外，其余每個元素有且僅有一個前趨和一個后繼元素【正確答案】：D解析：

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

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

冒泡排序只需要做10趟就可以了，其他排序方法需要全部排序?！菊_答案】：為B。96.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。97.值為()。A、一定是2B、一定是1C、不可能是1D、以上都不對【正確答案】：C解析：

若出棧序列中p1=3，說明1、2先進棧，次棧頂為2，此時可以出棧2（p2=2），或者4進棧再出棧（p2=4），或者4、5進棧再出棧5（p2=5），…，總之p2可能是除了1外的其他整數(shù)?！菊_答案】：為C。98.42.冒泡排序最少元素移動的次數(shù)是（）。A、1B、nC、3n(n-1)/2【正確答案】：A99.16.以下排序方法中，()在初始序列已基本有序的情況下，排序效率最高。A、二路歸并排序B、快速排序C、直接插入排序D、堆排序【正確答案】：C解析：

二路歸并排序和堆排序的效率用初始序列分布無關(guān)，而在初始序列已基本有序的情況下快速排序的效率最差?！菊_答案】：為C。100.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。1.12.n（n>2）個結(jié)點的二叉樹中至少有一個度為2的結(jié)點。A、正確B、錯誤【正確答案】：B2.6.置換-選擇排序算法的作用是由一個無序文件生成若干個有序的子文件。A、正確B、錯誤【正確答案】：A3.18.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。A、正確B、錯誤【正確答案】：B解析：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有些內(nèi)排序方法也適合數(shù)據(jù)采用鏈表方式存儲的情況。26.4.在隊空間大小為n的循環(huán)隊列中，最多只能進行n次進隊操作。A、正確B、錯誤【正確答案】：B解析：

在循環(huán)隊列中，元素出隊后，其位置空了出來，可以讓其他元素進隊，所以理論上講可以進隊任意次。27.徑。A、正確B、錯誤【正確答案】：A解析：

如果頂點j到頂點k有路徑，則頂點i有一條通過頂點j到達頂點k的路徑，與題中條件矛盾。28.29.冒泡排序在最好情況下元素移動的次數(shù)為0。A、正確B、錯誤【正確答案】：A解析：

冒泡排序在初始數(shù)據(jù)正序時元素移動的次數(shù)為0。91、30.冒泡排序中，關(guān)鍵字比較的次數(shù)與初始數(shù)據(jù)序列有關(guān)，而元素移動的次數(shù)與初始數(shù)據(jù)序列無29.27.簡單選擇排序在初始數(shù)據(jù)正序時，其時間復(fù)雜度為O(n)。A、正確B、錯誤【正確答案】：B30.23.從時間性能看，堆排序總是優(yōu)于簡單選擇排序。A、正確B、錯誤【正確答案】：A解析：

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

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

敗者樹的主要作用是加速從k個記錄中選取最小記錄，并不能減少歸并的趟數(shù)。35.2.數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。A、正確B、錯誤【正確答案】：B解析：

數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)無關(guān)。36.44.所有內(nèi)排序算法中的比較次數(shù)與初始元素序列的排列無關(guān)。A、正確B、錯誤【正確答案】：B37.6.線性表的長度是線性表占用的存儲空間的大小。A、正確B、錯誤【正確答案】：B解析：

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

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

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

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

對于二叉排序樹，左子樹上所有結(jié)點的關(guān)鍵字均小于根記錄的關(guān)鍵字；右子樹上所有結(jié)點的關(guān)鍵字均大于根記錄的關(guān)鍵字。而不是僅僅與左、右孩子的關(guān)鍵字進行比較。48.6.隊列是一種對進隊、出隊操作的次數(shù)做了限制的線性表。A、正確B、錯誤【正確答案】：B解析：

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次數(shù)。49.15.棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，它們的數(shù)據(jù)元素的邏輯關(guān)系也不同。A、正確B、錯誤【正確答案】：B解析：

棧和線性表是兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們的數(shù)據(jù)元素的邏輯關(guān)系都是線性關(guān)系。50.7.在二叉排序樹中，每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小。A、正確B、錯誤【正確答案】：A51.徑。A、正確B、錯誤【正確答案】：A解析：

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

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

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

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

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

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

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

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

內(nèi)排序采用直接插入排序時，可以產(chǎn)生375000/600=625個初始歸并段，5路平衡歸并排序的趟數(shù)=log5625=4。所以需做4趟歸并排序。66.37.基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用以字符串為關(guān)鍵字的情況。A、正確B、錯誤【正確答案】：B67.5.隊列是一種對進隊、出隊操作的次序做了限制的線性表。A、正確B、錯誤【正確答案】：B解析：

只要隊列不滿就可以進行進隊操作，只要隊列不空就可以進行出隊操作，并不規(guī)定進隊列、出隊列操作的次序。68.11.有n個不同的元素通過一個棧，產(chǎn)生的所有出棧序列恰好構(gòu)成這n個元素的全排列。A、正確B、錯誤【正確答案】：B69.8.哈夫曼樹中結(jié)點個數(shù)可以偶數(shù)也可以是奇數(shù)。A、正確B、錯誤【正確答案】：B70.12.相同的n個元素的不同序列通過一個棧一定不會得到相同的出棧序列。A、正確B、錯誤【正確答案】：B解析：

相同的n個元素的不同序列通過一個棧可能會得到相同的出棧序列。例如，進棧序列1、2、3和71.17.棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)是任意的。A、正確B、錯誤【正確答案】：B解析：

棧具有先進后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)一定是線性結(jié)構(gòu)，不能是樹形結(jié)構(gòu)或圖形結(jié)構(gòu)。72.2.順序查找方法只能從順序表的前端向后端查找。A、正確B、錯誤【正確答案】：B解析：

順序查找方法可以從順序表的前端向后端查找，也可以從順序表的后端向前端查找。73.3.在隊空間大小為n的非循環(huán)隊列中，最多只能進行n次進隊操作。A、正確B、錯誤【正確答案】：A解析：

在非循環(huán)隊列，元素進隊時隊尾指針遞增，當(dāng)?shù)竭_最大下標(biāo)時不能再進隊，所以總計只能進隊n次。74.個比較的方法選取最小記錄，則總共需要396次關(guān)鍵字比較。A、正確B、錯誤【正確答案】：A解析：

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

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

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

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

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

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

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

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

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