數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-第1章答案2014-5-16

1、WORD格式可編輯第 1 章緒論一、選擇題（每小題 2 分，共 20 分）1. 以下哪一個(gè)不是算法的特性（） 。A. 有窮性 B. 確定性 C.簡潔性 D.可行性2. 數(shù)據(jù)結(jié)構(gòu)的定義為 （D， S） ，其中 D是（） 的集合。A.算法 B. 數(shù)據(jù)元素 C.數(shù)據(jù)操作 D.邏輯結(jié)構(gòu)3. 設(shè) n 是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是（） 。 x=2；while（x<n/2）x=2*x ；2A.O（log 2n）B.O（n）C.O（nlog 2n）D.O（n）4. 執(zhí)行下面程序段時(shí)，執(zhí)行語句的次數(shù)為（） for （ inti=1 ； i<=n ； i+ ） for（intj

2、=1 ； j<=i ； j+）S ； A.n2B.n2/2C.n（n+1）D.n（n+1）/25. 在下面的程序段中，對 x 的賦值語句的頻度為（） 。 for（i=1 ； i<=n;i+）for（j=1 ； j<=n ； j+）x=x+1;2A.O（2n）B.O（n）C.O（n ）D.O（log 2n）6. 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（） 。A. 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B. 靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D. 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。7. 下面程序段的時(shí)間復(fù)雜度為（ C）for（inti=0 ； i<m； i+）for（intj=0 ； j&

3、lt;n ； j+）aij=i*j；A.O（m2）B.O（n2）C.O（m*n）D.O（m+n）2）B.O（n8. 算法的計(jì)算量的大小稱為計(jì)算的（） 。 A效率 B. 復(fù)雜性 C.現(xiàn)實(shí)性 D.難度9. 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（） 。A數(shù)據(jù)的存儲結(jié)構(gòu) B數(shù)據(jù)結(jié)構(gòu) C數(shù)據(jù)的邏輯結(jié)構(gòu) D數(shù)據(jù)元素之間的關(guān)系10. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。 A邏輯 B存儲 C邏輯和存儲 D物理11. 在存儲數(shù)據(jù)時(shí)，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲（）。 A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系 D數(shù)據(jù)的存儲方法12. 在決定選取何種存儲結(jié)構(gòu)時(shí)，一般不考慮（

4、）。A各結(jié)點(diǎn)的值如何 B結(jié)點(diǎn)個(gè)數(shù)的多少 C對數(shù)據(jù)有哪些運(yùn)算 D所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。13. 算法分析的目的是（），算法分析的兩個(gè)主要方面是（）。（ 1 ） A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進(jìn) D分析算法的易讀性和文檔性（ 2 ） A空間復(fù)雜度和時(shí)間復(fù)雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性15. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致 C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

5、14. 以下說法正確的是（）。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)二、判斷題（每小題 1 分，共 10 分）16. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）17. 算法可以用不同的語言描述，如果用C 語言或 PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。（）18. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（）19. 算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）20. 數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方 面。 （）21. 在決定選取何種存儲結(jié)

6、構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（）22. 抽象數(shù)據(jù)類型（ ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一 個(gè) ADT 的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（）23. 抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。（）24. 順序存儲結(jié)構(gòu)只能用于線性結(jié)構(gòu)，不能用于非線性型結(jié)構(gòu)。（）25. 健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）26. 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)。（）27. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。（）三、填空題（每空 1 分，共 10 分）1. 通常從四個(gè)方面評價(jià)算法的質(zhì)量： 、 、 和 。2. 根據(jù)數(shù)據(jù)元素之間的關(guān)系不同，通

7、常有以下四種結(jié)構(gòu)，、和 網(wǎng)狀結(jié)構(gòu)。3. 數(shù)據(jù)的物理結(jié)構(gòu)主要有 和 兩種不同的表示方法。4. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：和5. 算法的 5 個(gè)重要特性是 、 、 、輸入和輸出。6. 一個(gè)算法的效率可分為效率和效率。7. 下面程序段的時(shí)間復(fù)雜度是。for（i=0 ； i<n ； i+）for（j=0 ； j<m； j+）Aij=0；8. 下面程序段的時(shí)間復(fù)雜度是 。for（i=0 ； i<n ； i+）for（j=0 ；j<n ； j+）s+=Bij；9. 數(shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個(gè)重要指標(biāo)是算法的 和 。10. 計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句 s 的執(zhí)

8、行次數(shù)為 。FOR(i=l ； i<n-l ； i+)FOR(j=n； j>=i ； j-) s；15. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 和 ，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的 ，設(shè)計(jì)出相應(yīng)的 。16. 數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。17. 一個(gè)算法具有 5 個(gè)特性 : 、 、 ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。18. 抽象數(shù)據(jù)類型的定義僅取決于它的一組 ，而與 無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的 不變，都不影響其外部使用。19. 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中 稱為存儲結(jié)構(gòu)。20. 在有 n 個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行 場比賽。21. 對于給定的 n 個(gè)元

9、素，可以構(gòu)造出的邏輯結(jié)構(gòu)有 ， ， ， 四種。22. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 參考題：28. 下面程序段的時(shí)間復(fù)雜度為 。 (n>1) 答案 O(n)sum=1；for(i=0 ； sum<n； i+)sum+=1 ；29. 下面程序段的時(shí)間復(fù)雜度是( O(log3n) )。i 0；while ( i<=n )i=i*3 ；30. 設(shè) m,n 均為自然數(shù)， m可表示為一些不超過 n 的自然數(shù)之和， f(m,n) 為這種表示方式的 數(shù)目。例 f(5,3)=5 ，有 5 種表示方式： 3+2 ， 3+1+1， 2+2+1， 2+1+1+1， 1+1+1+1+1。 以下是該函數(shù)的程序段

10、，請將未完成的部分填入，使之完整intf(m,n) intm,n;if(m=1)return_(1)_;if(n=1)return_(2)_;if(m<n)returnf(m,m); if(m=n)return1+_(3)_;returnf(m.n-1)+f(m-n,_(4)_); 執(zhí)行程序， f(6,4)= 。答案 (1)1(2)1(3)f(m,n-1)(4)n 931. 下面程序段的時(shí)間復(fù)雜度為 。 (n>1) 答案 O(n)sum=1；for(i=0;sum<n;i+)sum+=1;223. 下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 。答案 log 2ni ：

11、=n*nWHILEi<>1DOi:=i_div_2;24. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是 。答案 nlog 2ni:=1;WHILEi<nBEGINFORj:=1TOnDO_x:=x+1;i:=i*2END ；25.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：i ： =1； WHILEi<nDOi： =i*2;32.在下面的程序段中，對的賦值語句的頻度為1+2+3) +,+ ( 1+2+,+n ) =n(n+1)(n+2)/6O(n 答案 log 2n表示為 n 的函數(shù))。答案1+( 1+2+3)專業(yè)知識 整理分享FORi： TOnDOFORj：

12、TOiDOFORk： 1TOjDO： delta ；11. 已知如下程序段FORi:=nDOWNTO1D語O句 1BEGINx:=x+1 ； 語句 2 y:=y+1; 語句 4FORj:=nDOWNTOiDO語句3END；語句 1 執(zhí)行的頻度為 ；語句 2 執(zhí)行的頻度為 ；語句 3 執(zhí)行的頻度為；語句 4 執(zhí)行的頻度為 。答案 n+1nn(n+3)/2n(n+1)/2 四、簡答題(共 10 分)1. 什么是算法 ?算法的 5 個(gè)特性是什么 ?試根據(jù)這些特性解釋算法與程序的區(qū)別。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括線性表、棧、隊(duì)列、數(shù)組等；非線性結(jié)構(gòu)包括樹、圖等；這兩

13、類結(jié)構(gòu)各自的特點(diǎn)是什么？3. 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、 非線性結(jié)構(gòu)。參考題：4. 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別？ 答案簡單來說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)據(jù)元素；抽象數(shù)據(jù)類型是指 一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作；而程序設(shè)計(jì)語言中的數(shù)據(jù)類型不僅定義了一 組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。5. 算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎 ?答案不是 , 事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值 等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與

14、求解問題的規(guī)模相關(guān)的。我們在討論時(shí) 間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。6. 常用的存儲表示方法有哪幾種 ?答案常用的存儲表示方法有四種 : 順序存儲方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯 關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附 加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。 索引存儲方法：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。 散列存儲方法：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算該結(jié)點(diǎn)的存儲地址。26. 試舉一個(gè)數(shù)據(jù)結(jié)

15、構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。 答案例如有一張學(xué)生成績表，記錄了一個(gè)班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成 的表。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄（ 有姓名，學(xué)號，成績等字段 ）就是一個(gè)結(jié)點(diǎn)，對于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn) （它的前面無記錄 ）和一個(gè)終端結(jié)點(diǎn) （ 它的后面無記錄 ），其 他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼 （ 它的前面和后面均有且只有一個(gè)記 錄 ） 。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)。那么我們怎樣把這個(gè)表中的數(shù)據(jù)存儲到計(jì)算 機(jī)里呢 ?用高級語言如何表示各結(jié)點(diǎn)之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄（ 如用數(shù)組表示 ）還是

16、隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲結(jié)構(gòu)的問題，我們從高級語言的層次討論這個(gè)問題。最后，我們有了這個(gè)表 （ 數(shù)據(jù)結(jié)構(gòu) ） ，肯定要用它，那 么就是要對這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對這個(gè)表可以進(jìn)行哪些操作以及 如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。33. 什么是數(shù)據(jù)結(jié)構(gòu) ?有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個(gè)方面 ? 答案數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的關(guān)系。記為：數(shù)據(jù)結(jié)構(gòu) =D,R 。其中， D 是某一 數(shù)據(jù)對象， R 是該對象中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。 有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三方面的內(nèi)容： 數(shù)據(jù)元素以及它們相互之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱為數(shù)據(jù)

17、結(jié)構(gòu)； 數(shù)據(jù)元素極其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的存儲表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡稱為存儲 結(jié)構(gòu)； 施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲不是一碼事，是與計(jì)算機(jī)存儲無 關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用 視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)（亦稱為映像），它是依賴 于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算，每種數(shù) 據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。例如搜索、插入、刪除、更新、排序等。34. 什么是數(shù)據(jù) ?它與信息是什么關(guān)系 ? 答案什么是信息？廣義地講，信息就是消息。宇

18、宙三要素（物質(zhì)、能量、信息）之一。它是 現(xiàn)實(shí)世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識到的也是信息。 信息的特征為：可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可 共享。什么是數(shù)據(jù)？因?yàn)樾畔⒌谋憩F(xiàn)形式十分廣泛，許多信息在計(jì)算機(jī)中不方便存儲和處理，例如， 一個(gè)大樓中 4 部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫明細(xì)表等，必 須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲、處理、變換。因此，數(shù)據(jù) （data） 是信息 的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識別和處 理的符號的集合。在計(jì)算機(jī)中，信息必須以數(shù)據(jù)的形

19、式出現(xiàn)。答案：一、選擇題 1-5CBADC6-10CCBAA11-16CACABD 二、判斷題 1-5 ××××× 6-10 × 11-12 ××三、填空題 1. 正確性易讀性健壯性高效率 2. 集合、線性、樹形 3. 順序 存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu) 4. 順序映像、非順序映像 5. 有窮性、確定性、可行性 6. 時(shí) 間、空間 7.m*n8.n2(n*n)9. 時(shí)間復(fù)雜度空間復(fù)雜度。 10.n(n+1)/2-3 或(n+3)(n-2)/211. 邏輯結(jié)構(gòu)物理結(jié)構(gòu)操作(運(yùn)算)算法 12. 數(shù)據(jù)元素?cái)?shù)據(jù) 元素間關(guān)系 13

20、. 有窮性確定性可行性 14. 邏輯特性在計(jì)算機(jī)內(nèi)部如何 表示和實(shí)現(xiàn)數(shù)學(xué)特性 15. 表示(又稱映像) 16.n(n-1)/217. 集合線性 結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 18. 數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏 輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。四、簡答題(共 10 分)27. 什么是算法 ?算法的 5 個(gè)特性是什么 ?試根據(jù)這些特性解釋算法與程序的區(qū)別。 答：通常，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個(gè)指令序列?！币粋€(gè)算法應(yīng)當(dāng)具有 以下特性：有輸入。一個(gè)算法必須有 0 個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。這些 輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在 算法內(nèi)給定。有輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動(dòng)作 都應(yīng)嚴(yán)格地、清晰地規(guī)定。 有窮性。一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。 可行性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行， 甚至人們僅用筆和紙做有限次運(yùn)算就能完成。算法和程序不同，程序可以不滿足上述的特性 (4) 。例如，一個(gè)操作系統(tǒng)在用戶未使用 前一直處于 "等待" 的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休