1.3　考研真題與典型題詳解

一、選擇題

1算法的計算量的大小稱為計算的（　　）。[北京郵電大學2000研]

A．效率

B．復雜性

C．現實性

D．難度

【答案】B

【解析】算法復雜度通常分為時間復雜度和空間復雜度，算法的計算量的大小可以用時間復雜度衡量，即可以稱為計算的復雜度。

2此程序的復雜度為（　　）。[大連理工2008研]

for(int i=0;i<m;i++)
  for(int j=0;j<n;j++)
    A[i][j]=i*j;

A．O（m²）

B．O（n²）

C．O（m×n）

D．O（m＋n）

【答案】C

【解析】時間復雜度是指基本操作重復執行次數的階數T（n）＝O（f（n））。基本操作為A[i][j]＝i*j，該語句的執行次數與外層的兩個循環次數相等，為m×n，因此，算法的復雜度為O（m×n）。

3計算算法的時間復雜度是屬于一種（　　）。[北京理工2005研]

A．事前統計的方法

B．事前分析估算的方法

C．事后統計的方法

D．事后分析估算的方法

【答案】B

【解析】度量一個程序的執行時間通常有兩種方法：

①事后統計。

②事前分析估計。

算法的時間復雜度是指算法中基本操作重復執行的次數的階數，因此計算算法的時間復雜度屬于事前分析估算的方法。

4以下屬于邏輯結構的是（　　）。[西安電子2001研]

A．順序表

B．哈希表

C．有序表

D．單鏈表

【答案】C

【解析】順序表是線性表的順序存儲結構；哈希表是存儲結構；單鏈表是線性表的鏈式存儲結構；有序表是指已經按照某一關鍵字排好序的線性表，它是邏輯結構。因此，C項正確，而ABD三項都是數據元素在計算機中的存儲結構，屬于物理結構，而不是題目要求的邏輯結構。

5以下數據結構中，哪一個是線性結構？（　　）[北方交通大學2001研]

A．廣義表

B．二叉樹

C．稀疏矩陣

D．串

【答案】D

【解析】線性結構：數據元素之間存在一對一的關系，常見的線性結構有：線性表、棧、隊列、雙隊列、數組、串。非線性結構指存在多對一或者一對多的關系，邏輯特征上表現為一個結點可能有多個前驅結點或多個后繼結點，常見的非線性結構有：二維數組、多維數組、樹、圖、廣義表等。

廣義表（又稱列表）是一種非線性的數據結構，是線性表的一種推廣。

6下面說法錯誤的是（　　）。

（1）算法原地工作的含義是指不需要任何額外的輔助空間

（2）在相同的規模n下，復雜度O（n）的算法在時間上總是優于復雜度O（2ⁿ）的算法

（3）所謂時間復雜度是指最壞情況下，估算算法執行時間的一個上界

（4）同一個算法，實現語言的級別越高，執行效率就越低

A．（1）

B．（1），（2）

C．（1），（4）

D．（3）

【答案】C

【解析】①一個可執行程序可能涉及中間變量和數組等，需要額外的存儲空間，如果這個額外空間相對于問題的規模（輸入數據）來說是個常數，稱之為原地工作，輔助空間為O（1）。

②對于相同的數據規模，O（n）的效率顯然優于O（2ⁿ）。

③對于O（1）、O（log₂n）、O（n）等，O的形式定義為：若f（n）是正數n的一個函數，則O（f（n））表示存在一個正常數M，使得當n≥n₀時滿足|O（f（n））|小于等于M×|f（n）|，即O（f（n））給出了函數f（n）的一個上界。

④編譯鏈接后的最終的機器指令操作的次數越少，說明該語言在某種編譯鏈接環境下效率越高，實際上即使同一種語言在不同的編譯環境下，也有可能不同。

【注意】在對錯判斷題中忌“絕對化”，當出現一定，任何等表示絕對性的詞語的時候需要慎重對待。

7程序段

FOR i=n-1 DOWNTO 1
  DO
  FOR j=l TO i
    DO
    IF A[j]>A[j+1]
      THEN A[j]與A[j+1]對換;

其中n為正整數，則最后一行的語句頻度在最壞情況下是（　　）。

A．O（n）

B．O（nlogn）

C．O（n³）

D．O（n²）

【答案】D

【解析】這個是冒泡排序，最壞的情況下需要進行1＋2＋…＋n－1次交換，即時間復雜度是O（n²）。

二、填空題

1抽象數據類型的定義僅取決于它的一組______，而與______無關，即不論其內部結構如何變化，只要它的______不變，都不影響其外部使用。[山東大學2001研]

【答案】邏輯特性；在計算機內部如何表示和實現；數學特性

2數據結構是研討數據的______和______以及它們之間的相互關系，并對與這種結構定義相應的______，設計出相應的______。

【答案】邏輯結構；物理結構；操作（運算）；算法

3在下面的程序段中，對X的賦值語句的頻度為______（表示為n的函數）。

FOR i=1 TO n
  DO
  FOR j=1 TO i
    DO
    FOR k=1 TO j
      DO
      x=x+delta;

【答案】1＋（1＋2）＋（1＋2＋3）＋…＋（1＋2＋…＋n）＝n（n＋1）（n＋2）/6，即O（n³）

【解析】當i＝1時，賦值語句就被執行了一次。當i＝2時，賦值語句被執行了1＋2次。當i＝3時，賦值語句被執行了1＋2＋3次。可以推出賦值語句總共被執行了1＋（1＋2）＋（1＋2＋3）＋…＋（1＋2＋…＋n）＝n（n＋1）（n＋2）/6次。

4對于給定的元素，可以構造出的邏輯結構有______，______，______，______四種。

【答案】集合；線性結構；樹形結構；圖狀結構（網狀結構）

5已知如下程序段：

FOR i=n DOWNTO 1
  DO {語句1}
  BEGIN
    x=x+1; {語句2}
    FOR j=n DOWNTO i
      DO {語句3}
      Y:=y+1; {語句4}
  END；

語句1執行的頻度為______；語句2執行的頻度為______；語句3執行的頻度為______；語句4執行的頻度為______。

【答案】n＋1；n；n（n＋3）/2；n（n＋1）/2

【解析】語句1執行到不符合條件情況下，即從i＝n到i＝0，執行了n＋1次；當語句1不符合條件時不會執行語句2，故語句2執行了n次；語句3每次都要執行到不符合條件，故執行次數為2＋3＋4…＋（n＋1）即n（n＋3）/2；同樣，當語句3不符合條件時不會執行語句4，故語句4執行了1＋2＋3…＋n次即n（n＋1）/2。

6一個算法具有5個特性：______、______、______、有零個或多個輸入、有一個或多個輸出。[華中理工大學2000研]

【答案】有窮性；確定性；可行性

7下面程序段中DO循環體執行次數的數量級是______。

i=1;
WHILE i<n
  DO i=i+2;

【答案】n/2

8計算機執行下面的語句時，語句s的執行次數為______。[南京理工大學2000研]

for(i=1;i<n-1;i++)
  for(j=n;j>=i;j--)
    s;

【答案】（n＋3）（n－2）/2

【解析】當i＝1時，s被執行了n次。當i＝n－2時，s被執行了3次。所以s總共被執行了3＋4＋…＋n＝（n＋3）（n－2）/2。

三、綜合題

1分析以下程序段中語句④的頻度以及該程序段的時間復雜度。

for(i=0;i<n;i++) //①
{
  y=y+1; //②
  for(j=0;j<=2*n;j++) //③
    x++; //④
}

答：語句的頻度是指該語句被重復執行的次數。在本題中語句④執行的次數是內外兩層循環的次數，即n（2n＋1）＝2n²＋n，因此該語句的頻度是2n²＋n。

時間復雜度可以用算法中的基本操作重復執行的次數來度量，本程序段中的語句④即為基本操作，所以該算法的時間復雜度＝2n²＋n＝O（n²）。

2分析以下算法的時間復雜度。

void fun(int n)
{
  int i=0;
  int s=0;
  while(s<n)
  {
    ++i;
    s=s+i;
  }
}

答：顯然n為問題規模，基本操作為語句“++i”和“s=s+i”。變量i與s都從0開始，假設循環執行m次結束，即當循環m次時，m＝n，則有s0＝0，s1＝1，s2＝1＋2＝3，s3＝1＋2＋3＝6，…，sm＝m（m＋1）/2（其中sm為執行到第m次的時候s的值），則有m（m＋1）/2＋K＝n（K為起修正作用的常數），由求根公式得

由此可知時間復雜度為

3舉一個數據結構的例子，敘述其邏輯結構、存儲結構、運算三個方面的內容。

答：例如有一張學生成績表，如表1-1所示，記錄了一個班的學生各門課的成績。這個表是一個數據結構。

表1-1　學生成績表

（1）邏輯結構

每個記錄（包括學號，姓名，成績）是指一個結點，對于整個表來說，只有一個開始結點（其前面無記錄）和一個終端結點（其后面無記錄），其他的結點則各有一個也只有一個前驅結點和后繼結點（即它的前面和后面均有且僅只有一個記錄）。

（2）存儲結構

若用鏈式存儲方式，結點的數據類型定義如下：

struct node
{
  int no; //存放學號的數據域
  char name[10]; //存放姓名的數據域
  int score; //存放成績的數據域
  struct node* next; //指向下一個結點的指針
}

（3）數據運算

在建表之后就要對這張表中的記錄進行查詢、修改、刪除等操作。

4以下算法的時間復雜度為多少？

void hanoi(int n,char x,char y,char z)
{
  if (n==1)
    printf("move %c to %c\n",x,z);
  else
  {
    hanoi(n-1,x,z,y);
    printf("move%cto%c\n",x,z);
    hanoi(n-1,y,x,z);
  }
}

答：設函數hanoi（n）的執行時間為T（n），則hanoi（n－1）的執行時間為T（n－1）。

有：

當n＝1時，T（1）＝1；

當n＞1時，T（n）＝2T（n－1）＋1。

所以有：

T（n）＝2T（n－1）＋1＝2（2T（n－2）＋1）＋1＝2²T（n－2）＋1＋2＝2²（2T（n－3）＋1）＋1＋2¹＝2³T（n－2）＋1＋2¹＋2²＝…＝2^n－1T（1）＋1＋2¹＋2²＋…＋2^n－2＝2^n－1＋2^n－1－1＝2ⁿ－1＝O（2ⁿ）

5假設一個不帶頭結點的單鏈表h中所有的結點數據域都為整數，設計一個遞歸算法求其中的最大值。

答：設單鏈表h（以h為首結點指針）中最大值為f（h），根據單鏈表的定義，h->next也是一個單鏈表，則f（h->next）為以h->next為首結點指針的單鏈表中的最大值，如圖1-7所示。

f（h）求a₁…a_n中最大元素

圖1-7　f（h）和f（h->next）的功能

得到以下遞歸模型：

f(h)＝h->data  //若h->next＝NULL或單鏈表中只有一個結點

f(h)＝MAX(h->data,f(h->next))  //其他情況

其中MAX表示求兩個數的最大值。對應的遞歸算法如下：

int f(LinkList h)
{
  int m;
  if(h->next==NULL)
    return h->data;
  else
  {
    m=f(h->next); //遞歸調用
    if(m>h->data)
      return m;
    else
      return h->data;
  }
}