06华中科技大学招收硕士研究生数据结构与算法分析考试试题答案

1、华中科技大学招收硕士研究生入学考试试题二OO六年数据结构与算法分析试题答案2二OO七年数据结构与算法分析试题答案5二O一一年数据结构与算法分析试题答案7二O一二年数据结构与算法分析试题答案8二OO六年数据结构与算法分析试题答案术语解释：（略）选择题：15：CDCCC简答题：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(e

2、lem);/将元素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)brace=pop();case ):if(brace!=(

4、)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 total=0;int InOrderTraverse(bitree* t)InOrderTraverse(t-lchild);if(t-data=x1)+total;if(t-datax2)return total;InOrderTraverse(t-rchild);return total;该算法为中序遍

5、历，时间复杂度为O(n)二OO七年数据结构与算法分析试题答案术语解释：选择题：15：BCDBD简答题：12由邻接矩阵可得该图为：顶点I=1I=2I=3I=4I=5I=6V210V3505050V45030V55040V610090VjV1V1,V2V1,V2,V4V1,V3V1,V2,V4,V5V1,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* array,

6、int num)int i=num-1,j=1;while(j!=i)array0=arrayi;if(arrayi=j;-v)arrayv-1=arrayv;arrayv=array0;+j;else-i;第一趟：1 6 5 4 3 2第二趟：1 2 6 5 4 3第三趟：1 2 3 6 5 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

7、-(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!=length;+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

8、：ABDCC简答题：1#define Size 100int stackSize=0;int top1=0,top2=Size-1;void push(int top,int elem)if(top1=top2)coutStack OverFlow!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=Size)coutStack OverFlow!endl;return ;

9、switch(top)case top1:elem=stacktop;-top1;break;case top2:elem=stacktop;+top2;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 V6 V3广度优先遍历：V1 V2

10、 V3 V4 V5 V6 V7 V8 V9应用编程题：1int QuickSort()int i=0,j=8;while(i0&aj0)int tmp=ai;ai=aj;aj=tmp;+i,-j;elseif(ai0)-j;2int sum(bitree* t)static int total;if(t=NULL)return 0;if(t-data0)total+=t-data;sum(t-lchild);sum(t-rchild);二O一二年数据结构与算法分析试题答案术语解释：（略）选择题：15：BBADA简答题：12函数调用过程如下：3模式串的next值：0 1 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(ij)if(ai+aj=x)return 0;if(ai+ajx)j-;return -1;该算法的时间复杂度为O(n)2int countHeigh