华中科技大学招收硕士研究生入学考试试题答案.doc
17页
华中科技大学招收硕士研究生入学考试试题二OO六年数据结构与算法分析试题答案 2二OO七年数据结构与算法分析试题答案 5二O一一年数据结构与算法分析试题答案 7二O一二年数据结构与算法分析试题答案 8整理为word格式二OO六年数据结构与算法分析试题答案术语解释：（略）选择题：1~5：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 83整理为word格式V1V1V2V1V2V3V4V13V2V3V4V1V2V3V4V7V1V2V3V4V7V6V1V2V3V4V7V6V54//用邻接表G存储图的顶点信息InitQueue(); //初始化队列为空EnQueue(elem); //将元素elem入队DeQueue(elem); //将队头元素退队并赋值给elemisEmpty(); //判断队列是否为空GetTotalID(i); //获取第i个顶点的入度并存于ID数组中ID[vexnum]; //用于存储各顶点的入度，vexnum为顶点数InitQueue();For(int i=0;i!=vexnum;++i) GetTotalID(i); //依次获取每个顶点的入度For(int i=0;i!=vexnum;++i){ If(ID[i]==0) EnQueue(i); //将入度为0 的顶点入队整理为word格式 For(int i=fristadj;i!=adjnum;++i) ID[i]-=1; //将该顶点的邻接点的入度数减1}While(!isEmpty()){DeQueue(elem); //将队列中各顶点依次退队并赋值给elemPrintf(elem); //输入拓扑排序序列}5A:11 B:01010 C:0111 D:00 E:011111 F:10 G:0100 H:0101应用及编程题1unsigned int isBallanced(char* string){ char brace;整理为word格式 for(ihnt i=0;i!=strlen(string);++i) { if(string[i]=='{'||string[i]=='['||string[i]=='(') push(string[i]); switch(string[i]) { brace=pop(); case ')': if(brace!='(') return 0; break; case ']': if(brace!='[') return 0; break; case '}': if(brace!='{') return 0; break; } if(isEmpty()) return 1; else return 0; }}该算法的时间复杂度为O(n),空间复杂度为O(n);2int InOrderTraverse(bitree* t){ Static int total=0; InOrderTraverse(t->lchild); if(t->data>=x1&&t->data<=x2) ++total; if(t->data>x2) return total; InOrderTraverse(t->rchild);}该算法为中序遍历，时间复杂度为O(n)整理为word格式二OO七年数据结构与算法分析试题答案术语解释：选择题：1~5： BCDCD简答题：1ABCDEFGBDF^I^E^IC^GH^^^^2由邻接矩阵可得该图为：顶点I=1I=2I=3I=4I=5I=6V210V3505050V45030V5∞50∞40V6∞100∞∞90整理为word格式VjV1V1,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 length){ for(int i=1;i!=length;++i) { int temp=num[i],j; for(j=i;j>0&&temp
