《數(shù)據(jù)結(jié)構(gòu)》試題匯編(帶答案)

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題匯編一、單項(xiàng)選擇題1. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A. 動(dòng)態(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)2. 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（ ）。A. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B. 數(shù)據(jù)結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)D. 數(shù)據(jù)元素之間的關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。A. 邏輯B. 存儲(chǔ)C. 邏輯和存儲(chǔ)D. 物理4. 計(jì)算機(jī)算法指的是（ ），它必須具備輸入、輸出和（ ）等5個(gè)特性。A. 計(jì)算方法B. 排序方法C. 解決問(wèn)題的有限運(yùn)算序列D. 調(diào)度方法A. 可行性、可移植性和可擴(kuò)充性B. 可行性

2、、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性5. 在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素（1in+1）位置插入一個(gè)新元素時(shí)，需要從后向前依次后移（ ）個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i6. 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需要從前向后依次前移（ ）個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i7. 在一個(gè)長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ ）。A. O(n)B. O(1)C. O(n2)D. O(log2n)8. 在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ ）。A

3、. O(n)B. O(n/2)C. O(1)D. O(n2)9. 不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是：（ ）A. first = NULL;B. first->next = NULL;C. first->next = first;D. first != NULL;10. 帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是：（ ）A. first = NULL;B. first->next = NULL;C. first->next = first;D. first != NULL;11. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, next）。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若

4、在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？（ ）A. s->next = p; p->next = s;B. p->next = s; s->next = p;C. s->next = p->next; p = s;D. s->next = p->next; p->next = s;12. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, next）。若想摘除結(jié)點(diǎn)*p(*p既不是第一個(gè)也不是最后一個(gè)結(jié)點(diǎn))的直接后繼，則應(yīng)執(zhí)行下列哪一個(gè)操作？（ ）A. p->next = p->next->next;B. p = p->nex

5、t; p->next = p->next->next;C. p->next = p->next;D. p = p->next->next;13. 非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足：（ ）A. p->next = NULL; B. p = NULL;C. p->next = first;D. p = first;14. 若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）種情況。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 215. 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度

6、為（ ）。A. n-2 B. n-1C. n D. n+116. 從一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，需要（ ）。A. 隊(duì)頭指針加一B. 隊(duì)頭指針減一C. 取出隊(duì)頭指針?biāo)傅脑谼. 取出隊(duì)尾指針?biāo)傅脑?7. 假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為（ ）。A. front+1 = rearB. rear+1 = frontC. front = 0D. front = rear18. 樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ ）。A. 0B. 1C. -1D. 219. 在一棵二叉樹(shù)的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（ ）。A. 2B

7、. 1C. 0D. -120. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于（ ）。A. n B. n-1C. n+1D. 2*n21. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的第i層上（假定根結(jié)點(diǎn)為第1層，i大于等于1而小于等于樹(shù)的高度），最多具有（ ）個(gè)結(jié)點(diǎn)。A. 2iB. 2i+1C. 2i-1D. 2n22. 在一棵高度為h（假定根結(jié)點(diǎn)的層號(hào)為1）的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（ ）。A. 2h-1B. 2h+1C. 2h-1D. 2h23. 在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，該樹(shù)的高度為（ ）。假定空樹(shù)的高度為0。A. 5B. 6C. 7D. 824. 在一棵具有n個(gè)結(jié)點(diǎn)的完全二

8、叉樹(shù)中，分支結(jié)點(diǎn)的最大編號(hào)為（ ）。假定樹(shù)根結(jié)點(diǎn)的編號(hào)為1。A. ë(n-1)/2ûB. ën/2û C. én/2ù D. ën/2û -125. 在一棵完全二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左子女結(jié)點(diǎn)的編號(hào)為（ ）。假定根結(jié)點(diǎn)的編號(hào)為1A. 2iB. 2i-1C. 2i+1D. 2i+226. 在一棵完全二叉樹(shù)中，假定根結(jié)點(diǎn)的編號(hào)為1，則對(duì)于編號(hào)為i（i1）的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為（ ）。A. ë(i+1)/2ûB. ë(i-1)/2ûC. ëi/2&#

9、251;D. ëi/2û -127. 設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)28. n個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。A. n-1 B. nC. n+1D. 029. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。A. 3B. 2C. 1D. 1/230. 圖的深度優(yōu)先搜索類似于樹(shù)的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次31. 圖的廣度優(yōu)先搜索類似于樹(shù)的（ ）次序遍歷。A. 先根B. 中根C. 后根D. 層次32. n (n1) 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含

10、有（ ）條有向邊。A. n-1 B. nC. n(n-1)/2D. n(n-1)33. 具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多可包含（ ）條有向邊。A. n-1B. n C. n(n-1)/2 D.n(n-1)34. 一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一定是（ ）。A. 連通的 B. 不連通的 C. 無(wú)環(huán)的 D. 有環(huán)的35. 在n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖的鄰接矩陣中至少有（ ）個(gè)零元素。A. nB. n(n-1)/2 C. n(n+1)/2D. n(n-1)36. 為了實(shí)現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)是（ ）。A. 棧 B. 隊(duì)列C. 二叉樹(shù) D. 樹(shù)37. 若搜索每一個(gè)元素的概率相等，則

11、在長(zhǎng)度為n的順序表上搜索到表中任一元素的平均搜索長(zhǎng)度為（ ）。A. nB. n+1C. (n-1)/2D. (n+1)/238. 對(duì)長(zhǎng)度為10的順序表進(jìn)行搜索(從表頭開(kāi)始搜索)，若搜索前面5個(gè)元素的概率相同，均為1/8，搜索后面5個(gè)元素的概率相同，均為3/40，則搜索到表中任一元素的平均搜索長(zhǎng)度為（ ）。A. 5.5B. 5C. 39/8D. 19/439. 對(duì)于長(zhǎng)度為n的有序順序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)度中最大的為（ ）的值的向上取整。A. log2(n+1)B. log2nC. n/2D. (n+1)/240. 對(duì)于長(zhǎng)度為n的有序順序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)

12、度中最大的為（ ）的值的向下取整加一。A. log2(n+1)B. log2nC. n/2D. (n+1)/241. 對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（ ）的值除以9。A. 20B. 18C. 25D. 2242. 對(duì)于長(zhǎng)度為18的有序順序表，若采用折半搜索，則搜索第15個(gè)元素的搜索長(zhǎng)度為（ ）。A. 3B. 4 C. 5 D. 643. 對(duì)具有n個(gè)元素的有序順序表進(jìn)行折半搜索，則搜索任一元素的時(shí)間復(fù)雜度為（ ）。A. O(n)B. O(n2)C. O(1)D. O(log2n)44. 對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行（ ）次比

13、較？A. 8B. 10C. 15D. 2545. 如果輸入序列是已經(jīng)排好順序的，則下列算法中（ ）算法最快結(jié)束？A. 起泡排序B. 直接插入排序C. 直接選擇排序D. 快速排序46. 如果輸入序列是已經(jīng)排好順序的，則下列算法中（ ）算法最慢結(jié)束？A. 起泡排序B. 直接插入排序C. 直接選擇排序D. 快速排序二、填空題1. 算法的五個(gè)重要特性是 有窮性 、確定性、可行性、輸入和輸出。2. 設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, next）。若想摘除結(jié)點(diǎn)*p本身，則應(yīng)執(zhí)行操作：q=p->next; p->data=q->data; p->next=q->next ; f

14、ree(q) ;3. 設(shè)循環(huán)隊(duì)列Q的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，隊(duì)列的最大容量為MaxSize，且規(guī)定判斷隊(duì)空的條件為Q.front = Q.rear，則判斷隊(duì)滿的條件為 (Q.rear+1)%MaxSize=Q.front ，而計(jì)算隊(duì)列長(zhǎng)度的表達(dá)式為(Q.rear-Q.front+MaxSize)%MaxSize 。4. 設(shè)有一個(gè)順序棧S，元素s1, s2, s3, s4, s5, s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2, s3, s4, s6, s5, s1，則順序棧的容量至少應(yīng)為 3 。5. 如果進(jìn)棧序列是1, 2, 3, 4, 5, 6, 7, 8。則可能的出棧序列有

15、 1430 種。6. 用簡(jiǎn)單的模式匹配算法在主串"aaaaaab"中檢索子串”aab”，則總的比較次數(shù)為15 。7. 用簡(jiǎn)單的模式匹配算法在主串"data_structure"中檢索子串”string”，總的比較次數(shù)為12 。8. 假定一棵三叉樹(shù)（即度為3的樹(shù)）的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為 5。假定根結(jié)點(diǎn)的高度為1。9. 在一棵高度為3的四叉樹(shù)中，最多含有 21 結(jié)點(diǎn)。10. 在一棵三叉樹(shù)中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有 6 個(gè)。11. 一棵高度為5的完全二叉樹(shù)中，最多包含有31個(gè)結(jié)點(diǎn)。假定

16、根結(jié)點(diǎn)的高度為1。12. 在一棵二叉樹(shù)中，假定度為2的結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，則葉結(jié)點(diǎn)數(shù)為6個(gè)。13. 假定一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為18，則它的最小高度為5。假定根結(jié)點(diǎn)的高度為1。14. 按照二叉樹(shù)的定義，具有5個(gè)結(jié)點(diǎn)的二叉樹(shù)有42種形態(tài)。15. 以順序搜索方法從長(zhǎng)度為n的順序表或單鏈表中搜索一個(gè)元素時(shí)，其時(shí)間復(fù)雜度為 O(n) 。16. 對(duì)長(zhǎng)度為n的搜索表進(jìn)行搜索時(shí)，假定搜索第i個(gè)元素的概率為pi，搜索長(zhǎng)度（即在搜索過(guò)程中依次同有關(guān)元素比較的總次數(shù)）為ci，則在搜索成功情況下的平均搜索長(zhǎng)度的計(jì)算公式為 。17. 假定一個(gè)順序表的長(zhǎng)度為40，并假定搜索每個(gè)元素的概率都相同，則在搜

17、索成功情況下的平均搜索長(zhǎng)度為20.5。18. 以折半搜索方法從長(zhǎng)度為n的有序表中搜索一個(gè)元素時(shí)，時(shí)間復(fù)雜度為O(log2n)。19. 從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時(shí)，其搜索長(zhǎng)度為3 。20. 假定對(duì)長(zhǎng)度n = 50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹(shù)中最后一層的結(jié)點(diǎn)數(shù)為19個(gè)。21. 直接插入排序在最好情況下的比較次數(shù)為 ，最壞情況下為 。（正序最好C=n-1，逆序最壞C=n*(n-1)/2）22. 直接插入排序在最好情況下的移動(dòng)次數(shù)為 ，最壞情況下為 。（最好M=0，最壞M=(n+4)*(n-1)/2）23. 簡(jiǎn)單選擇法排序時(shí)比較數(shù)據(jù)的次數(shù)為

18、。（任何情況下C=n*(n-1)/2）24. 簡(jiǎn)單選擇法排序在最好情況下的移動(dòng)次數(shù)為 ，最壞情況下為 。（最好正序M=0，最壞（非逆序，如6,1,2,3,4,5）M=3*(n-1)）25. 起泡排序在最好情況下的比較次數(shù)為 ，最壞情況下為 。（最好正序C=n-1，最壞逆序C=n*(n-1)/2）26. 起泡排序在最好情況下的移動(dòng)次數(shù)為 ，最壞情況下為 。（最好正序M=0，最壞（逆序）M=3*n*(n-1)/2）27. 在直接選擇排序中，排序碼比較次數(shù)的時(shí)間復(fù)雜度為O( n2 )。28. 在直接選擇排序中，數(shù)據(jù)對(duì)象移動(dòng)次數(shù)的時(shí)間復(fù)雜度為O(n)。29. 快速排序在平均情況下的時(shí)間復(fù)雜度為O(nl

19、og2n)。30. 快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n2)。三、簡(jiǎn)答題1. 下面程序段的時(shí)間復(fù)雜度是 O(n*m) 。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;2. 下面程序段的時(shí)間復(fù)雜度是 O(n0.5) 。i=s=0; while(s<n) i+; s+=i; 3. 下面程序段的時(shí)間復(fù)雜度是O(n2) 。s=0;for(i=0;i<n;i+) for(j=0;j<n;j+) s+=Bij;sum=s;4. 下面程序段的時(shí)間復(fù)雜度是O(log3n) 。i=1; while(i<=n) i=i*3;5. 寫出下列程序段

20、的輸出結(jié)果: 514263 。void main( ) SqStack S; SqQueue Q; int i,j,n=6,e;for(i=1;i<=n;+i)Push(&S,i);for(i=1;i<=n;+i)Pop(&S,&e); EnQueue(&Q,e); DeQueue(&Q,&e); EnQueue(&Q,e); for(i=1;i<=n;+i) DeQueue(&Q,&e); Push(&S,e); for(i=1;i<=n;+i) Pop(&S,&e); p

21、rintf("%d ",e); 6. 已知一棵二叉樹(shù)的前序和中序序列，畫圖并求該二叉樹(shù)的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列： 7. 已知一棵二叉樹(shù)的中序和后序序列如下，畫圖并求該二叉樹(shù)的前序序列。中序序列：c, b, d, e, a, g, i, h, j, f后序序列：c, e, d, b, i, j, h, g, f, a前序序列：8. 有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3, 7, 8, 2, 6, 10, 14，試以它們?yōu)槿~結(jié)點(diǎn)生成一棵赫夫曼樹(shù)，求出該樹(shù)的帶權(quán)

22、路徑長(zhǎng)度： 9. 設(shè)連通圖G如圖所示。試給出對(duì)它執(zhí)行從頂點(diǎn)V0開(kāi)始的廣度優(yōu)先遍歷和深度優(yōu)先遍歷的結(jié)果。V0V1V2V5V4V3V6V7V8廣度優(yōu)先遍歷：012345678深度優(yōu)先遍歷：01325678410. 設(shè)有一個(gè)連通網(wǎng)絡(luò)如圖所示。試采用prim算法從頂點(diǎn)0開(kāi)始構(gòu)造最小生成樹(shù)。（寫出加入生成樹(shù)頂點(diǎn)集合S和選擇邊Edge的順序）1234650910751187頂點(diǎn)集合邊(頂點(diǎn)，頂點(diǎn)，權(quán)值)0( 0 ， 1 ， 9 )01( 1 ， 3 ， 5 )013 ( 1 ， 2 ， 7 )0132( 2 ， 4 ， 6 )01324( 2 ， 5 ， 7 )013245 11. 設(shè)帶權(quán)有向圖如圖所示。

23、試采用Dijkstra算法求從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。 7182445912340頂點(diǎn)號(hào)路徑長(zhǎng)度路徑1401370328012410012411115191022344556612. 試對(duì)下圖所示的AOE網(wǎng)絡(luò)(1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。 (2) 確定哪些活動(dòng)是關(guān)鍵活動(dòng)。畫出由所有關(guān)鍵活動(dòng)構(gòu)成的圖，指出哪些活動(dòng)加速可使整個(gè)工程提前完成。拓?fù)湫蛄?32456每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間、最遲發(fā)生時(shí)間：1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43)工期：43天每個(gè)活動(dòng)的最早開(kāi)始時(shí)間、最遲開(kāi)始時(shí)間：1-2(0,17),1

24、-3(0,0),3-2(15,15),3-5(15,27),2-5(19,19),2-4(19,27)5-6(38,38),4-6(29,37)13. 一個(gè)一維數(shù)組a10中存儲(chǔ)著一個(gè)有序表，該有序表為：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，畫出折半搜索所對(duì)應(yīng)的判定樹(shù)，并求出在等概率情況下搜索成功的平均搜索長(zhǎng)度。平均搜索長(zhǎng)度： 2.9 14. 給定一組數(shù)據(jù)對(duì)象的排序碼為 46, 79, 56, 38, 40, 84，對(duì)其進(jìn)行一趟快速排序，結(jié)果為 40,38,46,56,79,84。四、算法設(shè)計(jì)題1. 設(shè)有一個(gè)順序表 (e0, e1, , en-2, en-1)。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)順序表原地逆置，即順序表的內(nèi)容置換為 (e