數(shù)據結構習題匯編一、單項選擇題1. 在數(shù)據結構中，從邏輯上可以把數(shù)據結構分成 。A. 動態(tài)結構和靜態(tài)結構B. 緊湊結構和非緊湊結構C. 線性結構和非線性結構D. 內部結構和外部結構2. 數(shù)據結構在計算機內存中的表示是指 。A. 數(shù)據的存儲結構B. 數(shù)據結構C. 數(shù)據的邏輯結構D. 數(shù)據元素之間的關系3. 在數(shù)據結構中，與所使用的計算機無關的是數(shù)據的 結構。A. 邏輯B. 存儲C. 邏輯和存儲D. 物理4. 計算機算法指的是 ，它必須具備輸入、輸出和 等5個特性。A. 計算方法B. 排序方法C. 解決問題的有限運算序列D. 調度方法A. 可行性、可移植性和可擴大性B. 可行性、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和安全性5. 在一個長度為n的順序表中向第i個元素1in+1位置插入一個新元素時，需要從后向前依次后移 個元素。A. n-iB. n-i+1C. n-i-1D. i6. 在一個長度為n的順序表中刪除第i個元素1in時，需要從前向后依次前移 個元素。A. n-iB. n-i+1C. n-i-1D. i7. 在一個長度為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. 不帶頭結點的單鏈表first為空的判定條件是： A. first=NULL;B. first->next=NULL;C. first->next=first;D. first!=NULL;10. 帶頭結點的單鏈表first為空的判定條件是： A. first = NULL;B. first->next = NULL;C. first->next = first;D. first != NULL;11. 設單鏈表中結點的結構為data, next。指針p所指結點不是尾結點，假如在*p之后插入結點*s，如此應執(zhí)行如下哪一個操作？ 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. 設單鏈表中結點的結構為data, next。假如想摘除結點*p(*p既不是第一個也不是最后一個結點)的直接后繼，如此應執(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的尾結點由p所指向滿足： A. p->next = NULL; B. p = NULL;C. p->next = first;D. p = first;14. 假如讓元素1,2,3依次進棧，如此出棧次序不可能出現(xiàn) 種情況。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 215. 當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為 。A. n-2 B. n-1C. n D. n+116. 從一個順序存儲的循環(huán)隊列中刪除一個元素時，需要 。A. 隊頭指針加一B. 隊頭指針減一C. 取出隊頭指針所指的元素D. 取出隊尾指針所指的元素17. 假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，如此判斷隊空的條件為 。A. front+1=rearB. rear+1=frontC. front=0D. front=rear18. 樹中所有結點的度等于所有結點數(shù)加。A. 0B. 1C. -1D. 219. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加。A. 2B. 1C. 0D. -120. 在一棵具有n個結點的二叉樹中，所有結點的空子樹個數(shù)等于。A. n B. n-1C. n+1D. 2*n21. 在一棵具有n個結點的二叉樹的第i層上假定根結點為第1層，i大于等于1而小于等于樹的高度，最多具有個結點。A. 2iB. 2i+1C. 2i-1D. 2n22. 在一棵高度為h假定根結點的層號為1的完全二叉樹中，所含結點個數(shù)不小于。A. 2h-1B. 2h+1C. 2h-1D. 2h23. 在一棵具有35個結點的完全二叉樹中，該樹的高度為。假定空樹的高度為0。A. 5B. 6C. 7D. 824. 在一棵具有n個結點的完全二叉樹中，分支結點的最大編號為。假定樹根結點的編號為1。A.ë(n-1)/2ûB. ën/2ûC. én/2ùD. ën/2û -125. 在一棵完全二叉樹中，假如編號為i的結點存在左孩子，如此左子女結點的編號為。假定根結點的編號為1A. 2iB. 2i-1C. 2i+1D. 2i+226. 在一棵完全二叉樹中，假定根結點的編號為1，如此對于編號為ii1的結點，其雙親結點的編號為 。A.ë(i+1)/2ûB. ë(i-1)/2ûC. ëi/2ûD. ëi/2û-127. 設無向圖的頂點個數(shù)為n，如此該圖最多有 條邊。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)28. n個頂點的連通圖至少有 條邊。A. n-1B.nC. n+1D. 029. 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。A. 3B.2C. 1D. 1/230. 圖的深度優(yōu)先搜索類似于樹的 次序遍歷。A. 先根B. 中根C. 后根D. 層次31. 圖的廣度優(yōu)先搜索類似于樹的 次序遍歷。A. 先根B. 中根C. 后根D. 層次32. n(n1) 個頂點的強連通圖中至少含有 條有向邊。A. n-1 B. nC. n(n-1)/2D. n(n-1)33. 具有n個頂點的有向無環(huán)圖最多可包含 條有向邊。A. n-1B. 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)/2D. n(n-1)36. 為了實現(xiàn)圖的廣度優(yōu)先遍歷，BFS算法使用的一個輔助數(shù)據結構是 。A. 棧 B. 隊列C. 二叉樹 D. 樹37. 假如搜索每一個元素的概率相等，如此在長度為n的順序表上搜索到表中任一元素的平均搜索長度為。A. nB. n+1C. (n-1)/2D. (n+1)/238. 對長度為10的順序表進展搜索(從表頭開始搜索)，假如搜索前面5個元素的概率一樣，均為1/8，搜索后面5個元素的概率一樣，均為3/40，如此搜索到表中任一元素的平均搜索長度為。A. 5.5B. 5C. 39/8D. 19/439. 對于長度為n的有序順序表，假如采用折半搜索，如此對所有元素的搜索長度中最大的為的值的向上取整。A. log2(n+1)B. log2nC. n/2D. (n+1)/240. 對于長度為n的有序順序表，假如采用折半搜索，如此對所有元素的搜索長度中最大的為的值的向下取整加一。A. log2(n+1)B. log2nC. n/2D. (n+1)/241. 對于長度為9的有序順序表，假如采用折半搜索，在等概率情況下搜索成功的平均搜索長度為的值除以9。A. 20B. 18C. 25D. 2242. 對于長度為18的有序順序表，假如采用折半搜索，如此搜索第15個元素的搜索長度為。A. 3B. 4C. 5 D. 643. 對具有n個元素的有序順序表進展折半搜索，如此搜索任一元素的時間復雜度為。A. O(n)B. O(n2)C. O(1)D. O(log2n)44. 對5個不同的數(shù)據元素進展直接插入排序，最多需要進展 次比擬？A.8B. 10C. 15D. 2545. 如果輸入序列是已經排好順序的，如此如下算法中 算法最快完畢？A. 起泡排序B. 直接插入排序C. 直接選擇排序D. 快速排序46. 如果輸入序列是已經排好順序的，如此如下算法中 算法最慢完畢？A. 起泡排序B. 直接插入排序C. 直接選擇排序D. 快速排序二、填空題1. 算法的五個重要特性是有窮性 、確定性、可行性、輸入和輸出。2. 設單鏈表中結點的結構為data, next。假如想摘除結點*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，如此判斷隊滿的條件為(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. 用簡單的模式匹配算法在主串"data_structure"中檢索子串string，總的比擬次數(shù)為12。8. 假定一棵三叉樹即度為3的樹的結點個數(shù)為50，如此它的最小高度為5。假定根結點的高度為1。9. 在一棵高度為3的四叉樹中，最多含有21結點。10. 在一棵三叉樹中，度為3的結點數(shù)有2個，度為2的結點數(shù)有1個，度為1的結點數(shù)為2個，那么度為0的結點數(shù)有6個。11. 一棵高度為5的完全二叉樹中，最多包含有31個結點。假定根結點的高度為1。12. 在一棵二叉樹中，假定度為2的結點個數(shù)為5個，度為1的結點個數(shù)為6個，如此葉結點數(shù)為6個。13. 假定一棵二叉樹的結點個數(shù)為18，如此它的最小高度為5。假定根結點的高度為1。14. 按照二叉樹的定義，具有5個結點的二叉樹有42種形態(tài)。15. 以順序搜索方法從長度為n的順序表或單鏈表中搜索一個元素時，其時間復雜度為O(n)。16. 對長度為n的搜索表進展搜索時，假定搜索第i個元素的概率為pi，搜索長度即在搜索過程中依次同有關元素比擬的總次數(shù)為ci，如此在搜索成功情況下的平均搜索長度的計算公式為。17. 假定一個順序表的長度為40，并假定搜索每個元素的概率都一樣，如此在搜索成功情況下的平均搜索長度為20.5。18. 以折半搜索方法從長度為n的有序表中搜索一個元素時，時間復雜度為O(log2n)。19. 從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時，其搜索長度為3。20. 假定對長度n=50的有序表進展折半搜索，如此對應的判定樹中最后一層的結點數(shù)為19個。21. 直接插入排序在最好情況下的比擬次數(shù)為，最壞情況下為。正序最好C=n-1，逆序最壞C=n*(n-1)/222. 直接插入排序在最好情況下的移動次數(shù)為，最壞情況下為。最好M=0，最壞M=(n+4)*(n-1)/223. 簡單項選擇擇法排序時比擬數(shù)據的次數(shù)為。任何情況下C=n*(n-1)/224. 簡單項選擇擇法排序在最好情況下的移動次數(shù)為，最壞情況下為。最好正序M=0，最壞非逆序，如6,1,2,3,4,5M=3*(n-1)25. 起泡排序在最好情況下的比擬次數(shù)為，最壞情況下為。最好正序C=n-1，最壞逆序C=n*(n-1)/226. 起泡排序在最好情況下的移動次數(shù)為，最壞情況下為。最好正序M=0，最壞逆序M=3*n*(n-1)/227. 在直接選擇排序中，排序碼比擬次數(shù)的時間復雜度為O(n2)。28. 在直接選擇排序中，數(shù)據對象移動次數(shù)的時間復雜度為O(n)。29. 快速排序在平均情況下的時間復雜度為O(nlog2n)。30. 快速排序在最壞情況下的時間復雜度為O(n2)。三、簡答題1. 下面程序段的時間復雜度是O(n*m)。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;2. 下面程序段的時間復雜度是O(n0.5)。i=s=0;while(s<n) i+; s+=i;3. 下面程序段的時間復雜度是O(n2)。s=0;for(i=0;i<n;i+) for(j=0;j<n;j+) s+=Bij;sum=s;4. 下面程序段的時間復雜度是O(log3n)。i=1;while(i<=n) i=i*3;5. 寫出如下程序段的輸出結果: 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); 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個帶權結點，其權值分別為3, 7, 8, 2, 6, 10, 14，試以它們?yōu)槿~結點生成一棵赫夫曼樹，求出該樹的帶權路徑長度：9. 設連通圖G如下列圖。試給出對它執(zhí)行從頂點V0開始的廣度優(yōu)先遍歷和深度優(yōu)先遍歷的結果。V0V1V2V5V4V3V6V7V8廣度優(yōu)先遍歷：012345678深度優(yōu)先遍歷：01325678410. 設有一個連通網絡如下列圖。試采用prim算法從頂點0開始構造最小生成樹。寫出參加生成樹頂點集合S和選擇邊Edge的順序1234650910751187頂點集合邊(頂點，頂點，權值)0(0 ， 1 ， 9 )01(1 ， 3 ， 5 )013(1 ， 2 ， 7 )0132(2 ， 4 ，6 )01324(2 ， 5 ，7 )01324511. 設帶權有向圖如下列圖。試采用Dijkstra算法求從頂點0到其他各頂點的最短路徑和最短路徑長度。7182445912340頂點號路徑長度路徑1401370328012410012411115191022344556612. 試對如下圖所示的AOE網絡(1) 這個工程最早可能在時間完畢。(2) 確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程提前完成。拓撲序列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ù)組a10中存儲著一個有序表，該有序表為：(15,26,34,39,45,56,58,63,74,76)，畫出折半搜索所對應的判定樹，并求出在等概率情況下搜索成功的平均搜索長度。平均搜索長度：2.914. 給定一組數(shù)據對象的排序碼為 46, 79, 56, 38, 40, 84，對其進展一趟快速排序，結果為40,38,46,56,79,84。四、算法設計題1. 設有一個順序表 (e0, e1, , en-2, en-1)。請編寫一個函數(shù)將這個順序表原地逆置，即順序表的內容置換為 (en-1, en-2, , e1, e0)。void Reverse(SqList *L)int i=0,j=L->length-1;ElemType t; for(;i<j;+i,-j) t=L->elemi;L->elemi=L->elemj;L->elemj=t; 2. 試編寫一個函數(shù)，用以刪除順序表L中所有值為x的元素要求就地工作。void DeleteX(SqList *L, ElemType x) int j=0;for(i=0;i<L->length;+i) if(L->elemi!=x)if(i>j)L->elemj=L->elemi; +j; 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(Rmid=k)return mid+1;else if(Rmid>k) high=mid-1;else low=mid+1;return 0;4. 試編寫一個函數(shù)，對數(shù)組r進展選擇法排序結果為正序。void SelectSort(ElemType r,int n)/對順序表r作簡單項選擇擇排序，n為數(shù)組元素個數(shù)int i,j,k;ElemType tmp;for(i=0;i<n-1;+i)k=i;for(j=i+1;j<n;+j)if(rj<rk)k=j;/k指向rin-1中的最小元素if(k!=i)tmp=ri; ri=rk; rk=tmp;