數(shù)據(jù)結(jié)構(gòu)（本科）期末綜合練習(xí)一（單選題）

1、數(shù)據(jù)結(jié)構(gòu)（本科）期末綜合練習(xí)一（單選題）單選題 1. 一個(gè)數(shù)組元素ai 與( )的表示等價(jià)。 A. *(a+i) B. a+i C. *a+i D. &a+i 2. 若需要利用形參直接訪(fǎng)問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為( )參數(shù)。 A. 指針 B. 引用 C. 傳值 D. 常值 3. 下面程序段的時(shí)間復(fù)雜度為( )。 for(int i=0; im; i+) for(int j=0; jn; j+) aij = i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 4. 執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為( )。 for(int i=1; i=n; i+) for

2、(int j=1; jlink = NULL;C. first-link = first; D. first != NULL; 29. 帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（ ）。A. first=NULL; B. first-link=NULL;C. first-link=first; D. first!=NULL; 30. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link）。已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的操作是（ ）。 A. s-link=p-link; p-link=s; B. q-link=s; s-link=p; C. p-

3、link=s-link; s-link=p; D. p-link=s; s-link=q; 31. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link）。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的操作是（ ）。 A.s-link=p; p-link=s; B. p-link=s; s-link=p; C.s-link=p-link; p=s; D. s-link=p-link; p-link=s; 32. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link）。若想摘除p-link所指向的結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（ ）。 A. p-link=p-link-link; B. p=p-li

4、nk; p-link=p-link-link; C. p-link=p; D. p=p-link-link; 33. 非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿(mǎn)足的條件是（ ）。 A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first; 34. 設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link），且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個(gè)結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（ ）。 A.s = rear; rear = rear-link; delete s; B.rear = rear-link; delet

5、e rear; C.rear = rear-link-link; delete rear; D.s = rear-link-link; rear-link-link = s-link; delete s;35. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需要平均比較的結(jié)點(diǎn)數(shù)是（ ）。 A. n B. n/2 C. (n-1)/2 D. (n+1)/236. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是（ ）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n)37. 給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間

6、復(fù)雜度是（ ）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n)38.單鏈表A長(zhǎng)度為m，單鏈表B長(zhǎng)度為n，若將B聯(lián)接在A的末尾，其時(shí)間復(fù)雜度應(yīng)為（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n)39. 利用雙向鏈表作線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是（ ）。 A. 便于單向進(jìn)行插入和刪除的操作 B. 便于雙向進(jìn)行插入和刪除的操作 C. 節(jié)省空間 D. 便于銷(xiāo)毀結(jié)構(gòu)釋放空間40. 帶表頭的雙向循環(huán)鏈表的空表滿(mǎn)足（ ）。 A. firstNULL; B. first-rLink=first C. first-lLink=NULL D. first-rLi

7、nk=NULL41. 已知L是一個(gè)不帶表頭的單鏈表, 在表首插入結(jié)點(diǎn)*p的操作是（ ）。A. p = L; p-link = L; B. p-link = L; p = L; C. p-link = L; L = p; D. L = p; p-link = L;42. 已知L是帶表頭的單鏈表, 刪除首元結(jié)點(diǎn)的語(yǔ)句是（ ）。A. L = L-link; B. L-link = L-link-link; C. L = L; D. L-link = L;43. 棧的插入和刪除操作在( )進(jìn)行。 A. 棧頂 B. 棧底 C. 任意位置D. 指定位置44. 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用t

8、op=n表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行( )語(yǔ)句修改top指針。 A. top+; B. top-; C. top = 0; D. top;45. 若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)( )種情況。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,246. 在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的( )位置。 A. 前一個(gè) B. 后一個(gè) C. 當(dāng)前 D. 后面47. 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為( )。 A. n-2 B. n-1 C. n D. n+148. 從一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，首先

9、需要( )。 A. 隊(duì)頭指針加一B. 隊(duì)頭指針減一 C. 取出隊(duì)頭指針?biāo)傅脑谼. 取出隊(duì)尾指針?biāo)傅脑?9. 假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為( )。 A. front+1 = rearB. rear+1 = front C. front = 0D. front = rear50. 假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL51. 設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data

10、, link），且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈ｍ敳迦胍粋€(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行( )操作。 A. top-link=s;B. s-link=top-link; top-link=s; C. s-link=top; top=s; D. s-link=top; top=top-link;52. 設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data, link），且top是指向棧頂?shù)闹羔槨Ｈ粝胝準(zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行( )操作。 A. x=top-data; top=top-link; B. top=top-link; x=top-data; C. x=top; t

11、op=top-link; D. x=top-data;53. 設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是 typedef struct DataType dataMaxSize; int front, rear; Queue; 若有一個(gè)Queue類(lèi)型的隊(duì)列Q，試問(wèn)判斷隊(duì)列滿(mǎn)的條件應(yīng)為( ) 。 A. Q.front=Q.rear; B. Q.front-Q.rear=MaxSize; C. Q.front+Q.rear=MaxSize; D. Q.front=(Q.rear+1) % MaxSize;54. 設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是 const int MaxSize = 100; typedef int DataType

12、; typedef struct DataType dataMaxSize; int front, rear; Queue; 若有一個(gè)Queue類(lèi)型的隊(duì)列Q，則應(yīng)用( )表達(dá)式計(jì)算隊(duì)列元素的個(gè)數(shù)。 A. (Q.rear-Q.front+MaxSize) % MaxSize; B.Q.rear-Q.front+1; C. Q.rear-Q.front-1; D. Q.rear-Qfront;55. 為增加內(nèi)存空間的利用率和減少溢出的可能性, 由兩個(gè)棧共享一塊連續(xù)的內(nèi)存空間時(shí), 應(yīng)將兩棧的( )分別設(shè)在這塊內(nèi)存空間的兩端。 A. 長(zhǎng)度 B. 深度 C. 棧頂 D. 棧底56. 遞歸是將一個(gè)較復(fù)雜的

13、（規(guī)模較大的）問(wèn)題轉(zhuǎn)化為一個(gè)稍為簡(jiǎn)單的（規(guī)模較小的）與原問(wèn)題（ ）的問(wèn)題來(lái)解決，使之比原問(wèn)題更靠近可直接求解的條件。 A. 相關(guān)B. 子類(lèi)型相關(guān)C. 同類(lèi)型D. 不相關(guān)57. 遞歸調(diào)用時(shí)系統(tǒng)需要利用一個(gè)（ ）來(lái)實(shí)現(xiàn)數(shù)據(jù)的傳遞和控制的轉(zhuǎn)移。 A. 隊(duì)列B. 優(yōu)先級(jí)隊(duì)列C. 雙端隊(duì)列D. 棧58. 在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時(shí)需利用遞歸工作記錄保存（ ），當(dāng)遞歸調(diào)用程序執(zhí)行結(jié)束時(shí)通過(guò)它將控制轉(zhuǎn)到上層調(diào)用程序。 A. 調(diào)用地址B. 遞歸入口C. 返回地址D. 遞歸出口59. 在遞歸執(zhí)行過(guò)程中，當(dāng)前執(zhí)行的遞歸函數(shù)過(guò)程的遞歸工作記錄一定是遞歸工作棧中的棧頂記錄，稱(chēng)之為（ ）記錄。 A. 活動(dòng)B. 當(dāng)前C. 日志

14、D. 標(biāo)記60. 將遞歸求解過(guò)程改變?yōu)榉沁f歸求解過(guò)程的目的是（ ）。 A. 提高速度B. 改善可讀性C. 增強(qiáng)健壯性D. 提高可維護(hù)性61. 如果一個(gè)遞歸函數(shù)過(guò)程中只有一個(gè)遞歸語(yǔ)句，而且它是過(guò)程體的最后語(yǔ)句，則這種遞歸屬于（ ），它很容易被改寫(xiě)為非遞歸過(guò)程。 A. 單向遞歸B. 回溯遞歸C. 間接遞歸D. 尾遞歸62. 設(shè)有一個(gè)遞歸算法如下int fact ( int n ) /n大于等于0 if ( n = 0 ) return 1; else return n * fact (n-1); 則計(jì)算fact (n) 需要函數(shù)調(diào)用的次數(shù)為（ ）次。 An Bn+1 Cn+2 Dn-163. 設(shè)有

15、一個(gè)遞歸算法如下int X ( int n ) if ( n 0)的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為( )。 A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2-1 79. 在一棵樹(shù)的左子女-右兄弟表示法中，一個(gè)結(jié)點(diǎn)的右子女是該結(jié)點(diǎn)的( )結(jié)點(diǎn)。 A. 兄弟 B. 父子 C. 祖先 D. 子孫 80. 在一棵樹(shù)的靜態(tài)雙親表示中，每個(gè)存儲(chǔ)結(jié)點(diǎn)包含( )個(gè)域。 A 1 B 2 C 3 D 4 81. 已知一棵二叉樹(shù)的廣義表表示為a(b(c),d(e(,g(h),f)，則該二叉樹(shù)的高度為( )。假定樹(shù)根結(jié)點(diǎn)的高度為0。 A. 3 B. 4 C. 5 D. 6 82. 已知一棵樹(shù)的邊集表示

16、為, , , , , , , ，則該樹(shù)的深度為( )。假定樹(shù)根結(jié)點(diǎn)的高度為0。 A. 2 B. 3 C. 4 D. 5 83. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的霍夫曼樹(shù)中共包含有( )個(gè)結(jié)點(diǎn)。 A. n B. n+1 C. 2*n D. 2*n-1 84. 利用3,6,8,12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵霍夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為( )。 A 55 B 29 C 58 D 38 85. 一棵樹(shù)的廣義表表示為a(b,c(e,f(g),d)，當(dāng)用左子女-右兄弟鏈表表示時(shí)，右指針域非空的結(jié)點(diǎn)個(gè)數(shù)為( )。 A 1 B 2 C 3 D 4 86. 向具有n個(gè)結(jié)點(diǎn)的堆中插入一個(gè)新元素的時(shí)間復(fù)雜度

17、為( )。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n) 87. 若搜索每個(gè)元素的概率相等，則在長(zhǎng)度為n的順序表上搜索任一元素的平均搜索長(zhǎng)度為( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 88. 對(duì)長(zhǎng)度為10的順序表進(jìn)行搜索，若搜索前面5個(gè)元素的概率相同，均為1/8，搜索后面5個(gè)元素的概率相同，均為3/40，則搜索任一元素的平均搜索長(zhǎng)度為( )。 A. 5.5 B. 5 C. 39/8 D. 19/4 89. 對(duì)長(zhǎng)度為3的順序表進(jìn)行搜索，若搜索第一個(gè)元素的概率為1/2，搜索第二個(gè)元素的概率為1/3，搜索第三個(gè)元素的概率為1/6

18、，則搜索任一元素的平均搜索長(zhǎng)度為( )。 A. 5/3 B. 2 C. 7/3 D. 4/3 90. 對(duì)長(zhǎng)度為n的單鏈有序表，若搜索每個(gè)元素的概率相等，則搜索任一元素的搜索成功的平均搜索長(zhǎng)度為( )。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 91. 對(duì)于長(zhǎng)度為n的順序存儲(chǔ)的有序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)度中最大的為( )的值向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 92. 對(duì)于長(zhǎng)度為n的順序存儲(chǔ)的有序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)度中最大的為( )的值的向下取整加1。 A. log2(n+

19、1) B. log2n C. n/2 D. (n+1)/2 93. 對(duì)于長(zhǎng)度為9的順序存儲(chǔ)的有序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為( )除以9。 A. 20 B. 18 C. 25 D. 22 94. 對(duì)于長(zhǎng)度為18的順序存儲(chǔ)的有序表，若采用折半搜索，則搜索第15個(gè)元素的搜索長(zhǎng)度為( )。 A. 3 B. 4 C. 5 D. 6 95. 對(duì)具有n個(gè)元素的有序表進(jìn)行折半搜索，則搜索任一元素的時(shí)間復(fù)雜度為( )。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 96. 在一棵高度為h的具有n個(gè)元素的二叉搜索樹(shù)中，搜索一個(gè)元素的最大搜索長(zhǎng)度為( )。

20、 A. n B. log2n C. (h+1)/2 D. h+1 97. 從具有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，在等概率情況下進(jìn)行成功搜索的時(shí)間復(fù)雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 98. 向具有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中插入一個(gè)元素的時(shí)間復(fù)雜度大致為( )。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n) 99. 在一棵AVL樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是( )。 A. -11 B. -22 C. 12 D. 01 100. 向一棵AVL樹(shù)插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的調(diào)整過(guò)程，此調(diào)

21、整分為( )種旋轉(zhuǎn)類(lèi)型。 A. 2 B. 3 C. 4 D. 5 101. 向一棵AVL樹(shù)插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的左單或右單旋轉(zhuǎn)的調(diào)整過(guò)程，此時(shí)需要修改相關(guān)( )個(gè)指針域的值。 A. 2 B. 3 C. 4 D. 5 102. 向一棵AVL樹(shù)插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的雙向旋轉(zhuǎn)的調(diào)整過(guò)程，此時(shí)需要修改相關(guān)( )個(gè)指針域的值。 A. 2 B. 3 C. 4 D. 5 103. 設(shè)G1=（V1，E1）和G2=（V2，E2）為兩個(gè)圖，如果V1V2，E1E2，則稱(chēng) ( )。 AG1是G2的子圖 BG2是G1的子圖 CG1是G2的連通分量 DG2是G1的連通分量104. 有向圖的

22、一個(gè)頂點(diǎn)的度數(shù)等于該頂點(diǎn)的 ( )。 A入度 B出度 C入度與出度之和 D（入度+出度）105. 一個(gè)連通圖的生成樹(shù)是包含圖中所有頂點(diǎn)的一個(gè) ( )。 A極小子圖 B連通子圖 C極小連通子圖 D無(wú)環(huán)子圖106. n個(gè)頂點(diǎn)的連通圖中至少含有 ( )。 An-1條邊 Bn條邊 Cn(n-1)/2條邊 Dn(n-1)條邊107. n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有 ( )。 An-1條有向邊 Bn條有向邊 Cn(n-1)/2條有向邊 Dn(n-1)條有向邊108. 在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的( ) 中。 A最小生成樹(shù) B生成樹(shù) C廣度優(yōu)先生成樹(shù) D深度優(yōu)先生成樹(shù)109. 對(duì)于具有e條

23、邊的無(wú)向圖，它的鄰接表中有 ( ) 個(gè)邊結(jié)點(diǎn)。 Ae-1 Be C2(e-1) D2e110. 具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多可包含 ( ) 條有向邊。 An-1 Bn Cn(n-1)/2 Dn(n-1) 111. 一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一定是 ( )。 A連通的 B不連通的 C無(wú)環(huán)的 D有環(huán)的112. 在n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖的鄰接矩陣中至少有 ( ) 個(gè)零元素。 An Bn(n-1)/2 Cn(n+1)/2 Dn(n-1) 113. 對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于 ( )。 A查找一條邊 B求一個(gè)頂點(diǎn)的鄰接點(diǎn) C進(jìn)行圖的深度優(yōu)先遍歷 D進(jìn)行圖的廣度優(yōu)先遍歷114. 在一個(gè)

24、有向圖的鄰接矩陣表示中，刪除一條邊需要耗費(fèi)的時(shí)間是 ( )。 AO(1) BO(i) CO(j) DO(i+j)115. 與鄰接矩陣相比，鄰接表更適合于存儲(chǔ) ( )。 A無(wú)向圖 B連通圖 C稀疏圖 D稠密圖116. 設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條邊的有向圖采用鄰矩陣表示，要計(jì)算某個(gè)頂點(diǎn)的出度所耗費(fèi)的時(shí)間是 ( )。 AO(n) BO(e) CO(n+e) DO(n2)117. 為了實(shí)現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)是 ( )。 A棧 B隊(duì)列 C二叉樹(shù) D樹(shù)118. 設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(

25、n-1)119. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。A. 3B. 2C. 1D. 1/2120. 若采用鄰接矩陣存儲(chǔ)具有n個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè) ( )。A. 上三角矩陣B. 稀疏矩陣C. 對(duì)角矩陣D. 對(duì)稱(chēng)矩陣121. 圖的深度優(yōu)先搜索類(lèi)似于樹(shù)的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次122. 圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次123. 在用Kruskal算法求解帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹(shù)時(shí)，通常采用一個(gè)（ ）輔助結(jié)構(gòu)，判斷一條邊的兩個(gè)端點(diǎn)是否在同一個(gè)連通分量上。A. 位向量 B. 堆

26、 C. 并查集 D. 生成樹(shù)頂點(diǎn)集合124. 采用Dijkstra算法求解帶權(quán)有向圖的最短路徑問(wèn)題時(shí)，要求圖中每條邊所帶的權(quán)值必須是（ ）數(shù)。A. 非零B. 非整C. 非負(fù)D. 非正125. 設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2) 126. 若待排序?qū)ο笮蛄性谂判蚯耙鸦景磁判虼a遞增順序排列，則采用( )方法比較次數(shù)最少。 A. 直接插入排序 B. 快速排序 C. 歸并排序D. 直接選擇排序 127. 對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子

27、序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是( )。 A. 直接選擇排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 128. 對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行( )次比較。 A. 8 B. 10 C. 15 D. 25 129. 下列排序算法中，( )算法是不穩(wěn)定的。 A. 起泡排序 B. 直接插入排序 C. 基數(shù)排序 D. 快速排序 130. 假設(shè)某文件經(jīng)過(guò)內(nèi)部排序得到100個(gè)初始?xì)w并段，那么如果要求利用多路平衡歸并在3 趟內(nèi)完成排序，則應(yīng)取的歸并路數(shù)至少是( )。 A. 3 B. 4 C. 5 D. 6 131. 在基于排序碼比較的

28、排序算法中，( )算法在最壞情況下的時(shí)間復(fù)雜度不高于O(nlog2n)。 A. 起泡排序 B. 希爾排序 C. 堆排序 D. 快速排序 132. 在下列排序算法中，( )算法使用的附加空間與輸入序列的長(zhǎng)度及初始排列無(wú)關(guān)。 A. 錦標(biāo)賽排序 B. 快速排序 C. 基數(shù)排序 D. 歸并排序 133. 一個(gè)對(duì)象序列的排序碼為46, 79, 56, 38, 40, 84，采用快速排序（以位于最左位置的對(duì)象為基準(zhǔn)）所得到的第一次劃分結(jié)果為( )。A. 38, 46, 79, 56, 40, 84 B. 38, 79, 56, 46, 40, 84C. 40, 38, 46, 79, 56, 84 D.

29、38, 46, 56, 79, 40, 84 134. 如果將所有中國(guó)人按照生日（不考慮年份，只考慮月、日）來(lái)排序，那么使用下列排序算法中( )算法最快。 A. 歸并排序 B. 希爾排序 C. 快速排序 D. 基數(shù)排序 135. 設(shè)有一個(gè)含有200個(gè)元素的表待散列存儲(chǔ)，用線(xiàn)性探查法解決沖突，按關(guān)鍵碼查詢(xún)時(shí)找到一個(gè)元素的平均探查次數(shù)不能超過(guò)1.5，則散列表的長(zhǎng)度應(yīng)至少為（ ）。（注：平均探查次數(shù)的計(jì)算公式為Snl=1+1/(1-)/2, 其中為裝填因子） A. 400B. 526C. 624D. 676 136. 5階B樹(shù)中, 每個(gè)結(jié)點(diǎn)最多允許有（ ）個(gè)關(guān)鍵碼。 A. 2B. 3C. 4D. 5

30、 137. 在10階B樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最少為（ ）。 A. 0B. 1C. 3D. 4 138. 在一棵高度為h的B樹(shù)中，葉結(jié)點(diǎn)處于第（ ）層。（注：樹(shù)根結(jié)點(diǎn)為第0層，B樹(shù)高度為失敗結(jié)點(diǎn)所處層數(shù)）。 A. h-1B. hC. h+1D. h+2 139. 在一棵高度為h的B樹(shù)中，插入一個(gè)新關(guān)鍵碼時(shí)，為搜索插入位置需讀?。?）個(gè)結(jié)點(diǎn)。 A. h-1B. hC. h+1D. h+2 140. 當(dāng)對(duì)一個(gè)線(xiàn)性表R60 進(jìn)行索引順序搜索（分塊搜索）時(shí)，若共分成了10個(gè)子表，每個(gè)子表有6個(gè)表項(xiàng)。假定對(duì)索引表和數(shù)據(jù)子表都采用順序搜索，則搜索每一個(gè)表項(xiàng)的平均搜索長(zhǎng)度為（ ）。 A. 7B. 8C.

31、 9D. 10 141. 當(dāng)對(duì)一個(gè)線(xiàn)性表R60 進(jìn)行索引順序搜索（分塊搜索）時(shí)，若共分成了8個(gè)子表，每個(gè)子表有6個(gè)表項(xiàng)。假定對(duì)索引表和數(shù)據(jù)子表都采用順序搜索，則搜索每一個(gè)表項(xiàng)的平均搜索長(zhǎng)度為（ ）。 A. 7B. 8C. 9D. 10 142. 既希望較快的搜索又便于線(xiàn)性表動(dòng)態(tài)變化的搜索方法是（ ）。 A. 順序搜索B. 折半搜索 C. 散列搜索D. 索引順序搜索 143. 散列函數(shù)應(yīng)該有這樣的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（ ）概率取其值域范圍內(nèi)的每一個(gè)值。 A. 最大 B. 最小 C. 平均D. 同等 144. 設(shè)散列地址空間為0m-1，k為表項(xiàng)的關(guān)鍵碼，散列函數(shù)采用除留余數(shù)法，即Hash(k)=k

32、%p。為了減少發(fā)生沖突的頻率，一般取p為（ ）。A. mB. 小于m的最大質(zhì)數(shù) C. 大于m的最小質(zhì)數(shù)D. 小于m的最大合數(shù) 145. 在采用開(kāi)散列法解決沖突時(shí)，每一個(gè)散列地址所鏈接的同義詞子表中各個(gè)表項(xiàng)的（ ）值相同。A. 關(guān)鍵碼 B. 非關(guān)鍵碼 C. 散列函數(shù) D. 某個(gè)域 146. 解決散列法中出現(xiàn)的沖突問(wèn)題常采用的方法是（ ）。A. 數(shù)字分析法、除留余數(shù)法、平方取中法 B. 數(shù)字分析法、除留余數(shù)法、線(xiàn)性探查法 C. 數(shù)字分析法、線(xiàn)性探查法、雙散列法 D. 線(xiàn)性探查法、雙散列法、開(kāi)散列法 147. 在閉散列表中，散列到同一個(gè)地址而引起的“堆積”問(wèn)題是由于（ ）引起的。A. 同義詞之間發(fā)生沖突 B. 非同義詞之間發(fā)生沖突 C. 同義詞之間或非同義詞之間發(fā)生沖突 D. 散列表“溢出” 148. 采用線(xiàn)性探查法解決沖突時(shí)所產(chǎn)生的一系列后繼散列地址（ ）。A.