數據結構基本概念及復雜度計算練習題及答案

 

一 選擇題

1. 算法的計算量的大小稱為計算的（B ）。

A． 效率      B. 復雜性     C. 現實性     D. 難度

2.算法的時間復雜度取決于（C ）

A．問題的規模       B. 待處理數據的初態       C. A和B      

3．從邏輯上可以把數據結構分為（C ）兩大類。

A．動態結構、靜態結構              B．順序結構、鏈式結構

C．線性結構、非線性結構            D．初等結構、構造型結構

4．連續存儲設計時，存儲單元的地址（A ）。

A．一定連續    B．一定不連續   C．不一定連續     D．部分連續，部分不連續

5. 以下屬于邏輯結構的是（C ）。

A．順序表       B. 哈希表       C.有序表      D. 單鏈表

 

二、判斷題

1. 數據元素是數據的最小單位 。(×)

2. 記錄是數據處理的最小單位。 (×)

3. 數據的邏輯結構是指數據的各數據項之間的邏輯關系；(×)

4．程序一定是算法。(×)

5. 在順序存儲結構中，有時也存儲數據結構中元素之間的關系。(×)

6. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。(×)

7. 數據結構的基本操作的設置的最重要的準則是，實現應用程序與存儲結構的獨立。(√)

8. 數據的邏輯結構說明數據元素之間的順序關系,它依賴于計算機的儲存結構. (×)

 

三、填空 

1．數據的物理結構包括 數據元素 的表示和數據元素間關系 的表示。

2. 對于給定的n個元素,可以構造出的邏輯結構有 集合， 線性結構 ， 樹形結構 ， 圖狀結構或網狀結構四種。

3．數據的邏輯結構是指數據的組織形式，即數據元素之間邏輯關系的總體。而邏輯關系是指數據元素之間的關聯方式或稱“鄰接關系”。

4．一個數據結構在計算機中表示（又稱映像） 稱為存儲結構。

5．抽象數據類型的定義僅取決于它的一組邏輯特性，而與在計算機內部如何表示和實現 無關，即不論其內部結構如何變化，只要它的數學特性不變，都不影響其外部使用。

6．數據結構中評價算法的兩個重要指標是 算法的時間復雜度和空間復雜度 。

7. 數據結構是研討數據的邏輯結構和物理結構，以及它們之間的相互關系，并對與這種結構定義相應的操作（運算），設計出相應的算法。

8． 一個算法具有5個特性: 有窮性 、確定性、可行性 ，有零個或多個輸入、有一個或多個輸出。

 

四、應用題

1. 數據結構是一門研究什么內容的學科？

答：數據結構是一門研究在非數值計算的程序設計問題中，計算機的操作對象及對象間的關系和施加于對象的操作等的學科

2. 數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？

答：四種表示方法

    （1）順序存儲方式。數據元素順序存放，每個存儲結點只含一個元素。存儲位置反映數據元素間的邏輯關系。存儲密度大，但有些操作（如插入、刪除）效率較差。

    （2）鏈式存儲方式。每個存儲結點除包含數據元素信息外還包含一組（至少一個）指針。指針反映數據元素間的邏輯關系。這種方式不要求存儲空間連續，便于動態操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。

    （3）索引存儲方式。除數據元素存儲在一地址連續的內存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲區間端點（下標），兼有靜態和動態特性。

    （4）散列存儲方式。通過散列函數和解決沖突的方法，將關鍵字散列在連續的有限的地址空間內，并將散列函數的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。

3. 數據類型和抽象數據類型是如何定義的。二者有何相同和不同之處，抽象數據類型的主要特點是什么？使用抽象數據類型的主要好處是什么？

答:數據類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應有整數范圍），其操作有加、減、乘、除、求余等。實際上數據類型是廠家提供給用戶的已實現了的數據結構。“抽象數據類型（ADT）”指一個數學模型及定義在該模型上的一組操作。“抽象”的意義在于數據類型的數學抽象特性。抽象數據類型的定義僅取決于它的邏輯特性，而與其在計算機內部如何表示和實現無關。無論其內部結構如何變化，只要它的數學特性不變就不影響它的外部使用。抽象數據類型和數據類型實質上是一個概念。此外，抽象數據類型的范圍更廣，它已不再局限于機器已定義和實現的數據類型，還包括用戶在設計軟件系統時自行定義的數據類型。使用抽象數據類型定義的軟件模塊含定義、表示和實現三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現細節。抽象數據類型的出現使程序設計不再是“藝術”，而是向“科學”邁進了一步。

4. 回答問題

（1）在數據結構課程中，數據的邏輯結構，數據的存儲結構及數據的運算之間存在著怎樣的關系？

答:數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關聯方式或“鄰接關系”），數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。數據的運算是對數據定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現則是依賴于存儲結構。

（2）若邏輯結構相同但存儲結構不同，則為不同的數據結構。這樣的說法對嗎？舉例說明之。

答: 邏輯結構相同但存儲不同，可以是不同的數據結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。

（3）在給定的邏輯結構及其存儲表示上可以定義不同的運算集合，從而得到不同的數據結構。這樣說法對嗎？舉例說明之。

答:棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數據結構。

（4）評價各種不同數據結構的標準是什么？

答:數據結構的評價非常復雜，可以考慮兩個方面，一是所選數據結構是否準確、完整的刻劃了問題的基本特征；二是是否容易實現（如對數據分解是否恰當；邏輯結構的選擇是否適合于運算的功能，是否有利于運算的實現；基本運算的選擇是否恰當。）

5．評價一個好的算法，您是從哪幾方面來考慮的？

答:評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健壯性；四是算法的時空效率（運行）。

6．解釋和比較以下各組概念

（1）算法的時間復雜性

答:算法的時間復雜性是算法輸入規模的函數。算法的輸入規模或問題的規模是作為該算法輸入的數據所含數據元素的數目，或與此數目有關的其它參數。有時考慮算法在最壞情況下的時間復雜度或平均時間復雜度。

（2）算法

答: 算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。 

（3）頻度

答:頻度。在分析算法時間復雜度時，有時需要估算基本操作的原操作，它是執行次數最多的一個操作，該操作重復執行的次數稱為頻度。 

7. 根據數據元素之間的邏輯關系，一般有哪幾類基本的數據結構？

答:集合、線性結構、樹形結構、圖形或網狀結構。

8．對于一個數據結構，一般包括哪三個方面的討論？

答:邏輯結構、存儲結構、操作（運算）。

9．分析下面語句段執行的時間復雜度。

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

    for(j=1;j＜=n；j++)

       s++;

答:O（n2）

 

（2）for(i=1;i＜=n;i++)

    for(j=i;j＜=n;j++)

      s++;

答:O（n2）

 

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

    for(j=1;j<=i;j++) 

       s++;

答:O（n2）