华中科技大学招收硕士研究生入学考试试题答案.docx
《华中科技大学招收硕士研究生入学考试试题答案.docx》由会员分享，可在线阅读，更多相关《华中科技大学招收硕士研究生入学考试试题答案.docx（22页珍藏版）》请在冰点文库上搜索。
华中科技大学招收硕士研究生入学考试试题答案
华中科技大学招收硕士研究生入学考试试题
二OO六年数据结构与算法分析试题答案2
二OO七年数据结构与算法分析试题答案5
二O一一年数据结构与算法分析试题答案7
二O一二年数据结构与算法分析试题答案8
二OO六年数据结构与算法分析试题答案
术语解释：
（略）
选择题：
1~5：
CDCDC
简答题：
1
2
第一趟：
68572413
第二趟：
56781234
第三趟：
12345678
3
4
//用邻接表G存储图的顶点信息
InitQueue（）;//初始化队列为空
EnQueue（elem）;//将元素elem入队
DeQueue（elem）;//将队头元素退队并赋值给elem
isEmpty（）;//判断队列是否为空
GetTotalID（i）;//获取第i个顶点的入度并存于ID数组中
ID[vexnum];//用于存储各顶点的入度，vexnum为顶点数
InitQueue（）;
For（inti=0;i!
=vexnum;++i）
GetTotalID（i）;//依次获取每个顶点的入度
For（inti=0;i!
=vexnum;++i）
{
If（ID[i]==0）
EnQueue（i）;//将入度为0的顶点入队
For（inti=fristadj;i!
=adjnum;++i）
ID[i]-=1;//将该顶点的邻接点的入度数减1
}
While（!
isEmpty（））
{
DeQueue（elem）;//将队列中各顶点依次退队并赋值给elem
Printf（elem）;//输入拓扑排序序列
}
5
A:
11B:
01010C:
0111D:
00E:
011111F:
10G:
0100H:
0101
应用及编程题
1
unsignedintisBallanced（char*string）
{
charbrace;
for（ihnti=0;i!
=strlen（string）;++i）
{
if（string[i]=='{'||string[i]=='['||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;
else
return0;
}
}
该算法的时间复杂度为O（n）,空间复杂度为O（n）;
2
intInOrderTraverse（bitree*t）
{
Staticinttotal=0;
InOrderTraverse（t->lchild）;
if（t->data>=x1&&t->data<=x2）
++total;
if（t->data>x2）
returntotal;
InOrderTraverse（t->rchild）;
}
该算法为中序遍历，时间复杂度为O（n）
二OO七年数据结构与算法分析试题答案
术语解释：
选择题：
1~5：
BCDCD
简答题：
1
2
由邻接矩阵可得该图为：
顶点
I=1
I=2
I=3
I=4
I=5
I=6
V2
10
V3
50
50
50
V4
50
30
V5
∞
50
∞
40
V6
∞
100
∞
∞
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-2）+2K-1+2K=……=T（20）+2K+2K-1+2K-2+……=2K+1-1=2*2logn-1=2n-1
所以时间复杂度为O（2n-1）
4
voidInsertSort（intlength）
{
for（inti=1;i!
=length;++i）
{
inttemp=num[i],j;
for（j=i;j>0&&tempnum[j]=num[j-1];
num[j]=temp;
}
}
第一趟：
165432第二趟：
126543第三趟：
123654第四趟：
123465第五趟：
123456
5
应用编程题:
1
voidDelete（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];
}
}
}
该算法的时间复杂度为O（n3）
voidDelete（int*A,intlength）
{
inti=0,j=0;
for（;i!
=length;++i）
{
if（A[j]!
=A[i]）
{
A[j+1]=A[i];
++j;
}
}
length=j;
}
二O一一年数据结构与算法分析试题答案
术语解释：
（略）
选择题：
1~5：
ABDCC
简答题：
1
#defineSize100
intstack[Size]={0};
inttop1=0,top2=Size-1;
voidpush（inttop,intelem）
{
if（top1>=top2）
{
cout<<"StackOverFlow!
"<return;
}
switch（top）
{
casetop1:
stack[top]=elem;
++top1;
break;
casetop2:
stack[top]=elem;
++top2;
break;
}
return;
}
voidpop（inttop,intelem）
{
if（top1<0||top2>=Size）
{
cout<<"StackOverFlow!
"<return;
}
switch（top）
{
casetop1:
elem=stack[top];
--top1;
break;
casetop2:
elem=stack[top];
++top2;
break;
}
return;
}
2
3
Func
（1）:
1
Func
（2）:
141
Func（3）:
191
Func（5）:
14125141
该算法的时间复杂度为O（n）
4
A:
101B:
00C:
111D:
10010E:
110F:
010G:
01111H:
100I:
0110
5
深度优先遍历：
V1V2V4V5V7V8V9V3V6
广度优先遍历：
V1V2V3V4V5V6V7V8V9
应用编程题：
1
intPartition（intlow,inthigh）
{
while（low{
while（num[low]<0）low++;
while（num[high]>0）high--;
if（low{
inttemp=num[low];
num[low]=num[high];
num[high]=temp;
}
}
return0;
}
2
intsum（bitree*t）
{
staticinttotal;
if（t==NULL）
return0;
if（t->data>0）
total+=t->data;
sum（t->lchild）;
sum（t->rchild）;
}
二O一二年数据结构与算法分析试题答案
术语解释：
（略）
选择题：
1~5：
DBADA
简答题：
1
2
函数调用过程如下：
3
模式串的next值：
01112
4
深度优先遍历：
V1V2V3V6V4V5V7
5
A:
0010B:
1101C:
11001D:
111E:
000F:
0011G:
10H:
01I:
110000J:
11001
算法题
1
intisSum（int*a,intn,intx）
{
inti=0,j=n-1;
while（i{
if（a[i]+a[j]==x）
return0;
if（a[i]+a[j]i++;
if（a[i]+a[j]>x）
j--;
}
return-1;
}
该算法的时间复杂度为O（n）
2
intcountHeight（BiTreeNode*root）
{
if（!
root->left&&!
root->right）
return0;
intlHeight=countHeight（root->left）;
intrHeight=countheight（root->rchild）;
returnlHeight>rHeight?
lHeight+1:
rHeight+1;
}
升级会员 