孫夫雄數(shù)據(jù)結(jié)構(gòu)習題

1、數(shù)據(jù)結(jié)構(gòu)習題一、 單選題1. 研究數(shù)據(jù)結(jié)構(gòu)就是研究 A) 數(shù)據(jù)的邏輯結(jié)構(gòu)B) 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C) 數(shù)據(jù)的存儲結(jié)構(gòu)D) 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)2. 下面關(guān)于算法的說法，錯誤的是 。 A) 算法最終必須由計算機程序?qū)崿F(xiàn)B) 為解決某問題的算法與為該問題編寫的程序含義是相同的程序=算法+數(shù)據(jù)結(jié)構(gòu)C) 算法的可行性（確定性）是指指令不能有二義性D) 以上幾個都是錯誤的3. 計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備 5個特性輸入、輸出 、 。A) 可執(zhí)行性、可移植性和可擴充性B) 可執(zhí)行性、有窮性和確定性C) 確定性、有窮性和穩(wěn)定性D) 易讀性、穩(wěn)定

2、性和確定性4. 以下屬于邏輯結(jié)構(gòu)的概念是 。A) 順序表B) 哈希表C) 有序表 D) 單鏈表5. 具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是 。A) 圖B) 樹 C) 廣義表D) 棧6. 數(shù)據(jù)的存儲結(jié)構(gòu)包括順序、鏈接、散列和 種基本類型。A) 向量B) 數(shù)組C) 集合D) 索引7. 根椐數(shù)據(jù)元素之間關(guān)系的不同特性，以下4類基本邏輯結(jié)構(gòu)反映了4類基本數(shù)據(jù)組織形式。下列解釋錯誤的是 。A) 集合中任何兩個結(jié)點之間都有邏輯關(guān)系，但組織形式松散B) 線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次存儲成一行C) 樹型結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹D) 圖狀結(jié)構(gòu)中各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接8. 在

3、數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 。A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)9. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的 。A) 存儲結(jié)構(gòu)B) 存儲實現(xiàn)C) 邏輯結(jié)構(gòu)D) 運算實現(xiàn)10. 以下說法錯誤的是 。A) 程序設(shè)計的實質(zhì)是算法設(shè)計B) 數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式，基本運算規(guī)定了數(shù)據(jù)的基本操作方式C) 運算實現(xiàn)是完成運算功能的算法或這些算法的設(shè)計D) 算法設(shè)計思想總是與數(shù)據(jù)的某種相應存儲形式相聯(lián)系11. 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用 存儲方式最節(jié)省運算

4、時間。 A) 單鏈表B) 僅有頭指針的單循環(huán)鏈表C) 雙鏈表D) 僅有尾指針的單循環(huán)鏈表12. 單鏈表的主要優(yōu)點是 。A) 便于隨機查詢B) 存儲密度高C) 邏輯上相鄰的元素在物理上也是相鄰的D) 插入和刪除比較方便13. 線性表采用鏈式存儲時，其地址 。A) 必須連續(xù)B) 一定不連續(xù) C) 部分連續(xù)D) 連續(xù)與否均可14. 對于一個線性表，既要求能夠較快地進行插入和刪除，又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應該 。A) 以順序方式存儲B) 以鏈接方式存儲C) 以散列方式存儲D) 以上均可15. 若線性表中最常用的操作是取第i個的前趨元素，采用 存儲方式最節(jié)省時間。A) 順序表B)

5、 單鏈表C) 雙鏈表D) 單循環(huán)鏈表16. 若用單鏈表來表示隊列，則應該選用 。 A) 帶尾指針的非循環(huán)鏈表B) 帶尾指針的循環(huán)鏈表C) 帶頭指針的非循環(huán)鏈表D) 帶頭指針的循環(huán)鏈表17. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當rear和front的值分別為0和3。從隊列中出隊一個元素，再進隊兩個元素后，rear和front的值分別為 A) 1和5B) 2和4C) 4和2D) 5和118. 設(shè)棧的輸入序列是(1、2、3，4)，則 不可能輸出的序列。A) 1243B) 2134C) 1432D) 431219. 一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是 。A) 23

6、415B) 54132C) 23145D) 1543220. 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應該是 。A) 6 B) 4 C) 3D) 221. 一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞增歸算法應該設(shè)置 。A) 堆棧B) 隊列C) 堆?；蜿犃蠨) 數(shù)組22. 設(shè)棧的輸入序列是1、2、n，若輸出序列的第一個元素是n，則第i個輸出元素 。A) 不確定B) n-i+lC) cD) n-i23. 假定一個順序循環(huán)隊列的隊首和隊尾指針分別用front和r

7、ear表示，則判隊空的條件是 。A) front+1=rearB) front=rear+1C) front=OD) front=rear24. 假定一個順序循環(huán)隊列存儲于數(shù)組an中，其隊首和隊尾指針分別用front和rear表示，則判斷隊滿的條件是 。A) (rear-1)n=frontB) rear=(front-1)nC) (rear+1)n=frontD) rear=(front+1)n25. 采用 數(shù)據(jù)結(jié)構(gòu)設(shè)計一個判別表達式中左、右括號是否配的算法最佳。A) 線性表的順序存儲結(jié)構(gòu)B) 隊列C) 線性表的鏈式存儲結(jié)構(gòu)D) 棧26. 在下列算法描述中，涉及到隊運算的算法是 。A) 表達式

8、求值算法B) 深度優(yōu)先搜索C) 二叉樹前中后序遍歷D) 廣度優(yōu)先搜索27. 當利用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為 。A) N-2B) N-1C) ND) N+l28. 鏈棧與順序棧相比有一個明顯的優(yōu)點，即 。A) 插入操作更加方便B) 通常不會出現(xiàn)棧滿的情況C) 不會出現(xiàn)棧空的情況D) 刪除操作更加方便29. 一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足 。A) 所有的結(jié)點均無左孩子B) 所有的結(jié)點均無右孩子C) 只有一個葉子結(jié)點D) 是任意一棵二叉樹30. 一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是 。A) 250B) 500C)

9、 505 D) 50131. 以下說法正確的是 。A) 若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點，則它必是該子樹后序遍歷序列中的最后一個結(jié)點B) 若一個樹葉是某二叉樹前序遍歷序列中的最后一個結(jié)點，則它必是該子樹中序遍歷序列中的最后一個結(jié)點C) 在二叉樹中，具有兩個子女的父結(jié)點，在中序遍歷序列中，它的后繼結(jié)點最多只能有一個子女結(jié)點D) 在二叉樹中，具有一個子女的父結(jié)點，在中序遍歷序列中，它沒有后繼子女結(jié)點32. 以下說法錯誤的是 。A) 哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近B) 若一個二叉樹的樹葉是某子樹中序遍歷序列中的第一個結(jié)點，則它必是該子樹后序遍歷序列中的第

10、一個結(jié)點C) 己知二叉樹的前序遍歷和后序遍歷并不能惟一地確定這棵樹，因為不知道樹的根結(jié)點是哪一個D) 在前序遍歷二叉樹的序列中，任何結(jié)點其子樹的所有結(jié)點都是直接跟在該結(jié)點之后的33. 二叉樹在線索化后，仍不能有效求解的問題是 。A) 前序線索二叉樹中求前序后繼B) 中序線索二叉樹中求中序后繼C) 中序線索二叉樹中求中序前趨D) 后序線索二叉樹中求后序后繼34. 若二叉樹采用鏈式存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用 遍歷方法最合適。A) 前序B) 中序C) 后序D) 層次35. 一棵有124個葉結(jié)點的完全叉樹，最多有 個結(jié)點。A) 247B) 248C) 249D) 25036.

11、 設(shè)a、b為一棵二叉樹上的兩個結(jié)點。在中序遍歷時，a在b前面的條件是 A) a在b的右方B) a在b的左方C) a是b的祖先D) a是b的子孫37. 在一棵具有n個結(jié)點的完全二叉樹中，分枝結(jié)點的最大編號為 。A) (n+1)2)下限取整B) (n-1)2) 下限取整C) (n2) 下限取整D) (n2) 上限取整38. 在N個結(jié)點的線索二叉樹中，線索的數(shù)目為 。A) N-1B) NC) N+1D) 2N39. 設(shè)深度為K的二叉樹上只有度為0和2的結(jié)點，則這類二叉樹上所含的結(jié)點總數(shù)至少為 。A) K+1B) 2KC) 2K-1D) 2K+140. 設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼

12、樹共有 個結(jié)點。A) 13B) 12C) 26D) 2541. 以下說法錯誤的是 。A) 存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相同B) 二叉樹是樹的特殊情形C) 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的D) 在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹42. 若二叉樹是 則從二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序。A) 二叉排序樹B) 哈夫曼樹C) 堆D) 退化二叉樹43. 一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右的順序存儲在一維數(shù)組A1n)中，則二叉樹中第i個結(jié)點(i從1開始用上述方法編號)的右孩子在數(shù)組A中的位置

13、是 。 A) A2i (2inB) A2i+1) (2i+1n)C) Ai/2D) 條件不充分，無法確定44. 將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是 。A) 4B) 5C) 6D) 745. 下列有關(guān)二叉樹的說法正確的是 。A) 二叉樹的度為2B) 一棵二叉樹度可以小于2C) 二叉樹中至少有一個結(jié)點的度為2D) 二叉樹中任一個結(jié)點的度都為246. 某二叉樹中序序列為ABCDEFG，后序序列為BDCAFGE，則前序序列是 。，A) EGFACDBB) EACBDGFC) EAGCFBDD) 上面的都不對47. 對二叉排序樹進行 遍歷，可以得到該二叉樹所有結(jié)點構(gòu)

14、成的排序序列A) 前序B) 中序C) 后序D) 按層次48. 的遍歷仍需要棧的支持。A) 前序線索樹B) 中序線索樹C) 后序線索樹D) 層次遍歷49. 在一棵深度為h的完全二叉樹中，所含結(jié)點的個數(shù)不小于 。A) 2hB) 2h+1C) 2h-1D) 2h-150. 在一棵具有n個結(jié)點的二叉樹第i層上，最多具有 個結(jié)點。A) 2iB) 2i+1C) 2i-1D) 2n51. 樹最適合用來表示 。A) 有序數(shù)據(jù)元素B) 無序數(shù)據(jù)元素C) 元素之間具有分支層次關(guān)系的數(shù)據(jù)D) 元素之間無聯(lián)系的數(shù)據(jù)52. 以下說法錯誤的是 。A) 一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近B) 哈大曼樹中沒有度數(shù)為

15、1的分支結(jié)點C) 若初始森林中共有n棵二叉樹，最終求得的哈夫曼樹中共有2n-1個結(jié)點D) 若初始森林中共有n棵二叉樹，進行2n-1次合并后才能剩下最終的哈夫曼樹53. 以下說法錯誤的是 。A) 二叉樹可以是空集B) 二叉樹的任一結(jié)點都可以有兩棵子樹C) 二叉樹與樹具有相同的樹形結(jié)構(gòu)D) 二叉樹中任一結(jié)點的兩棵子樹有次序之分54. 某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是 的二叉樹。A) 空或只有一個結(jié)點B) 任一結(jié)點無左子樹C) 高度等于其結(jié)點數(shù)D) 任一結(jié)點無右子樹55. 設(shè)無向圖的頂點個數(shù)為n，則該無向圖最多有 條邊。A) n-1B) n(n-1)/2C) n(n+1)/2D

16、) 0E) n256. 采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的 。A) 中序遍歷B) 先序遍歷C) 后序遍歷D) 按層次遍歷57. 采用鄰接表存儲的圖，其廣度優(yōu)先遍歷類似于二叉樹的 。A) 按層次遍歷B) 中序遍歷C) 后序遍歷D) 先序遍歷 ，58. 一個圖中包含有七個連通分量，若按深度優(yōu)先(DFS)遍歷,必須調(diào)用 次深度優(yōu)先遍歷算法。A) kB) 1C) k-1D) k+159. 下列說法中不正確的是 A) 無向圖中的極大連通子圖稱為連通分量B) 連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C) 圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點D) 有向圖的遍歷不可

17、采用廣度優(yōu)先搜索方法 60. 具有n個頂點的有向圖最多有 條邊。A) nB) n(n-1)C) n(n+1)D) n261. 在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情況下不可能出現(xiàn)的是 。A) G中有弧B) G中有一條從Vi到Vj的路徑C) G中沒有弧 D) G中有一條從Vj到Vi的路徑62. 一個n個頂點的連通無向圖，其邊的個數(shù)至少為 。A) n-1B) n C) n+lD) nlog2n63. 下列說法中，正確的有 。A) 最小生成樹也是哈夫曼樹。B) 最小生成樹惟一C) 普里姆(Prim)最小生成樹算法時間復雜度為O(n2)D) 克魯斯卡爾(Kruskal)最小生成樹算

18、法比普里姆算法更適合于邊稠密的網(wǎng)64. 判定一個有向圖是否存在回路，除了可以利用拓撲排序的方法外，還可以利用 。A) 求關(guān)鍵路徑的方法B) 求最短路徑的Dijkstra方法C) 深度優(yōu)先遍歷算法D) 廣度優(yōu)先遍歷算法65. 在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為 。A) sB) s-1C) s+lD) n66. 在一個無向圖中，若兩個頂點之間的路徑長度為k條邊，則該路徑上的頂點數(shù)為 。A) kB) k+lC) k+2D) 2k67. 一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為 。A) 0B) 1C) nD) n+168. 對于一個有向圖，若一個

19、頂點的入度為k1、出度為k2，則對應鄰接表中該頂點單鏈表中的結(jié)點數(shù)為 。A) klB) k2C) k1-k2D) k1+k269. 對于一個有向圖，若一個頂點的入度為k1、出度為k2，則對應逆鄰接表中該頂點單鏈表中的結(jié)點數(shù)為 。A) klB) k2C) k1-k2D) k1+k270. 對于一個無向圖，下面 的說法是正確的。A) 每個頂點的入度等于出度B) 每個頂點的度等于其入度與出度之和C) 每個頂點的入度為0 D) 每個頂點的出度為071. 為了方便地對圖狀結(jié)構(gòu)的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結(jié)構(gòu)宜采用 。A) 順序存儲B) 鏈式存儲C) 索引存儲D) 散列存儲72. 設(shè)有一個按各元素的

20、值排好序的線性表且長度大于2，對給定的值X，分別用順序查找法和二分查找法查找一個與K相等的元素，比較次數(shù)分別是s和b：在查找不成功的情況下，正確的s和b的數(shù)量關(guān)系是 。A) 總有s=bB) 總有sbC) 總有sbD) 與K值大小有關(guān)73. 若在線性表中采用折半查找法查找元素，該線性表應該 。A) 元素按值有序B) 采用順序存儲結(jié)構(gòu)C) 元素按值有序，且采用順序存儲結(jié)構(gòu)D) 元素按值有序，且采用鏈式存儲結(jié)構(gòu)74. 假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進行 次探測。A) k-1次B) k次C) k+1次D) k(k+1)2次75. 設(shè)散列地址空間0m-1，k

21、為關(guān)鍵字，用p去除k，將余數(shù)作為k的散列地址 (h(k)=k%p)，為了減少發(fā)生沖突的可能性，一般取P為 。A) 小于m的最大奇數(shù)B) 小于m的最大素數(shù)C) 小于m的最大偶數(shù)D) 小于m的最大合數(shù)76. 設(shè)散列表的長m=14，散列函數(shù)為h(k)=k%11，表中已有4個記錄(如圖所示)如果用二次探測再散列來處理沖突，則關(guān)鍵字為49的記錄其存儲地址是 。0 1 2 3 4 5 6 7 8 9 10 11 12 1315386184 圖 散列表A) 8B) 3C) 5D) 977. 從具有n個結(jié)點的二叉排序樹中查找一個元素時，最壞情況下的時間復雜性 。A) O(n)B) O(1)C) O(log2n

22、)D) O(n2)78. 下面關(guān)于二叉排序樹論述中，錯誤的是 。A) 當所有結(jié)點的權(quán)值都相等時，用這些結(jié)點構(gòu)造的二叉排序樹除根結(jié)點外只有右子樹B) 中序遍歷二叉排序樹的結(jié)點就可以得到排好序的結(jié)點序列C) 任一二叉排序樹的平均查找時間都小于用順序查找法查找同樣結(jié)點的線性表的平均查找時間D) 對兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹，按中序遍歷得到的序列是一樣的79. 以下說法錯誤的是 。A) 散列法存儲的基本思想是由關(guān)鍵碼值決定數(shù)據(jù)的存儲地址B) 散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C) 裝填因子是散列法的一個重要參數(shù)，它反映了散列表的裝填程度D) 散列表的查找效率主要取

23、決于散列表造表時選取的散列函數(shù)和處理沖突的方法80. 設(shè)有一個用線性探測法解決沖突得到的散列表如圖所示0 1 2 3 4 5 6 7 8 9 101325801617614 圖 散列表散列函數(shù)為H=11，若要查找元素14，探測的次數(shù)是 。A) 8B) 9C) 3D) 681. 如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，則可采用的查找方法是 。A) 分塊查找B) 順序查找C) 折半查找D) 基于屬性查找82. 有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應選擇下面哪個序列輸入 。A) 45,24,53，12,37,

24、96,30B) 37,24,12,30,53,45,96C) 12,24,30,37,45,53,96D) 30,24,12,37,45,96,5383. 建立序列50，72，43，85，75，20，35，45，65，30對應的二叉排序樹以后，查找元素35要進行 元素間的比較A) 4次B) 5次C) 7次D) 10次84. 在順序表(n足夠大)中進行順序查找，其查找不成功的平均長度是 。A) (n+1)2B) n2+lC) n D) n+l85. 對線性表進行二分檢索時，要求線性表必須 。A) 以順序存儲方式存儲B) 以鏈式存儲方式存儲C) 以順序存儲方式存儲且數(shù)據(jù)有序D) 以鏈式存儲方式存儲

25、且數(shù)據(jù)有序86. 在一棵深度為h的具有n個元素的二叉排序樹中，查找所有元素的最長查找長度A) nB) log2nC) (h+1)2D) h87. 在散列查找中，平均查找長度主要與 有關(guān)。A) 散列表長度B) 散列元素個數(shù)C) 裝填因子D) 處理沖突方法88. 若根據(jù)查找表建立長度為m的散列表并采用二次探測處理沖突，假定對個元素第一次計算的散列地址為d，則第四次計算的散列地址為 。A) (d+1)mB) (d-1)mC) (d+4)mD) (d-4)m89. 以下說法正確的是 。A) 數(shù)字分析法需事先知道所有可能出現(xiàn)的鍵值及所有鍵值的每一位上各數(shù)字分布情況，并且鍵值的位數(shù)比散列地址的位數(shù)多B)

26、除余法要求事先知道全部鍵值C) 平方取中法需要事先掌握鍵值的分布情況D) 隨機數(shù)法適用于鍵值不相等的場合90. 分塊查找的時間效率 。A) 低于二分查找B) 高于順序查找而低于二分查找C) 高于順序查找D) 低于順序查找而高于二分查找91. 在一個具有n個結(jié)點的單鏈表中查找值為m的某結(jié)點，若查找成功，則平均比較 個結(jié)點。A) nB) n2C) (n-1)2D) (n+1)292. 以下序列不是堆的是 。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,7

27、7,80,82,85,98,100)D) (100,85,40,77,80,60,66,98,82,10,20,)93. 在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序方法是 A) 直接插入排序B) 冒泡排序C) 簡單選擇排序D) 歸并排序94. 在下列算法中， 算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A) 堆排序B) 冒泡排序C) 插入排序D) 快速排序95. 從未排序的序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在排序序列的合適位置，該排序方法稱為 排序法。 A) 插入 B) 選擇C) 希爾D) 二路歸并96. 下面給出的四種

28、排序法中， 排序是不穩(wěn)定排序法。A) 插入B) 冒泡C) 二路歸并D) 堆97. 快速排序在最壞情況下時間復雜度是O(n2)，比 的性能差。A) 堆排序B) 冒泡排序C) 選擇排序D) 二路歸并98. 對給出的一組關(guān)鍵字14，5，19，20，11，19。若按關(guān)鍵字非遞減排序，第一趟排序結(jié)果為14，5，19，20，11，19，問采用的排序算法是 。A) 簡單選擇排序B) 快速排序C) 希爾排序D) 二路歸并排序99. 就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是 。A) 堆排序快速排序歸并排序B) 堆排序歸并排序歸并排序快速排序D) 堆排序快速排序歸并排序E) 巳以上答案都不

29、對100. 假設(shè)某文件經(jīng)過內(nèi)部排序得到27個初始歸并段，若要使多路歸并3趟完成，則應取歸并的路數(shù)為 。A) 2B) 3C) 4D) 5101. 下面排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列無關(guān)的是 。A) 希爾(Shell)排序B) 冒泡排序C) 直接插入排序D) 直接選擇排序102. 對記錄的關(guān)鍵字集合key=50，26，38，80，70，90，8，30，40，20進行排序，各趟排序結(jié)束時的結(jié)果為：50 26 38 80 70 90 8 30 40 2050 8 30 40 20 90 26 38 80 7026 8 30 40 20 80 50 38 90 708 20 26 30 38

30、 40 50 70 80 90其使用的排序方法是 。A) 快速排序B) 基數(shù)排序C) 希爾排序D) 歸并排序103. 一組記錄的關(guān)鍵字為45，80，50，40，42，85則利用堆排序的方法建立的初始堆為 。A) 45 50 40 42 85B) 80 50 40 42 45C) 80 50 45 42 40D) 50 80 42 45，40， 104. 一組記錄的關(guān)鍵字為25，50，15，35，80，85，20，40，36，70，其中含有5個長度為2的有序表，用歸并排序方法對該序列進行一趟歸并后的結(jié)果為 。A) 15，25，35，50，20，40，80，85，36，70B) 15，25，35，

31、50，80，20，85，40，70，36C) 15，25；50，35，80，85，20，36，40，70D) 15，25，35，50，80，20，36，40，70，85105. 在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜性為 。A) O(1) B) O(Log2n)C) O(n2) D) O(n)106. 在對n個元素進行快速排序的過程中，第一次劃分最多需要移動 次元素(包括開始將基準元素移到臨時變量的那一次)。A) n2 B) n-1C) nD) n+1107. 下述幾種排序方法中，要求內(nèi)存量最大的是 。A) 插入排序B) 選擇排序C) 快速排序D) 歸并排序108. 下面排序方

32、法中，時間復雜性不是O(n2)的是 。A) 直接插入排序B) 二路歸并排序C) 冒泡排序D) 直接選擇排序109. 一個序列中有10000個元素，若只想得到其中前10個最小元素，最好采用 法。A) 快速排序B) 堆排序C) 插入排序D) 二路歸并排序110. 對下列4個序列用快速排序方法進行排序，以序列的第1個元素為基準進行劃分。在第1趟劃分過程中，元素移動次數(shù)最多的是序列 。 A) 70，75，82，90，23，16，10，68 B) 70，75，68，23，10，16，90，82C) 82，75，70，16，10，90，68，23 D) 23，10，16，70，82，75，68，90111

33、. 在對n個元素的序列進行排序時，堆排序所需要的附加存儲空間是 。A) O(log2n)B) O(1)C) O(n)D) O(nlog2n)112. 對下列4種排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是 。A) 直接插入B) 二分法插入C) 快速排序D) 歸并排序113. 采用簡單選擇排序，比較次數(shù)與移動次數(shù)分別是 。A) O(n)，O(log2n)B) O(log2n)，O(n2)C) O(n2)，O(n)D) O(nlog2n)，O(n)114. 歸并排序中，歸并的趟數(shù)是 。 A) O(n)B) O(log2n)C) O(nlog2n)D) O(n2)115. 在待排序的元素序

34、列基本有序的前提下，效率最高的排序方法是 。A) 插入排序B) 選擇排序C) 快速排序D) 歸并排序116. 直接插入排序在最好情況下的時間復雜度為 。A) O(log2n)B) O(n)C) O(nlog2n)D) O(n2)117. 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 。A) nB) 2n-1C) 2nD) n-1118. 下列排序算法中，穩(wěn)定的排序算法是 。A) 堆排序B) 快速排序C) 基數(shù)排序D) 希爾排序119. 就平均性能而言，目前最好的內(nèi)排序方法是 排序法。A) 冒泡B) 希爾插入C) 交換D) 快速120. 快速排序 在情況下不利于發(fā)揮其長處。A)

35、 待排序數(shù)據(jù)量太大B) 待排序數(shù)據(jù)相同值過C) 待排序數(shù)據(jù)已基本有序D) 待排序數(shù)據(jù)值差過大121. 在對n個元素進行直接選擇排序過程中，第i趟需從 個元素中選擇出最小元素。A) n-i+lB) n-iC) iD) i+1122. 若對n個元素進行直接選擇排序,是進行任一趟排序的過程中，為尋找最小值元素所需要的時間復雜性為 。A) O(1)B) O(log2n)C) O(n2)D) O(n)123. 在下列排序方法中，空間復雜性為O(log2n)的方法是 。A) 直接選擇排序B) 歸并排序C) 堆排序D) 快速排序124. 從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，

36、將其放入已排序序列的正確位置上的方法，稱為 。A) 希爾排序B) 冒泡排序C) 插入排序D) 選擇排序125. 從未排序序列中挑選元素，并將其依次放入已排序序列(初始時為空)一端的方法稱為 。A) 希爾排序B) 歸并排序C) 插入排序D) 選擇排序126. 用ISAM和VSAM組織文件屬于 。A) 順序文件B) 索引文件C) 散列文件127. 索引順序文件是 。A) HASH文件B) ISAM文件C) 順序文件D) 索引文件128. 刪除ISAM文件記錄時，一般 。A) 只需做刪除標志B) 需移動記錄C) 需改變指針D) 一旦刪除就要做整理129. 直接存取方法是利用 進行組織的文件。A) H

37、ASH法 B) 順序索引法C) VSAM法D) ISAM法130. 倒排文件的主要優(yōu)點是 。A) 便于進行插入和刪除運算B) 便于節(jié)省存儲空間C) 便于進行文件合并D) 能大大提高基于非關(guān)鍵字的檢索速度131. 散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為散列函數(shù)是一對一的關(guān)系，所以選擇好的 方法是散列文件(Hash)的關(guān)鍵。A) 散列函數(shù)B) 除余法中的質(zhì)數(shù)C) 沖突處理D) 散列函數(shù)和沖突處理132. 倒排文件包含有若干個倒排表，倒排表的內(nèi)容是 ，倒排文件檢查速度快但修改、維護較難。A) 一個關(guān)鍵字值和該關(guān)鍵字的記錄地址B) 一個屬性值和該屬性的一個記錄地址C) 一個

38、屬性值和該屬性的全部記錄地址D) 承多個關(guān)鍵字值和它們相對應的某個記錄地址133. 影響文件檢索效率的一個重要因素是 。A) 邏輯記錄的大小B) 物理記錄的大小C) 訪問外存的次數(shù)D) 設(shè)備的讀寫速度134. 順序文件適于 。A) 直接存取B) 成批處理C) 按關(guān)鍵字存取D) 隨機存取135. 對散列文件，以下說法錯誤的是 。A) 散列文件插入、刪除方便，不需要索引區(qū)且節(jié)省存儲空間B) 散列文件只能按關(guān)鍵字隨機存取且存取速度快C) 經(jīng)過多次插入、刪除后，可能出現(xiàn)溢出桶滿而基桶內(nèi)多數(shù)記錄已被刪除的情況D) 散列文件順序存取方便136. 對于一個索引順序文件，索引表中的每個索引項對應主文件中的 。

39、A) 一條記錄B) 多條記錄C) 所有記錄D) 三條以下記錄137. 對于索引文件，稠密索引中的每個索引項對應被索引表中的 。A) 所有記錄B) n條以下記錄C) 一條記錄D) 多條記錄138. VSAM文件的索引集是一個 。A) 二叉排序樹結(jié)構(gòu)B) 散列表結(jié)構(gòu)C) 線性表結(jié)構(gòu)D) B+樹結(jié)構(gòu)139. 散列文件又稱按桶散列文件，若散列文件中含有m個基桶，每個桶能夠存儲m個記錄，若不使用溢出桶，則該散列文件最多能夠存儲 個記錄。A) m+kB) mk-1C) mk+lD) mk140. 對文件進行直接存取的依據(jù)是 。A) 按邏輯記錄號去存取某個記錄B) 按邏輯記錄的結(jié)構(gòu)去存取某個記錄C) 按邏輯

40、記錄的關(guān)鍵字去存取某個記錄D) 按邏輯記錄的具體內(nèi)容去存取某個記錄141. 直接存取文件的特點是 。A) 記錄按關(guān)鍵字排序B) 記錄可以進行順序存取C) 存取速度快但占用較多的存儲空間D) 記錄不需要排序且存取效率高142. 索引順序文件的記錄，在邏輯上按關(guān)鍵字的順序排列，但物理上不一定按關(guān)鍵字順序存儲，故需建立一張指示邏輯記錄和物理記錄之間一一對應關(guān)系的 。A) 索引表B) 鏈接表C) 符號表D) 交叉訪問表143. 以下說法錯誤的是 。A) 在磁帶上的順序文件的最后添加新的記錄時不必復制整個文件B) 索引順序文件既能順序訪問又能隨機訪問C) 變更磁盤上的順序文件記錄的內(nèi)容時，不一定要復制整

41、個文件D) 索引順序文件是一種特殊的順序文件，因此通常放在磁帶上二、 多項選擇題1. 數(shù)據(jù)元素是 。A) 數(shù)據(jù)集合中的一個個體B) 數(shù)據(jù)的基本單位C) 數(shù)據(jù)的最小單位D) 一個結(jié)點E) 一個記錄2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K，R)，其中K是 的有限集，R是K上的 有限集。A) 算法B) 數(shù)據(jù)元素C) 數(shù)據(jù)操作D) 邏輯結(jié)構(gòu)A) 操作B) 映像C) 存儲 D) 關(guān)系3. 線性表的說法錯誤的是 A) 每個元素都有一個直接前驅(qū)和一個直接后繼B) 線性表中至少要有一個元素C) 表中諸元素的排列順序必須是由小到大或由大到小D) 除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼

42、4. 以下說法錯誤的是 A) 順序存儲方式的優(yōu)點是存儲密度大且插入、刪除運算效率高B) 鏈表的每個結(jié)點中都恰好包含一個指針C) 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)D) 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)而鏈式結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)5. 以下說法正確的是 A) 對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后移操作掃描整個循環(huán)鏈表B) 對簡單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點C) 雙鏈表的特點是找結(jié)點的前趨和后繼都很容易D) 對雙鏈表中來說，結(jié)點中既存放其前趨結(jié)點指針，也存放后繼結(jié)點指針6. 以下說法正確的是 。A) 求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈式存儲結(jié)構(gòu)時實現(xiàn)的效

43、率低B) 順序存儲的線性表可以直接存取C) 由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D) 線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)7. 便于插入和刪除操作的是 A) 單鏈表B) 順序表C) 雙鏈表D) 循環(huán)鏈8. 從表中任一結(jié)點出發(fā)都能掃描整個鏈表的是 A) 單鏈表B) 順序表C) 雙鏈表D) 循環(huán)鏈表9. 雙向鏈表的主要優(yōu)點是 。A) 不再需要頭指針B) 已知某結(jié)點位置后能容易找到其直接前趨C) 在進行插入、刪除運算時能保證鏈表不斷開D) 從表中任一結(jié)點出發(fā)都能掃描整個鏈表10. 對順序表的優(yōu)缺點，以下說法正確的是 。A) 無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間B) 可以

44、方便地隨機取表中的任一結(jié)點C) 插入和刪除運算較為方便D) 由于要求占用連續(xù)空間，所以存儲分配只能預先進行(靜態(tài)分配)11. 循環(huán)隊列是 。A) 順序存儲結(jié)構(gòu)B) 不會產(chǎn)生下溢C) 不會產(chǎn)生假溢D) 不會產(chǎn)生上溢12. 以下說法正確的是 。A) 存在這樣的二叉樹，對它采用任何次序遍歷其結(jié)點訪問序列均相同B) 二叉樹是樹的特殊情形C) 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的D) 在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹13. 設(shè)高為h的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點樹至少為 ，至多為 。A) 2hB) 2h-1C) 2h+1D) h+1A) 2h-1B

45、) 2h-1C) 2h+1+1D) 2h+114. 對于前序遍歷與中序遍歷結(jié)果相同的 F 。前序遍歷與后序遍歷結(jié)果相同的二叉樹為 B 。A) 一般二叉樹B) 只有根結(jié)點的二叉樹C) 根結(jié)點無左孩子的二叉樹D) 根結(jié)點無右孩子的二叉樹E) 所有結(jié)點只有左子樹的二叉樹F) 所有結(jié)點只有右子樹的二叉樹15. 完全二叉樹 。A) 適合于用順序結(jié)構(gòu)存儲B) 葉子結(jié)點可在任一層出現(xiàn)C) 某些結(jié)點有左子樹則必有右子樹D) 某些結(jié)點有右子樹則必有左子樹16. 下列有關(guān)二叉樹的說法錯誤的是 。A) 二叉樹的度為2B) 一棵二叉樹度可以小于2C) 二叉樹中至少有一個結(jié)點的度為2D) 二叉樹中任一個結(jié)點的度都為21

46、7. 下面哪一個方法可以判斷出一個有向圖中是否有環(huán)(回路)。A) 深度優(yōu)先遍歷B) 拓撲排序C) 求最短路徑D) 求關(guān)鍵路徑18. 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表向量的大小為(1)，所有頂點的鄰接表的結(jié)點總數(shù)為(2)。 (1) A)n B)n+1 C)n-1 D)n+e (2) A)e2 B)e C)2e D)n+e19. 圖的應用算法有 。A) 克魯斯卡爾算法B) 哈夫曼算法C) 拓撲排序算法D) 迪杰斯特拉算法20. 對初始狀態(tài)為遞增序列的表按遞增序列排序，最省時間的是(1 C )算法，最費時間的是（2 B ）算法A) 堆排序B) 快速排序C) 插入排序D)

47、歸并排序21. 在下述排序算法中，所需輔助存儲量最多的是 (B)，所需輔助存儲量最少的是(C)，平均速度最快的是(A)A) 快速排序B) 歸并排序C) 堆排序22. 在堆排序過程中，由n個待排序的記錄建成初始堆需要(B)次篩選：由初始堆到排序結(jié)束需要進行(D)上次篩選運算；在每次篩選運算的過程中，記錄的比較和移動次數(shù)的數(shù)量級為(E)，堆排序算法的時間復雜度為(G)。A) nB) n2C) log2nD) n-1E) O(log2n)F) O(n)G) O(nlog2n)H) O(n2)23. 下面的排序算法中不穩(wěn)定的是 。A) 起泡排序B) 折半插入排序C) 簡單選擇排序D) 希爾排序E) 基

48、數(shù)排序F) 堆排序24. 穩(wěn)定的排序方法有 。A) 希爾排序法B) 歸并排序法C) 直接選擇法D) 直接插入法E) 冒泡排序法25. 下列那些排序算法的時間復雜度是O(n2)的有 。A) 冒泡法B) 歸并法C) 堆排序D) 直接插入E) 直接選擇26. 在排序算法中實施過程中，使用輔助存儲空間為O(1)的有 。A) 直接插入排序法B) 快速排序遞歸算法C) 歸并排序法D) 堆排序法27. 如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的， 就是不穩(wěn)定的排序算法。 A) 起泡排序B) 歸并排序C) Shell排序D) 直接插入排序E) 簡單選擇

49、排序28. 堆排序是(E)類排序，堆排序平均執(zhí)行的時間復雜度和需要附加的存儲空間復雜度分別是(G)。A) 插入B) 交換C) 歸并D) 基數(shù)E) 選擇F) 0(n2)和O(1)G) O(nlog2n)和O(1)H) O(nlog2n)和O(n)I) O(n2)和O(n)29. 直接插入排序和冒泡排序的時間復雜度為(D)，若初始數(shù)據(jù)有序(即正序)，則時間復雜度為(A)。A) O(n)B) O(log2n)C) O(nlog2n)D) O(n2)30. 在直接選擇排序中，記錄比較次數(shù)為(C)數(shù)量級，記錄的移動次數(shù)為(A)數(shù)量級。A) O(n)B) O(log2nC) O(n2)D) O(nlog2n)31. 在平均情況下，快速排序的時間復雜度為(C)，空間復雜性為(B)，在最壞情況下(如初始記錄已有序)，快速排序的時間復雜度為(D)