數(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)）。B.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系2 .數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)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.倜度方法A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和后窮性C.確定性、有窮性和穩(wěn)定性D.

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

3、表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,A.s->next=p;p->next=s;C.s->next=p->next;p=s;

4、則應(yīng)執(zhí)行下列哪一個(gè)操作？（）B. p->next=s;s->next=p;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)單鏈表firstA.p

5、->next=NULL;C.p->next=first;的尾結(jié)點(diǎn)（由p所指向）滿足：（）B.p=NULL;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ì)列的最大長度為（）。A.n-2B.n-1C.nD.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，則判斷

6、隊(duì)空的條件為（）。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.nB.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)為1）的完全二

7、叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于（）。A.2h-1B.2h+1C.2h-1D.2h。假定空樹的高度為0。D.8）。假定樹根結(jié)點(diǎn)的編號(hào)為1。D.M/2-123 .在一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹中，該樹的高度為（A.5B.6C.724 .在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，分支結(jié)點(diǎn)的最大編號(hào)為（A.H（n-1）/2B.M/2C.n/2)。假定根結(jié)點(diǎn)25 .在一棵完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左子女結(jié)點(diǎn)的編號(hào)為(的編號(hào)為1A.2iB.2i-1C.2i+1D.2i+226.27.28.29.30.31.32.33.34.35.36.37.在一棵完全二叉樹中，假定根結(jié)點(diǎn)的編號(hào)為1,則對(duì)于編號(hào)為i

8、(i>1)的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為()。A.|l(i+1)/2B.|l(i-1)/2C.|li/2D.|li/2-1設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多后()條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)n個(gè)頂點(diǎn)的連通圖至少有()條邊。A.n-1B.nC.n+1D.0在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。A.3B.2C.1D.1/2圖的深度優(yōu)先搜索類似于樹的()次序遍歷。A.先根B.中根C.后根D.層次圖的廣度優(yōu)先搜索類似于樹的()次序遍歷。A.先根B.中根C.后根D.層次n(n>1)個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()條有向邊。A.n-1B.

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

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

11、索成功的平均搜索長度為()的值除以9。A.20B.18C.25D.2242 .對(duì)于長度為18的有序順序表，若采用折半搜索，則搜索第15個(gè)元素的搜索長度為()。A.3B.4C.5D.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 .如果輸入序列是已經(jīng)排好順序的，則下列算法中()算法最快結(jié)束？A.起泡排序B.直接插入排序C.直接選擇排序D.快速排序46 .如果輸入序列是已經(jīng)排好順序的，則下列算法中()

12、算法最慢結(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->nextfree(q),3 .設(shè)循環(huán)隊(duì)列Q的隊(duì)頭和隊(duì)尾指針分別為front和rear，隊(duì)列的最大容量為MaxSize，且規(guī)定判斷隊(duì)空的條件為Q.front=Q.rear,則判斷隊(duì)滿的條件為(Q.rear+1)%MaxSize=Q.front,而計(jì)算隊(duì)列長度的表達(dá)式為

13、(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 .用簡單的模式匹配算法在主串"aaaaaab"中檢索子串"aab”,則總的比較次數(shù)為15。7 .用簡單的模式匹配算法在主串"data_structure"中檢索子串”string”，總的比較次數(shù)為12。8 ,假定一棵三叉科(即度為3的樹)

14、的結(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)的高度為1。14 .按照二叉樹的定義，具有5個(gè)結(jié)點(diǎn)的二叉樹有42種形態(tài)。15 .以順序搜索方法從長度為n的順序表或單鏈表中搜索一個(gè)

15、元素時(shí)，其時(shí)間復(fù)雜度為O(n)。16 .對(duì)長度為n的搜索表進(jìn)行搜索時(shí)，假定搜索第i個(gè)元素的概率為pi,搜索長度(即在搜索過程中依次同有關(guān)元素比較的總次數(shù))為ci,則在搜索成功情況下的平均搜索長度的計(jì)算公式為ASL="rg17 .假定一個(gè)順序表的長度為40,并假定搜索每個(gè)元素的概率都相同，則在搜索成功情況下的平均搜索長度為20.5。18 .以折半搜索方法從長度為n的有序表中搜索一個(gè)元素時(shí)，時(shí)間復(fù)雜度為O(log2n)。19 .從有序表(12,18,30,43,56,78,82,95)中折半搜索元素56時(shí)，其搜索長度為3。20 .假定對(duì)長度n=50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹中最

16、后一層的結(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 .簡單選擇法排序時(shí)比較數(shù)據(jù)的次數(shù)為。(任何情況下C=n*(n-1)/2)24 .簡單選擇法排序在最好情況下的移動(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 .起泡排序在最好情況下

17、的移動(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ù)雜度為0(n)。29 .快速排序在平均情況下的時(shí)間復(fù)雜度為0(nlog即)。30 .快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n2)。三、簡答題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

18、(nA2)qs=0;for(i=0;i<n;i+)for(j=0;j<n;j+)s+=Bij;sum=s;4 .下面程序段的時(shí)間復(fù)雜度是O(log3n)oi=1;while(i<=n)i=i*3;5 .寫出下列程序段的輸出結(jié)果:514263。voidmain()SqStackS;SqQueueQ;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

19、);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前序序列：,試以它們?yōu)?/p>

20、葉結(jié)點(diǎn)生成一棵赫夫曼樹,8.有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14求出該樹的帶權(quán)路徑長度：9,設(shè)連通圖G如圖所示。試給出對(duì)它執(zhí)行從頂點(diǎn)廣度優(yōu)先遍歷：012345678深度優(yōu)先遍歷：013256784V0開始的廣度優(yōu)先遍歷和深度優(yōu)先遍歷的結(jié)果。10,設(shè)有一個(gè)連通網(wǎng)絡(luò)如圖所示。試采用集合S和選擇邊Edge的順序）prim算法從頂點(diǎn)0開始構(gòu)造最小生成樹。（寫出加入生成樹頂點(diǎn)頂點(diǎn)集合邊（頂點(diǎn)，頂點(diǎn)，權(quán)值）0(0,1,9)011(1,3,5)013(1,2,7)0132(2,4,6)01324(2，5,7)01324511 .設(shè)帶權(quán)有向圖如圖所示。試采用Dijkstra算法求從頂點(diǎn)0

21、到其他各頂點(diǎn)的最短路徑和最短路徑長度。頂點(diǎn)號(hào)路徑長度路徑1401370328012410012412 .試對(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)的最早開始時(shí)間、最遲開始時(shí)間：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 .一個(gè)一維數(shù)組a10中存儲(chǔ)著一個(gè)有序表，該有序表為：(15,26,34,39,45,56,58,63,74,76),畫出折半搜索所對(duì)應(yīng)的判定樹，并求出在等概率情況下搜索成功的平均搜索長度。平均搜索長度：2.9,對(duì)其進(jìn)行一趟快速排序,14 .給定一組數(shù)據(jù)對(duì)象的排序碼為46,79,56,38,40,84)結(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)容置換為(en-1,en-2,，e1,e0)。voidReverse(Sq