實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)參考答案

1、0單元練習(xí)單元練習(xí)1一判斷題（下列各題，正確的請在前面的括號內(nèi)打一判斷題（下列各題，正確的請在前面的括號內(nèi)打√；錯誤的打；錯誤的打╳）（√）（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（√）（2）一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運(yùn)算集構(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)時可以通用。（√）

2、（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)的存儲映像。（√）（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)可分為兩大類，它們是線性

3、結(jié)構(gòu)和非線性結(jié)構(gòu)。（4）樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。（5）在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個結(jié)點(diǎn)只有1個前趨結(jié)點(diǎn)。（6）在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(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)結(jié)構(gòu)中的元素之間存在一對多的關(guān)系，（11）圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。（1

4、2）數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法（或運(yùn)算）三個方面的內(nèi)容。（13）數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。（14）算法是一個有窮指令的集合。（15）算法效率的度量可以分為事先估算法和事后統(tǒng)計法。（16）一個算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。（17）算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲空間，它是該算法求解問題規(guī)模n的函數(shù)。（18）若一個算法中的語句頻度之和為T（n）=6n3nl

5、og2n，則算法的時間復(fù)雜度為O（nlog2n）。2A.邏輯結(jié)構(gòu)B.存儲結(jié)構(gòu)C.邏輯實現(xiàn)D.存儲實現(xiàn)（14）每一個存儲結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，存儲結(jié)點(diǎn)存放在連續(xù)的存儲空間，另外有一組指明結(jié)點(diǎn)存儲位置的表，該存儲方式是（C）存儲方式。A.順序B.鏈?zhǔn)紺.索引D.散列（15）算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的（A）。A.正確性B.易讀性C.健壯性D.高效性（16）算法在發(fā)生非法操作時可以作出處理的特性稱為算法的（C）。A.正確性B.易

6、讀性C.健壯性D.高效性（17）下列時間復(fù)雜度中最壞的是（D）。A.O（1）B.O（n）C.O（log2n）D.O（n2）（18）下列算法的時間復(fù)雜度是（D）。f(i=0ini)f(j=0inj)c[i][j]=ijA.O（1）B.O（n）C.O（log2n）D.O（n2）（19）算法分析的兩個主要方面是（A）。A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（20）計算機(jī)算法必須具備輸入、輸出和