本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題第1章緒論

一、選擇題（每題2分，共20分）1.以下哪一個(gè)不是算法的特性（）。

A.有窮性B.確定性C.簡(jiǎn)單性D.可行性2.數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是()的集合。

A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.規(guī)律結(jié)構(gòu)

3.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間繁雜度是（）。x=2；

while(x=i；j--)s；

11.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的__________和__________，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的__________，設(shè)計(jì)出相應(yīng)的__________。12.數(shù)據(jù)的物理結(jié)構(gòu)包括_________的表示和_________的表示。

13.一個(gè)算法具有5個(gè)特性:__________、__________、__________，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。

14.抽象數(shù)據(jù)類型的定義僅取決于它的一組_________，而與_________無關(guān)，即不管其內(nèi)部結(jié)構(gòu)如何變化，只要它的__________不變，都不影響其外部使用。15.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中_________稱為存儲(chǔ)結(jié)構(gòu)。

16.在有n個(gè)選手參與的單循環(huán)賽中，總共將進(jìn)行______場(chǎng)比賽。

17.對(duì)于給定的n個(gè)元素，可以構(gòu)造出的規(guī)律結(jié)構(gòu)有_______，_______，_______，______四種。

18.數(shù)據(jù)的規(guī)律結(jié)構(gòu)是指_________________________________________________________。

參考題：

20.下面程序段的時(shí)間繁雜度為________。(n>1)答案O(n)sum=1；

for(i=0；sum1)答案O(n)sum=1；

for(i=0;sum1DOi:=i_div_2;

25.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是_______。答案nlog2ni:=1;

WHILEi<nBEGINFORj:=1TOnDO_x:=x+1;i:=i*2END；

26.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是：_________答案log2ni：=1；WHILEi<nDOi：=i*2;

答案1+25.在下面的程序段中，對(duì)ｘ的賦值語句的頻度為______（表示為n的函數(shù)）。（1+2++

3

（1+2+3）+?+（1+2+?+n）=n(n+1)(n+2)/6O(n)FORi：＝１TOnDOFORj：＝１TOiDO

FORk：＝1TOjDO

ｘ：＝ｘ＋delta；

27.已知如下程序段

FORi:=nDOWNTO1DO{語句1}BEGIN

x:=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。

四、簡(jiǎn)答題（共10分）

1.什么是算法?算法的5個(gè)特性是什么?試根據(jù)這些特性解釋算法與程序的區(qū)別。

2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括線性表、棧、隊(duì)列、數(shù)組等；非線性結(jié)構(gòu)包括樹、圖等；這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？

3.簡(jiǎn)述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

參考題：

4.試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別？答案簡(jiǎn)單來說，數(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í)間繁雜度僅與問題的規(guī)模相關(guān)嗎?

答案不是,事實(shí)上，算法的時(shí)間繁雜度不僅與問題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的狀況下，其時(shí)間繁雜度就是只與求解問題的規(guī)模相關(guān)的。我們?cè)谔接憰r(shí)間繁雜度時(shí)，一般就是以最壞狀況下的時(shí)間繁雜度為準(zhǔn)的。6.常用的存儲(chǔ)表示方法有哪幾種?答案常用的存儲(chǔ)表示方法有四種:

順序存儲(chǔ)方法：它是把規(guī)律上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的規(guī)律關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來表達(dá)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。

2

鏈接存儲(chǔ)方法：它不要求規(guī)律上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的規(guī)律關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。散列存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算該結(jié)點(diǎn)的存儲(chǔ)地址。

7.試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、表達(dá)其規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。答案例如有一張學(xué)生成績(jī)表，記錄了一個(gè)班的學(xué)生各門課的成績(jī)。按學(xué)生的姓名為一行記成的表。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，成績(jī)等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的規(guī)律結(jié)構(gòu)。那么我們?cè)鯓影堰@個(gè)表中的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)里呢?用高級(jí)語言如何表示各結(jié)點(diǎn)之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲(chǔ)結(jié)構(gòu)的問題，我們從高級(jí)語言的層次探討這個(gè)問題。最終，我們有了這個(gè)表(數(shù)據(jù)結(jié)構(gòu))，確定要用它，那么就是要對(duì)這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。

7.什么是數(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ù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。有關(guān)數(shù)據(jù)結(jié)構(gòu)的探討一般涉及以下三方面的內(nèi)容：

①數(shù)據(jù)元素以及它們相互之間的規(guī)律關(guān)系，也稱為數(shù)據(jù)的規(guī)律結(jié)構(gòu)，簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)；②數(shù)據(jù)元素極其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡(jiǎn)稱為存儲(chǔ)結(jié)構(gòu)；

③施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。

數(shù)據(jù)的規(guī)律結(jié)構(gòu)是從規(guī)律關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)不是一碼事，是與計(jì)算機(jī)存儲(chǔ)無關(guān)的。因此，數(shù)據(jù)的規(guī)律結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是規(guī)律數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)（亦稱為映像），它是依靠于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)規(guī)律結(jié)構(gòu)上的一組運(yùn)算，每種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。例如探尋、插入、刪除、更新、排序等。8.什么是數(shù)據(jù)?它與信息是什么關(guān)系?

答案什么是信息？廣義地講，信息就是消息。宇宙三要素（物質(zhì)、能量、信息）之一。它是現(xiàn)實(shí)世界各種事物在人們頭腦中的反映。此外，人們通過科學(xué)儀器能夠認(rèn)識(shí)到的也是信息。信息的特征為：可識(shí)別、可存儲(chǔ)、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。

什么是數(shù)據(jù)？由于信息的表現(xiàn)形式十分廣泛，大量信息在計(jì)算機(jī)中不便利存儲(chǔ)和處理，例如，一個(gè)大樓中4部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫(kù)明細(xì)表等，必需將它們轉(zhuǎn)換成數(shù)