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

1、0單元練習(xí)單元練習(xí)1一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打√；錯(cuò)誤的打；錯(cuò)誤的打╳）（√）（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(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）程序和算法原則上沒(méi)有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。（√）

2、（6）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類(lèi)。（√）（7）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。（√）（8）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。（ㄨ）（9）數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴(lài)于計(jì)算機(jī)的。（√）（10）算法是對(duì)解題方法和步驟的描述。二填空題二填空題（1）數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)。（2）數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)。（3）數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們是線性

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

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

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

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