《大數(shù)據(jù)結(jié)構(gòu)》試的題目總匯編(帶問題詳解)

《《大數(shù)據(jù)結(jié)構(gòu)》試的題目總匯編(帶問題詳解)》由會員分享，可在線閱讀，更多相關《《大數(shù)據(jù)結(jié)構(gòu)》試的題目總匯編(帶問題詳解)（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、《數(shù)據(jù)結(jié)構(gòu)》習題匯編 一、單項選擇題 1. 在數(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) 2. 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指〔 〕。 A. 數(shù)據(jù)的存儲結(jié)構(gòu) B. 數(shù)據(jù)結(jié)構(gòu) C. 數(shù)據(jù)的邏輯結(jié)構(gòu) D. 數(shù)據(jù)元素之間的關系 3. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的〔 〕結(jié)構(gòu)。 A. 邏輯B. 存儲 C. 邏輯和存儲 D. 物理 4. 計算機算法指的是〔 ① 〕，它必須具備輸入、

2、輸出和〔 ② 〕等5個特性。 ①A. 計算方法 B. 排序方法 C. 解決問題的有限運算序列D. 調(diào)度方法 ②A. 可行性、可移植性和可擴大性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和安全性 5. 在一個長度為n的順序表中向第i個元素〔1≤i≤n+1〕位置插入一個新元素時，需要從后向前依次后移〔 〕個元素。 A. n-i B. n-i+1 C. n-i-1 D. i 6. 在一個長度為n的順序表中刪除第i個元素〔1≤i≤n〕時，需要從前向后依次前移〔 〕個元素。 A. n-i

3、 B. n-i+1 C. n-i-1 D. i 7. 在一個長度為n的順序表的表尾插入一個新元素的漸進時間復雜度為〔 〕。 A. O(n) B. O(1) C. O(n2) D. O(log2n) 8. 在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為〔 〕。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 9. 不帶頭結(jié)點的單鏈表first為空的判定條件是：〔 〕 A. first==NULL;B. first->next==NULL; C. first->next==

4、first;D. first!=NULL; 10. 帶頭結(jié)點的單鏈表first為空的判定條件是：〔 〕 A. first == NULL;B. first->next == NULL; C. first->next == first;D. first != NULL; 11. 設單鏈表中結(jié)點的結(jié)構(gòu)為〔data, next〕。指針p所指結(jié)點不是尾結(jié)點，假如在*p之后插入結(jié)點*s，如此應執(zhí)行如下哪一個操作？〔 〕 A. s->next = p; p->next = s;B. p->next = s; s->next = p; C. s->next = p

5、->next; p = s;D. s->next = p->next; p->next = s; 12. 設單鏈表中結(jié)點的結(jié)構(gòu)為〔data, next〕。假如想摘除結(jié)點*p(*p既不是第一個也不是最后一個結(jié)點)的直接后繼，如此應執(zhí)行如下哪一個操作？〔 〕 A. p->next = p->next->next;B. p = p->next; p->next = p->next->next; C. p->next = p->next;D. p = p->next->next; 13. 非空的循環(huán)單鏈表first的尾結(jié)點〔由p所指向〕滿足：〔 〕 A. p

6、->next == NULL; B. p == NULL; C. p->next == first;D. p == first; 14. 假如讓元素1,2,3依次進棧，如此出棧次序不可能出現(xiàn)〔 〕種情況。 A. 3, 2, 1 B. 2, 1, 3C. 3, 1, 2 D. 1, 3, 2 15. 當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為〔 〕。 A. n-2 B. n-1C. n D. n+1 16. 從一個順序存儲的循環(huán)隊列中刪除一個元素時，需要〔 〕。 A. 隊頭指針加一 B. 隊頭指針

7、減一 C. 取出隊頭指針所指的元素D. 取出隊尾指針所指的元素 17. 假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，如此判斷隊空的條件為〔 〕。 A. front+1==rear B. rear+1==front C. front==0 D. front==rear 18. 樹中所有結(jié)點的度等于所有結(jié)點數(shù)加〔〕。 A. 0B. 1C. -1D. 2 19. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加〔〕。 A. 2B. 1C. 0D. -1 20. 在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于〔

8、〕。 A. n B. n-1C. n+1D. 2*n 21. 在一棵具有n個結(jié)點的二叉樹的第i層上〔假定根結(jié)點為第1層，i大于等于1而小于等于樹的高度〕，最多具有〔〕個結(jié)點。 A. 2iB. 2i+1C. 2i-1D. 2n 22. 在一棵高度為h〔假定根結(jié)點的層號為1〕的完全二叉樹中，所含結(jié)點個數(shù)不小于〔〕。 A. 2h-1B. 2h+1C. 2h-1D. 2h 23. 在一棵具有35個結(jié)點的完全二叉樹中，該樹的高度為〔〕。假定空樹的高度為0。 A. 5B. 6C. 7D. 8 24. 在一棵具有n個結(jié)點的完全二叉樹中，分支結(jié)點的最大編號為〔〕。假定樹根結(jié)點的

9、編號為1。 A.?(n-1)/2?B. ?n/2?C. én/2ùD. ?n/2? -1 25. 在一棵完全二叉樹中，假如編號為i的結(jié)點存在左孩子，如此左子女結(jié)點的編號為〔〕。假定根結(jié)點的編號為1 A. 2iB. 2i-1C. 2i+1D. 2i+2 26. 在一棵完全二叉樹中，假定根結(jié)點的編號為1，如此對于編號為i〔i＞1〕的結(jié)點，其雙親結(jié)點的編號為〔 〕。 A.?(i+1)/2?B. ?(i-1)/2?C. ?i/2?D. ?i/2?-1 27. 設無向圖的頂點個數(shù)為n，如此該圖最多有〔 〕條邊。 A. n-1 B. n(n-1)/2C. n(n

10、+1)/2 D. n(n-1) 28. n個頂點的連通圖至少有〔 〕條邊。 A. n-1 B.nC. n+1 D. 0 29. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。 A. 3 B.2C. 1 D. 1/2 30. 圖的深度優(yōu)先搜索類似于樹的〔 〕次序遍歷。 A. 先根B. 中根 C. 后根 D. 層次 31. 圖的廣度優(yōu)先搜索類似于樹的〔 〕次序遍歷。 A. 先根 B. 中根 C. 后根 D. 層次 32. n(n＞1) 個頂點的強連通圖中至少含

11、有〔 〕條有向邊。 A. n-1 B. n C. n(n-1)/2 D. n(n-1) 33. 具有n個頂點的有向無環(huán)圖最多可包含〔 〕條有向邊。 A. n-1 B. n C. n(n-1)/2 D.n(n-1) 34. 一個有n個頂點和n條邊的無向圖一定是〔 〕。 A. 連通的 B. 不連通的 C. 無環(huán)的 D. 有環(huán)的 35. 在n個頂點的有向無環(huán)圖的鄰接矩陣中至少有〔 〕個零元素。 A. nB. n(n-1)/2C. n(n+1)/2 D. n(n-1

12、) 36. 為了實現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個輔助數(shù)據(jù)結(jié)構(gòu)是〔 〕。 A. 棧 B. 隊列 C. 二叉樹 D. 樹 37. 假如搜索每一個元素的概率相等，如此在長度為n的順序表上搜索到表中任一元素的平均搜索長度為〔〕。 A. nB. n+1C. (n-1)/2D. (n+1)/2 38. 對長度為10的順序表進展搜索(從表頭開始搜索)，假如搜索前面5個元素的概率一樣，均為1/8，搜索后面5個元素的概率一樣，均為3/40，如此搜索到表中任一元素的平均搜索長度為〔〕。 A. 5.5B. 5C. 39/8D. 19/4

13、 39. 對于長度為n的有序順序表，假如采用折半搜索，如此對所有元素的搜索長度中最大的為〔〕的值的向上取整。 A. log2(n+1)B. log2nC. n/2D. (n+1)/2 40. 對于長度為n的有序順序表，假如采用折半搜索，如此對所有元素的搜索長度中最大的為〔〕的值的向下取整加一。 A. log2(n+1)B. log2nC. n/2D. (n+1)/2 41. 對于長度為9的有序順序表，假如采用折半搜索，在等概率情況下搜索成功的平均搜索長度為〔〕的值除以9。 A. 20 B. 18C. 25D. 22 42. 對于長度為18的有序順序表，假如采

14、用折半搜索，如此搜索第15個元素的搜索長度為〔〕。 A. 3B. 4C. 5 D. 6 43. 對具有n個元素的有序順序表進展折半搜索，如此搜索任一元素的時間復雜度為〔〕。 A. O(n)B. O(n2)C. O(1)D. O(log2n) 44. 對5個不同的數(shù)據(jù)元素進展直接插入排序，最多需要進展〔 〕次比擬？ A.8 B. 10 C. 15 D. 25 45. 如果輸入序列是已經(jīng)排好順序的，如此如下算法中〔 〕算法最快完畢？ A. 起泡排序 B. 直接插入排序 C. 直接選擇排序 D. 快速排序 46. 如果輸入序列

15、是已經(jīng)排好順序的，如此如下算法中〔 〕算法最慢完畢？ A. 起泡排序 B. 直接插入排序 C. 直接選擇排序 D. 快速排序 二、填空題 1. 算法的五個重要特性是有窮性 、確定性、可行性、輸入和輸出。 2. 設單鏈表中結(jié)點的結(jié)構(gòu)為〔data, next〕。假如想摘除結(jié)點*p本身，如此應執(zhí)行操作： q=p->next;p->data=q->data;p->next=q->next;free(q); 3. 設循環(huán)隊列Q的隊頭和隊尾指針分別為front和rear，隊列的最大容量為MaxSize，且規(guī)定判斷隊空的條件為Q.front == Q.rear

16、，如此判斷隊滿的條件為(Q.rear+1)%MaxSize==Q.front，而計算隊列長度的表達式為(Q.rear-Q.front+MaxSize)%MaxSize。 4. 設有一個順序棧S，元素s1, s2, s3, s4, s5, s6依次進棧，如果6個元素的出棧順序為s2, s3, s4, s6, s5, s1，如此順序棧的容量至少應為3。 5. 如果進棧序列是1, 2, 3, 4, 5, 6, 7, 8。如此可能的出棧序列有1430種。 6. 用簡單的模式匹配算法在主串"aaaaaab"中檢索子串〞aab〞，如此總的比擬次數(shù)為15。 7. 用簡單的模式匹配算法

17、在主串"data_structure"中檢索子串〞string〞，總的比擬次數(shù)為12。 8. 假定一棵三叉樹〔即度為3的樹〕的結(jié)點個數(shù)為50，如此它的最小高度為5。假定根結(jié)點的高度為1。 9. 在一棵高度為3的四叉樹中，最多含有21結(jié)點。 10. 在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有6個。 11. 一棵高度為5的完全二叉樹中，最多包含有31個結(jié)點。假定根結(jié)點的高度為1。 12. 在一棵二叉樹中，假定度為2的結(jié)點個數(shù)為5個，度為1的結(jié)點個數(shù)為6個，如此葉結(jié)點數(shù)為6個。 13. 假定一棵二叉樹的結(jié)

18、點個數(shù)為18，如此它的最小高度為5。假定根結(jié)點的高度為1。 14. 按照二叉樹的定義，具有5個結(jié)點的二叉樹有42種形態(tài)。 15. 以順序搜索方法從長度為n的順序表或單鏈表中搜索一個元素時，其時間復雜度為O(n)。 16. 對長度為n的搜索表進展搜索時，假定搜索第i個元素的概率為pi，搜索長度〔即在搜索過程中依次同有關元素比擬的總次數(shù)〕為ci，如此在搜索成功情況下的平均搜索長度的計算公式為。 17. 假定一個順序表的長度為40，并假定搜索每個元素的概率都一樣，如此在搜索成功情況下的平均搜索長度為20.5。 18. 以折半搜索方法從長度為n的有序表中搜索一個元素時，時

19、間復雜度為O(log2n)。 19. 從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時，其搜索長度為3。 20. 假定對長度n=50的有序表進展折半搜索，如此對應的判定樹中最后一層的結(jié)點數(shù)為19個。 21. 直接插入排序在最好情況下的比擬次數(shù)為，最壞情況下為?！舱蜃詈肅=n-1，逆序最壞C=n*(n-1)/2〕 22. 直接插入排序在最好情況下的移動次數(shù)為，最壞情況下為?！沧詈肕=0，最壞M=(n+4)*(n-1)/2〕 23. 簡單項選擇擇法排序時比擬數(shù)據(jù)的次數(shù)為?！踩魏吻闆r下C=n*(n-1)/2〕 24. 簡單項選擇擇法

20、排序在最好情況下的移動次數(shù)為，最壞情況下為。〔最好正序M=0，最壞〔非逆序，如6,1,2,3,4,5〕M=3*(n-1)〕 25. 起泡排序在最好情況下的比擬次數(shù)為，最壞情況下為?！沧詈谜駽=n-1，最壞逆序C=n*(n-1)/2〕 26. 起泡排序在最好情況下的移動次數(shù)為，最壞情況下為?！沧詈谜騇=0，最壞〔逆序〕M=3*n*(n-1)/2〕 27. 在直接選擇排序中，排序碼比擬次數(shù)的時間復雜度為O(n^2)。 28. 在直接選擇排序中，數(shù)據(jù)對象移動次數(shù)的時間復雜度為O(n)。 29. 快速排序在平均情況下的時間復雜度為O(nlog2n)。 30.

21、 快速排序在最壞情況下的時間復雜度為O(n2)。 三、簡答題 1. 下面程序段的時間復雜度是O(n*m)。for(i=0;i

22、; 5. 寫出如下程序段的輸出結(jié)果: 514263 。 void main( ) { SqStack S; SqQueue Q;inti,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); printf("%d ",e); }

23、} 6. 一棵二叉樹的前序和中序序列，畫圖并求該二叉樹的后序序列。 前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列： 7. 一棵二叉樹的中序和后序序列如下，畫圖并求該二叉樹的前序序列。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a 前序序列： 8. 有7個帶權結(jié)點，其權值分別為3, 7, 8, 2, 6, 10, 14，試以它們?yōu)槿~結(jié)點生成一棵赫夫曼樹，求出該樹的帶權路徑長度： 9. 設連通圖

24、G如下列圖。試給出對它執(zhí)行從頂點V0開始的廣度優(yōu)先遍歷和深度優(yōu)先遍歷的結(jié)果。 V0 V1 V2 V5 V4 V3 V6 V7 V8 廣度優(yōu)先遍歷：012345678 深度優(yōu)先遍歷：013256784 10. 設有一個連通網(wǎng)絡如下列圖。試采用prim算法從頂點0開始構(gòu)造最小生成樹。〔寫出參加生成樹頂點集合S和選擇邊Edge的順序〕 1 2 3 4 6 5 0 9 10 7 5 11 8 7 頂點集合 邊(頂點，頂點，權值) 0 (0 ， 1 ， 9 ) 01 (1 ， 3 ， 5 ) 013

25、(1 ， 2 ， 7 ) 0132 (2 ， 4 ，6 ) 01324 (2 ， 5 ，7 ) 013245 11. 設帶權有向圖如下列圖。試采用Dijkstra算法求從頂點0到其他各頂點的最短路徑和最短路徑長度。 7 1 8 2 4 4 5 9 1 2 3 4 0 頂點號 路徑長度 路徑 1 4 01 3 7 03 2 8 012 4 10 0124 1 11 15 19 10 2 2 3 4 4 5 5 6 6 12. 試對如下圖所示的AO

26、E網(wǎng)絡 (1) 這個工程最早可能在時間完畢。 (2) 確定哪些活動是關鍵活動。畫出由所有關鍵活動構(gòu)成的圖，指出哪些活動加速可使整個工程提前完成。 拓撲序列132456 每個頂點的最早發(fā)生時間、最遲發(fā)生時間：1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43) 工期：43天 每個活動的最早開始時間、最遲開始時間：1-2(0,17),1-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. 一個一維數(shù)組a[10]中存儲著一個有序表

27、，該有序表為：(15,26,34,39,45,56,58,63,74,76)，畫出折半搜索所對應的判定樹，并求出在等概率情況下搜索成功的平均搜索長度。 平均搜索長度：2.9 14. 給定一組數(shù)據(jù)對象的排序碼為 {46, 79, 56, 38, 40, 84}，對其進展一趟快速排序，結(jié)果為40,38,46,56,79,84。 四、算法設計題 1. 設有一個順序表 (e0, e1, …, en-2, en-1)。請編寫一個函數(shù)將這個順序表原地逆置，即順序表的內(nèi)容置換為 (en-1, en-2, …, e1, e0)。 void Reverse(SqList *L){ int i

28、=0,j=L->length-1; ElemType t; for(;ielem[i]; L->elem[i]=L->elem[j]; L->elem[j]=t; } } 2. 試編寫一個函數(shù)，用以刪除順序表L中所有值為x的元素〔要求就地工作〕。 void DeleteX(SqList *L, ElemType x){ int j=0; for(i=0;ilength;++i){ if(L->elem[i]!=x){ if(i>j)L->elem[j]=L->elem[i]; ++j; } }

29、 L->length =j; } 3. 試編寫一個函數(shù)，在數(shù)組R〔已正序排列〕中進展折半查找某個值k，找到如此返回其位置，否如此返回0。 int SearchBin(int R[], int n, int k){ //有序〔正序〕的順序表的二分查找，n為數(shù)組元素個數(shù)，k為待查找的值 int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2; if(R[mid]==k)return mid+1; else if(R[mid]>k) high=mid-1; else low=mid+

30、1; } return 0; } 4. 試編寫一個函數(shù)，對數(shù)組r進展選擇法排序〔結(jié)果為正序〕。 void SelectSort(ElemType r[],int n){ //對順序表r作簡單項選擇擇排序，n為數(shù)組元素個數(shù) int i,j,k; ElemType tmp; for(i=0;i