練習題1

1．單項選擇題

（1）線性結構中數據元素之間是（　）關系。

A．一對多

B．多對多

C．多對一

D．一對一

（2）數據結構中與計算機無關的是數據的（　）結構。

A．存儲

B．物理

C．邏輯

D．物理和存儲

（3）在計算機中存儲數據時，通常不僅要存儲各數據元素的值，而且要存儲（　）。

A．數據的處理方法

B．數據元素的類型

C．數據元素之間的關系

D．數據的存儲方法

（4）數據采用鏈式存儲結構時，要求（　）。

A．每個結點占用一片連續的存儲區域

B．所有結點占用一片連續的存儲區域

C．結點的最后一個域必須是指針域

D．每個結點有多少后繼結點，就必須設多少個指針域

（5）計算機算法指的是（　）。

A．計算方法

B．排序方法

C．求解問題的有限運算序列

D．調度方法

（6）計算機算法必須具備輸入、輸出和（　）等5個特性。

A．可行性、可移植性和可擴充性

B．可行性、確定性和有窮性

C．確定性、有窮性和穩定性

D．易讀性、穩定性和安全性

（7）算法分析的目的是（　）。

A．找出數據結構的合理性

B．研究算法中的輸入和輸出的關系

C．分析算法的效率以求改進

D．分析算法的易懂性和文檔性

（8）算法分析的兩個主要方面是（　）。

A．空間復雜性和時間復雜性

B．正確性和簡明性

C．可讀性和文檔性

D．數據復雜性和程序復雜性

（9）某算法的時間復雜度為O（n2），表明該算法的（　）。

A．問題規模是n2

B．執行時間等于n2

C．執行時間與n2成正比

D．問題規模與n2成正比

（10）某算法的空間復雜度為O（1），表明執行該算法時（　）。

A．不需要存儲空間

B．需要的臨時存儲空間為常量

C．需要的存儲空間恰好為1

D．需要的臨時存儲空間為1

2．填空題

（1）數據結構包括數據的（ ① ）、數據的（ ② ）和數據的（ ③ ）三個方面的內容。

（2）數據結構按邏輯結構可分為兩大類，它們分別是（ ① ）和（ ② ）。

（3）數據結構被形式地定義為（D，R），其中，D是（ ① ）的有限集合，R是D上的（ ② ）的有限集合。

（4）在線性結構中，開始元素（ ① ）前驅元素，其余每個元素有且只有一個前驅元素；最后一個元素（ ② ）后繼元素，其余每個元素有且只有一個后繼元素。

（5）在樹狀結構中，樹根結點沒有（ ① ）結點，其余每個結點有且只有（ ② ）個前驅結點；葉子結點沒有（ ③ ）結點，其余每個結點的后繼結點數可以是（ ④ ）。

（6）在圖形結構中，每個結點的前驅結點個數和后繼結點個數可以是（　）。

（7）數據的存儲結構主要有4種，它們分別是（ ① ）、（ ② ）、（ ③ ）和（ ④ ）存儲結構。

（8）一個算法的效率可分為（ ① ）效率和（ ② ）效率。

（9）在分析算法時，其時間復雜度是（　）的函數。

（10）在分析算法時，其空間復雜度是指執行該算法時所需（　）的大小。

3．簡答題

（1）簡述數據結構中運算描述和運算實現的異同。

（2）以下各函數是算法中語句的執行頻度，n為問題規模，給出對應的時間復雜度。

T1（n）=nlog2n—1000log2n

T2（n）=nlog23—1000log2n

T3（n）=n2—1000log2n

T4（n）=2nlog2n—1000log2n

（3）分析下面程序段中循環語句的執行次數。

      int j=0,s=0,n=100;
      do
      {    j=j+1;
           s=s+10 ? j;
      } while(j<n && s<n);

（4）執行下面的語句時，語句s++的執行次數為多少？

      int s=0;
      for (i=1;i<n—1;i++)
           for (j=n;j>=i;j——)
                    s++;

（5）設n為問題規模，求以下算法的時間復雜度。

（6）設n為問題規模，是一個正偶數，試計算以下算法結束時m的值，并給出該算法的時間復雜度。