數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案

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

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

3、圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以任意多個。7.數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。8.數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈?zhǔn)酱鎯Α⑺饕鎯蜕⒘写鎯Α?.線性結(jié)構(gòu)中的元素之間存在一對一的關(guān)系。10.樹形結(jié)構(gòu)中的元素之間存在一對多的關(guān)系。11.圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。12.數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法（或運算）3個方面的內(nèi)容。13.數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系有限集

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

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

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

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

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

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

10、存放在前趨結(jié)點的指針域中。15.線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用鏈子存儲結(jié)構(gòu)。16.在線性表中的鏈?zhǔn)酱鎯χ?，元素之間的邏輯關(guān)系是通過指針決定。17.在雙向鏈表中，每個結(jié)點都有兩個指針域，它們一個指向其前趨結(jié)點，另一個指向其后繼結(jié)點。18.對一個需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。19.雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點，則需要執(zhí)行的操作為pprinext=pnext；pnextpri