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

华中科技大学招收硕士研究生入学考试试题 TOC \o "1-5" \h \z \o "Current Document" OO 六年数据结构与算法分析试题答案 2 \o "Current Document" OO 七年数据结构与算法分析试题答案 6 \o "Current Document" O 一一年数据结构与算法分析试题答案 10 \o "Current Document" O 一二年数据结构与算法分析试题答案 14 二OO六年数据结构与算法分析试题答案 术语解释：（略） 选择题： 1~5: CDCCC 简答题： 1 2 第一趟：6 8 5 7 2 4 1 3 第二趟：5 6 7 8 1 2 3 4 第三趟：1 2 3 4 5 6 7 8 V1V1V1V1V3V3V2V2V2V4V4V1V1V3V3V2V2V4V4V7V7V6V1V3V2V4V7V6V5 V1 V1 V1 V1 V3 V3 V2 V2 V2 V4 V4 V1 V1 V3 V3 V2 V2 V4 V4 V7 V7 V6 V1 V3 V2 V4 V7 V6 V5 4 〃用邻接表G存储图的顶点信息 InitQueue(); //初始化队列为空 EnQueue(elem); 〃将元素 elem 入队 DeQueue(elem); 〃将队头元素退队并赋值给 elem isEmpty(); 〃判断队列是否为空 GetTotallD(i); //获取第i个顶点的入度并存于ID数组中 ID[vexnum]; 〃用于存储各顶点的入度， vexnum为顶点数 InitQueue(); For(int i=0;i!=vexnum;++i) GetTotallD(i); //依次获取每个顶点的入度 For(int i=0;i!=vexnum;++i) { If(ID[i]==0) EnQueue(i); 〃将入度为0的顶点入队 For(int i=fristadj;i!=adjnum;++i) ID[i]-=1; //将该顶点的邻接点的入度数减 1 } While(!isEmpty()) { DeQueue(elem); 〃将队列中各顶点依次退队并赋值给 elem Printf(elem); //输入拓扑排序序列 } 应用及编程题 unsigned int isBallanced(char* string) { char brace; 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); 2 int total=0; int InOrderTraverse(bitree* t) { InOrderTraverse(t->lchild); if(t->data>=x1) ++total; if(t->data>x2) return total; InOrderTraverse(t->rchild); return total; } 该算法为中序遍历，时间复杂度为 O(n) 术语解释: 二OO七年数据结构与算法分析试题答案 选择题： 1~5: BCDBD 简答题： 2 由邻接矩阵可得该图为: 顶点 I=1 I=2 I=3 I=4 I=5 I=6 V2 10 V3 50 50 50 V4 50 30 V5 oo 50 oo 40 V6 oo 100 oo oo 90 Vj V1 V1,V2 V1,V2,V4 V1,V3 V1,V2,V4,V5 V1,V2,V4,V5,V6 3 设 N=2K,T(N尸T(N/2)+N 即 T(2K)=T(2K-1)+2K=T(2K-j+2K-1+2K=……=T(20)+2K+2K-1+2K-2+……=2K+1-1=2*2logn-1=2n-1 所以时间复杂度为 O(2n-1) 4 void InsertSort(int* array,int num) { int i=num-1,j=1; while(j!=i) { array[0]=array[i]; if(array[i]<array[j]) { for(i