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

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

2、8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。（√）9.數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。（）10.算法是對解題方法和步驟的描述。（√）二、填空題二、填空題1.數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(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é)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)結(jié)點(diǎn)。6.在

3、圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個(gè)。7.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu)。8.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。9.線性結(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)、存儲(chǔ)結(jié)構(gòu)和算法（或運(yùn)算）3個(gè)方面的內(nèi)容。13.數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系有限集

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

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

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

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

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

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

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