華中科技大學(xué)招收碩士研究報告生入學(xué)考試題答案

1、.華中科技大學(xué)招收碩士研究生入學(xué)考試試題二OO六年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案2二OO七年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案5二O一一年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案7二O一二年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案8二OO六年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案術(shù)語解釋：（略）選擇題：15：CDCDC簡答題：12第一趟：6 8 5 7 2 4 1 3第二趟：5 6 7 8 1 2 3 4第三趟：1 2 3 4 5 6 7 83V1V1V2V1V2V3V4V13V2V3V4V1V2V3V4V7V1V2V3V4V7V6V1V2V3V4V7V6V54/用鄰接表G存儲圖的頂點信息InitQueue();/初始化隊列為空EnQueue(

2、elem);/將元素elem入隊DeQueue(elem);/將隊頭元素退隊并賦值給elemisEmpty();/判斷隊列是否為空GetTotalID(i);/獲取第i個頂點的入度并存于ID數(shù)組中IDvexnum;/用于存儲各頂點的入度，vexnum為頂點數(shù)InitQueue();For(int i=0;i!=vexnum;+i)GetTotalID(i);/依次獲取每個頂點的入度For(int i=0;i!=vexnum;+i)If(IDi=0)EnQueue(i);/將入度為0 的頂點入隊For(int i=fristadj;i!=adjnum;+i)IDi-=1;/將該頂點的鄰接點的入度

3、數(shù)減1While(!isEmpty()DeQueue(elem);/將隊列中各頂點依次退隊并賦值給elemPrintf(elem);/輸入拓撲排序序列5A:11B:01010C:0111D:00E:011111F:10G:0100H:0101應(yīng)用及編程題1unsigned int isBallanced(char* string)char brace;for(ihnt i=0;i!=strlen(string);+i)if(stringi=''|stringi=''|stringi='(')push(stringi);switch(stringi

4、)brace=pop();case ')':if(brace!='(')return 0;break;case '':if(brace!='')return 0;break;case '':if(brace!='')return 0;break;if(isEmpty()return 1;elsereturn 0;該算法的時間復(fù)雜度為O(n),空間復(fù)雜度為O(n);2int InOrderTraverse(bitree* t)Static int total=0;InOrderTraverse(t-&

5、gt;lchild);if(t->data>=x1&&t->data<=x2)+total;if(t->data>x2)returntotal;InOrderTraverse(t->rchild);該算法為中序遍歷，時間復(fù)雜度為O(n)二OO七年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案術(shù)語解釋：選擇題：15：BCDCD簡答題：1ABCDEFGBDFIEICGH2由鄰接矩陣可得該圖為：頂點I=1I=2I=3I=4I=5I=6V210V3505050V45030V55040V610090VjV1V1,V2V1,V2,V4V1,V3V1,V2,V4,V5V

6、1,V2,V4,V5,V63設(shè)N=2K,T(N)=T(N/2)+N即T(2K)=T(2K-1)+2K=T(2K-2)+2K-1+2K=T(20)+2K+2K-1+2K-2+=2K+1-1=2*2logn-1=2n-1所以時間復(fù)雜度為O(2n-1)4void InsertSort(int length)for(int i=1;i!=length;+i)int temp=numi,j;for(j=i;j>0&&temp<numj-1;-j)numj=numj-1;numj=temp;第一趟：1 6 5 4 3 2第二趟：1 2 6 5 4 3第三趟：1 2 3 6 5

7、4第四趟：1 2 3 4 6 5 第五趟：1 2 3 4 5 650123456772244661188332223335511199H(key)=key MOD 70123456774411552266993322288H(key)=(key/100+(key/10-key/100)*10)+(key-(key-(key/10)*10) MOD 7333111應(yīng)用編程題:1void Delete(int* A,int length)for(int i=1;i!=length;+i)for(int j=i+1;j!=length;+j)if(Ai=Aj)for(int k=j+1;j!=len

8、gth;+k)Ak-1=Ak;該算法的時間復(fù)雜度為O(n3)void Delete(int *A,int length)int i=0,j=0;for(;i!=length;+i)if(Aj!=Ai)Aj+1=Ai;+j;length=j;二O一一年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案術(shù)語解釋：（略）選擇題：15：ABDCC簡答題：1*define Size 100int stackSize=0;int top1=0,top2=Size-1;void push(int top,int elem)if(top1>=top2)cout<<"Stack OverFlow!"

9、;<<endl;return ;switch(top)case top1:stacktop=elem;+top1;break;case top2:stacktop=elem;+top2;break;return ;void pop(int top,int elem)if(top1<0|top2>=Size)cout<<"Stack OverFlow!"<<endl;return ;switch(top)case top1:elem=stacktop;-top1;break;case top2:elem=stacktop;+to

10、p2;break;return ;20123456789103577233525371032793739575973Func(1):1Func(2):1 4 1Func(3):1 9 1Func(5): 1 4 1 25 1 4 1該算法的時間復(fù)雜度為O(n)4A:101B:00C:111D:10010E:110F:010G:01111H:100I:01105深度優(yōu)先遍歷：V1 V2 V4 V5 V7 V8 V9 V3 V6廣度優(yōu)先遍歷：V1 V2 V3 V4 V5 V6 V7 V8 V9應(yīng)用編程題：1int Partition(int low,int high)while(low<hi

11、gh)while(numlow<0) low+;while(numhigh>0) high-;if(low<high)int temp=numlow;numlow=numhigh;numhigh=temp;return 0;2int sum(bitree* t)static int total;if(t=NULL)return 0;if(t->data>0)total+=t->data;sum(t->lchild);sum(t->rchild);二O一二年數(shù)據(jù)結(jié)構(gòu)與算法分析試題答案術(shù)語解釋：（略）選擇題：15：DBADA簡答題：12函數(shù)調(diào)用過程如下：3模式串的next值：0 1 1 1 24深度優(yōu)先遍歷：V1 V2 V3 V6 V4 V5 V75A:0010B:1101C:11001D:111E:000F:0011G:10H:01I:110000J:11001算法題1int isSum(int *a,int n,int x)int i=0,j=n-1;while(i<j)if(ai+aj=x)return 0;if(ai+aj<x)i+;if(ai+aj>x)j-;return -1;該算法的時間復(fù)雜度為O(n)2int countHeight(BiTreeNode* roo