第1章 绪 论
1．选择题
BCCCA CCDBA D
2．填空题
（1）线性结构，树形结构，图形结构，非线性结构
（2）没有，1，没有，1
（3）前驱，1，后续，任意多个
（4）任意多个
（5）一对一，一对多，多对多
（6）有穷性，确定性，可行性，输入，输出
（7）评价算法的效率
（8）f(n)
3．问答题
（1）略。
（2）略。
|
图A-1 3种数据结构的表示
|
B=(K,R)
K={a,b,c,d,e,f,g,h,i}
R={<a,b>,<a,c>,<c,d>,<c,e>,<d,f>,<d,g>,<e,h>,<f,i>}
它是树形结构。
（4）几种用二元组表示的数据结构，图形与结构如下：
①如图A-1（a）所示，它是线性结构。
②如图A-1（b）所示，它是树形结构。
③如图A-1（c）所示，它是图形结构。
4．上机操作题
（1）对应的算法如下：
void order(int a,int b,int c)
{
if(a>b)
{
if(b>c)
printf("%d,%d,%d\n",c,b,a);
else if(a>c)
printf("%d,%d,%d\n",b,c,a);
else
printf("%d,%d,%d\n",b,a,c);
}
else
{
if(b>c)
{
if(a>c)
printf("%d,%d,%d\n",c,a,b);
else
printf("%d,%d,%d\n",a,c,b);
}
else
printf("%d,%d,%d\n",a,b,c);
}
}
（2）对应的算法如下：
void maxmin(int A[],int n,int &max,int &min)
{
int i;
max=min=A[0];
for(i=1;i<n;i++)
{
if(A[i]>max)
max=A[i];
if(A[i]<min)
min=A[i];
}
}
（3）各种算法关于n的时间复杂度如下：
①设while循环执行m次，则i=1+2m≤n，m≤(n-1)/2，算法的时间复杂度为m，即O(n)。
②T(n)= 
=
=O(n2)。
③设while循环执行m次，则s=1+2+…+m=m(1+m)/2≤n，算法的时间复杂度为m，即O(
)。
（4）各程序段中x=x+1语句的执行次数如下：
①50次（i=1、3、5、…、99）。
②99次（i=2、3、4、…、100）。
③101次（i=1、2、3、…100、101）。