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

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ī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)。A. 邏輯B. 存儲(chǔ)C. 邏輯和存儲(chǔ)D. 物理4. 計(jì)算機(jī)算法指的是 ，它必須具備輸入、輸出和 等5個(gè)特性。A. 計(jì)算方法B. 排序方法C. 解決問題的有限運(yùn)算序列D. 調(diào)度方法A. 可行性、可移植性和可擴(kuò)大性B. 可行性、確定性和有窮性C.

2、 確定性、有窮性和穩(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. O(n)B. O(n/2)C. O(1)

3、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)，假如在*p之后插入結(jié)點(diǎn)*s，如此應(yīng)執(zhí)行如下哪一個(gè)操作？ A. s-next = p; p-next = s;B

4、. 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-next; 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

5、; 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)度為 。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ì)尾指針分別為front和rear，如此判斷隊(duì)空的

6、條件為 。A. front+1=rearB. rear+1=frontC. front=0D. front=rear18. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加。A. 0B. 1C. -1D. 219. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加。A. 2B. 1C. 0D. -120. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于。A. n B. n-1C. n+1D. 2*n21. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹的第i層上假定根結(jié)點(diǎn)為第1層，i大于等于1而小于等于樹的高度，最多具有個(gè)結(jié)點(diǎn)。A. 2iB. 2i+1C. 2i-1D. 2n22. 在一棵高度為h假定根結(jié)點(diǎn)的層號(hào)為

7、1的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于。A. 2h-1B. 2h+1C. 2h-1D. 2h23. 在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹中，該樹的高度為。假定空樹的高度為0。A. 5B. 6C. 7D. 824. 在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，分支結(jié)點(diǎn)的最大編號(hào)為。假定樹根結(jié)點(diǎn)的編號(hào)為1。A.(n-1)/2B. n/2C. n/2D. n/2 -125. 在一棵完全二叉樹中，假如編號(hào)為i的結(jié)點(diǎn)存在左孩子，如此左子女結(jié)點(diǎn)的編號(hào)為。假定根結(jié)點(diǎn)的編號(hào)為1A. 2iB. 2i-1C. 2i+1D. 2i+226. 在一棵完全二叉樹中，假定根結(jié)點(diǎn)的編號(hào)為1，如此對(duì)于編號(hào)為ii1的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為

8、。A.(i+1)/2B. (i-1)/2C. i/2D. i/2-127. 設(shè)無向圖的頂點(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-1B.nC. n+1D. 029. 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 ( ) 倍。A. 3B.2C. 1D. 1/230. 圖的深度優(yōu)先搜索類似于樹的 次序遍歷。A. 先根B. 中根C. 后根D. 層次31. 圖的廣度優(yōu)先搜索類似于樹的 次序遍歷。A. 先根B. 中根C. 后根D. 層次32. n(n1) 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有

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

10、索到表中任一元素的平均搜索長(zhǎng)度為。A. nB. n+1C. (n-1)/2D. (n+1)/238. 對(duì)長(zhǎng)度為10的順序表進(jìn)展搜索(從表頭開始搜索)，假如搜索前面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)度中最大的為的值的向下取整加

11、一。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. 4C. 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)展 次比擬？A.8B. 10C. 15D. 2545. 如

12、果輸入序列是已經(jīng)排好順序的，如此如下算法中 算法最快完畢？A. 起泡排序B. 直接插入排序C. 直接選擇排序D. 快速排序46. 如果輸入序列是已經(jīng)排好順序的，如此如下算法中 算法最慢完畢？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;free(q);3. 設(shè)循環(huán)隊(duì)列Q的隊(duì)頭和隊(duì)尾指針分別為front和rear，隊(duì)列的最大容量為MaxSize

13、，且規(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。如此可能的出棧序列有1430種。6. 用簡(jiǎn)單的模式匹配算法在主串a(chǎn)aaaaab中檢索子串a(chǎn)ab，如此總的比擬次數(shù)為15。7. 用簡(jiǎn)單

14、的模式匹配算法在主串data_structure中檢索子串string，總的比擬次數(shù)為12。8. 假定一棵三叉樹即度為3的樹的結(jié)點(diǎn)個(gè)數(shù)為50，如此它的最小高度為5。假定根結(jié)點(diǎn)的高度為1。9. 在一棵高度為3的四叉樹中，最多含有21結(jié)點(diǎn)。10. 在一棵三叉樹中，度為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的完全二叉樹中，最多包含有31個(gè)結(jié)點(diǎn)。假定根結(jié)點(diǎn)的高度為1。12. 在一棵二叉樹中，假定度為2的結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，如此葉結(jié)點(diǎn)數(shù)為6個(gè)。13. 假定一棵二叉樹的結(jié)點(diǎn)個(gè)數(shù)為18，如此它的最小高度為5。假定根結(jié)點(diǎn)

15、的高度為1。14. 按照二叉樹的定義，具有5個(gè)結(jié)點(diǎn)的二叉樹有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ān)元素比擬的總次數(shù)為ci，如此在搜索成功情況下的平均搜索長(zhǎng)度的計(jì)算公式為。17. 假定一個(gè)順序表的長(zhǎng)度為40，并假定搜索每個(gè)元素的概率都一樣，如此在搜索成功情況下的平均搜索長(zhǎng)度為20.5。18. 以折半搜索方法從長(zhǎng)度為n的有序表中搜索一個(gè)元素時(shí)，時(shí)間復(fù)雜度為O(log2n)。19. 從有序表(12,18,30,43,56,78,82,9

16、5)中折半搜索元素56時(shí)，其搜索長(zhǎng)度為3。20. 假定對(duì)長(zhǎng)度n=50的有序表進(jìn)展折半搜索，如此對(duì)應(yīng)的判定樹中最后一層的結(jié)點(diǎn)數(shù)為19個(gè)。21. 直接插入排序在最好情況下的比擬次數(shù)為，最壞情況下為。正序最好C=n-1，逆序最壞C=n*(n-1)/222. 直接插入排序在最好情況下的移動(dòng)次數(shù)為，最壞情況下為。最好M=0，最壞M=(n+4)*(n-1)/223. 簡(jiǎn)單項(xiàng)選擇擇法排序時(shí)比擬數(shù)據(jù)的次數(shù)為。任何情況下C=n*(n-1)/224. 簡(jiǎn)單項(xiàng)選擇擇法排序在最好情況下的移動(dòng)次數(shù)為，最壞情況下為。最好正序M=0，最壞非逆序，如6,1,2,3,4,5M=3*(n-1)25. 起泡排序在最好情況下的比擬次

17、數(shù)為，最壞情況下為。最好正序C=n-1，最壞逆序C=n*(n-1)/226. 起泡排序在最好情況下的移動(dòng)次數(shù)為，最壞情況下為。最好正序M=0，最壞逆序M=3*n*(n-1)/227. 在直接選擇排序中，排序碼比擬次數(shù)的時(shí)間復(fù)雜度為O(n2)。28. 在直接選擇排序中，數(shù)據(jù)對(duì)象移動(dòng)次數(shù)的時(shí)間復(fù)雜度為O(n)。29. 快速排序在平均情況下的時(shí)間復(fù)雜度為O(nlog2n)。30. 快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n2)。三、簡(jiǎn)答題1. 下面程序段的時(shí)間復(fù)雜度是O(n*m)。for(i=0;in;i+) for(j=0;jm;j+) Aij=0;2. 下面程序段的時(shí)間復(fù)雜度是O(n0.5)。i=

18、s=0;while(sn) i+; s+=i;3. 下面程序段的時(shí)間復(fù)雜度是O(n2)。s=0;for(i=0;in;i+) for(j=0;jn;j+) s+=Bij;sum=s;4. 下面程序段的時(shí)間復(fù)雜度是O(log3n)。i=1;while(i=n) i=i*3;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(&

19、Q,e); for(i=1;i=n;+i) DeQueue(&Q,&e); Push(&S,e); for(i=1;ilength-1;ElemType t; for(;ielemi;L-elemi=L-elemj;L-elemj=t; 2. 試編寫一個(gè)函數(shù)，用以刪除順序表L中所有值為x的元素要求就地工作。void DeleteX(SqList *L, ElemType x) int j=0;for(i=0;ilength;+i) if(L-elemi!=x)if(ij)L-elemj=L-elemi; +j; L-length=j;3. 試編寫一個(gè)函數(shù)，在數(shù)組R已正序排列中進(jìn)展折半查找某個(gè)值

20、k，找到如此返回其位置，否如此返回0。int SearchBin(int R, int n, int k)/有序正序的順序表的二分查找，n為數(shù)組元素個(gè)數(shù)，k為待查找的值int low=0,high=n-1,mid;while(lowk) high=mid-1;else low=mid+1;return 0;4. 試編寫一個(gè)函數(shù)，對(duì)數(shù)組r進(jìn)展選擇法排序結(jié)果為正序。void SelectSort(ElemType r,int n)/對(duì)順序表r作簡(jiǎn)單項(xiàng)選擇擇排序，n為數(shù)組元素個(gè)數(shù)int i,j,k;ElemType tmp;for(i=0;in-1;+i)k=i;for(j=i+1;jn;+j)if(rjrk)k=j;/k指向rin-1中的最小元素if(k!=i)tmp=ri; ri=rk; rk=tmp;