數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 第1章

第1章緒論

二、難點(diǎn)與重點(diǎn)

1、基本概念：理解什么是數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與

物理結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的抽象層次。

3、算法與算法分析：理解算法的定義、算法的特性、算法的時(shí)間代價(jià)、算法的空間代

價(jià)。

>算法與程序的不同之處需要從算法的特性來解釋

>算法的正確性是最主要的要求

>算法的可讀性是必須考慮的

>程序的程序步數(shù)的計(jì)算與算法的事前估計(jì)

>程序的時(shí)間代價(jià)是指算法的漸進(jìn)時(shí)間復(fù)雜性度量

三、習(xí)題的解析

1-2什么是數(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ān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱為數(shù)據(jù)結(jié)構(gòu);

②數(shù)據(jù)成員極其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡稱為

存儲(chǔ)結(jié)構(gòu)；

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

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)不是一碼事，是與計(jì)算機(jī)存

儲(chǔ)無關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的

應(yīng)用視圖。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)（亦稱為映像），它是

依賴于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算，每

種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。例如搜索、插入、刪除、更新、排序等。

1-3數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、棧、

隊(duì)列、優(yōu)先級(jí)隊(duì)列等；非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？

【解答】

線性結(jié)構(gòu)的特點(diǎn)是：在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于一個(gè)序列中，有且僅有一個(gè)開始成員

和一個(gè)終端成員，并且所有數(shù)據(jù)成員都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。例如，一維數(shù)

組、線性表等就是典型的線性結(jié)構(gòu)

非線性結(jié)構(gòu)的特點(diǎn)是：一個(gè)數(shù)據(jù)成員可能有零個(gè)、一個(gè)或多個(gè)直接前驅(qū)和直接后繼。例

如，樹、圖或網(wǎng)絡(luò)等都是典型的非線性結(jié)構(gòu)。

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

【解答】

通常，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個(gè)指令序列?！币粋€(gè)算法應(yīng)當(dāng)具有

以下特性：

①有輸入。一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。

這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語

句在算法內(nèi)給定。

②有輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。

③確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對(duì)于每一種情況，需要執(zhí)行的

動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。

④有窮性。一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。

⑤有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們?cè)瓌t上都能精確地

執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。

算法和程序不同，程序可以不滿足上述的特性（4）。例如，一個(gè)操作系統(tǒng)在用戶未使用

前一直處于“等待”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運(yùn)行,

直到系統(tǒng)停工。

此外，算法是面向功能的，通常用面向過程的方式描述；程序可以用面向?qū)ο蠓绞酱罱?/p>

它的框架。

1-7設(shè)〃為正整數(shù)，分析下列各程序段中加下劃線的語句的程序步數(shù)。

(1)for(inti=1;i<=n;i++)(2)x=0;yo；

for(intj=l;j<=n;j++){for(inti=1;i<=n;i++)

c[i]Ul=0.0;for(intj=l；j<=i；j++)

for(intk=1;k<=n;k++)for(intk=1;k<=j;k++)

=c川[i]+aU*]*b[k][il;x=x+y;

【解答】

nnn

⑴=

i=lj=lk=l

i=lj=lk=li=lj=li=l\乙J乙i=l乙i=l

1n(n—+—l)-(--2---n---+----l--)--------1----n---(-n-_|_+-1-)--------n--(--n----+-l)--(--n---+-----2--)------------------

-2622-6

四、其他練習(xí)題

1-10填空題

（A）由某一數(shù)據(jù)對(duì)象和該對(duì)象中各個(gè)數(shù)據(jù)成員間的關(guān)系組成。依據(jù)所有數(shù)據(jù)成員

之間關(guān)系的不同，（A）分為兩大類：（B）和（C）。在（B）中的各個(gè)數(shù)

據(jù)成員依次排列在一個(gè)線性序列中；（C）的各個(gè)數(shù)據(jù)成員不再保持在一個(gè)線性序列中，

每個(gè)數(shù)據(jù)成員可能與零個(gè)或多個(gè)其他數(shù)據(jù)成員發(fā)生聯(lián)系。

根據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的(D)和(E)。(D)是面向問題的,

(E)是面向計(jì)算機(jī)的。

【解答】

A：數(shù)據(jù)結(jié)構(gòu)B：線性結(jié)構(gòu)C：非線性結(jié)構(gòu)

D：邏輯結(jié)構(gòu)E：存儲(chǔ)結(jié)構(gòu)

1-11判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前打“Y”，否則打“x”。

(1)數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

(2)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。

(3)數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象。

(4)數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。

(5)算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的。

【解答】

⑴x⑵4(3)x(4)<(5)x

1-12判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前打“4”，否則打“x”。

(1)所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。

(2)同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)

據(jù)項(xiàng)的個(gè)數(shù)都相等。

(3)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。

(4)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。

(5)從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

【解答】

⑴<(2)x⑶Y(4)x(5)<

1-13填空題

算法是一個(gè)有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。它應(yīng)當(dāng)具有輸

入、輸出、(A)、有窮性和可執(zhí)行性等特性。

算法效率的度量分為(B)和(C(B)主要通過在算法的某些部位插裝

時(shí)間函數(shù)來測(cè)定算法完成某一規(guī)定功能所需的時(shí)間。而(C)不實(shí)際運(yùn)行算法，它是分

析算法中語句的執(zhí)行次數(shù)來度量算法的時(shí)間復(fù)雜性。

程序所需的存儲(chǔ)空間包含兩個(gè)部分(D)和(E)。(D)空間的大小與輸

入輸出數(shù)據(jù)的個(gè)數(shù)多少，數(shù)值大小無關(guān)；(E)空間主要包括其大小與問題規(guī)模有關(guān)的

成分變量所占空間，引用變量所占空間，以及遞歸棧所用的空間，還有在算法運(yùn)行過程中動(dòng)

態(tài)分配和回收的空間。

【解答】

A：確定性B：事后測(cè)量C：事前估計(jì)

D：固定部分E：可變部分

1-15單選題

(1)一個(gè)數(shù)組元素a[i]與的表示等價(jià)。

A：*(a+i)B：a+iC：*a+iD：&a+i

(2)對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是不同則不是重載函數(shù)。

A：參數(shù)類型B：參數(shù)個(gè)數(shù)C：函數(shù)類型

(3)若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為一_______參數(shù)

A：指針B：引用C：值

(4)下面程序段的時(shí)間復(fù)雜度為________。

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j；

A：O(m2)B：O(n2)C：0(m*n)D：0(m+n)

(5)執(zhí)行下面程序段時(shí)，執(zhí)行S語句的次數(shù)為________。

for(inti=1;i<=n;i++)

for(intj=l；j<=i；j++)

s；

A：n2B：n2/2C：n(n+l)D：n(n+l)/2

(6)下面算法的時(shí)間復(fù)雜度為________。

intf(unsignedintn){

if(n==0||n==l)return1;

elsereturnn*f(n-1);

}

A：0(1)B：0(n)C：O(n2)D：0(n!)

【解答】

(1)A(2)C(3)B(4)C(5)D(6)B

1-16填空題

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、、和______四種。

(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、、和四種。

(3)在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，直接前驅(qū)和直接后繼結(jié)點(diǎn)之間分別存在著

、和的聯(lián)系。

(4)一種抽象數(shù)據(jù)類型包括和兩個(gè)部分。

(5)當(dāng)一個(gè)傳值型形式參數(shù)所占的體積較大時(shí)，應(yīng)最好說明為,以節(jié)省參數(shù)值

的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。

(6)當(dāng)需要用一個(gè)形式參數(shù)直接改變對(duì)應(yīng)實(shí)際參數(shù)的值時(shí)，則該形式參數(shù)應(yīng)說明為

(7)在函數(shù)中對(duì)引用型形式參數(shù)的修改就是對(duì)相應(yīng)________的修改，而對(duì)________型形

式參數(shù)的修改只局限在該函數(shù)的內(nèi)部，不會(huì)反映到對(duì)應(yīng)的實(shí)際參數(shù)上。

(8)當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí)，則應(yīng)在程序文件中包含頭文件，當(dāng)需要進(jìn)行

文件I/O操作時(shí)，則應(yīng)在程序文件中包含頭文件。

(9)一個(gè)記錄r理論上占有的存儲(chǔ)空間的大小等于所有域,實(shí)際上占有的存儲(chǔ)

空間的大小即記錄長度為。

(10)一個(gè)數(shù)組a所占有的存儲(chǔ)空間的大小即數(shù)組長度為,下標(biāo)為i的元素a[i]

的存儲(chǔ)地址為,或者為。

(11)函數(shù)重載要求、或有所不同。

(12)對(duì)于雙目操作符，其重載函數(shù)(非成員函數(shù))帶有個(gè)參數(shù)，其中至少有一

個(gè)為的類型。

(13)若對(duì)象ra和rb中至少有一個(gè)是屬于用戶定義的類型，則執(zhí)行ra==rb時(shí)，需要調(diào)

用______重載函數(shù)，該函數(shù)的第一個(gè)參數(shù)應(yīng)與的類型相同，第二個(gè)參數(shù)應(yīng)與

的類型相同。

(14)從一維數(shù)組a[n]中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為,輸出一

個(gè)二維數(shù)組b[m][n]中所有元素值的時(shí)間復(fù)雜度為o

(15)在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為，p*=j語句的執(zhí)行次數(shù)為

，該程序段的時(shí)間復(fù)雜度為。

inti=0,s=0;

while(++i<=n){

intp=1;

for(intj=l;j<=i;j++)p*=j;

s=s+p;

)

(16)一個(gè)算法的時(shí)間復(fù)雜度為(3/+2〃log2〃+4〃-7)/(5〃)，其數(shù)量級(jí)表示為o

【解答】

(1)集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)(次序無先后)

(2)順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)(次序無先后)

(3)1