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

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-第1章答案2023-5-16第1章緒論一、選擇題〔每題2分，共20分〕1.以下哪一個不是算法的特性〔〕。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ù)，下面程序片段的時間復(fù)雜度是〔〕。x=2；while(x<n/2)x=2*x；A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)4.執(zhí)行下面程序段時，執(zhí)行Ｓ語句的次數(shù)為〔〕．for〔inti=1；i<=n；i++〕for(intj=1；j<=i；j++)S；A.n2B.n2/25.在下面的程序段中，對x的賦值語句的頻度為〔〕。for(i=1；i<=n;i++)for(j=1；j<=n；j++)x=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)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)與動態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。7.下面程序段的時間復(fù)雜度為〔C〕for(inti=0；i<m；i++)for(intj=0；j<n；j++)a[i][j]=i*j；A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)8.算法的計算量的大小稱為計算的〔〕。A．效率B.復(fù)雜性C.現(xiàn)實性D.難度9.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指〔〕。A．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)B．?dāng)?shù)據(jù)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)D．?dāng)?shù)據(jù)元素之間的關(guān)系10.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的〔〕結(jié)構(gòu)。A．邏輯B．存儲C．邏輯和存儲D．物理11.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲〔〕。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)元素的類型C．?dāng)?shù)據(jù)元素之間的關(guān)系D．?dāng)?shù)據(jù)的存儲方法12.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮〔〕。A．各結(jié)點的值如何B．結(jié)點個數(shù)的多少C．對數(shù)據(jù)有哪些運算D．所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。13.算法分析的目的是〔〕，算法分析的兩個主要方面是〔〕。

〔1〕A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系

C．分析算法的效率以求改進(jìn)D．分析算法的易讀性和文檔性

〔2〕A．空間復(fù)雜度和時間復(fù)雜度B．正確性和簡明性

C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性

15.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著〔〕。

A．?dāng)?shù)據(jù)元素具有同一特點

B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致

C．每個數(shù)據(jù)元素都一樣

D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等16.以下說法正確的選項是〔〕。

A．?dāng)?shù)據(jù)項是數(shù)據(jù)的根本單位

B．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位

C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合

D．一些外表上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

二、判斷題〔每題1分，共10分〕1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。〔〕2.算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，那么算法實際上就是程序了?！病?.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系?！病?.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機(jī)有關(guān)。〔〕5.數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機(jī)中的存儲方式和數(shù)據(jù)的運算三個方面。()6.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何?！病?.抽象數(shù)據(jù)類型〔ADT〕包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實現(xiàn)。()

8.抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實現(xiàn)無關(guān)?！病?.順序存儲結(jié)構(gòu)只能用于線性結(jié)構(gòu)，不能用于非線性型結(jié)構(gòu)?！病?0.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。〔〕11.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)?！病?2.數(shù)據(jù)項是數(shù)據(jù)的根本單位?！病橙?、填空題〔每空1分，共10分〕1.通常從四個方面評判算法的質(zhì)量：_________、_________、_________和_________。2.根據(jù)數(shù)據(jù)元素之間的關(guān)系不同，通常有以下四種結(jié)構(gòu)，、、和網(wǎng)狀結(jié)構(gòu)。3.數(shù)據(jù)的物理結(jié)構(gòu)主要有_____________和______________兩種不同的表示方法。4.數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有兩種不同的表示方法：和5.算法的5個重要特性是_________、__________、__________、輸入和輸出。6.一個算法的效率可分為效率和效率。7.下面程序段的時間復(fù)雜度是。for(i=0；i<n；i++)for(j=0；j<m；j++)A[i][j]=0；8.下面程序段的時間復(fù)雜度是_______。for(i=0；i<n；i++)for(j=0；j<n；j++)s+=B[i][j]；9.數(shù)據(jù)結(jié)構(gòu)中評判算法的兩個重要指標(biāo)是算法的__________和__________。10.計算機(jī)執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為_______。FOR(i=l；i<n-l；i++)FOR(j=n；j>=i；j--)s；11.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的__________和__________，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的__________，設(shè)計出相應(yīng)的__________。12.數(shù)據(jù)的物理結(jié)構(gòu)包括_________的表示和_________的表示。13.一個算法具有5個特性:__________、__________、__________，有零個或多個輸入、有一個或多個輸出。14.抽象數(shù)據(jù)類型的定義僅取決于它的一組_________，而與_________無關(guān)，即不管其內(nèi)部結(jié)構(gòu)如何變化，只要它的__________不變，都不影響其外部使用。15.一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中_________稱為存儲結(jié)構(gòu)。16.在有n個選手參加的單循環(huán)賽中，總共將進(jìn)行______場比賽。17.對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有_______，_______，_______，______四種。18.數(shù)據(jù)的邏輯結(jié)構(gòu)是指_________________________________________________________。參考題：20.下面程序段的時間復(fù)雜度為________。(n>1)答案O(n)sum=1；for(i=0；sum<n；i++)sum+=1；21.下面程序段的時間復(fù)雜度是〔O(log3n)〕。

i＝0；

while〔i<=n〕

i=i*3；

22.設(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ù)的程序段，請將未完成的局部填入，使之完整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②923.下面程序段的時間復(fù)雜度為________。(n>1)答案O(n)sum=1；for(i=0;sum<n;i++)sum+=1;24.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是_______。答案log2n2i：=n*nWHILEi<>1DOi:=i_div_2;25.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是_______。答案nlog2ni:=1;WHILEi<nBEGINFORj:=1TOnDO_x:=x+1;i:=i*2END；26.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：_________答案log2ni：=1；WHILEi<nDOi：=i*2;25.在下面的程序段中，對ｘ的賦值語句的頻度為______〔表示為n的函數(shù)〕。答案1+〔1+2++〔1+2+3〕+…+〔1+2+…+n〕=n(n+1)(n+2)/6O(n3)FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；27.如下程序段FORi:=nDOWNTO1DO{語句1}BEGINx:=x+1；{語句2}FORj:=nDOWNTOiDO{語句3}y:=y+1;{語句4}END；語句1執(zhí)行的頻度為__________；語句2執(zhí)行的頻度為__________；語句3執(zhí)行的頻度為__________；語句4執(zhí)行的頻度為___________。答案n+1nn(n+3)/2n(n+1)/2。四、簡答題〔共10分〕1.什么是算法?算法的5個特性是什么?試根據(jù)這些特性解釋算法與程序的區(qū)別。2.數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括線性表、棧、隊列、數(shù)組等；非線性結(jié)構(gòu)包括樹、圖等；這兩類結(jié)構(gòu)各自的特點是什么？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è)計語言中數(shù)據(jù)類型概念的區(qū)別？答案簡單來說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)據(jù)元素；抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作；而程序設(shè)計語言中的數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。5.算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?答案不是,事實上，算法的時間復(fù)雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的元素取值等相關(guān)，但在最壞的情況下，其時間復(fù)雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復(fù)雜度時，一般就是以最壞情況下的時間復(fù)雜度為準(zhǔn)的。6.常用的存儲表示方法有哪幾種?答案常用的存儲表示方法有四種:順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來表達(dá)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。散列存儲方法：根據(jù)結(jié)點的關(guān)鍵字直接計算該結(jié)點的存儲地址。7.試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、表達(dá)其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。答案例如有一張學(xué)生成績表，記錄了一個班的學(xué)生各門課的成績。按學(xué)生的姓名為一行記成的表。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學(xué)號，成績等字段)就是一個結(jié)點，對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點那么各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)。那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機(jī)里呢?用高級語言如何表示各結(jié)點之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲結(jié)構(gòu)的問題，我們從高級語言的層次討論這個問題。最后，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對這個表可以進(jìn)行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。7.什么是數(shù)據(jù)結(jié)構(gòu)?有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個方面?答案數(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ù)結(jié)構(gòu)；②數(shù)據(jù)元素極其關(guān)系在計算機(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ī)存儲無關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計算機(jī)存儲器中的實現(xiàn)〔亦稱為映像〕，它是依賴于計算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運算，每種數(shù)據(jù)結(jié)構(gòu)都有一個運算的集合。例如搜索、插入、刪除、更新、排序等。8.什么是數(shù)據(jù)?它與信息是什么關(guān)系?答案什么是信息？廣義地講，信息就是消息。宇宙三要素〔物質(zhì)、能量、信息〕之一。它是現(xiàn)實世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識到的也是信息。信息的特征為：可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因為信息的表現(xiàn)形式十分廣泛，許多信息在計算機(jī)中不方便存儲和處理，例如，一個大樓中4部電梯在軟件控制下調(diào)度和運行的狀態(tài)、一個商店中商品的在庫明細(xì)表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計算機(jī)中存儲、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。在計算機(jī)中，信息必須以數(shù)據(jù)的形式出現(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.時間、空間7.m*n8.n2(n*n)9.時間復(fù)雜度空間復(fù)雜度。10.n(n+1)/2-3或(n+3)(n-2)/211.邏輯結(jié)構(gòu)物理結(jié)構(gòu)操作〔運算〕算法12.數(shù)據(jù)元素數(shù)據(jù)元素間關(guān)系13.有窮性確定性可行性14.邏輯特性在計算機(jī)內(nèi)部如何表示和實現(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分〕1.什么是算法?算法的5個特性是什么?試根據(jù)這些特性解釋算法與程序的區(qū)別。答：通常，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個指令序列。〞一個算法應(yīng)當(dāng)具有以下特性：①有輸入。一個算法必須有0個或多個輸入。它們是算法開始運算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。②有輸出。一個算法應(yīng)有一個或多個輸出，輸出的量是算法計算的結(jié)果。③確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動作都應(yīng)嚴(yán)格地、清晰地規(guī)定。④有窮性。一個算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。⑤可行性。算法中每一條運算都必須是足夠根本的。就是說，它們原那么上都能精確地執(zhí)行，甚至人們僅用筆和紙