習題一

一、概念題

1．試述數據結構研究的三個方面的內容。

2．試述集合、線性結構、樹形結構和圖形結構四種常用數據結構的特性。

3．設有數據的邏輯結構的二元組定義形式為B=（D，R），其中D={a1，a2，…，an}，R={<ai，ai+1>|i=1，2，…，n-1}。請畫出此邏輯結構對應的順序存儲結構和鏈式存儲結構的。

4．設一個數據結構的邏輯結構如圖1-11所示，請寫出它的二元組定義形式。

5．設有函數f（n）=3n2-n+4，請證明f（n）=O（n2）。

6．請比較下列函數的增長率，并按增長率遞增的順序排列下列函數：

（1）2 100（2）（3/2）n（3）（4/3）n（4）nn（5）n2/3（6）n3/2（7）n!

（8）（9）n（10）log2n（11）1/log2n（12）log2（log2n）（13）nlog2n（14）

7．試確定下列程序段中有標記符號“*”的語句行的語句頻度（其中n為正整數）。

    （1）i=1；k=0；
          while（i＜=n-1）{
              k+=1 0*i；  //*
              i++；
          }
    （2）i=1；k=0；
          do {
              k+=1 0*i；    //*
              i++；
          }while（i＜=n-1）；
    （3）i=1；k=0；
          while（i＜=n-1）{
              i++；

              k+=1 0*i；    //*
          }
    （4）k=0；
          for（i=1；i＜=n；i++）{
            for（j=1；j＜=i；j++）
              k++；        //*
          }
    （5）i=1；j=0；
          while（i+j＜=n）{
              if（i＞j）j++；  //*
              else i++；
          }
    （6）x=n；y=0；   //n是不小于 1的常數
          while（x＞=（y+1）*（y+1））{
            y++；     //*
          }
    （7）x=91；y=100；
          while（y＞0）{
              if（x＞100）{x-=10；y--；}     //*
              else x++；
    （8）a=1；m=1；
          while（a＜n）
          {
            m+=a； a*=3；   //*
          }

二、算法設計題

1．設計算法，求長度為n的實數數組中值最大的數組元素及其在數組中的下標，并分析算法的時間復雜度。

2．設計算法，求一元多項式的值Pn（x0），并確定算法中每一條語句的執行次數和整個算法的時間復雜度。算法的輸入是ai（i=0，1，2，…，n），n和x0；輸出為Pn（x0）。