數據結構練習題及答案

1、1第1章緒論緒論一、一、判斷題判斷題1.數據的邏輯結構與數據元素本身的內容和形式無關。（√）2.一個數據結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。（√）3.數據元素是數據的最小單位。（）4.數據的邏輯結構和數據的存儲結構是相同的。（）5.程序和算法原則上沒有區(qū)別，所以在討論數據結構時可以通用。（）6.從邏輯關系上講，數據結構主要分為線性結構和非線性結構兩類。（√）7.數據的存儲結構是數據的邏輯結構的存儲映象。（√）

2、8.數據的物理結構是指數據在計算機內實際的存儲形式。（√）9.數據的邏輯結構是依賴于計算機的。（）10.算法是對解題方法和步驟的描述。（√）二、填空題二、填空題1.數據有邏輯結構和存儲結構兩種結構。2.數據邏輯結構除了集合以外，還包括線性結構、樹形結構和圖形結構。3.數據結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構。4.樹形結構和圖形結構合稱為非線性結構。5.在樹形結構中，除了樹根結點以外，其余每個結點只有1個前驅結點。6.在

3、圖形結構中，每個結點的前驅結點數和后繼結點數可以任意多個。7.數據的存儲結構又叫物理結構。8.數據的存儲結構形式包括順序存儲、鏈式存儲、索引存儲和散列存儲。9.線性結構中的元素之間存在一對一的關系。10.樹形結構中的元素之間存在一對多的關系。11.圖形結構的元素之間存在多對多的關系。12.數據結構主要研究數據的邏輯結構、存儲結構和算法（或運算）3個方面的內容。13.數據結構被定義為（D，R），其中D是數據的有限集合，R是D上的關系有限集

4、合。14.算法是一個有窮指令的集合。15.算法效率的度量可以分為事先估算法和事后統(tǒng)計法。16.一個算法的時間復雜度是算法輸入規(guī)模的函數。17.算法的空間復雜度是指該算法所耗費的存儲空間，它是該算法求解問題規(guī)模的n的函數。18.若一個算法中的語句頻度之和為T(n)=6n3nlog2n則算法的時間復雜度為O（nlog2n）。19.若一個算法的語句頻度之和為T(n)=3nnlog2n2則算法的時間復雜度為O（n2）。20.數據結構是一門研究非

5、數值計算的程序問題中計算機的操作對象，以及它們之間的關系和運算的學科。三、選擇題三、選擇題1.數據結構通常是研究數據的（A）及它們之間的相互關系。A存儲結構和邏輯結構B存儲和抽象C聯(lián)系和抽象D聯(lián)系與邏輯2.在邏輯上可以把數據結構分成（C）。A動態(tài)結構和靜態(tài)結構B緊湊結構和非緊湊結構C線性結構和非線性結構D內部結構和外部結構。3.數據在計算機存儲內表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A存儲結構B邏輯結構C順序存儲結構

6、D鏈式存儲結構4.非線性結構中的每個結點（D）。A無直接前驅結點B無直接后繼結點3第2章線性表線性表一、判斷題一、判斷題1.線性表的鏈式存儲結構優(yōu)于順序存儲。（）2.鏈表的每個結點都恰好包含一個指針域。（）3.在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（√）4.順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。（）5.線性鏈表的刪除算法簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。

7、（）6.順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。（）7.線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數據元素。（√）8.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（√）9.順序表結構適宜進行順序存取，而鏈表適宜進行隨機存取。（）10.插入和刪除操作是數據結構中是最基本的兩種操作，所以這兩種操作在數組中也經常使用。（）二、填空題二、填空題1.順序表中邏輯上相鄰的元素在物理位置上必須相鄰。2

8、.線性表中結點的集合是有限的，結點間的關系是一對一關系。3.順序表相對于鏈表的優(yōu)點是節(jié)省存儲和隨機存取。4.鏈表相對于順序表的優(yōu)點是插入、刪除方便。5.當線性表的元素總數基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應采用順序存儲結構。6.順序表中訪問任意一個結點的時間復雜度均為O（1）。7.鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。8.在雙向鏈表中要刪除已知結點P，其時間復雜度為O（1）。9

9、.在單向鏈表中要在已知結點P之前插入一個新結點，需找到P的直接前驅結點的地址，其查找的時間復雜度為O(n)。10.在單向鏈表中需知道頭指針才能遍歷整個鏈表。11.線性表中第一個結點沒有直接前驅，稱為開始結點。12.在一個長度為n的順序表中刪除第i個元素，要移動ni個元素。13.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移ni1個元素。14.在無頭結點的單向鏈表中，第一個結點的地址存放在頭指針中，而其他結點的存儲地址

10、存放在前趨結點的指針域中。15.線性表的元素總數不確定，且經常需要進行插入和刪除操作，應采用鏈子存儲結構。16.在線性表中的鏈式存儲中，元素之間的邏輯關系是通過指針決定。17.在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其前趨結點，另一個指向其后繼結點。18.對一個需要經常進行插入和刪除操作的線性表，采用鏈式存儲結構為宜。19.雙向鏈表中，設P是指向其中待刪除的結點，則需要執(zhí)行的操作為pprinext=pnext；pnextpri