第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种数据结构的表示

（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(n²)。

③设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）。