習題

1.填空題

（1）數據結構所研究的內容包括數據的邏輯結構、數據的物理結構和數據的運算集合。存儲結構（又稱物理結構）是邏輯結構在_____，它包括_____和_____的表示。施加于_____之上的一組操作構成了數據的運算集合。

（2）數據類型是高級語言中的_____數據結構。

（3）算法的設計要求包括：正確性、可讀性、健壯性和_____，可讀性的含義是_____，健壯性是指_____。

（4）算法效率的度量應拋開具體機器的，對于一個特定算法只考慮算法本身的效率，而算法自身的執行效率是_____函數。

（5）一個算法的時間復雜度隨問題的輸入數據集的不同而不同，通常討論_____情況下的時間復雜度。

（6）一個算法的語句頻度表達式是5n*n*log2n+2n*n*n*log2n+1000*n*n*n*n，這個算法的時間復雜度是_____，另一個算法的語句頻度表達式是40*n*n+2log2n+1000，這個算法的時間復雜度是_____。

（7）算法的時間復雜度與空間復雜度相比，通常以_____作為主要度量指標。

（8）在下面程序段中，s=s+p語句的頻度為_____，p*=j語句的頻度為_____，該程序段的時間復雜度為_____。

i=0,
s=0;
while (++i<=n)
{  p=1;
  for(j=1;j<=i;j++)
      p*=j;
  s=s+p;
}

2.判斷題

（1）數據元素是數據的最小單位。

（2）算法可以用不同的語言描述，如果用類C語言或類Pascal語言等高級語言來描述，算法實際上就是程序了。

（3）存儲結構既要存儲數據元素本身又要表示數據元素之間的邏輯關系。

（4）數據結構是帶有結構的數據元素的集合。

（5）數據的邏輯結構是指各數據元素之間的邏輯關系，是用戶根據需要而建立的。

（6）數據結構在計算機中的映像（或表示）稱為存儲結構。

（7）算法的可讀性的含義是：對于非法的輸入數據，算法能給出相應的響應，而不是產生不可預料的后果。

（8）數據的物理結構是指數據在計算機內實際的存儲形式。

（9）算法的時間復雜度是算法執行時間的絕對度量。

（10）算法的正確性是指算法不存在錯誤。

3.簡答題

（1）簡述下列概念：數據、數據元素、數據類型、數據結構、邏輯結構、存儲結構。

（2）設n為正整數，給出下列算法中原操作語句的語句頻度及程序段的時間復雜度。

（a）i=1;

k=0;

while (i<=n-1)
{
     k=k+2*i;
     i++;
}

（b）i=1;k=0;

do
{
         k=k+2*i;
         i++;
}
while (i!=n)

（c）x=91;

n=100;
while (n>0)
     if (x>100 )
     {
         x=x-10;
         n=n-1;
     }
     else
x++;

（d）x=n;/* n>1 */

y=0;
while (x>=(y+1)*( y+1))
     y++;

（e）for(i=1;i<=n;i++)

for(i=1;i<=n;i++)
     for(j=i;j<=i;j++)
          for(k=j;k<=j;k++)
               x++;