數(shù)據(jù)結構（本科）期末綜合練習一（單選題）

1、數(shù)據(jù)結構（本科）期末綜合練習一（單選題）單選題 1. 一個數(shù)組元素ai 與( )的表示等價。 A. *(a+i) B. a+i C. *a+i D. &a+i 2. 若需要利用形參直接訪問實參，則應把形參變量說明為( )參數(shù)。 A. 指針 B. 引用 C. 傳值 D. 常值 3. 下面程序段的時間復雜度為( )。 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í)行下面程序段時，執(zhí)行S語句的次數(shù)為( )。 for(int i=1; i=n; i+) for

2、(int j=1; jlink = NULL;C. first-link = first; D. first != NULL; 29. 帶頭結點的單鏈表first為空的判定條件是（ ）。A. first=NULL; B. first-link=NULL;C. first-link=first; D. first!=NULL; 30. 設單鏈表中結點的結構為（data, link）。已知指針q所指結點是指針p所指結點的直接前驅，若在*q與*p之間插入結點*s，則應執(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. 設單鏈表中結點的結構為（data, link）。已知指針p所指結點不是尾結點，若在*p之后插入結點*s，則應執(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. 設單鏈表中結點的結構為（data, link）。若想摘除p-link所指向的結點，則應執(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的尾結點（由p所指向）滿足的條件是（ ）。 A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first; 34. 設單循環(huán)鏈表中結點的結構為（data, link），且rear是指向非空的帶表頭結點的單循環(huán)鏈表的尾結點的指針。若想刪除鏈表第一個結點，則應執(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. 從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需要平均比較的結點數(shù)是（ ）。 A. n B. n/2 C. (n-1)/2 D. (n+1)/236. 在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是（ ）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n)37. 給定有n個元素的向量，建立一個有序單鏈表的時間

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

7、nk=NULL41. 已知L是一個不帶表頭的單鏈表, 在表首插入結點*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是帶表頭的單鏈表, 刪除首元結點的語句是（ ）。A. L = L-link; B. L-link = L-link-link; C. L = L; D. L-link = L;43. 棧的插入和刪除操作在( )進行。 A. 棧頂 B. 棧底 C. 任意位置D. 指定位置44. 當利用大小為n的數(shù)組順序存儲一個棧時，假定用t

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

9、需要( )。 A. 隊頭指針加一B. 隊頭指針減一 C. 取出隊頭指針所指的元素D. 取出隊尾指針所指的元素49. 假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為( )。 A. front+1 = rearB. rear+1 = front C. front = 0D. front = rear50. 假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL51. 設鏈式棧中結點的結構為（data

10、, link），且top是指向棧頂?shù)闹羔?。若想在鏈式棧的棧頂插入一個由指針s所指的結點，則應執(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. 設鏈式棧中結點的結構為（data, link），且top是指向棧頂?shù)闹羔?。若想摘除鏈式棧的棧頂結點，并將被摘除結點的值保存到x中，則應執(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. 設循環(huán)隊列的結構是 typedef struct DataType dataMaxSize; int front, rear; Queue; 若有一個Queue類型的隊列Q，試問判斷隊列滿的條件應為( ) 。 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. 設循環(huán)隊列的結構是 const int MaxSize = 100; typedef int DataType

12、; typedef struct DataType dataMaxSize; int front, rear; Queue; 若有一個Queue類型的隊列Q，則應用( )表達式計算隊列元素的個數(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. 為增加內存空間的利用率和減少溢出的可能性, 由兩個棧共享一塊連續(xù)的內存空間時, 應將兩棧的( )分別設在這塊內存空間的兩端。 A. 長度 B. 深度 C. 棧頂 D. 棧底56. 遞歸是將一個較復雜的

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

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

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

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

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

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

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

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

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

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

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

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

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

26、 C. 并查集 D. 生成樹頂點集合124. 采用Dijkstra算法求解帶權有向圖的最短路徑問題時，要求圖中每條邊所帶的權值必須是（ ）數(shù)。A. 非零B. 非整C. 非負D. 非正125. 設有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓撲排序時，總的計算時間為（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2) 126. 若待排序對象序列在排序前已基本按排序碼遞增順序排列，則采用( )方法比較次數(shù)最少。 A. 直接插入排序 B. 快速排序 C. 歸并排序D. 直接選擇排序 127. 對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子

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

28、排序算法中，( )算法在最壞情況下的時間復雜度不高于O(nlog2n)。 A. 起泡排序 B. 希爾排序 C. 堆排序 D. 快速排序 132. 在下列排序算法中，( )算法使用的附加空間與輸入序列的長度及初始排列無關。 A. 錦標賽排序 B. 快速排序 C. 基數(shù)排序 D. 歸并排序 133. 一個對象序列的排序碼為46, 79, 56, 38, 40, 84，采用快速排序（以位于最左位置的對象為基準）所得到的第一次劃分結果為( )。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. 如果將所有中國人按照生日（不考慮年份，只考慮月、日）來排序，那么使用下列排序算法中( )算法最快。 A. 歸并排序 B. 希爾排序 C. 快速排序 D. 基數(shù)排序 135. 設有一個含有200個元素的表待散列存儲，用線性探查法解決沖突，按關鍵碼查詢時找到一個元素的平均探查次數(shù)不能超過1.5，則散列表的長度應至少為（ ）。（注：平均探查次數(shù)的計算公式為Snl=1+1/(1-)/2, 其中為裝填因子） A. 400B. 526C. 624D. 676 136. 5階B樹中, 每個結點最多允許有（ ）個關鍵碼。 A. 2B. 3C. 4D. 5

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

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

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