1.2 强化习题详解_严蔚敏《数据结构》（第2版）笔记和习题（含考研真题）详解-QQ阅读男生历史网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

1.2　强化习题详解

【基础知识题】

1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

答：（1）数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。

（2）数据元素是数据的基本单位。

（3）数据对象是性质相同的数据元素的集合，是数据的一个子集。

（4）数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

（5）存储结构是数据结构在计算机中的表示（又称映象或数据的物理结构）。

（6）数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

（7）抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

答：数据结构：相互之间存在一种或多种特定关系的数据元素的集合；

抽象数据类型：一个数学模型以及在该模型上的一组操作。

区别：

①抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

②抽象数据类型包含一般数据类型的概念，但含义比一般数据类型的范畴更广。

③抽象数据类型可通过程序设计语言中的数据类型来表示和实现。

3设有数据结构（D，R），其中D＝{d1，d2，d3，d4}，R＝{r}，r＝{（d1，d2），（d2，d3），（d3，d4）}，试按图论中图的画法惯例画出其逻辑结构图。

答：逻辑结构图如图1-2所示。

图1-2　程序逻辑结构图

4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

答：

ADT Complex{
  数据对象：D={r,i|r,i为实数}
  数据关系：R={<r,i>}
  基本操作：
    InitComplex(&C,re,im)
      操作结果：构造一个复数C，其实部和虚部分别为re和im
    DestroyCmoplex(&C)
      操作结果：销毁复数C
    Get(C,k,&e)
      操作结果：用e返回复数C的第k元的值
    Put(&C,k,e)
      操作结果：改变复数C的第k元的值为e
    IsAscending(C)
      操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0
    IsDescending(C)
      操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0
    Max(C,&e)
      操作结果：用e返回复数C的两个元素中值较大的一个
    Min(C,&e)
      操作结果：用e返回复数C的两个元素中值较小的一个
}ADT Complex

ADT RationalNumber{
  数据对象：D={s,m|s,m为自然数,且m不为0}
  数据关系：R={<s,m>}
  基本操作：
    InitRationalNumber(&R,s,m)
      操作结果：构造一个有理数R，其分子和分母分别为s和m
    DestroyRationalNumber(&R)
      操作结果：销毁有理数R
    Get(R,k,&e)
      操作结果：用e返回有理数R的第k元的值
    Put(&R,k,e)
      操作结果：改变有理数R的第k元的值为e
    IsAscending(R)
      操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0
    IsDescending(R)
      操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0
    Max(R,&e)
      操作结果：用e返回有理数R的两个元素中值较大的一个
    Min(R,&e)
      操作结果：用e返回有理数R的两个元素中值较小的一个
}ADT RationalNumber

【注意】考研中很少出现直接书写ADT的题目，但是会要求设计一个数据结构，无非就是对ADT的设计与完善过程。

5试画出与下列程序段等价的框图。

（1）

product=1;
i=1;
while(i<=n)
{
product*=i;
i++;
}

（2）

i=0;
do
{
i++;
}while((i!=n)&&(a[i]!=x));

（3）

switch
{
  case x<y:
    z=y-x;
    break;
  case x==y:
    z=abs(x*y);
    break;
  default:
    z=(x-y)/abs(x)*abs(y); //abs()为取绝对值函数
}

答：以上程序段等价框图分别如图1-3，图1-4和图1-5所示。

（1）

图1-3　等价框图（1）

（2）

图1-4　等价框图（2）

（3）

图1-5　等价框图（3）

6在程序设计中，常用下列三种不同的出错处理方式：

（1）用exit语句终止执行并报告错误；

（2）以函数的返回值区别正确返回或错误返回；

（3）设置一个整型变量的函数参数以区别正确返回或某种错误返回。

试讨论这三种方法各自的优缺点。

答：（1）优点：exit用于异常错误处理，可以强行中断程序的执行，并返回至操作系统，操作系统会自动回收资源。

缺点：退出地点太多不利于调试。

（2）优点：以函数的返回值区别正确返回或错误返回，常用于子程序的测试，便于实现程序的局部控制，不会直接终止程序的运行。

缺点：判断太多，必须人工维护一份错误值列表。

（3）优点：用整型函数进行错误处理可以给出错误类型，便于迅速确定错误。

缺点：需要完整的整型变量的释义，才能方便理解。

7在程序设计中，可采用下列三种方法实现输出和输入：

（1）通过scanf和printf语句；

（2）通过函数的参数显式传递；

（3）通过全局变量隐式传递。

试讨论这三种方法的优缺点。

答：（1）用scanf和printf直接进行输入输出

优点：形象、直观。

缺点：需要格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃，参数类型受限制，内存开销大。

（2）通过函数的参数显式传递进行输入输出

优点：便于实现信息的隐蔽，减少出错的可能。

缺点：参数说明比较烦琐，内存开销大。

（3）通过全局变量的隐式传递进行输入输出

优点：方便，只需修改变量的值即可，内存开销小；

缺点：过多的全局变量使程序的维护较为困难，内容极易丢失。

8设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：

（1）

i=1;
k=0;
while(i <= n-1)
{
@ k+=10*i;
i++;
}

（2）

i=1;
k=0;
do
{
@ k+=10*i;
i++;
} while(i<=n-1);

（3）

i=1;
k=0;
while (i<=n-1)
{
i++;
@ k+=10*i;
}

（4）

k=0;
for (i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
@ k++;
}

（5）

for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
@ x+=delta;
}

（6）

i=1;
j=0;
while(i+j<=n)
{
@ if(i>j)
      j++;
    else
      i++;
}

（7）

x=n; //n是不小于1的常数
y=0;
while(x>=(y+1)*(y+1))
{
@ y++;
}

（8）

x=91;
y=100;
while(y>0)
{
@ if(x>100)
    {
      x-=10;
      y--;
    }else
      x++;
}

答：（1）n－1

（2）n－1

（3）n－1

（4）

（5）

（6）n

（7）

（8）1100

9假设n为2的乘幂，并且n＞2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。

int Time(int n)
{
  count=0;
  x=2;
  while(x<n/2)
  {
    x*=2;
    count++;
  }
  return count;
}

答：因为循环执行条件是x<n/2，则循环语句x*=2;count++;的执行频度是O（log₂n）。count++共执行了log₂n－2次，所以count＝log₂n－2。

10按增长率由小至大的顺序排列下列各函数：2¹⁰⁰，（3/2）ⁿ，（2/3）ⁿ，（4/3）ⁿ，nⁿ，n^3/2，n^2/3，，n!，n，log₂n，n/log_n2，，log₂（log₂n），nlog₂n，（常见函数的增长率示意图如图1-6）。

111

图1-6　常见函数的增长率示意图

答：常见时间复杂度按照数量级递增排列为：

O（1）＜O（log₂n）＜O（n）＜O（nlog₂n）＜O（n²）＜O（n³）＜O（n^k）＜O（2ⁿ）

此处参考常见的次序以及图像得出次序排列为：

（2/3）ⁿ＜2¹⁰⁰＜log₂（log₂n）＜log₂n＜＜＜n^2/3＜n/log_n2＜n＜nlog₂n＜n^3/2＜（4/3）ⁿ＜（3/2）ⁿ＜＜n!＜nⁿ

11已知有实现同一功能的两个算法，其时间复杂度分别为O（2ⁿ）和O（n¹⁰），假设现实中计算机可连续运算的时间为10⁷秒（100多天），每秒可执行基本操作（根据这些操作来估算算法时间复杂度）10⁵次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。

答：10⁷*10⁵＝10¹²

2ⁿ＝10¹²，n＝40

n¹⁰＝10¹²，n＝16

第一种算法更合适，因为对于同样的循环次数n，第二种算法所花费的代价比较大。

12设有以下三个函数：f（n）＝21n⁴＋n²＋1000，g（n）＝15n⁴＋500n³，h（n）＝500n^3.5＋nlogn。请判断以下断言正确与否：

（1）f（n）是O（g（n））

（2）h（n）是O（f（n））

（3）g（n）是O（h（n））

（4）h（n）是O（n^3.5）

（5）h（n）是O（nlogn）

答：由分析可知，O（f（n））＝O（g（n））＝O（n⁴）；O（h（n））＝O（n^3.5）。故：

（1）对

（2）错

（3）错

（4）对

（5）错

【注意】O表示的是渐进时间复杂度，计算出结果后只需取其规模的阶数来做比较。

13试设定若干n值，比较两函数n²和50nlog₂n的增长趋势，并确定n在什么范围内，函数n²的值大于50nlog₂n的值。

答：（1）n²的增长趋势快，但在n较小的时候，50nlog₂n的值较大。

（2）令n²＝50nlog₂n，解得n≈450，故当n＞450时，n²＞50nlog₂n。

14判断下列各对函数f（n）和g（n），当n→∞时，哪个函数增长更快？

（1），g（n）＝2n⁴＋n＋7

（2）f（n）＝（ln（n!）＋5）²，g（n）＝13n^2.5

（3），

（4），

答：（1）g（n）更快

（2）g（n）更快

（3）f（n）更快

（4）f（n）更快

【注意】该题需要找到主要影响函数增长的部分，例如（1）相当于比较n²和n⁴的增长速度。

15试用数学归纳法证明：

（1）

（2）

（3）

（4）

答：（1）证明：

①n＝1时，1＝1×（1＋1）×（2×1＋1）/6＝1，等式成立；

②n＝2时，1＋4＝2×（2＋1）×（2×2＋1）/6＝5，等式成立；

③设n＝k（k＞＝0）时，公式成立，即1＋4＋9＋…＋k²＝k（k＋1）（2k＋1）/6。

则当n＝k＋1时，1＋4＋9＋…＋k²＋（k＋1）²＝k（k＋1）（2k＋1）/6＋（k＋1）²＝（k＋1）×[2×（k²）＋k＋6（k＋1）]/6＝（k＋1）×[2×（k²）＋7k＋6]/6＝（k＋1）×（2k＋3）×（k＋2）/6＝（k＋1）×[（k＋1）＋1]×[2（k＋1）＋1]/6也满足公式。

综上所述，

成立，得证。

（2）证明：

①n＝0时，x⁰＝1，（x－1）/（x－1）＝1，等式成立；

②n＝1时，1＋x＝（x²－1）/（x－1）＝1＋x，等式成立；

③设n＝k（k＞＝0）时等式成立，即x⁰＋x¹＋x²＋…＋x^k＝（x^k^＋¹－1）/（x－1）

则当n＝k＋1时，x⁰＋x¹＋x²＋…＋x^k＋x^k^＋¹＝（x^k^＋¹－1）/（x－1）＋x^k^＋¹＝[（x^k^＋¹－1）＋x^k^＋¹（x－1）]/（x－1）＝[（x^k^＋¹－1）＋x^k^＋²－x^k^＋¹]/（x－1）＝（x^k^＋²－1）/（x－1）也满足公式。

综上所述

成立，得证。

（3）证明：

①n＝1时，2¹^－¹＝2¹－1＝1，等式成立；

②n＝2时，2⁰＋2¹＝2²－1，等式成立；

③设n＝k（k＞＝1）时等式成立，即2⁰＋2¹＋…＋2^k^－¹＝2^k－1

则当n＝k＋1时，2⁰＋2¹＋…＋2^k^－¹＋2^k＝2^k－1＋2^k＝2×2^k－1＝2^k^＋¹－1也满足公式。

综上所述

成立，得证。

（4）证明：

①n＝1时，2×1－1＝1²＝1，等式成立；

②n＝2时，（2×1－1）＋（2×2－1）＝4＝2²，等式成立；

③设n＝k（k＞＝1）时等式成立，即（2×1－1）＋（2×2－1）＋…＋（2×k－1）＝k²

则当n＝k＋1时，（2×1－1）＋（2×2－1）＋…＋（2×k－1）＋[2×（k＋1）－1]＝k²＋[2×（k＋1）－1]＝k²＋2k＋1＝（k＋1）²也满足公式。

综上所述

成立，得证。

【注意】数学归纳法基本步骤：

①由题设证明n＝1等特殊情况成立；

②设n＝k时成立；

③证明n＝k＋1时成立。

【算法设计题】

16试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。

答：假设我们仍依X、Y和Z的次序输入这三个整数，则此题的目标是做到X≥Y≥Z。在算法中应考虑对这3个元素做尽可能少的比较和移动，如下述算法在最坏的情况下只需进行3次比较和7次移动。

void print_descending(int X,int Y,int Z) //按从大到小顺序输出三个整数
{
  scanf("%d",&X);
  scanf("%d",&Y);
  scanf("%d",&Z);
  if(X<Y)
    Exchange(X,Y);
  if(X<Z)
    Exchange(X,Z);
  if(Y<Z)
    Exchange(Y,Z);
  printf("%d",X);
  printf("%d",Y);
  printf("%d",Z);
} //print_descending

void Exchange(int x,int y)
{
  int temp;
  temp=x;
  x=y;
  y=temp;
} //Exchange

17已知k阶斐波那契序列的定义为

f₀＝0，f₁＝0，…，f_k_－₂＝0，f_k_－₁＝1

f_n＝f_n_－₁＋f_n_－₂＋…＋f_n_－_k，n＝k，k＋1，…

试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

答：

Status fib(int k,int m,int &f) //求k阶斐波那契序列的第m项的值f
{
  int a[100];
  if(k<2||m<0)
    return FALSE;
  if(m<k-1)
    f=0;
  else if (m==k-1)
    f=1;
  else
  {
    for(i=0;i<=k-2;i++)
      a[i]=0;
    a[k-1]=1; //初始化
    for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
    {
       sum=0;
       for(j=i-k;j<i;j++)
         sum+=a[j];

       a[i]=sum;
    }
    f=a[m];
  }
    return OK;
}

分析：k阶斐波那契序列的第m项的值

f[m]＝f[m－1]＋f[m－2]＋…＋f[m－k]＝f[m－1]＋f[m－2]＋…＋f[m－k]＋f[m－k－1]－f[m－k－1]＝2×f[m－1]－f[m－k－1]

所以上述算法的时间复杂度仅为O（m）。如果采用递归设计，将达到O（k^m）。即使采用暂存中间结果的方法，也将达到O（m²）。

18假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为

编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

答：

typedef enum{A,B,C,D,E} SchoolName;
typedef enum{Female,Male} SexType;
typedef struct
{
  char event[3]; //项目
  SexType sex;
  SchoolName school;
  int score;
}Component;
typedef struct
{
  int MaleSum; //男团总分
  int FemaleSum; //女团总分
  int TotalSum; //团体总分
}Sum;
Component report[n];
Sum result[5];
//算法过程体中主要结构：
for(i=0;i<n;i++)
{
  //对result[report[i].school]进行处理;
}
for(s=A;s<=E;s++)
printf(……);

例如：

typedef enum{A,B,C,D,E} SchoolName;
typedef enum{Female,Male} SexType;
typedef struct
{
  char event[3]; //项目
  SexType sex;
  SchoolName school;
  int score;
}Component;
typedef struct
{
  int MaleSum; //男团总分
  int FemaleSum; //女团总分
  int TotalSum; //团体总分
}Sum;
Sum SumScore(SchoolName sn,Component a[],int n)
{
  Sum temp;
  temp.MaleSum=0;
  temp.FemaleSum=0;
  temp.TotalSum=0;
  int i;
  for(i=0;i<n;i++)
  {
    if(a[i].school==sn)
    {
      if(a[i].sex==Male)
        temp.MaleSum+=a[i].score;
      if(a[i].sex==Female)
        temp.FemaleSum+=a[i].score;
    }
  }
  temp.TotalSum=temp.MaleSum+temp.FemaleSum;
  return temp;
}

19试编写算法，计算i!*2ⁱ（i＝0，1，…，n－1）的值并存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT，则当n＞arrsize或对某个k（1≤k≤n），使k!*2^k＞MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。

答：注意MAXINT为计算机中允许出现的最大值，则在过程体中不能以计算机所得结果大于MAXINT作为判断出错的依据。

#include<stdio.h>
#define MAXINT 65535
#define ArrSize 100
int main()
{
  int i,k;
  int a[ArrSize];
  printf("Enter k: ");
  scanf("%d",&k);
  if(k>ArrSize-1)
    exit(0); //选用exit()作为出错处理方法
  for(i=0;i<=k;i++)
  {
    if(i==0)
      a[i]=1;
    else
    {
      if(2*i*a[i-1]>MAXINT)
        exit(0); //选用exit()作为出错处理方法
      else
        a[i]=2*i*a[i-1];
    }
  }
  for(i=0;i<=k;i++)
  {
    if(a[i]>MAXINT)
      exit(0); //选用exit()作为出错处理方法
    else
      printf("%d\n",a[i]);
  }
  return 0;
}

20试编写算法求一元多项式的值的值P_n（x₀），并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a_i（i＝0，1，…，n），x₀和n，输出为P_n（x₀）。

答：注意计算过程中不要对多项式中的每一项独立计算x的幂。

#include<stdio.h>
#define N 10
double polynomail(int a[],int i,double x,int n);
int main()
{
  double x;
  int n,i;
  int a[N];
  printf("Input the value of x:");
  scanf("%d",&x);
  printf("Input number of terms:");
  scanf("%d",&n);
  if(n>N-1)
    exit(0);
  printf("输入多项式的系数a[0]—a[n]:"); //在此之上所有语句仅执行一次
  for(i=0;i<=n;i++)
    scanf("%d",&a[i]); //执行n+1次
  printf("The polynomail value is:%d\n",polynomail(a,n,x,n)); //执行一次
  return 0;
}
double polynomail(int a[],int i,double x,int n)
{
  if(i>0)
    return a[n-i]+polynomail(a,i-1,x,n)*x; //递归函数，polynomail函数执行n＋1次
  else
    return a[n];
}

本算法的时间复杂度为O（n）。