华中科技大学招收硕士研究报告生入学考试题答案

1、.华中科技大学招收硕士研究生入学考试试题二OO六年数据结构与算法分析试题答案2二OO七年数据结构与算法分析试题答案5二O一一年数据结构与算法分析试题答案7二O一二年数据结构与算法分析试题答案8二OO六年数据结构与算法分析试题答案术语解释：（略）选择题：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数组中IDvexnum;/用于存储各顶点的入度，vexnum为顶点数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、数减1While(!isEmpty()DeQueue(elem);/将队列中各顶点依次退队并赋值给elemPrintf(elem);/输入拓扑排序序列5A:11B:01010C:0111D:00E:011111F:10G:0100H:0101应用及编程题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;该算法的时间复杂度为O(n),空间复杂度为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);该算法为中序遍历，时间复杂度为O(n)二OO七年数据结构与算法分析试题答案术语解释：选择题：15：BCDCD简答题：1ABCDEFGBDFIEICGH2由邻接矩阵可得该图为：顶点I=1I=2I=3I=4I=5I=6V210V3505050V45030V55040V610090VjV1V1,V2V1,V2,V4V1,V3V1,V2,V4,V5V

6、1,V2,V4,V5,V63设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所以时间复杂度为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应用编程题: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;该算法的时间复杂度为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一一年数据结构与算法分析试题答案术语解释：（略）选择题：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该算法的时间复杂度为O(n)4A:101B:00C:111D:10010E:110F:010G:01111H:100I:01105深度优先遍历：V1 V2 V4 V5 V7 V8 V9 V3 V6广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V8 V9应用编程题：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一二年数据结构与算法分析试题答案术语解释：（略）选择题：15：DBADA简答题：12函数调用过程如下：3模式串的next值：0 1 1 1 24深度优先遍历：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;该算法的时间复杂度为O(n)2int countHeight(BiTreeNode* roo