數(shù)據(jù)結構試卷帶答案

數(shù)據(jù)結構試卷〔一)一、選擇題〔20分〕組成數(shù)據(jù)的根本單位是〔1.C〕。數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量設數(shù)據(jù)結構A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},那么數(shù)據(jù)結構入是〔C〕。(A)線性結構(B)樹型結構(C)圖型結構(D)集合數(shù)組的邏輯結構不同于以下〔D〕的邏輯結構。(A)線性表(B)棧(C)隊列(D)樹二叉樹中第i(iN1)層上的結點數(shù)最多有〔C〕個。(A)2i(B)2i(C)2i-i(D)2i-1設指針變量p指向單鏈表結點A,那么刪除結點A的后繼結點B需要的操作為〔.A〕。p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)p->next=p設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進入隊列Q,假設6個元素出列的順序為E2、E4、E3、E6、E5和E1,那么棧S的容量至少應該是〔.C〕。TOC\o"1-5"\h\z(A)6(B)4(C)3(D)2將10階對稱矩陣壓縮存儲到一維數(shù)組A中，那么數(shù)組A的長度最少為〔C〕。(A)100(B)40(C)55(D)80設結點A有3個兄弟結點且結點B為結點A的雙親結點，那么結點B的度數(shù)數(shù)為〔8.B(A)3(B)4(C)5(D)1根據(jù)二叉樹的定義可知二叉樹共有〔B〕種不同的形態(tài)。(A)4(B)5(C)6(D)7設有以下四種排序方法，那么〔B〕的空間復雜度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序二、填空題(30分)設順序循環(huán)隊列Q[0：m-1]的隊頭指針和隊尾指針分別為F和R,其中隊頭指針F指向當前隊頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的位置，那么出隊列的語句為F=；。設線性表中有n個數(shù)據(jù)元素，那么在順序存儲結構上實現(xiàn)順序查找的平均時間復雜度為，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為。設一棵二叉樹中有n個結點，那么當用二叉鏈表作為其存儲結構時，該二叉鏈表中共個指針域，個空指針域。設指針變量p指向單鏈表中結點A,指針變量s指向被插入的結點B,那么在結點A的后面插入結點B的操作序列為。設無向圖G中有n個頂點和e條邊，那么其對應的鄰接表中有個表頭結點和個表結點。設無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m,那么e和m有關系。設一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,那么該二叉樹的后序遍歷序列為設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從1開始順序編號，那么編號為8的雙親結點的編號是，編號為8的左孩子結點的編號是。以下程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。intindex(chars[],chart[]){i=j=0;

while(i<strlen(s)&&j<strlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i=;j=;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}設一個連通圖G中有n個頂點e條邊，那么其最小生成樹上有條邊。三、應用題〔30分)設完全二叉樹的順序存儲結構中存儲數(shù)據(jù)ABCDE,要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。設給定一個權值集合W=(3,5,7,9,11),要求根據(jù)給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。設一組初始記錄關鍵字序列為(19,21,16,5,18,23)，要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。設一組初始記錄關鍵字集合為(25,10,8,27,32,68)，散列表的長度為8,散列函數(shù)H(k)=kmod7,要求分別用線性探測和鏈地址法作為解決沖突的方法設計哈希表。設無向圖G〔所右圖所示〕，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設計題(20分)設計判斷單鏈表中結點是否關于中心對稱算法。設計在鏈式存儲結構上建立一棵二叉樹的算法。設計判斷一棵二叉樹是否是二叉排序樹的算法。數(shù)據(jù)結構試卷〔一)參考答案一、選擇題5.A6.C7.C8.B9.B10.BC2.C3.D4.C二、填空題(F+1)%mO(n),O(n)2n,n+1s->next=p->next;p->next=sn,2eTOC\o"1-5"\h\zm=2eCBA4,16i-j+1,0n-1三、應用題鏈式存儲結構略，前序ABDEC,哈夫曼樹略，WPL=78(18,5,16,19,21,23),(5,16,中序DBEAC，后序DEBCA。21,19,4.234A102556322718,23)h0h_>85.A6.C7.C8.B9.B10.B三、應用題鏈式存儲結構略，前序ABDEC,哈夫曼樹略，WPL=78(18,5,16,19,21,23),(5,16,中序DBEAC，后序DEBCA。21,19,4.234A102556322718,23)h0h_>8「h7,,,268鏈地址法：h3->10h->25->32h4->68h6->275.深度：125364,廣度：123456,最小生成樹T的邊集為E={(1,4),(1,3),(3,5),(5,6),(5,6)}四、算法設計題設計判斷單鏈表中結點是否關于中心對稱算法。typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack.top=-1;lklist*p;for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;}for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}設計在鏈式存儲結構上建立一棵二叉樹的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;scanf("%c”,&ch);if(ch=='#'){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);}設計判斷一棵二叉樹是否是二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}數(shù)據(jù)結構試卷〔二〕一、選擇題(24分)下面關于線性表的表達錯誤的選項是〔.D線性表采用順序存儲必須占用一片連續(xù)的存儲空間線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)設哈夫曼樹中的葉子結點總數(shù)為m,假設用二叉鏈表作為存儲結構，那么該哈夫曼樹中總共有〔B〕個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，那么該循環(huán)隊列中的元素個數(shù)為〔3.C〕。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，那么后序遍歷該二叉樹得到序列為〔4.A〕。(A)BADC(B)BCDA(C)CDAB(D)CBDA設某完全無向圖中有n個頂點，那么該完全無向圖中有〔5.A〕條邊。

(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1設某棵二叉樹中有2000個結點，那么該二叉樹的最小高度為〔C〕。(A)9(B)10(C)11(D)12設某有向圖中有n個頂點，那么該有向圖對應的鄰接表中有〔B〕個表頭結點。(A)n-1(B)n(C)n+1(D)2n-1設一組初始記錄關鍵字序列(5,2,6,3,8),以第一個記錄關鍵字5為基準進行一趟快速排序的結果為〔8.C〕。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空題(24分)為了能有效地應用HASH查找技術，必須解決的兩個問題是構造一個好的HASH函數(shù)和_確定解決沖突的方法。下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-printf("overf)owelse{;；}}中序遍歷二叉排序樹所得到的序列序列〔填有序或無序〕?？焖倥判虻淖顗臅r間復雜度為，平均時間復雜度為。設某棵二叉樹中度數(shù)為0的結點數(shù)為N。，度數(shù)為1的結點數(shù)為眈，那么該二叉樹中度數(shù)為2的結點數(shù)為；假設采用二叉鏈表作為該二叉樹的存儲結構，那么該二叉樹中共個空指針域。設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,那么e=。設一組初始記錄關鍵字序列為(55,63,44,38,75,80,31,56)，那么利用篩選法建立的初始堆為。v1v8.v1v8.設某無向圖G的鄰接表為2v3v4311123432,那么從頂點V1開始的深度優(yōu)先遍歷序列為；廣度優(yōu)先遍歷序列為。三、應用題(36分)設一組初始記錄關鍵字序列為(45,80,48,40,22,78),那么分別給出第4趟簡單項選擇擇排序和第4趟直接插入排序后的結果。設指針變量P指向雙向鏈表中結點A,指針變量q指向被插入結點B,要求給出在結點A的后面插入結點B的操作序列〔設雙向鏈表中結點的兩個指針域分別為llink和rlink〕。設一組有序的記錄關鍵字序列為(13,18,24,35,47,50,62,83,90)，查找方法用二分查找，要求計算出查找關鍵字62時的比擬次數(shù)并計算出查找成功時的平均查找長度。設一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。(5)(S設有無向圖仔〔如右圖所示〕，要求給出用普里姆算法構造最小生成樹所走(5)(S設有一組初始記錄關鍵字為(45,80,48,40,22,78),要求構造一棵二叉排序樹并給出構造過程。四、算法設計題(16分)設有一組初始記錄關鍵字序列〔K「K2，…，K〕，要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩局部，其中左半局部的每個關鍵字均小于％,右半局部的每個關鍵字均大于等于嗎。設有兩個集合A和集合B,要求設計生成集合C=AHB的算法，其中集合A、B和C用鏈式存儲結構表示。數(shù)據(jù)結構試卷〔二)參考答案一、選擇題D2.B3.C4.A5.A6.C7.B8.C二、填空題構造一個好的HASH函數(shù)，確定解決沖突的方法stack.top++,stack.s[stack.top]=x有序O(n2),O(nlog2n)N0-1,2N0+N1d/27.(31,38,54,56,75,80,55,63)8.(1,3,4,2),(1,3,2,4)三、應用題1.(22,40,45,48,80,78),(40,45,48,80,22,78)q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9樹的鏈式存儲結構略，二叉樹略E={(1,3),(1,2),(3,5),(5,6),(6,4)}略四、算法設計題設有一組初始記錄關鍵字序列〔％,、，???，K〕，要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩局部，其中左半局部的每個關鍵字均小于嗎，右半局部的每個關鍵字均大于等于嗎。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設有兩個集合A和集合B,要求設計生成集合C=AHB的算法，其中集合A、B和C用鏈式存儲結構表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}數(shù)據(jù)結構試卷〔三〕一、選擇題(30分)設某數(shù)據(jù)結構的二元組形式表示為A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},那么數(shù)據(jù)結構入是〔B〕。(A)線性結構(B)樹型結構(C)物理結構(D)圖型結構下面程序的時間復雜為〔B〕for〔i=1,s=0；i<=n；i++〕{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)設指針變量p指向單鏈表中結點A,假設刪除單鏈表中結點A,那么需要修改指針的操作序列為〔A〕。q=p->next；p->data=q->data；p->next=q->next；free(q)；q=p->next；q->data=p->data；p->next=q->next；free(q)；q=p->next；p->next=q->next；free(q)；q=p->next；p->data=q->data；free(q)；設有n個待排序的記錄關鍵字，那么在堆排序中需要〔A〕個輔助記錄單元。(A)1(B)n(C)nlog2n(D)n2設一組初始關鍵字記錄關鍵字為(20,15,14,18,21,36,40,10),那么以20為基準記錄的一趟快速排序結束后的結果為(A)。(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,21(C)10,15,14,20,18,40,36,21(D)15,10,14,18,20,36,40,216?設二叉排序樹中有n個結點，那么在二叉排序樹的平均平均查找長度為〔B〕。(A)O(1)(B)O(log2n)(C)O(n)(D)O(n2)設無向圖G中有n個頂點e條邊，那么其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為〔D〕。(A)n,e(B)e,n(C)2n,e(D)n,2e設某強連通圖中有n個頂點，那么該強連通圖中至少有〔C〕條邊。(A)n(n-1)(B)n+1(C)n(D)n(n+1)設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，那么用以下〔B〕方法可以到達此目的。(A)快速排序(B)堆排序(C)歸并排序(D)插入排序以下四種排序中〔D〕的空間復雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序二、填空殖(48分，其中最后兩小題各6分)數(shù)據(jù)的物理結構主要包括和兩種情況。設一棵完全二叉樹中有500個結點，那么該二叉樹的深度為—9；假設用二叉鏈表作為該完全二叉樹的存儲結構，那么共有501個空指針域。設輸入序列為1、2、3,那么經(jīng)過棧的作用后可以得到5種不同的輸出序列。設有向圖G用鄰接矩陣A[n][n]作為存儲結構，那么該鄰接矩陣中第i行上所有元素之和等于頂點i的—出度，第i列上所有元素之和等于頂點i的―入度。設哈夫曼樹中共有n個結點，那么該哈夫曼樹中有0個度數(shù)為1的結點。設有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,那么e和d的關系為__e=d。―中序遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列〔填先序、中序或后序。設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,那么最多需要比擬7次就可以斷定數(shù)據(jù)元素X是否在查找表中。不管是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為__O(n)。設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，那么第i個結點的雙親結點編號為—[i/2]，右孩子結點的編號為—2i+1。設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，那么以記錄關鍵字72為基準的一趟快速排序結果為__(5,16,23,71,72,73,94)。設有向圖G中有向邊的集合E={＜1，2＞，＜2，3＞，＜1，4＞，＜4，2＞，＜4，3＞}，那么該圖的一種拓撲序列為__1,4,2,3。以下算法實現(xiàn)在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(_j+1)%m;if(i==j)return(-1);}if()return(j);elsereturn(-1);}以下算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t-＞key==k);elseif(t-＞key＞k)t=t-＞lchild;else;}三、算法設計題(22分)設計在單鏈表中刪除值相同的多余結點的算法。設計一個求結點x在二叉樹中的雙親結點算法。數(shù)據(jù)結構試卷〔三〕參考答案一、選擇題B2.B3.A4.A5.AB7.D8.C9.B10.D第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的根底上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。二、填空題順序存儲結構、鏈式存儲結構TOC\o"1-5"\h\z9，5015出度，入度0e=d中序70(1)i/2,2i+1(5,16,71,23,72,94,73)(1,4,3,2)j+1,hashtable[j].key==kreturn(t),t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。三、算法設計題2設計在單鏈表中刪除值相同的多余結點的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設計一個求結點x在二叉樹中的雙親結點算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c”,bt->data);elseprintf("notparent");}數(shù)據(jù)結構試卷〔四)一、選擇題(30分)設一維數(shù)組中有n個數(shù)組元素，那么讀取第i個數(shù)組元素的平均時間復雜度為〔〕。(A)0(n)(B)0(nlog2n)(C)0(1)(D)0(m)設一棵二叉樹的深度為k,那么該二叉樹中最多有〔〕個結點。(A)2k-1(B)2k(C)2k-1(D)2k-1設某無向圖中有n個頂點e條邊，那么該無向圖中所有頂點的入度之和為〔〕。(A)n(B)e(C)2n(D)2e在二叉排序樹中插入一個結點的時間復雜度為〔〕。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)設某有向圖的鄰接表中有n個表頭結點和m個表結點，那么該圖中有〔〕條有向邊。(A)n(B)n-1(C)m(D)m-1設一組初始記錄關鍵字序列為(345,253,674,924,627),那么用基數(shù)排序需要進行〔〕趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A)3(B)4(C)5(D)8設用鏈表作為棧的存儲結構那么退棧操作〔〕。(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何判別以下四種排序中〔〕的空間復雜度最大。TOC\o"1-5"\h\z(A)快速排序(B)冒泡排序(C)希爾排序(D)堆設某二叉樹中度數(shù)為0的結點數(shù)為No，度數(shù)為1的結點數(shù)為眈，度數(shù)為2的結點數(shù)為凡，那么以下等式成立的是〔〕?！?(A)N=N+1(B)N=N+N(C)N=N+1(D)N=2N+l010l20201設有序順序表中有n個數(shù)據(jù)元素，那么利用二分查找法查找數(shù)據(jù)元素X的最多比擬次數(shù)不超過〔〕。(A)logn+1(B)logn-1(C)logn(D)log(n+1)二、填空題(42分)22設有n個無序的記錄關鍵字，那么直接插入排序的時間復雜度，快速排序的平均時間復雜度為。設指針變量p指向雙向循環(huán)鏈表中的結點X,那么刪除結點X需要執(zhí)行的語句序列為〔設結點中的兩個指針域分別為llink和rlink〕。根據(jù)初始關鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為。深度為k的完全二叉樹中最少有個結點。設初始記錄關鍵字序列為(K「K2,…，K)那么用篩選法思想建堆必須從第個元素開始進行篩選。設哈夫曼樹中共有99個結點，那么該樹中有個葉子結點；假設采用二叉鏈表作為存儲結構，那么該樹中有個空指針域。設有一個順序循環(huán)隊列中有M個存儲單元，那么該循環(huán)隊列中最多能夠存儲個隊列元素；當前實際存儲個隊列元素〔設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置〕。設順序線性表中有n個數(shù)據(jù)元素，那么第i個位置上插入一個數(shù)據(jù)元素需要移動表中個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中個元素。設一組初始記錄關鍵字序列為(20,18,22,16,30,19)，那么以20為中軸的一趟快速排序結果為設一組初始記錄關鍵字序列為(20,18,22,16,30,19),那么根據(jù)這些初始關鍵字序列建成的初始堆為。設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，那么頂點i和頂點j互為鄰接點的條件是。設無向圖對應的鄰接矩陣為A,那么A中第i上非0元素的個數(shù)第i列上非0元素的個數(shù)〔填等于，大于或小于〕。設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC,那么后序遍歷該二叉樹的序列為。設散列函數(shù)H(k)=kmodp,解決沖突的方法為鏈地址法。要求在以下算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。typedefstructnode{intkey;structnode*next;}Iklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;i<m;i++);for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];;}}三、算法設計題(28分)設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。在鏈式存儲結構上建立一棵二叉排序樹。數(shù)據(jù)結構試卷〔四)參考答案一、選擇題C2.D3.D4.B5.C6.A7.B8.A9.C10.A二、填空題0(n2),O(nlog2n)p>llink->rlink=p->rlink;p->rlink->llink=p->rlinkTOC\o"1-5"\h\z3\o"CurrentDocument"2k-1n/250，51m-1,(R-F+M)%Mn+1-i,n-i(19,18,16,20,30,22)(16,18,19,20,32,22)A[i][j]=1等于BDCAhashtable[i]=0,hashtable[k]=s三、算法設計題設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}在鏈式存儲結構上建立一棵二叉排序樹。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}數(shù)據(jù)結構試卷〔五)一、選擇題(30分)數(shù)據(jù)的最小單位是〔A〕。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量設一組初始記錄關鍵字序列為(50,40,95,20,15,70,60,45)，那么以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為〔〕。(A)40,50,20,95(B)15,40,60,20(C)15,20,40,45(D)45,40,15,20設一組初始記錄關鍵字序列為(25,50,15,35,80,85,20,40,36,70)，其中含有5個長度為2的有序子表，那么用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為〔〕。(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,85函數(shù)substr("DATASTRUCTURE〃，5,9)的返回值為〔〕。(A)“STRUCTURE"(B)"DATA”(C)“ASTRUCTUR"(D)"DATASTRUCTURE”設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，那么該操作的時間復雜度為〔〕。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)設一棵m叉樹中度數(shù)為0的結點數(shù)為No，度數(shù)為1的結點數(shù)為N「，度數(shù)為m的結點數(shù)為Nm,那么N0=〔〕?！?A)眈+鹽+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N「……+(m-1)Nm(D)2Ni+3N2+……+(m+1)Nm設有序表中有41000個元素，那么用二分查找查找元素X最多需要比擬〔〕次。(A)25(B)10(C)7(D)1設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，那么從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為〔〕。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，那么輸出序列中第i個輸出元素是〔〕。(A)n-i(B)n-1-i(C)n+1-i(D)不能確定10設一組初始記錄關鍵字序列為(45,80，55,40,42，85)，那么以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是〔C〕。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80二、填空題(共30分)設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，那么判斷共享棧滿的條件是。在圖的鄰接表中用順序存儲結構存儲表頭結點的優(yōu)點是。設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素〔包括對角線上元素〕存放在n(n+1)個連續(xù)的存儲單元中，那么A[i][j]與A[0][0]之間有個數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為表:隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為表。設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF，那么該二叉樹的前序遍歷序列為，中序遍歷序列為，后序遍歷序列為。設一棵完全二叉樹有128個結點，那么該完全二叉樹的深度為，有個葉子結點。設有向圖G的存儲結構用鄰接矩陣A來表示，那么A中第i行中所有非零元素個數(shù)之和等于頂點i的，第i列中所有非零元素個數(shù)之和等于頂點i的。設一組初始記錄關鍵字序列(k「k2,……，匕)是堆，那么對i=1，2,…，n/2而言滿足的條件為。下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<;j++)if(r[j]>r[j+1]){temp=r[j+1];;r[j]=temp;exchange=1;}if(exchange==0)return；}}下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。

structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){;if(r[mid].key==k)return(mid+1);elseif()high=mid-1;elselow=mid+1;}return(0);}三、應用題(24分)設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC,要求給出該4二叉樹的的后序遍歷序列。設無向圖G〔如右圖所示〕，給出該圖的最小生成樹上邊的集合并計算最小生8成樹各邊上的權值之和。設一組初始記錄關鍵字序列為(15，17，18,22,35,51，60)，要求計算出成①一^-一^①功查找時的平均查找長度。設散列表的長度為8，散列函數(shù)H(k)=kmod7,初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。四、算法設計題(16分)設計判斷兩個二叉樹是否相同的算法。設計兩個有序單鏈表的合并排序算法。數(shù)據(jù)結構試卷〔五)參考答案一、選擇題1.A2.B3.A4.A5.D6.B7.B8.B9.C10.C二、填空題top1+1=top2可以隨機訪問到任一個頂點的簡單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，64出度，入度&WWi&&ki<=kEn-i，r[j+1]=r[j]mid=(low+high)/2，r[mid].key>k三、應用題DEBCAE={(1,5),(5,2),(5,3),(3,4)},W=10ASL=(1*1+2*2+3*4)/7=17/7ASL1=7/6，ASL2=4/3四、算法設計題設計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0IIbt2==0Ilbt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}設計兩個有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}數(shù)據(jù)結構試卷〔六)一、選擇題(30分)設一組權值集合W={2,3,4,5,6},那么由該權值集合構造的哈夫曼樹中帶權路徑長度之和為〔〕。(A)20(B)30(C)40(D)45執(zhí)行一趟快速排序能夠得到的序列是〔〕。(A)[41,12,34,45,27]55[72,63](B)[45,34,12,41]55[72,63,27](C)[63,12,34,45,27]55[41,72](D)[12,27,45,41]55[34,63,72]設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，那么其判空條件是〔〕。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是〔〕。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序設二叉樹的先序遍歷序列和后序遍歷序列正好相反，那么該二叉樹滿足的條件是〔〕。(A)空或只有一個結點(B)高度等于其結點數(shù)(C)任一結點無左孩子(D)任一結點無右孩子一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是〔〕。(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序設某棵三叉樹中有40個結點，那么該三叉樹的最小高度為〔〕。(A)3(B)4(C)5(D)6順序查找不管在順序線性表中還是在鏈式線性表中的時間復雜度為〔〕。(A)O(n)(B)O(n2)(C)O(ni/2)(D)O(1og2n)二路歸并排序的時間復雜度為〔〕。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)深度為k的完全二叉樹中最少有〔〕個結點。22(A)2k-i-1(B)2k-i(C)2k-i+1(D)2k-1設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X,那么入隊列的操作序列為〔〕。(A)front-〉next=s；front=s；(B)s-〉next=rear；rear=s；(C)rear-〉next=s；rear=s；(D)s-〉next=front；front=s；設某無向圖中有n個頂點e條邊，那么建立該圖鄰接表的時間復雜度為〔〕。O(n+e)(B)O(n2)(C)O(ne)(D)O(n3)設某哈夫曼樹中有199個結點，那么該哈夫曼樹中有〔〕個葉子結點。(A)99(B)100(C)101(D)102設二叉排序樹上有n個結點，那么在二叉排序樹上查找結點的平均時間復雜度為〔〕。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)設用鄰接矩陣A表示有向圖G的存儲結構，那么有向圖G中頂點1的入度為〔〕。(A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和(C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和二、判斷題(20分)調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。〔〕分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關?！病趁芭菖判蛟诔跏缄P鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多?！病碀M二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。〔〕設一棵二叉樹的先序序列和后序序列，那么能夠唯一確定出該二叉樹的形狀。〔〕層次遍歷初始堆可以得到一個有序的序列?！病吃O一棵樹T可以轉化成二叉樹BT，那么二叉樹BT中一定沒有右子樹?！病尘€性表的順序存儲結構比鏈式存儲結構更好?！病持行虮闅v二叉排序樹可以得到一個有序的序列?！病晨焖倥判蚴桥判蛩惴ㄖ衅骄阅茏詈玫囊环N排序?！病橙⑻羁疹}(30分)for(i=1，t=1，s=0；i＜=n；i++){t=t*i；s=s+t；}的時間復雜度為。設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，那么進行插入操作的語句序列為〔設結點的指針域為next〕。設有向圖G的二元組形式表示為G=〔D，R〕，D={1，2,3,4,5}，R={r}，r={＜1,2＞，＜2,4＞，＜4,5＞，＜1,3＞，＜3,2＞，＜3,5＞}，那么給出該圖的一種拓撲排序序列。設無向圖G中有n個頂點，那么該無向圖中每個頂點的度數(shù)最多是。設二叉樹中度數(shù)為0的結點數(shù)為50，度數(shù)為1的結點數(shù)為30，那么該二叉樹中總共有個結點數(shù)。設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，那么判斷該循環(huán)隊列為空的條件為設二叉樹中結點的兩個指針域分別為Ichild和rchild，那么判斷指針變量p所指向的結點為葉子結點的條件是。簡單項選擇擇排序和直接插入排序算法的平均時間復雜度為。快速排序算法的空間復雜度平均情況下為，最壞的情況下為。散列表中解決沖突的兩種方法是和。四、算法設計題(20分)1.設計在順序有序表中實現(xiàn)二分查找的算法。設計判斷二叉樹是否為二叉排序樹的算法。在鏈式存儲結構上設計直接插入排序算法數(shù)據(jù)結構試卷〔六)參考答案一、選擇題1.D2.A3.A4.A5.D6.D7.B8.A9.C10.B11.C12.A13.B14.D15.B二、判D斷題TOC\o"1-5"\h\z錯2.對3.對4.對5.錯錯7.對8.錯9.對10.對三、填空題O(n)s->next=p->next;p->next=s(1,3,2,4,5)n-1129F==Rp->lchild==0&&p->rchild==0O(n2)O(nlog2n),O(n)開放定址法，鏈地址法四、算法設計題設計在順序有序表中實現(xiàn)二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}設計判斷二叉樹是否為二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}在鏈式存儲結構上設計直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}數(shù)據(jù)結構試卷〔七）一、選擇題(30分)設某無向圖有n個頂點，那么該無向圖的鄰接表中有〔〕個表頭結點。(A)2n(B)n(C)n/2(D)n(n-1)設無向圖G中有n個頂點，那么該無向圖的最小生成樹上有〔〕條邊。(A)n(B)n-1(C)2n(D)2n-1設一組初始記錄關鍵字序列為(60,80,55,40,42,85),那么以第一個關鍵字45為基準而得到的一趟快速排序結果是〔〕。(A)40,42,60,55,80,85(B)42,45,55,60,85,80(C)42,40,55,60,80,85(D)42,40,60,85,55,80〔〕二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，那么編號為i結點的左孩子結點的編號為〔〕。(A)2i+1(B)2i(C)i/2(D)2i-1程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復雜度為〔〕。(A)O(n)(B)O(nlog2n)(C)O(m)(D)O(n3/2)設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，那么其判空條件是〔〕。(A)head==0(B)head-〉next==0(C)head-〉next==head(D)head!=0設某棵二叉樹的高度為10，那么該二叉樹上葉子結點最多有〔〕。(A)20(B)256(C)512(D)1024設一組初始記錄關鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),那么利用二分法查找關鍵字90需要比擬的關鍵字個數(shù)為〔〕。(A)1(B)2(C)3(D)4設指針變量top指向當前鏈式棧的棧頂，那么刪除棧頂元素的操作序列為〔〕。(A)top=top+1;(B)top=top-1;(C)top-〉next=top;(D)top=top-〉next;二、判斷題(20分)不管是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出〃情況?！病钞斚蚨媾判驑渲胁迦胍粋€結點，那么該結點一定成為葉子結點?！病吃O某堆中有n個結點，那么在該堆中插入一個新結點的時間復雜度為O(log2n)?！病惩耆鏄渲械娜~子結點只可能在最后兩層中出現(xiàn)?！病?哈夫曼樹中沒有度數(shù)為1的結點?！病硨B通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點?！病诚刃虮闅v一棵二叉排序樹得到的結點序列不一定是有序的序列。〔〕由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。〔〕線性表中的所有元素都有一個前驅元素和后繼元素?！病硯酂o向圖的最小生成樹是唯一的?！病橙⑻羁疹}(30分)設指針變量p指向雙向鏈表中的結點A,指針變量s指向被插入的結點X,那么在結點A的后面插入結點X的操作序列為=p；s-〉right=p-〉right；=s；p-〉right-〉left=s；〔設結點中的兩個指針域分別為left和right〕。設完全有向圖中有n個頂點，那么該完全有向圖中共有條有向條；設完全無向圖中有n個頂點，那么該完全無向圖中共有條無向邊。設關鍵字序列為(K「K2，…，Kn),那么用篩選法建初始堆必須從第個元素開始進行篩選。解決散列表沖突的兩種方法是°和。設一棵三叉樹中有50個度數(shù)為0的結點，21個度數(shù)為2的結點，那么該二叉樹中度數(shù)為3的結點數(shù)有個。高度為h的完全二叉樹中最少有__2卜1個結點，最多有_2h-1個結點。設有一組初始關鍵字序列為(24,35，12,27，18,26)，那么第3趟直接插入排序結束后的結果的是__(12,24,35,27,18,26)。設有一組初始關鍵字序列為(24,35，12,27，18,26)，那么第3趟簡單項選擇擇排序結束后的結果的是—(12,18,24,27,35,26)。設一棵二叉樹的前序序列為ABC,那么有5種不同的二叉樹可以得到這種序列。下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(i<j){while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while()i=i+1;if(i<j){r[j]=r[i];j=j-1;}};}四、算法設計題(20分)設計在鏈式結構上實現(xiàn)簡單項選擇擇排序算法。設計在順序存儲結構上實現(xiàn)求子串算法。設計求結點在二叉排序樹中層次的算法。數(shù)據(jù)結構試卷〔七)一、選擇題1.B2.B3.C4.B5.B6.A7.C8.C9.B10.D二、判斷題1.對2.對3.對4.對5.對6.對7.對8.錯9.錯10.錯三、填空題s->left=p,p->rightn(n-1),n(n-1)/2TOC\o"1-5"\h\zn/2開放定址法，鏈地址法142h-1,2h-1(12,24,35,27,18,26)(12,18,24,27,35,26)5i<j&&r[i].key<x.key,r[i]=x四、算法設計題設計在鏈式結構上實現(xiàn)簡單項選擇擇排序算法。

voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}設計在順序存儲結構上實現(xiàn)求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0';}}設計求結點在二叉排序樹中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}數(shù)據(jù)結構試卷〔八〕一、選擇題(30分)1.字符串的長度是指〔1.(B)串中不同字母的個數(shù)(D)(B)串中不同字母的個數(shù)(D)串中不同數(shù)字的個數(shù)(C)串中所含字符的個數(shù)2.建立一個長度為2.建立一個長度為n的有序單鏈表的時間復雜度為〔〕(A)O(n)(B)O(1)3.兩個字符串相等的充要條件是〔(A)兩個字符串的長度相等(C)同時具備(A)和((A)O(n)(B)O(1)3.兩個字符串相等的充要條件是〔(A)兩個字符串的長度相等(C)同時具備(A)和(B)兩個條件兩個字符串中對應位置上的字符相等以上答案都不對設某散列表的長度為100，散列函數(shù)H(k)=k%P,那么P通常情況下最好選擇〔〕。(A)99(B)97(C)91(D)93在二叉排序樹中插入一個關鍵字值的平均時間復雜度為〔〕。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)設一個順序有序表A[1:14]中有14個元素，那么采用二分法查找元素A[4]的過程中比擬元素的順序為()。(A)A[1],A[2],A[3],A[4](B)A[1],A[14],A[7],A[4]A[7],A[3],A[5],A[4](D)A[7],A[5],A[3],A[4]設一棵完全二叉樹中有65個結點，那么該完全二叉樹的深度為〔〕。(A)8(B)7(C)6(D)5設一棵三叉樹中有2個度數(shù)為1的結點，2個度數(shù)為2的結點，2個度數(shù)為3的結點，那么該三叉鏈權中有〔〕個度數(shù)為0的結點。(A)5(B)6(C)7(D)8設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，那么從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為〔〕。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc隊列是一種〔〕的線性表。(A)先進先出(B)先進后出(C)只能插入(D)只能刪除二、判斷題(20分)如果兩個關鍵字的值不等但哈希函數(shù)值相等，那么稱這兩個關鍵字為同義詞。〔〕設初始記錄關鍵字根本有序，那么快速排序算法的時間復雜度為O(nlog2n)?！病撤謮K查找的根本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找?！病扯S數(shù)組和多維數(shù)組均不是特殊的線性結構。〔〕向二叉排序樹中插入一個結點需要比擬的次數(shù)可能大于該二叉樹的高度?！病橙绻硞€有向圖的鄰接表中第i條單鏈表為空，那么第i個頂點的出度為零?！病撤强盏碾p向循環(huán)鏈表中任何結點的前驅指針均不為空?！病巢还芫€性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)?！病硤D的深度優(yōu)先遍歷算法中需要設置一個標志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問過。〔〕稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素?！病橙⑻羁疹}(30分)設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，那么以d=4為增量的一趟希爾排序結束后的結果為。下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結點，請在下劃線處填上正確的內容。typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk){if(t==0){;t->data=k;t->lchild=t->rchild=0;}elseif(t->data>k)bstinsert(t->lchild,k);else;}設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，那么在結點A的后面插入結點X需要執(zhí)行的語句序列：s->next=p->next;;。設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，那么指針變量p和指針變量head之間的關系是p=和head=〔設結點中的兩個指針域分別為llink和rlink〕。設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，那么其前序遍歷序列為。完全二叉樹中第5層上最少有個結點，最多有個結點。設有向圖中不存在有向邊<V.,V>，那么其對應的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，那么第4趟直接選擇排序結束后的結果為。設連通圖G中有n個頂點e條邊，那么對應的最小生成樹上有條邊。設有一組初始記錄關鍵字序列為(50，16，23,68,94，70，73)，那么將它們調整成初始堆只需把16與相互交換即可。四、算法設計題(20分)設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。數(shù)據(jù)結構試卷〔八〕參考答案一、選擇題1.C2.C3.C4.B5.B6.C7.B8.C9.A10.A二、判斷題1.對2.錯3.對4.錯5.錯6.對7.對8.對9.對10.對三、填空題(49，13，27，50，76，38，65，97)t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)p->next=shead->rlink，p->llinkCABDTOC\o"1-5"\h\z1，160(13，27，38，50，76，49，65，97)n-150四、算法設計題設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結構試卷〔九）一、選擇題（30分）以下程序段的時間復雜度為〔〕。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；(A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t)(D)O(m*t+n)設順序線性表中有n個數(shù)據(jù)元素，那么刪除表中第i個元素需要移動〔〕個元素。(A)n-i(B)n+l-i(C)n-1-i(D)i設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B,T1、T2和T3的結點數(shù)分別為N1、N2和N3，那么二叉樹B的根結點的左子樹的結點數(shù)為〔〕。(A)N1-1(B)N2-1(C)N2+N3(D)N1+N3利用直接插入排序法的思想建立一個有序線性表的時間復雜度為〔〕。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)設指針變量p指向雙向鏈表中結點A,指針變量s指向被插入的結點乂，那么在結點A的后面插入結點X的操作序列為〔〕。p->right=s；s->left=p；p->right->left=s；s->right=p->right；s->left=p；s->right=p->right；p->right=s；p->right->left=s；p->right=s；p->right->left=s；s->left=p；s->right=p->right；s->left=p；s->right=p->right；p->right->left=s；p->right=s；以下各種排序算法中平均時間復雜度為O(n2)是〔〕。(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序設輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，那么輸出序列中的第i個輸出元素是〔〕。(A)n-i(B)n-1-i(C)n+l-i(D)不能確定設散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，那么p最好選擇〔〕。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素數(shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有〔〕個。(A)4(B)5(C)6(D)7設完全無向圖中有n個頂點，那么該完全無向圖中有〔〕條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2設順序表的長度為n，那么順序查找的平均比擬次數(shù)為〔〕。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2設有序表中的元素為(13，18,24，35,47，50,62)，那么在其中利用二分法查找值為24的元素需要經(jīng)過〔〕次比擬。(A)1(B)2(C)3(D)4設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，那么其平均查找長度為〔〕。(A)6(B)11(C)5(D)6.5設有向無環(huán)圖G中的有向邊集合E={<1，2>，<2,3>，<3,4>，<1，4>}，那么以下屬于該有向圖G的一種拓撲排序序列的是〔〕。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，那么由這組記錄關鍵字生成的二叉排序樹的深度為〔〕。(A)4(B)5(C)6(D)7二、填空題(30分)設指針p指向單鏈表中結點A，指針s指向被插入的結點X，那么在結點A的前面插入結點X時的操作序列為：1）s->next=；2）p->next=s；3）t=p->data；4）p->data=；5）s->data=t；設某棵完全二叉樹中有100個結點，那么該二叉樹中有個葉子結點。設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，那么該循環(huán)隊列中最多存儲隊列元素。對一組初始關鍵字序列〔40，50，95，20，15，70，60，45，10〕進行冒泡排序，那么第一趟需要進行相鄰記錄的比擬的次數(shù)為，在整個排序過程中最多需要進行趟排序才可以完成。在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選排序，如果從節(jié)省存儲空間的角度來考慮那么最好選擇排序。設一組初始記錄關鍵字序列為（20，12,42,31，18，14,28），那么根據(jù)這些記錄關鍵字構造的二叉排序樹的平均查找長度是。設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，那么這棵二叉樹的前序序列為設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權值構造哈夫曼樹，那么這棵哈夫曼樹的高度。設一組記錄關鍵字序列為（80，70，33，65，24，56，48），那么用篩選法廠、妃廣、TOC\o"1-5"\h\z建成的初始堆為?！卧O無向圖G〔如右圖所示〕，那么其最小生成樹上所有邊的權值之和為°W三、判斷題（20分）G二點有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。（）6對鏈表進行插入和刪除操作時不必移動鏈表中結點。（）子串"ABC”在主串“AABCABCD”中的位置為2。（）假設一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，那么它必是該二叉樹的先序遍歷序列中的最后一個結點。（）希爾排序算法的時間復雜度為O（n》°（）用鄰接矩陣作為圖的存儲結構時，那么其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。（）中序遍歷一棵二叉排序樹可以得到一個有序的序列。（）入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。（）順序表查找指的是在順序存儲結構上進行查找?！病扯咽峭耆鏄洌耆鏄洳灰欢ㄊ嵌??！病澄?、算法設計題（20分）設計計算二叉樹中所有結點值之和的算法。設計將所有奇數(shù)移到所有偶數(shù)之前的算法。設計判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結構試卷〔九）參考答案一、選擇題1.A2.A3.A4.C5.D6.D7.C8.B9.C10.A11.C12.C13.D14.A15.A二、填空題p->next，s->data50m-1

TOC\o"1-5"\h\z6,8快速，堆19/7CBDA6(24,65，33，80,70,56，48)8三、判斷題錯2.對3.對4.對5.錯錯7.對8.對9.錯10.對四、算法設計題1.設計計算二叉樹中所有結點值之和