1.2　強化習(xí)題詳解

【基礎(chǔ)知識題】

1簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。

答：（1）數(shù)據(jù)是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機程序處理的符號的總稱。

（2）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。

（3）數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

（4）數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

（5）存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象或數(shù)據(jù)的物理結(jié)構(gòu)）。

（6）數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。

（7）抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。

2試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。

答：數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合；

抽象數(shù)據(jù)類型：一個數(shù)學(xué)模型以及在該模型上的一組操作。

區(qū)別：

①抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。

②抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型的范疇更廣。

③抽象數(shù)據(jù)類型可通過程序設(shè)計語言中的數(shù)據(jù)類型來表示和實現(xiàn)。

3設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D＝{d1，d2，d3，d4}，R＝{r}，r＝{（d1，d2），（d2，d3），（d3，d4）}，試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。

答：邏輯結(jié)構(gòu)圖如圖1-2所示。

圖1-2　程序邏輯結(jié)構(gòu)圖

4試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù)）。

答：

ADT Complex{
  數(shù)據(jù)對象：D={r,i|r,i為實數(shù)}
  數(shù)據(jù)關(guān)系：R={<r,i>}
  基本操作：
    InitComplex(&C,re,im)
      操作結(jié)果：構(gòu)造一個復(fù)數(shù)C，其實部和虛部分別為re和im
    DestroyCmoplex(&C)
      操作結(jié)果：銷毀復(fù)數(shù)C
    Get(C,k,&e)
      操作結(jié)果：用e返回復(fù)數(shù)C的第k元的值
    Put(&C,k,e)
      操作結(jié)果：改變復(fù)數(shù)C的第k元的值為e
    IsAscending(C)
      操作結(jié)果：如果復(fù)數(shù)C的兩個元素按升序排列，則返回1，否則返回0
    IsDescending(C)
      操作結(jié)果：如果復(fù)數(shù)C的兩個元素按降序排列，則返回1，否則返回0
    Max(C,&e)
      操作結(jié)果：用e返回復(fù)數(shù)C的兩個元素中值較大的一個
    Min(C,&e)
      操作結(jié)果：用e返回復(fù)數(shù)C的兩個元素中值較小的一個
}ADT Complex
 
ADT RationalNumber{
  數(shù)據(jù)對象：D={s,m|s,m為自然數(shù),且m不為0}
  數(shù)據(jù)關(guān)系：R={<s,m>}
  基本操作：
    InitRationalNumber(&R,s,m)
      操作結(jié)果：構(gòu)造一個有理數(shù)R，其分子和分母分別為s和m
    DestroyRationalNumber(&R)
      操作結(jié)果：銷毀有理數(shù)R
    Get(R,k,&e)
      操作結(jié)果：用e返回有理數(shù)R的第k元的值
    Put(&R,k,e)
      操作結(jié)果：改變有理數(shù)R的第k元的值為e
    IsAscending(R)
      操作結(jié)果：若有理數(shù)R的兩個元素按升序排列，則返回1，否則返回0
    IsDescending(R)
      操作結(jié)果：若有理數(shù)R的兩個元素按降序排列，則返回1，否則返回0
    Max(R,&e)
      操作結(jié)果：用e返回有理數(shù)R的兩個元素中值較大的一個
    Min(R,&e)
      操作結(jié)果：用e返回有理數(shù)R的兩個元素中值較小的一個
}ADT RationalNumber

【注意】考研中很少出現(xiàn)直接書寫ADT的題目，但是會要求設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，無非就是對ADT的設(shè)計與完善過程。

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()為取絕對值函數(shù)
}

答：以上程序段等價框圖分別如圖1-3，圖1-4和圖1-5所示。

（1）

圖1-3　等價框圖（1）

（2）

圖1-4　等價框圖（2）

（3）

圖1-5　等價框圖（3）

6在程序設(shè)計中，常用下列三種不同的出錯處理方式：

（1）用exit語句終止執(zhí)行并報告錯誤；

（2）以函數(shù)的返回值區(qū)別正確返回或錯誤返回；

（3）設(shè)置一個整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯誤返回。

試討論這三種方法各自的優(yōu)缺點。

答：（1）優(yōu)點：exit用于異常錯誤處理，可以強行中斷程序的執(zhí)行，并返回至操作系統(tǒng)，操作系統(tǒng)會自動回收資源。

缺點：退出地點太多不利于調(diào)試。

（2）優(yōu)點：以函數(shù)的返回值區(qū)別正確返回或錯誤返回，常用于子程序的測試，便于實現(xiàn)程序的局部控制，不會直接終止程序的運行。

缺點：判斷太多，必須人工維護一份錯誤值列表。

（3）優(yōu)點：用整型函數(shù)進行錯誤處理可以給出錯誤類型，便于迅速確定錯誤。

缺點：需要完整的整型變量的釋義，才能方便理解。

7在程序設(shè)計中，可采用下列三種方法實現(xiàn)輸出和輸入：

（1）通過scanf和printf語句；

（2）通過函數(shù)的參數(shù)顯式傳遞；

（3）通過全局變量隱式傳遞。

試討論這三種方法的優(yōu)缺點。

答：（1）用scanf和printf直接進行輸入輸出

優(yōu)點：形象、直觀。

缺點：需要格式控制，較為煩瑣，如果出現(xiàn)錯誤，則會引起整個系統(tǒng)的崩潰，參數(shù)類型受限制，內(nèi)存開銷大。

（2）通過函數(shù)的參數(shù)顯式傳遞進行輸入輸出

優(yōu)點：便于實現(xiàn)信息的隱蔽，減少出錯的可能。

缺點：參數(shù)說明比較煩瑣，內(nèi)存開銷大。

（3）通過全局變量的隱式傳遞進行輸入輸出

優(yōu)點：方便，只需修改變量的值即可，內(nèi)存開銷小；

缺點：過多的全局變量使程序的維護較為困難，內(nèi)容極易丟失。

8設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號@的語句的頻度：

（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的常數(shù)
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假設(shè)n為2的乘冪，并且n＞2，試求下列算法的時間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。

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

答：因為循環(huán)執(zhí)行條件是x<n/2，則循環(huán)語句x*=2;count++;的執(zhí)行頻度是O（log₂n）。count++共執(zhí)行了log₂n－2次，所以count＝log₂n－2。

10按增長率由小至大的順序排列下列各函數(shù)：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，（常見函數(shù)的增長率示意圖如圖1-6）。

圖1-6　常見函數(shù)的增長率示意圖

答：常見時間復(fù)雜度按照數(shù)量級遞增排列為：

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已知有實現(xiàn)同一功能的兩個算法，其時間復(fù)雜度分別為O（2ⁿ）和O（n¹⁰），假設(shè)現(xiàn)實中計算機可連續(xù)運算的時間為10⁷秒（100多天），每秒可執(zhí)行基本操作（根據(jù)這些操作來估算算法時間復(fù)雜度）10⁵次。試問在此條件下，這兩個算法可解問題的規(guī)模（即n值的范圍）各為多少？哪個算法更適宜？請說明理由。

答：10⁷*10⁵＝10¹²

2ⁿ＝10¹²，n＝40

n¹⁰＝10¹²，n＝16

第一種算法更合適，因為對于同樣的循環(huán)次數(shù)n，第二種算法所花費的代價比較大。

12設(shè)有以下三個函數(shù)：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表示的是漸進時間復(fù)雜度，計算出結(jié)果后只需取其規(guī)模的階數(shù)來做比較。

13試設(shè)定若干n值，比較兩函數(shù)n²和50nlog₂n的增長趨勢，并確定n在什么范圍內(nèi)，函數(shù)n²的值大于50nlog₂n的值。

答：（1）n²的增長趨勢快，但在n較小的時候，50nlog₂n的值較大。

（2）令n²＝50nlog₂n，解得n≈450，故當(dāng)n＞450時，n²＞50nlog₂n。

14判斷下列各對函數(shù)f（n）和g（n），當(dāng)n→∞時，哪個函數(shù)增長更快？

（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）更快

【注意】該題需要找到主要影響函數(shù)增長的部分，例如（1）相當(dāng)于比較n²和n⁴的增長速度。

15試用數(shù)學(xué)歸納法證明：

（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，等式成立；

③設(shè)n＝k（k＞＝0）時，公式成立，即1＋4＋9＋…＋k²＝k（k＋1）（2k＋1）/6。

則當(dāng)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，等式成立；

③設(shè)n＝k（k＞＝0）時等式成立，即x⁰＋x¹＋x²＋…＋x^k＝（x^k＋1－1）/（x－1）

則當(dāng)n＝k＋1時，x⁰＋x¹＋x²＋…＋x^k＋x^k＋1＝（x^k＋1－1）/（x－1）＋x^k＋1＝[（x^k＋1－1）＋x^k＋1（x－1）]/（x－1）＝[（x^k＋1－1）＋x^k＋2－x^k＋1]/（x－1）＝（x^k＋2－1）/（x－1）也滿足公式。

綜上所述

成立，得證。

（3）證明：

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

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

③設(shè)n＝k（k＞＝1）時等式成立，即2⁰＋2¹＋…＋2^k－1＝2^k－1

則當(dāng)n＝k＋1時，2⁰＋2¹＋…＋2^k－1＋2^k＝2^k－1＋2^k＝2×2^k－1＝2^k＋1－1也滿足公式。

綜上所述

成立，得證。

（4）證明：

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

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

③設(shè)n＝k（k＞＝1）時等式成立，即（2×1－1）＋（2×2－1）＋…＋（2×k－1）＝k²

則當(dāng)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）²也滿足公式。

綜上所述

成立，得證。

【注意】數(shù)學(xué)歸納法基本步驟：

①由題設(shè)證明n＝1等特殊情況成立；

②設(shè)n＝k時成立；

③證明n＝k＋1時成立。

【算法設(shè)計題】

16試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)X，Y和Z的值。

答：假設(shè)我們?nèi)砸繶、Y和Z的次序輸入這三個整數(shù)，則此題的目標(biāo)是做到X≥Y≥Z。在算法中應(yīng)考慮對這3個元素做盡可能的比較和移動，如下述算法在最壞的情況下只需進行3次比較和7次移動。

void print_descending(int X,int Y,int Z) //按從大到小順序輸出三個整數(shù)
{
  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;
}

17已知k階斐波那契序列的定義為

f₀＝0，f₁＝0，…，f_k－2＝0，f_k－1＝1

f_n＝f_n－1＋f_n－2＋…＋f_n－k，n＝k，k＋1，…

試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。

答：

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]

所以上述算法的時間復(fù)雜度僅為O（m）。如果采用遞歸設(shè)計，將達(dá)到O（k^m）。即使采用暫存中間結(jié)果的方法，也將達(dá)到O（m²）。

18假設(shè)有A，B，C，D，E五個高等院校進行田徑對抗賽，各院校的單項成績均已存入計算機，并構(gòu)成一張表，表中每一行的形式為

編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團體總分，并輸出。

答：

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];
//算法過程體中主要結(jié)構(gòu)：
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）的值并存入數(shù)組a[arrsize]的各個分量中。假設(shè)計算機中允許的整數(shù)最大值為MAXINT，則當(dāng)n＞arrsize或?qū)δ硞€k（1≤k≤n），使k!*2^k＞MAXINT時，應(yīng)按出錯處理。注意選擇你認(rèn)為較好的出錯處理方法。

答：注意MAXINT為計算機中允許出現(xiàn)的最大值，則在過程體中不能以計算機所得結(jié)果大于MAXINT作為判斷出錯的依據(jù)。

#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₀），并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。本題的輸入為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("輸入多項式的系數(shù)a[0]—a[n]:"); //在此之上所有語句僅執(zhí)行一次
  for(i=0;i<=n;i++)
    scanf("%d",&a[i]); //執(zhí)行n+1次
  printf("The polynomail value is:%d\n",polynomail(a,n,x,n)); //執(zhí)行一次
  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; //遞歸函數(shù)，polynomail函數(shù)執(zhí)行n+1次
  else
    return a[n];
}

本算法的時間復(fù)雜度為O（n）。