第1章緒論

課后習(xí)題講解

1、填空

（1）（）就是數(shù)據(jù)得基本單位，在L算機程序中通常作為一個整體進行考慮與處理。

【解答】數(shù)據(jù)元素

⑵（）就是數(shù)據(jù)得最小單位,（）就是討論數(shù)據(jù)結(jié)構(gòu)時涉及得最小數(shù)據(jù)單位。

【解答】數(shù)據(jù)項，數(shù)據(jù)元素

【分析】數(shù)據(jù)結(jié)構(gòu)指得就是數(shù)據(jù)元素以及數(shù)據(jù)元素之間得關(guān)系。

⑶從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（）、（）與（）。

【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu),圖結(jié)構(gòu)

（4）數(shù)據(jù)得存儲結(jié)構(gòu)主要有（）與（）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面得內(nèi)容：（）與（）。

【解答】順序存儲結(jié)構(gòu)，璉接存儲結(jié)構(gòu)，數(shù)據(jù)元素,數(shù)據(jù)元素之間得關(guān)系

⑸算法具有五個特性，分別就是（）、（）、（）、（）、（）。

【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性,可行性

（6）算法得描述方法通常有（）、（）、（）與（）四種，其中,（）被稱為算法語言。

【解答】自然語m,程序設(shè)計語旨,流程圖，偽代碼,偽代碼

⑺在一般情況下，一個算法得時間復(fù)雜度就是（）得函數(shù)。

【解答】問題規(guī)模

⑻設(shè)待處理問題得規(guī)模為n,若一個算法得時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級得形式為（）,若為

n*log25n,則表示成數(shù)量級得形式為（）。

【解答】O（l）,O（nlog2n）

【分析】用大。記號表示算法得時間復(fù)雜度，需要將低次耗去掉，將最高次耗得系數(shù)去掉。

2、選擇題

⑴順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間得邏輯關(guān)系就是由（）表示得，鏈接存儲結(jié)構(gòu)中得數(shù)據(jù)元素之間得邏輯關(guān)系

就是由（）表示得。

A線性結(jié)構(gòu)B非線性結(jié)構(gòu)C存儲位置D指針

【解答】C,D

【分析】順序存儲結(jié)構(gòu)就就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中得數(shù)據(jù)元素，其邏輯關(guān)系由存儲位置（即元素在數(shù)

組中得下標(biāo)）表示;鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中得一個結(jié)點,元素之間得邏輯關(guān)系由結(jié)點中得指

針表示。

⑵假設(shè)有如下遺產(chǎn)繼承規(guī)則:丈夫與妻子可以相互繼承遺產(chǎn);子女可以繼承父親或母親得遺產(chǎn);子女間不能

相互繼承。則表示該遺產(chǎn)繼承關(guān)系得最合適得數(shù)據(jù)結(jié)構(gòu)應(yīng)該就是（）。

A樹B圖C線性表D集合

【解答】B

【分析】將丈夫、妻子與子女分別作為數(shù)據(jù)元素,根據(jù)題意畫出邏輯結(jié)構(gòu)圖。

⑶算法指得就是（）.

A對特定問題求解步驟得一種描述，就是指令得有限序列。

B計算機程序C解決問題得計算方法D數(shù)據(jù)處理

【解答】A

【分析】計算機程序就是對算法得具體實現(xiàn);簡單地說,算法就是解決問題得方法;數(shù)據(jù)處理就是通過算法完

成得。所以，只有A就是算法得準(zhǔn)確定義。

⑷下面（）不就是算法所必須具備得特性。

A有窮性B確切性C高效性D可行性

【解答】C

【分析】高效性就是好算法應(yīng)具備得特性。

⑸算法分析得目得就是（），算法分析得兩個主要方面就是（）?

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

C分析算法得效率以求改進D分析算法得易讀性與文檔性

E空間性能「時間性能F正確性。簡明性

G可讀性與文檔性H數(shù)據(jù)復(fù)雜性與程序復(fù)雜性

【解答】CZE

3、判斷題

⑴算法得時間復(fù)雜度都要通過算法中得基本語句得執(zhí)行次數(shù)來確定。

【解答】鉛。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)得數(shù)量級來確定。

⑵每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作:插入、刪除與查找。

【解答】錯。如數(shù)組就沒有插入與刪除操作。此題注意就是每種數(shù)據(jù)結(jié)構(gòu)。

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

【解答】錯。就是數(shù)據(jù)之間得邏輯關(guān)系得整體。

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

【解答】對。因此邏輯結(jié)構(gòu)就是數(shù)據(jù)組織得主要方面。

⑸基于某種邏輯結(jié)構(gòu)之上得基本操作,其實現(xiàn)就是唯一得。

【解答】錯?；静僮鞯脤崿F(xiàn)就是基于某種存儲結(jié)構(gòu)設(shè)計得,因而不就是唯一得。

4、分析以下各程序段,并用大。記號表示其執(zhí)行時間。

⑴1=1;k=0;⑵i=l;k=0;

while(i<n-l)do

((

k=k+10*i;k=k+10*i;

i++；i++;

)}while(i<=n)

(3)i=l;j=O,⑷y-0;

while(i+j<=n)while((y+l)*(y+l)<=n)

if(i>j)j++；

y=y+l；

elsei++;

(5)for(i=l;i<=n;i++)

for(j=l;j<=i;j++)

for(k=l;k<=j;k++)

x++;

【解答】⑴基本語句就是k=k+10*i,共執(zhí)行In-2次，所以T(n)=O(n)。

⑵基本語句就是k=k+10*i,共執(zhí)行了n次，所以T(n)=O(n)。

⑶分析條件語句，每循環(huán)一次,i+j整體加1,共循環(huán)n次，所以T(n)=O(n)u

(4)設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1,最終T(n)=y,即：

(T(n)+l)2fn,所以T(n)=O(nl/2)o

⑸x++就是基本語句，所以

5.設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R),其中D=<1,2,3,4,5,6},R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫

出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。

【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示,它就是一種圖結(jié)構(gòu)。

6、為整數(shù)定義一個抽象數(shù)據(jù)類型,包含整數(shù)得常見運算，每個運算對應(yīng)一個基本操作,每個基本操作得接口

需定義前置條件、輸入、功能、輸出與后置條件。

【解答】整數(shù)得抽象數(shù)據(jù)類型定義如F：

ADTinteger

Data

整數(shù)a:可以就是正整數(shù)(1,2,3,...)、負(fù)整數(shù)(?1,?2,?3,...)與零

Operation

Constructor

前置條件:整數(shù)a不存在

輸入:一個整數(shù)b

功能:構(gòu)造一個與輸入值相同得整數(shù)

輸出:無

后置條件:整數(shù)a具有輸入得值

Set

前置條件:存在一-個整數(shù)a

輸入:一個整數(shù)b

功能:修改整數(shù)a得值，使之與輸入得整數(shù)值相同

輸出:無

后置條件:整數(shù)a得值發(fā)生改變

Add

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入得整數(shù)b相加

輸出:相加后得結(jié)果

后置條件:整數(shù)a得值發(fā)生改變

Sub

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入得整數(shù)b相減

輸出:相減得結(jié)果

后置條件:整數(shù)a得值發(fā)生改變

Multi

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與胸入得整數(shù)b相乘

輸出:相乘得結(jié)果

后置條件:整數(shù)a得值發(fā)生改變

Div

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:將整數(shù)a與輸入得整數(shù)b相除

輸出:若整數(shù)b為零，則拋出除軍異常,否則輸出相除得結(jié)果

后置條件:整數(shù)a得值發(fā)生改變

Mod

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:求當(dāng)前整數(shù)與輸入整數(shù)得模，即正得余數(shù)

輸出:若整數(shù)b為零，則拋出除零異常,否則輸出取模得結(jié)果

后置條件:整數(shù)a得值發(fā)牛.改變

Equal

前置條件:存在一個整數(shù)a

輸入:一個整數(shù)b

功能:判斷整數(shù)a與輸入得整數(shù)b就是否相等

輸出:若相等返回1,否則返回0

后置條件:整數(shù)a得值不發(fā)生改變

endADT

7、求多項式A(x)得算法可根據(jù)下列兩個公式之一來設(shè)計：

(1)A(x)=anxn+an-lxn-l+...+alx+aO

⑵A(x)=(...(anx+an-l)x+...+al)x)+aO

根據(jù)算法得時間復(fù)雜度分析比較這兩種算法得優(yōu)劣。

【解答】第二種算法得時間性能要好些。笫一種算法需執(zhí)行大量得乘法運算，而笫二種算法進行了優(yōu)化，減

少了不必要得乘法運算。

8、算法設(shè)計(要求:算法用偽代碼與C++描述,并分析最壞情況下得時間復(fù)雜度)

⑴對一個整型數(shù)組A［n］設(shè)計一個排序算法。

【解答】下面就是簡單選擇排序算法得偽代碼描述。

初.對n個記錄進行r1趟間單選擇排序:

1.1在無序區(qū)［i，nT］中選取最小記錄，設(shè)其下標(biāo)為index；

1.2將最小記錄與第1個記錄交換；

______________________________________________________________________________下面就是

簡單選擇排序算法得C++描述。

簡單選擇排序算法seasonL

voidSdectSort(intr[],intn)

(

for(i=0;i<n-l;i++)網(wǎng)n個記錄進行n-1趟簡單選擇排序

(

index=i,

for(j=i+1；j<n;j++)臨無序區(qū)中選取最小記錄

if(r[j]<r[index])index=j,

if(index!=i)r[i]-<~?-r[index];/皮換元素

)

)

分析算法,有

兩層嵌套得for循環(huán)，所以，.

⑵找出整型數(shù)組A［n］中元素得最大值。次最大值。

【解答】算法得偽代碼描述如下：

港4將前兩個元素進行比較，較大者放生」max中，較小者游nmax中；

V2,從第3個元素開始直到最后一個元素依次取元素A[小執(zhí)行下列操作：

2.1如果A[i]>max,則A[i]為最大值，原來的最大值為次最大值；

2.2否則，如果A[i]>nmax,則最大值不變，A[i]為次最大值；

3.輸出最大值max,次最大值nmax；

______________________________________________________________________________算法得

C++描述如下:

最大值和次最大值算法Max_NextMax|

voidMax_NextMax(intA[],intn,int&max,int&nmax)

(

if(A[O]>=A[1]){

max=A[0];

nmax=A[l];

)

else(

max=A[l];

nmax=A[0],

J

for(i=2;i<n;i++)

if(A[i]>=max)(

nmax=max;

max=A[i];

}

elseif(A[i]>nmax)nmax=A[i];

cout<<"最大值為:"?max?"\n次最大值為："?nmax?endl;

}

分析算法,

只有一層循環(huán)，共執(zhí)行n-2次,所以,T（n）=O（n）,

學(xué)習(xí)自測及答案

1.順序存儲結(jié)構(gòu)得特點就是（）,鏈接存儲結(jié)構(gòu)得特點就是（）。

【解答】用元素在存儲器中得相對位置來表示數(shù)據(jù)元素之間得邏輯關(guān)系，用指示元素存儲地址得指針我示

數(shù)據(jù)元素之間得邏輯關(guān)系.

2.算法在發(fā)牛非法操作時可以作出處理得特件稱為（）.

【解答】健壯性

3、常見得算法時間復(fù)雜度用大0記號表示為:常數(shù)階（）、對數(shù)階（）、線性階（）、平方階（）與指數(shù)階（）。

【解答】O（l）,O（log2n）,0（n）z0（n2）,0（2n）

4.將下列函數(shù)按它們在n時得無窮大階數(shù)，從小到大排列。

nzn-n3+7n5,nlogn,2n/2,n3,Iog2nznl/2+log2n,(3/2)n,n!,n2+log2n

【解答】

Iog2n,nl/2+log2nzn,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2z(3/2)n,n!

5.試描述數(shù)據(jù)結(jié)構(gòu)?J抽象數(shù)據(jù)類型得概念，程序設(shè)計語言中數(shù)據(jù)類型概念得區(qū)別。

【解答】數(shù)據(jù)結(jié)構(gòu)就是指相互之間存在?定關(guān)系得數(shù)據(jù)元素得集合。而抽象數(shù)據(jù)類型就是指?個數(shù)據(jù)結(jié)構(gòu)

以及定義在該結(jié)構(gòu)上得一組操作。程序設(shè)計語言中得數(shù)據(jù)類型就是一個值得集合與定義在這個值集上一組

操作得總稱。抽象數(shù)據(jù)類型可以瞧成就是對數(shù)據(jù)類型得?種抽象,

6、對下列用二元組表示得數(shù)據(jù)結(jié)構(gòu)，試分別畫出對應(yīng)得邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。

(1)A=(D,R),其中D={al,a2,a3,a4},R={}

其中

⑵B=(D,R),D={a,b,czd,e,f},R={〃〃}

口田),其中口={求={〃〃,}

⑶C=(3,>"/6/}

⑷D=(D,R),其中D={1,2,3,4,5,6},

R={(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(3,6),(4,6)}

【解答】⑴屬于集合，其邏輯結(jié)構(gòu)圖如圖l-4(a)所示;⑵屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖l-4(b)所示;⑶

屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖l-4(c)所示;⑷屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖l-4(d)所示。

法得時間復(fù)雜度。

count=0;x=l;

while(x{

x*=2;

count++;

}

returncount;

【解答】O(log2n)

第2章線性表

課后習(xí)題講解

1、填空

⑴在順序表中,等概率情況下，插入與刪除一個元素平均需移動（）個元素，具體移動元素得個數(shù)與（）與（）有

關(guān)。

【解答】表長得一半，表長，該元素在表中得位置

⑵順序表中第一個元素得存儲地址就是100,每個元素得長度為2,則第5個元素得存儲地址就是（）。

【解答】108

【分析】第5個元素得存儲地址=第1個元素得存儲地址+（5—1）x2=108

⑶設(shè)單鏈表中指針p指向結(jié)點A,若要刪除A得后繼結(jié)點（假設(shè)A存在后繼結(jié)點），則需修改指針得操作為（）。

【解答】p->next=（p->next）->next

⑷單鏈表中設(shè)置頭結(jié)點得作用就是（）。

【解答】為了運算方便

【分析】例如在插入與刪除操作時不必對表頭得情況進行特殊處理。

⑸非空得單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（）。

【解答】p->next=head

【分析】如圖2-8所示。

⑹在由尾指針rear指示得單循環(huán)鋅表中，在表尾插入一個結(jié)點s得操作序列就是（）;刪除開始結(jié)點得

操作序列為（）。

【解答】s->next=rear->next;rear->next=s;rear=s;

q=rear->next->next;rear->next->next=q->next;deleteq;

【分析】操作示意圖如圖2-9所示：

圖2-9帶尾指針的循環(huán)梃表中插入和刪除操作示意圖

⑺一個具有n個結(jié)點得單鏈表,在指針p所指結(jié)點后插入一個新結(jié)點得時間復(fù)雜度為（）;在給定值為x得結(jié)

點后插入一個新結(jié)點得時間復(fù)雜度為（）。

【解答】。⑴Q（n）

【分析】在p所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為0（1）;而在給定值為x得結(jié)點后

插入一個新結(jié)點需要先查找值為x得結(jié)點，所以時間復(fù)雜度為O（n）。

⑻可由一個尾指針唯一確定存鏈表有（）、（）、（）。

【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表

2、選擇題

⑴線性表得順序存儲結(jié)構(gòu)就是一種（）得存儲結(jié)構(gòu)，線性表得鏈接存儲結(jié)構(gòu)就是一種（）得存儲結(jié)構(gòu)。

A隨機存取B順序存取C索引存取D散列存取

【解答】A,B

【分析】參見2、2、1。

⑵線性表采用鏈接存儲時，其地址（）.

A必須就是連續(xù)得B部分地址必須就是連續(xù)得

C一定就是不連續(xù)得D連續(xù)與否均可以

【解答】D

【分析】線性表得鏈接存儲就是用一組任意得存儲單元存儲線性表得數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也

可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。

⑶單循環(huán)鏈表得主要優(yōu)點就是（）。

A不再需要頭指針了

B從表中任一結(jié)點出發(fā)都能掃描到整個鏈表；

C已知某個結(jié)點得位置后，能夠容易找到它得直接前趨；

D在進行插入、刪除操作時,能更好地保證鏈表不斷開。

【解答】B

（4）鏈表不具有得特點就是（）。

A可隨機訪問任一元素B插入、刪除不需要移動元素

C不必事先估計存儲空間D廳需空間與線性表長度成正比

【解答】A

⑸若某線性表中最常用得操作就是取第i個元素與我第i個元素得前趨，則采用（）存儲方法最節(jié)省時間。

A順序表B單鏈表C雙鏈表D單循環(huán)鏈表

【解答】A

【分析】線性表中最常用得操作就是取第i個元素，所以，應(yīng)選擇隨機存取結(jié)構(gòu)即順序表，同時在順序表中查

找第i個元素得前趨也很方便，單鏈表與單循環(huán)鏈表既不能實現(xiàn)隨機存取,查找第i個元素得前趨也不方便,

雙鏈表雖然能快速查找第i個元素得前趨，但不能實現(xiàn)隨機存取。

⑹若鏈表中最常用得操作就是在最后一個結(jié)點之后插入一個結(jié)點與刪除第一個結(jié)點，則采用（）存儲方法最

節(jié)省時間。

A單鏈表B帶頭指針得單循環(huán)鏈表C雙鏈表D帶尾指針得單循環(huán)鏈表

【解答】D

【分析】在鏈表中得最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點得地址，所以，單鏈表、帶頭指針得

單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針得單循環(huán)鏈表中刪除第?個結(jié)點，其時間性能就是0（1）,所

以，答案就是D。

⑺若鏈表中最常用得操作就是在最后一個結(jié)點之后插入一個結(jié)點與刪除最后一個結(jié)點，則采用（）存儲方法

最節(jié)省運算時間。

A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針得單循環(huán)鏈表

【解答】B

【分析】在鏈表中得最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點得地址，所以，單鏈表、單循環(huán)依表

都不合適,刪除最后一個結(jié)點常要知道終端結(jié)點得前驅(qū)結(jié)點得地址，所以，帶尾指針得單循環(huán)鏈?zhǔn)讲缓线m，而

循環(huán)雙鏈表滿足條件。

(8)在具有n個結(jié)點得有序單鏈表中插入一個新結(jié)點并仍然有序得時間紅雜度就是()。

AO(1)B0(n)C0(n2)DO(nlog2n)

【解答】B

【分析】首先應(yīng)順序查找新結(jié)點在單鏈表中得位置。

⑼對于n個元素組成得線性表，建立?個有序單鏈表得時間復(fù)雜發(fā)就是()。

A0(1)B0(n)C0(n2)DO(nlog2n)

【解答】C

【分析】該算法借要將n個元素依次插入到有序單鏈表中，而插入每個元素需0(n)c

⑩使用雙鏈表存儲線性表，其優(yōu)點就是以()。

A提高查找速度B更方便數(shù)據(jù)得插入與刪除

C節(jié)約存儲空間D很快回收存儲空間

【解答】B

【分析】在鏈表中?股只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，

顯然不能節(jié)約存儲空間，對于可態(tài)存儲分配，回收存儲空間得速度就是一樣得。由于雙鏈表具有對稱性,所以,

其插入與刪除操作更加方便。

(11)在一個單鏈表中，已知q所韋結(jié)點就是p所指結(jié)點得直接前驅(qū)，若在q與p之間插入s所指結(jié)點，則執(zhí)行()

操作。

As->next=p->next;p->next=s;Bq->next=s;s->next=p;

Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;

【解答】B

【分析】注意此題就是在q與p之間插入新結(jié)點，所以，不用考慮修改指針得順序。

02)在循環(huán)雙鏈表得p所指結(jié)點后插入s所指結(jié)點得操作就是().

Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s

【解答】D

【分析】在鏈表中,對指針得修改必須保持線性表得邏輯關(guān)系，否則，將違背線性表得邏輯特征，圖2-10給出

備選答案C與D得圖解。

（a）備選答案C鐮作示意圖（第4步指針修改無法進行）（b）備選答案D操作示意圖

圖2-10雙鏈表插入操作修改指針操作示意圖

判斷題

⑴線性表得邏輯順序與存儲順序總就是一致得。

【解答】錯。順序表得邏輯順序與存儲順序一致，鏈表得邏輯順序與存儲順序不一定一致。

⑵線性表得順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。

【解答】錯。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。

⑶設(shè)M就是指針，若p=q,則*P=*q。

【解答】錯。p=q只能表示p與q指向同一起始地址,而所指類型則不一定相同。

（力線性結(jié)構(gòu)得基本特征就是:每個元素有且僅有一個直接前驅(qū)與一個宜接后繼。

【解答】錯。每個元素最多只有一個直接前驅(qū)與一個直接后繼，第一個元素沒有前驅(qū),最后一個元素沒有后

繼。

⑸在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點得地址即可，閃此單鏈表就是隨機存取結(jié)構(gòu)。

【解答】錯。要找到該結(jié)點得地址，必須從頭指針開始查找，所以單鏈表就是順序存取結(jié)構(gòu)。

4,請說明順序表與單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。

⑴若線性表得總長度基本穩(wěn)定,且很少進行插入與刪除操作，但要求以最快得速度存取線性及中得元素。

⑵如果n個線性表同時并存,年且在處理過程中各表得長度會動態(tài)發(fā)生變化。

⑶描述一個城市得設(shè)計與規(guī)劃。

【解答】順序表得優(yōu)點:①無需為表示表中元素之間得邏輯關(guān)系而增加額外得存儲空間;②可以快速地存

取表中任一位置得元素（即隨機存?。ｍ樞虮淼萌秉c:①插入與刪除操作需移動大量元素;②表得容量難以

確定;③造成存儲空間得''碎片"。

單鏈表得優(yōu)點:①不必事先知道線性表得長度;②插入與刪除元素時只需修改指針，不用移動元素。單鏈表

得缺點:①指針得結(jié)構(gòu)性開銷;②存取表中任意元素不方便,只能法行順序存取。

⑴應(yīng)選用順序存儲結(jié)構(gòu)。因為順序表就是隨機存取結(jié)構(gòu),單鏈表就是順序存取結(jié)構(gòu)。本題很少進行插入與

刪除操作，所以空間變化不大，且需要快速存取,所以應(yīng)選用順序存儲結(jié)構(gòu)。

⑵應(yīng)選用鏈接存儲結(jié)構(gòu)。鏈表容易實現(xiàn)表容量得擴充，適合表得長度動態(tài)發(fā)生變化.

⑶應(yīng)選用鏈接存儲結(jié)構(gòu)。因為一個城市得設(shè)計?與規(guī)劃涉及活動很多，需要經(jīng)常修改、擴充與刪除各種信息,

才能適應(yīng)不斷發(fā)展得需要。而順序表得插入、刪除得效率低，故不合適。

5.算法設(shè)計

(1)設(shè)計一個時間復(fù)雜度為0(n)得算法，實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個位置。

【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。

箱環(huán)右移算法Converse|

voidConverse(intA[],intn,intk)

(

Reverse(A,0,k-l),

Reverse(A,k,n-1);

Reverse(A,0,n-l);

)

voidReverse(intA[],intfrom,intto)解數(shù)組A中元素從from到to逆置

(

for(i=0,i<(to-from+l)/2;i++)

A[from+i]?A[to-i];或換元素

)分析算法,

第一次調(diào)用Reverse函數(shù)得時間復(fù)雜度為O(k),第二次調(diào)用Reverse函數(shù)得時間復(fù)雜度為O(n-k),第三次調(diào)

用Reverse函數(shù)得時間復(fù)雜度為O(n),所以，總得時間復(fù)雜度為O(n).

⑵已知數(shù)組A[n]中得元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為

偶數(shù),并要求算法得時間復(fù)雜度為O(n)。

【解答】從數(shù)組得兩端向中間比較,設(shè)置兩個變量i與j,初始時i=O,j=n-l,若A[i]為偶數(shù)并且A[j]為奇數(shù)，則

將A[i]與A[j]交換。具體算法如下：

數(shù)如奇偶調(diào)整算法Adjust

voidAdjust(intA[],n)

(

i=0,j=n-l;

while(i<j)

(

while(A[i]%2!=0]i++;

while(A[j]%2=0)j—

if(i<j)A[j];

)

)分析算法,

兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為o(n).

⑶試編寫在無頭結(jié)點得單鏈表上實現(xiàn)線性表得插入操作得算法,并與帶頭結(jié)點得單鏈表上得插入操作得實

現(xiàn)進行比較。

【解答】參見2、2、3。

⑷試分別以順序表與單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置得算法。

【解答】順序表得逆置，即就是將對稱元素交換，設(shè)順序表得長度為length,則將表中第i個元素與第length-

i-1個元素相交換。具體算法如下：

順序表逆置算法Reverse|

template<classT>

voidReverseddata[],intlength)

(

for(i=0;i<=length/2;i++)

(

temp=data[i],

data[i]=data[length-i-1];

data[length-i-l]=temp;

)

)單鏈表得

逆置請參見2、2、4算法2-4與算法2-6。

⑸假設(shè)在長度大于1得循環(huán)鏈表中，即無頭結(jié)點也無頭指針,s為指向鏈表中某個結(jié)點得指針,試編寫算法刪

除結(jié)點s得前趨結(jié)點.

【解答】利用單循環(huán)鏈表得特點，通過指針s可找到其前驅(qū)結(jié)點r以及r得前驅(qū)結(jié)點p,然后將結(jié)點r刪除，如

圖2-11所示，具體算法如下：

循環(huán)鞋表即命算法Da|

template<classT>

voidDel(Node<T>*s)

(

p=s,，江作指針p初始化，查找s的前驅(qū)結(jié)點的前驅(qū)結(jié)點，用p指示

while(p->ne2<t->next!=s)

p=p->next,

r=p->next,加為p的前驅(qū)結(jié)點，q為r的前驅(qū)結(jié)點

p->next=s;/刪除r所指結(jié)點

deleter;

)

圖2-11刪除結(jié)點s的前驅(qū)結(jié)點操作示意圖⑹已知

一單鏈表中得數(shù)據(jù)元素含有三類字符:字母、數(shù)字與其她字符。試編叼算法，構(gòu)造三個循環(huán)鏈表，使每人循環(huán)

鏈表中只含同一類字符。

【解答】在單鏈表A中依次取元素，若取出得元素就是字母,把它插入到字母鏈表B中,若取出得元素就是數(shù)

字，則把它插入到數(shù)字鏈表D中，直到鏈表得尾部,這樣表B,D,A中分別存放字母、數(shù)字與其她字符。具體算

法如下：

單鞋表拆分算法Adjust

template<classT>

voidAdjust(Node<T>*A,Node<int>*D,Node<char>XB)

(晨

D=newNode<int>;D->next=D;。創(chuàng)建空循環(huán)鏈表D,存放數(shù)字

B=newNode<char>;B->next=B;"創(chuàng)建空循環(huán)鏈表B,存放字符

p=A;q=p->next;力工作指針q初始化

while(q)

(

if(CA'<=q->data)&&(q->data>='Z')11Ca1<=q->data)&&(q->data>=?z,))(

p->next=q->next;

q->next=B->next;

B-：>next=q;//采用頭插法插在循環(huán)椎表B的頭結(jié)點的后面

)

elseif((,0,<=q->data)&&(q->data>='9')){

p->next=q->next,

q->next=D->next,

D->next=q;，味用頭插法插在循環(huán)旌表D的頭結(jié)點的后面

)

elsep=q;

q=p->next;

)

p->next=A;R=A;/解於表A構(gòu)造為循環(huán)鏈表，為除字母和數(shù)字的其他字符

}

⑺設(shè)單鏈

表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同得多余結(jié)點。

【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點得元素值與后繼結(jié)點得元素值不相等,則指針后移;否則刪除該后

繼結(jié)點。具體算法如下：

單槌表刪除相同值算法Purge____________________________

voidPurge(Node<T>*first)

(

p=first->next,

while(p->next)

if(p->data==p->next->data)(

q=p->next,

p->next=q->next,

deleteq;

)

elsep=p->next;

)

（8）判斷帶

頭結(jié)點得雙循環(huán)鏈表就是否對稱。

【解答】設(shè)工作指針p與q分別指向循環(huán)雙鏈表得開始結(jié)點與終端結(jié)點,若結(jié)點p與結(jié)點q得數(shù)據(jù)域相等,

則工作指針p后移，工作指針q前移，直到指針p與指針q指向同一結(jié)點（循環(huán)雙鏈表中結(jié)點個數(shù)為奇數(shù)），或

結(jié)點q成為結(jié)點p得前驅(qū)（循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù)）。如圖2-12所示。

判斷雙鞋表對稱算法Equal_______________________________________________

template<classT>

structDulNode

(

Tdata;

DulNode<T>*prior,*next;

｝；

template<classT>

boolEqual(DulNode<T>*first)

(

p=first->next;q=first->prior;

while(p!=q&&p->prior!=q)

if(p->data==q->data)(

p=p->next,"工作指針p后移

q=q->prior;"工作指針q前移

)

elsereturn0;

return1;

)____________________________________________________________________

學(xué)習(xí)自

測及答案

1、已知一維數(shù)組A采用順序存儲結(jié)構(gòu),每個元素占用4個存儲單元，第9個元素得地址為144,則第一個元

素得地址就是()。

A108B180C176D112

【解答】D

2.在長度為n得線性表中查找值為x得數(shù)據(jù)元素得時間復(fù)雜度為：()?

A0(0)B0(1)C0(n)D0(n2)

【解答】C

3.在一個長度為n得順序表得笫i(14區(qū)n+1)個亓素力前插入一個元素，需向后移動()個亓素，刪除第

i(lWiWn)個元素時，需向前移動()個元素。

【解答】n-i+lzn-i

4.在單鏈表中，除了頭結(jié)點以外，任一結(jié)點得存儲位置由()指示。

【解答】其前趨結(jié)點得指針域

5.當(dāng)線性表采用順序存儲結(jié)構(gòu)時，其主要特點就是()。

【解答】邏輯結(jié)構(gòu)中相鄰得結(jié)點在存儲結(jié)構(gòu)中仍相鄰

6.在雙鏈表中，每個結(jié)點設(shè)置了兩個指針域,其中一個指向()結(jié)點，另一個指向()結(jié)點。

【解答】前驅(qū)，后繼

7.設(shè)A就是一個線性表(al,a2,…，an),采用順序存儲結(jié)構(gòu)，則在等概率得前提下,平均每插入一個元素需要

移動得元素個數(shù)為多少？若元素插在ai與ai+1之間(isiwn)得概率為，則平均每插入一個元素所要移動得

元素個數(shù)又就是多少？

【解答】

8.線性表存放在整型數(shù)組A[arrsize]得前elenum個單元中,且遞增有序。編寫算法,將元素x插入到線性表

得適當(dāng)位置上，以保持線性表得有序性，并且分析算法得時間復(fù)雜度。

【解答】本題就是在一個遞增有序我中插入元素x,基本思路就是從有序表得尾部開始依次取元素與x比較,

若大于x,此元素后移一位，再取它前面一個元素重復(fù)上述步驟;否則,找到插入位置，將x插入。具體算法如

下：

有序順序表插入算法Insert

constintarrsize=100;

classSeqList

private:

intdata[arrsize];

intdenum;

public:

Insert(intx);

｝，

voidSeqList::Insert(intx)

(

if(elenum==arrsize)throw"overflow";

else(

i=denum-l;

while(i>=1

data[i+l]=data[i];

i++；

)

data[i+l]=x;

)

J

9、已知

單鏈表中各結(jié)點得元素值為整型且遞增有序，設(shè)計算法刪除鏈表中所有大于mink且小于maxk得所有元素,

并釋放被刪結(jié)點得存儲空間。

【解答】因為就是在有序單鏈表上得操作，所以，要充分利用其有序性。在單鏈表中查找第一個大于mink

得結(jié)點與第?個小于maxk得結(jié)點，再將二者間得所有結(jié)點刪除。

有序鞋表刪除算法DeleteBetween

template<classT>

voidDeleteBetween(Node<T>*first,intmink,intmsxk)

(

p=first,

while(p->next&&p->next->data<=mink)

p=p->next;

if(p->next){

q=p->next;

while(q->data<maxk)

(

u=q->next;

p->next=q->next;

deleteq;

q=u,

)

)

)

10.設(shè)單循

環(huán)鏈表LI,對其遍歷得結(jié)果就是:xl,x2zx3,...zxn-lzxn.請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表LI與L2,使

得L1中含有原L1表中序號為奇數(shù)得結(jié)點且遍歷結(jié)果為:xl,x3z...;L2中含有原L1表中序號為偶數(shù)得結(jié)點

且遍歷結(jié)果為:…，x4,x2o

【解答】算法如下：

循環(huán)犍表拆分算法DePatch]

template<classT>

Node<T>*DePatch(Node<T>*L1)

{

L2=newNode<T>;L2->next=L2;

q=Ll->next;Ll->next=Ll;

P=Ll；i=l；

while(q!=Ll)

(

if(i%2=l)(//應(yīng)用尾插法

p->next=q;p=q;p->next=Ll;

q=q->next,i++;

)

else(

L2->next=q;u=q->next;q->next=L2->next;

q=u,i++;

)

)

)第3

章特殊線性表一棧、隊列與串

課后習(xí)題講解

1、填空

⑴設(shè)有一個空棧,棧頂指針為1000H,現(xiàn)有輸入序列為1、2、3、4、5,經(jīng)過

push/push,pop,push,pop,push,pijsh后,輸出序列就是（）,棧頂指針為（）。

【解答】23J003H

⑵棧通常采用得兩種存儲結(jié)構(gòu)就是（）；其判定棧空得條件分別就是（）,判定棧滿得條件分別就是（）。

【解答】順序存儲結(jié)構(gòu)與鏈接存儲結(jié)構(gòu)（或順序棧與鏈棧），棧頂指針top=-1與top=NULL,棧頂指針top等

于■數(shù)組得長度與內(nèi)存無可用空間

（3）（）可作為實現(xiàn)遞歸函數(shù)調(diào)用得一種數(shù)據(jù)結(jié)構(gòu)。

【解答】棧

【分析】遞歸函數(shù)得調(diào)用與返回正好符合后進先出性。

（4）表達(dá)式a*（b+c）-d得后綴表達(dá)式就是（）。

【解答】abc+*d-

【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個技巧:將操作數(shù)依次寫卜來，再將算符插在它得兩個操作數(shù)得

后面。

⑸棧與隊列就是兩種特殊得線性表，棧得操作特性就是（）,隊列得操作特性就是（）,棧與隊列得主要區(qū)別在

于（）。

【解答】后進先出，先進先出,對插入與刪除操作限定得位置不同

⑹循環(huán)隊列得引入就是為了克服（）。

【解答】假溢出

（7）數(shù)組Q[n]用來表示一個循環(huán)隊列,front為隊頭元素得前一個位置,rear為隊尾元素得位置,計算隊列中元

素個數(shù)得公式為（）。

【解答】（rear-front+n）%n

【分析】也可以就是（rear-front）%n,但rear-front得結(jié)果可能就是負(fù)整數(shù),而對一個負(fù)整數(shù)求模，其結(jié)果在

不同得編譯器環(huán)境下可能會有所不同。

（8）用循環(huán)鏈表表示得隊列長度為n,若只設(shè)頭指針，則出隊與入隊得時間復(fù)雜度分別就是（）與（）。

【解答】0（1）,0（n）

【分析】在帶頭指針得循環(huán)鏈表中，出隊即就是刪除開始結(jié)點，這只需修改相應(yīng)指針;入隊即就是在終端結(jié)點

得后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點得地址。

⑼串就是一種特殊得線性表，其特殊性體現(xiàn)在（）。

【解答】數(shù)據(jù)元素得類型就是一個字符

⑩兩個串相等得充分必要條件就是（）。

【解答】長度相同且對應(yīng)位置得字符相等

【分析】例如七bd'abc"JabcWbca"。

2、選擇題

⑴若一個棧得輸入序列就是1,2,3,.,n,輸出序列得第一個元素就是n,則第i個輸出元素就是（）。

A不確定Bn-iCn-i-1Dn-i+1

【解答】D

【分析】此時，輸出序列--定就是輸入序列得逆序。

⑵設(shè)棧S與隊列Q得初始狀態(tài)為空，元素el、e2、e3、e4、e5、e6依次通過棧S,一個元素出棧后即進入

隊列Q,若6個元素出隊得順序就是e2、e4、e3、e6、e5、el,則棧S得容量至少應(yīng)該就是（）。

A6B4C3D2

【解答】C

【分析】由于隊列具有先進先出性，所以，此題中隊列形同虛設(shè),即同棧得順序也就是e2、e4、e3、e6、e5、

elo

⑶一個棧得入棧序列就是1,2,3,4,5,則棧得不可能得輸出序列就是（）。

A54321B45321C43512D12345

【解答】C

【分析】此題有一個技巧:在輸出序列中任意元素后面小能出現(xiàn)比該元素小并H.就是升序（指得就是元素得

序號）得兩個元素。

（力設(shè)計一個判別表達(dá)式中左右括號就是否配對得算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳

A順序表B棧C隊列D鏈表

【解答】B

【分析】每個右括號與它前面得最后一個沒有匹配得左括號配對，因此具有后進先出性。

（5）在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該就是一個（）

結(jié)構(gòu)。

A棧B隊列C數(shù)組D線性表

【解答】B

【分析】先進入打印緩沖區(qū)得文件先被打印，因此具有先進先出性。

（6）一個隊列得入隊順序就是1,2,3,4,則隊列得輸出順序就是（）。

A4321B1234C1432D3241

【解答】D

【分析】隊列得入隊順序與出隊順序總就是一致得。

⑺棧與隊列得主要區(qū)別在于（）。

A它們得邏輯結(jié)構(gòu)不一樣B它們得存儲結(jié)構(gòu)不-?樣

C所包含得運算不一樣D插入、刪除運算得限定不一樣

【解答】D

【分析】棧與隊列得邏輯結(jié)構(gòu)都就是線性得，都有順序存儲與鏈接存儲，有可能包含得運算不一樣，但不就是

主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含得運算都可能不同。

⑻設(shè)數(shù)組S[n]作為兩個棧S1與S2得存儲空間,對任何一個棧只芍當(dāng)S[n]全滿時才不能進行進棧操作。為

這兩個棧分配空間得最佳方案就是（）。

AS1得棧底位置為0,S2得棧底位置為n-1

BS1得棧底位置為0,S2得棧底位置為n/2

CS1得棧底位置為0,S2得棧底位置為n

DS1得棧底位置為0萬2得棧底位置為1

【解答】A

【分析】兩棧共享空間首先兩個棧就是相向增長得，棧底應(yīng)該分別指向兩個棧中得第一個元素得位置，并注

意C++中得數(shù)組下標(biāo)就是從C開始得。

（9）設(shè)有兩個串p與q,求q在p中首次出現(xiàn)得位置得運算稱作（）。

A連接B模式匹配C求了串D求串長

【解答】B

3、判斷題

⑴有n個元素依次進棧,則出棧序列有（n?l）/2種。

【解答】錯。應(yīng)該有種。

⑵?？梢宰鳛閷崿F(xiàn)過程調(diào)用得一種數(shù)據(jù)結(jié)構(gòu)。

【解答】對。只要操作滿足后進先出性,都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。

<3）在棧滿得情況下不能做進棧操作，否則將產(chǎn)生益

【解答】對。

（4）在循環(huán)隊列中,front指向隊頭元素得前一個位置jear指向隊尾元素得位置，則隊滿得條件就是

front=rearo

【解答】錯。這就是隊空得判定條件，在循環(huán)隊列中要將隊空與隊滿得判定條件區(qū)別開。

⑸空串與空格串就此相同得C

【解答】錯?？沾瞄L度為零，而空格串得長度不為。，其長度就是串中空格得個數(shù)。

4、設(shè)有一個棧，元素進棧得次序為A,B,C,D,E,能否得到如下出棧序列，若能，請寫出操作序列，若不能,請說明

原因。

⑴C,E,A,B,D

⑵C,B,A,D,E

【解答】⑴不能，因為在C、E出棧得情況下,A一定在棧中,而且在B得下面，不可能先FB出棧。(2)可以，設(shè)

I為進棧操作,0為入棧操作，則其操作序列為III000I0I0.

5、舉例說明順序隊列得''假溢出"現(xiàn)象。

【解答】假設(shè)有一個順序隊列，如圖3-6所示，隊尾指針rear=4,隊頭指針front=l,如果再有元素入隊，就會

產(chǎn)生”上溢。此時得''上溢"乂稱為''假溢出。因為隊列并不就是真得溢出了，存儲隊列得數(shù)組中還有2個存儲單

元空閑，其下標(biāo)分別為。與1。

6、在操作序列push(l)、push⑵、pop、push⑸、push。)、pop、push(6)之后，棧頂元素與棧底元素分

別就是什么？(push(k)表示整數(shù)k入棧,pop表示棧頂元素出棧。)

【解答】棧頂元素為6,棧底元素為1°其執(zhí)行過程如圖3-7所示。

入棧一；*4出棧

(a)push(1)?push(2)(b)pop?pirh(5)?push(7)(c)pop,push(6)

圖3-7枝的執(zhí)行過程示意圖7.在操作序列

EnQueue(l)、EnQueue(3)xDeQueue.EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭

元素。隊尾元素分別就是什么？(EnQueue(k)表示整數(shù)k入隊,DeQueue表示隊頭元素出隊)。

【解答】隊頭元素為5,隊尾元素為9.其執(zhí)行過程如圖3-8所示。

357579

(a)EnQueue(1)正nQueue(3)(b)DeQueue/EnQueue(5)EiQueue(7)(c)DeQueue#EnQueue(9)

困34隊列的執(zhí)行過程示意圖