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

1、第一章概論第一章概論自測(cè)題答案自測(cè)題答案一、填空題一、填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)操作對(duì)象以及它們之間的以及它們之間的關(guān)系關(guān)系和運(yùn)算等的學(xué)科。和運(yùn)算等的學(xué)科。2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（數(shù)據(jù)結(jié)構(gòu)被形式地定義為（DR），其中），其中D是數(shù)據(jù)元素?cái)?shù)據(jù)元素的有限的有限集合，集合，R是D上的上的關(guān)系關(guān)系有限集合。有限集合。3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包

2、括數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、數(shù)據(jù)的、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的和數(shù)據(jù)的運(yùn)算運(yùn)算這三個(gè)方面的內(nèi)容。這三個(gè)方面的內(nèi)容。4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)非線性結(jié)構(gòu)。5.線性結(jié)構(gòu)中元素之間存在線性結(jié)構(gòu)中元素之間存在一對(duì)一一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多多對(duì)多關(guān)

3、系。關(guān)系。6在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒有沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有且只有1個(gè)后續(xù)結(jié)點(diǎn)。個(gè)后續(xù)結(jié)點(diǎn)。7.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)

4、后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以結(jié)點(diǎn)數(shù)可以任意多個(gè)任意多個(gè)。8.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多任意多個(gè)。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序順序、鏈?zhǔn)芥準(zhǔn)?、索引、索引和散列散列?0.數(shù)據(jù)的運(yùn)算最常用的有數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是種，它們分別是插入插

5、入、刪除、修改、刪除、修改、查找、排序、排序。11.一個(gè)算法的效率可分為一個(gè)算法的效率可分為時(shí)間時(shí)間效率和效率和空間空間效率。效率。二、單項(xiàng)選擇題二、單項(xiàng)選擇題（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一關(guān)系（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；構(gòu)；A)存儲(chǔ)B)物理fi=0ini)f(j=0