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

-二OO六年数据结构与算法分析试题答案1二OO七年数据结构与算法分析试题答案4二O一一年数据结构与算法分析试题答案7二O一二年数据结构与算法分析试题答案10二OO六年数据结构与算法分析试题答案123.z.-V1V1V1V2V1V1V2V3V4V1V3V2V4V1V1V3V2V4V7V6V1V3V2V4V7V6V5V1V3V2V4V74//用邻接表G存储图的顶点信息InitQueue();//初始化队列为空EnQueue(elem);DeQueue(elem);isEmpty();GetTotalID(i);ID[ve*num];InitQueue();//将元素elem入队//将队头元素退队并赋值给elem//判断队列是否为空//获取第i个顶点的入度并存于ID数组中For(inti=0;i!=ve*num;++i)GetTotalID(i);//依次获取每个顶点的入度For(inti=0;i!=ve*num;++i){If(ID[i]==0)EnQueue(i);//将入度为0的顶点入队For(inti=fristadj;i!=adjnum;++i)ID[i]-=1;//将该顶点的邻接点的入度数减1.z.-}While(!isEmpty()){DeQueue(elem);//将队列中各顶点依次退队并赋值给elemPrintf(elem);//输入拓扑排序序列}5A:11B:01010C:0111D:00E:011111F:10G:0100H:0101应用及编程题1unsignedintisBallanced(char*string){charbrace;for(ihnti=0;i!=strlen(string);++i){push(string[i]);switch(string[i]){brace=pop();case')':if(brace!='(')return0;break;case']':if(brace!='[')return0;break;case'}':if(brace!='{')return0;break;}if(isEmpty())return1;return0;}}该算法的时间复杂度为O(n),空间复杂度为O(n);2intInOrderTraverse(bitree*t){Staticinttotal=0;.z..z.-InOrderTraverse(t->lchild);if(t->data>=*1&&t->data<=*2)alif(t->data>*2)returntotal;InOrderTraverse(t->rchild);}该算法为中序遍历，时间复杂度为O(n)二OO七年数据结构与算法分析试题答案1ABCDEFGIBDF^^^I^CEG^^^H^2V2I1I2I3I4I5I6V3V4V5∞∞V6∞∞∞VjV1V1,V2V1,V2,V4V1,V3V1,V2,V4,V5V1,V2,V4,V5,V63设N=2K,T(N)=T(N/2)+N.z.所以时间复杂度为O(2n-1)4voidInsertSort(intlength){tiilengthi{inttemp=num[i],j;forjijtempnumj1];--j)num[j]=num[j-1];numjtemp;}}5-5-^^333^^^^^^4023456H(key)=keyMOD7333333^^^^4023456^^应用编程题:1voidDelete(int*A,intlength){for(inti=1;i!=length;++i){for(intj=i+1;j!=length;++j){if(A[i]==A[j])for(intk=j+1;j!=length;++k)A[k-1]=A[k];}}}.z.-该算法的时间复杂度为O(n3)voidDelete(int*A,intlength){inti=0,j=0;for(;i!=length;++i){if(A[j]!=A[i]){A[j+1]=A[i];}}length=j;}二O一一年数据结构与算法分析试题答案1*defineSize100intstack[Size]={0};inttop1=0,top2=Size-1;voidpush(inttop,intelem){if(top1>=top2){cout<<"StackOverFlow!"<<endl;return;}switch(top){casetop1:stack[top]=elem;topbreak;casetop2:stack[top]=elem;topbreak;}return;}.z..z.-voidpop(inttop,intelem){{cout<<"StackOverFlow!"<<endl;return;}switch(top){casetop1:elem=stack[top];--top1;break;casetop2:elem=stack[top];topbreak;}return;}2^^^^^^0123456789^^^^^3Func(1):1Func(2):141Func(3):191Func(5):14125141该算法的时间复杂度为O(n)4A:101B:00C:111D:10010E:1105124578936广度优先遍历：124578936广度优先遍历：VVVVVVVVV1234567891intPartition(intlow,inthigh){while(low<high){while(num[low]<0)low++;while(num[high]>0)high--;if(low<high){inttemp=num[low];numlow]=num[high];numhigh=temp;}}urn}2intsum(bitree*t){staticinttotal;.-F:010G:01111H:100I:0110z.-if(t==NULL)return0;if(t->data>0)total+=t->data;sum(t->lchild);sum(t->rchild);}二O一二年数据结构与算法分析试题答案1234123645712364575A:0010B:1101C:11001D:111E:000F:0011G:10H:01I:110000J:110011intisSum(int*a,intn,int*){inti=0,j=n-1;while(i<j){if(a[i]+a[j]==*)return0;if(a[i]+a[j]<*)i++;if(a[i]+a[j]>*)j--;}return-1;}该算法的时间复杂度为O(n)2intcountHeight(BiTreeNode*root){if(!root->left&&!root->right).