《數(shù)據(jù)結(jié)構(gòu)》課后參考答案1

單元練習(xí)1

一.判斷題(下列各題,正確的請在前面的括號內(nèi)打，;錯誤的打X)

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

(M)(2)一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個

基本運(yùn)算集構(gòu)成的整體。

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

(X)(0數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。

(X)(5)程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以

通用。

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

構(gòu)兩類。

(M)(7)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。

(M)(3數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)內(nèi)實際的存儲形式。

(X)(9)數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機(jī)的。

(V)(10)算法是對解題方法和步驟的描述。

二.填空題

(1)數(shù)據(jù)有謬輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。

(2)數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和

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

(3)數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線

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

(4)樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。

(5)在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個結(jié)點(diǎn)只有—1

個前趨結(jié)點(diǎn)。

(6)在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_任

意多個。

(7)數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。

(8)數(shù)據(jù)的存儲結(jié)構(gòu)形式包括：順序存儲、鏈?zhǔn)酱鎯?、索引存儲?/p>

散列存儲。

(9)線性結(jié)構(gòu)中的元素之間存在一對一的關(guān)系。

(10)樹形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在一對多的關(guān)系,

(11)圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。

(12)數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法

(或運(yùn)算)-三個方面的內(nèi)容。

(13)數(shù)據(jù)結(jié)構(gòu)被定義為。其中D是數(shù)據(jù)的有限集合，R

是D上的關(guān)系的有限集合。

(14)算法是一個有窮指令的集合。

(15)算法效率的度量可以分為事先估算法和事后統(tǒng)計

法。

(16)一個算法的時間復(fù)雜性杲算法輸入規(guī)模的函數(shù)。

(17)算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲空間，它

是該算法求解問題規(guī)模n的函數(shù)。

(18)若一個算法中的語句頻度之和為T(n)=6irBnlogn,則算

法的時間復(fù)雜度為O(nlo巧0。

(19)若一個算法中的語句頻度之和為T(mWMiHogrH死則

算法的時間復(fù)雜度為。(片)。

(2Q數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的

操作對象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。

三.選擇題

(1)數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的(A)及它們之間的相互聯(lián)系。

A存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B存儲和抽象C聯(lián)系和抽象

D聯(lián)系與邏輯

(2)在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：(C)o

A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B緊湊結(jié)構(gòu)和

非緊湊結(jié)構(gòu)

C線性結(jié)構(gòu)和非線性結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和

外部結(jié)構(gòu)

(3)數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址和邏輯地址相同并且

是連續(xù)的，稱之為(C)o

A存儲結(jié)構(gòu)B邏輯結(jié)構(gòu)C順序存儲結(jié)

構(gòu)D鏈?zhǔn)酱鎯Y(jié)構(gòu)

(4)非線性結(jié)構(gòu)中的每個結(jié)點(diǎn)(D)。

A無直接前趨結(jié)點(diǎn)

B無直接后繼結(jié)點(diǎn)

C只有一個直接前趨結(jié)點(diǎn)和一個直接后繼結(jié)點(diǎn)

D可能有多個直接前趨結(jié)點(diǎn)和多個直接后繼結(jié)點(diǎn)

（5）鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（A）。

A分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放表示結(jié)點(diǎn)

間關(guān)系的指針

B只有一部分，存放結(jié)點(diǎn)的值

C只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針

D分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占

單元素

（0算法的計算量大小稱為算法的（C）。

A現(xiàn)實性B難度C時間復(fù)雜

性D效率

（刀數(shù)據(jù)的基本單位是（B）0

A數(shù)據(jù)結(jié)構(gòu)B數(shù)據(jù)元素C數(shù)據(jù)項

D文件

（S每個結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，所有存儲結(jié)點(diǎn)相繼存放在一個

連續(xù)的存儲區(qū)里，這種存儲結(jié)構(gòu)稱為（A）結(jié)構(gòu)。

A順序存儲B鏈?zhǔn)酱鎯索引存儲

D散列存儲

（9每一個存儲結(jié)點(diǎn)不僅含有一個數(shù)據(jù)元素，還包含一組指針，該

存儲方式是（B）存儲方式。

A順序B鏈?zhǔn)紺索引

D散列

(10)以下任何兩個結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是(D)o

A圖形結(jié)構(gòu)B線性結(jié)構(gòu)C樹形結(jié)構(gòu)

D集合

(11)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是(C)o

A物理結(jié)構(gòu)B存儲結(jié)構(gòu)C邏輯結(jié)構(gòu)

D邏輯和存儲結(jié)構(gòu)

(12)下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是

(A)。

A集合B線性結(jié)構(gòu)C樹形結(jié)構(gòu)

D圖形結(jié)構(gòu)

(13)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)

的(A)。

A邏輯結(jié)構(gòu)B存儲結(jié)構(gòu)C邏輯實現(xiàn)

D存儲實現(xiàn)

(每一個存儲結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，存儲結(jié)點(diǎn)存放在連續(xù)的

存儲空間，另外有一組指明結(jié)點(diǎn)存儲位置的表，該存儲方式是(C)

存儲方式。

A順序B鏈?zhǔn)紺索引

D散列

(15)算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的(A)o

A正確性B易讀性C健壯性

D高效性

(16)算法在發(fā)生非法操作時可以作出處理的特性稱為算法的

(C)o

A正確性B易讀性C健壯性

D高效性

(17)下列時間復(fù)雜度中最壞的是(D)0

A0(1)B0(n)C0(logi^

D0(n)

(18)下列算法的時間復(fù)雜度是(D)o

for(i=Qi<n;i-H)

for(j=Qi<n;j-H)

cLi]D]=i+j;

A0(1)B0(ri)CO(logii)

D0(n)

(12)算法分析的兩個主要方面是(A)。

A空間復(fù)雜性和時間復(fù)雜性B正確性和簡明

性

C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和

程序復(fù)雜性

(2Q計算機(jī)算法必須具備輸入、輸出和C)。

A計算方法B排序方法

C解決問題的有限運(yùn)算步驟D程序設(shè)計方

法

四.分析下面各程序段的時間復(fù)雜度

(1)for(i=Qi<xi-H)

for(j=Qj-H)

A[i]皿

解：O(n^

(2)F

for(i=Qi<rxi-H)

for(j=Qj<n;j-H)

s+=S[i]DI；

sun?=s;

解：o6)

(3)華

卻

B=^

解：0(1)

(4si(intii)

{intp=l,

for(i=l;i<FD；i-H)

{P』i；S-HR}

return(s);

(5)s2(intrj)

forgl;k<?=n;leH)

for(i=l;i<FD；i-H)

for0=1;j<^j-H)

yH

解：od)

五.根據(jù)二元組關(guān)系，畫出對應(yīng)邏輯圖形的草圖，指出它們屬于何

種數(shù)據(jù)結(jié)構(gòu)。

(1)、⑴其中：

D={&b,c,d,8,

Q{}

解：OaOb

O°0

cde

屬于集合

(2)及(DR,其中：

D={a,b,c,d,e,f},《{r}

占總培Q口<c，g<d,2<s,f>(尖括號表示結(jié)點(diǎn)之

間關(guān)系是有向的)

屬于線性結(jié)構(gòu)。

(3)之⑴以其中:

D={50,25,6457,82,36,75,55},

抬40,25為<50,64^><25,3g<6454<64,82^<57,55^<57

,75,

解:

屬于樹結(jié)構(gòu)

(4)CMDR,其中：

*{1,2,3,45,4,仁你

—(1,2),(2,3),(2,4,(3,4),(3,5),(3,0,《5),《⑥}(園

括號表示結(jié)點(diǎn)之間關(guān)系是有向的)

解：

屬于圖結(jié)構(gòu)

(5年⑴R,其中：

D={a,b,c,d,e,f,gh},抬{*

心包培＜4婦＜d,狎＜b,心＜fe,f＞

解：

屬于樹結(jié)構(gòu)。

單元練習(xí)2

一.判斷題(下列各題，正確的請在前面的括號內(nèi)打，;錯誤的打X)

(x)(1)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。

(x)(4鏈表的每個結(jié)點(diǎn)都恰好包含一個指針域。

(M)(3)在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物

理位置上并不一定緊鄰。

(x)(4順序存儲方式的優(yōu)點(diǎn)是存儲密度大，插入、刪除效率高。

(x)(5)線性鏈表的刪除算法簡單，因為當(dāng)刪除鏈中某個結(jié)點(diǎn)后，

計算機(jī)會自動地將后續(xù)的各個單元向前移動。

(x)(⑥順序表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)

點(diǎn)可以是一個復(fù)雜類型。

(M)(7)線性表鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是可以用一組任意的存儲單元存儲

表中的數(shù)據(jù)元素。

(，)(8線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。

(x)(9順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)

存取。

(X)(1。插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以

這兩種操作在數(shù)組中也經(jīng)常使用。

二.填空題

(1)順序表中邏輯上相鄰的元素在物理位置上必須相連。

(2)線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對一

關(guān)系。

(3)順序表相對于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲和隨機(jī)存取。

(4)鏈表相對于順序表的優(yōu)點(diǎn)是：插入、刪除方便。

(5)采用順序存儲結(jié)構(gòu)的線性表叫順序表。

(6順序表中訪問任意一個結(jié)點(diǎn)的時間復(fù)雜度均為0(1)。

(7)鏈表相對于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲密

度小。

(8)在雙鏈表中要刪除已知結(jié)點(diǎn)*P,其時間復(fù)雜度為

0(1)

(9在單鏈表中要在已知結(jié)點(diǎn)*「之前插入一個新結(jié)點(diǎn)，需找到*P

的直接前趨結(jié)點(diǎn)的地址，其查找的時間復(fù)雜度為O⑹。

(10單鏈表中需知道頭指針才能遍歷整個鏈表。

(11)性表中第一個結(jié)點(diǎn)沒有直接前趨，稱為開始結(jié)點(diǎn)。

(12)在一個長度為n的順序表中刪除第i個元素，要移動n=i

個元素。

(13)在一個長度為n的順序表中，如果要在第i個元素前插入

一個元素，要后移n~i+1個元素。

(14)在無頭結(jié)點(diǎn)的單鏈表中，第一個結(jié)點(diǎn)的地址存放在頭指針

中，而其它結(jié)點(diǎn)的存儲地址存放在前趨結(jié)點(diǎn)的指針域中。

(15)當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操

作，但要求以最快速度存取線性表中的元素時，應(yīng)采用順序

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

(16)在線性表的鏈?zhǔn)酱鎯χ校刂g的邏輯關(guān)系是通過_指

包—決定的。

(17)在雙向鏈表中，每個結(jié)點(diǎn)都有兩個指針域，它們一個指向

其前趨結(jié)點(diǎn),另一個指向其—后繼結(jié)點(diǎn)。

(1顏對一個需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用_鏈

式—存儲結(jié)構(gòu)為宜。

(19雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的

操作為：p^>pi~ior->next=p^>next。

(20)在如圖所示的鏈表中，若在指針?biāo)乖诘慕Y(jié)點(diǎn)之后插入

數(shù)據(jù)域值為咻口b的兩個結(jié)點(diǎn)，則可用下列兩個語句：

S^>next^>next=P^>next;和P-^next=S;來實現(xiàn)該操作。

p

A

s

三.選擇題

(1)在具有n個結(jié)點(diǎn)的單鏈表中，實現(xiàn)(A)的操作，其算法的

時間復(fù)雜度都是0(0。

A遍歷鏈表或求鏈表的第i個結(jié)點(diǎn)B在地址為P的

結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)

C刪除開始結(jié)點(diǎn)D刪除地址為P的結(jié)

點(diǎn)的后繼結(jié)點(diǎn)

(與設(shè)區(qū)hc為三個結(jié)點(diǎn)，p1Q20分別代表它們的地址，則

如下的存儲結(jié)構(gòu)稱為(B)。

Pa10b20

A循環(huán)鏈表B單鏈表C雙向循環(huán)鏈表

D雙向鏈表

(3)單鏈表的存儲密度(C)o

A大于1B等于1C小于1

D不能確定

(4已知一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)占m個存儲單元，若

第一個結(jié)點(diǎn)的地址為R則第1個結(jié)點(diǎn)的地址為(A)o

A&F(i—1)BBj-i*mCB-i*m

D肝(i+1)

(5)在有n個結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時間復(fù)雜度

為(B)。

A01)BQ足CQi?)DO

(logrj)

(位設(shè)LIink.RIink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針，則

指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是(D)。

AP=LB.LC.P=NULL

DP^Rlinl^=i

(7)兩個指針P和Q分別指向單鏈表的兩個元素,P所指元素是

Q所指元素前驅(qū)的條件是(B)。

AP-^>next==Q^>nextBP-^>next=QCQ^>next=P

DR=Q

(8)用鏈表存儲的線性表，其優(yōu)點(diǎn)是(C)。

A便于隨機(jī)存取B花費(fèi)的存儲空

間比順序表少

C便于插入和刪除D數(shù)據(jù)元素的物

理順序與邏輯順序相同

(0在單鏈表中，增加頭結(jié)點(diǎn)的目的是(C)。

A使單鏈表至少有一個結(jié)點(diǎn)B標(biāo)志表中首結(jié)

點(diǎn)的位置

C方便運(yùn)算的實現(xiàn)D說明該單鏈表

是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

(10)下面關(guān)于線性表的敘述中，錯誤的是(D)關(guān)系。

A順序表必須占一片地址連續(xù)的存儲單元B順序表可以隨

機(jī)存取任一元素

C鏈表不必占用一片地址連續(xù)的存儲單元D鏈表可以隨機(jī)

存取任一元素

(11)L是線性表，已知LengthList(I)的值是5,經(jīng)DelList"

2)運(yùn)算后，LengthList(I)的值是(C)。

A2B3C4

D5

(12)單鏈表的示意圖如下:

L

pQR

指向鏈表。吉點(diǎn)的前趨的指針是(B)0

ALBPCQDR

(13)設(shè)P為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則*P的直接前驅(qū)

(C)o

A找不到B查找時間復(fù)雜度為

0(1)

C查找時間復(fù)雜度為0(0D查找結(jié)點(diǎn)的次數(shù)約為

n

(%等概率情況下，在有n個結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需

平均移動結(jié)點(diǎn)的數(shù)目為(C)o

AnB.(p—1)/2C.r)/2

D

(15)在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是

(C)o

A雙向鏈表B單循環(huán)鏈表C.單鏈表

D雙向循環(huán)鏈表

(16)在順序表中，只要知道(D),就可以求出任一結(jié)點(diǎn)的存儲

地址。

A基地址B.結(jié)點(diǎn)大小C.向量大小

D基地址和結(jié)點(diǎn)大小

(IT)在雙鏈表中做插入運(yùn)算的時間復(fù)雜度為(A)o

A0(1)B0(rj)C0(n)DO

(logri)

(16)鏈表不具備的特點(diǎn)是(A)o

A隨機(jī)訪問B不必事先估計存儲

空間

C插入刪除時不需移動元素D所需空間與線性表

成正比

(n以下關(guān)于線性表的論述，不正確的為(c)o

A線性表中的元素可以是數(shù)字、字符、記錄等不同類型

B線性順序表中包含的元素個數(shù)不是任意的

C線性表中的每個結(jié)點(diǎn)都有且僅有一個直接前趨和一個直接后繼

D存在這樣的線性表，即表中沒有任何結(jié)點(diǎn)

(2Q在(B)的運(yùn)算中，使用順序表比鏈表好。

A插入B.根據(jù)序號查找c.刪除

D根據(jù)元素查找

[TH/A4?L—r^、上加

3?"ListNode*Demol(LinkListL,ListNode*p)

{〃L是有頭結(jié)點(diǎn)的單鏈表

()ListNode*q=L->next;

While(q&&q->next!=p)

q=q->next;

if(q)

returnq;

else

Error(u*pnotinL");

voidDemo2(ListNode*p,ListNode*q)

{〃p,*q是鏈表中的兩個結(jié)點(diǎn)

l々DataTypetemp;

temp=p->data;

p->data=q->data;

q->data=temp;

解:

(1)返回結(jié)點(diǎn)*p的直接前趨結(jié)點(diǎn)地址。

(2)交換結(jié)點(diǎn)*p和結(jié)點(diǎn)*q(p和q的值不變)。

五.程序填空

(1)已知線性表中的元素是無序的，并以帶表頭結(jié)點(diǎn)的單鏈表作存

儲。試寫一算法，刪除表中所有大于min,小于max的元素，試完成

下列程序填空。

Voiddelete(Ikiisthea&datatypemin,ma9

{(p4iead->next;

vvhile0

{if(^H>data<^nin)||(p^data>roax)

P->next;}

else

{cH>next=p->next;

delete⑥；

p=cH>next;}

(2)在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素用試完成

下列程序填空。

structnode

{elentypedata;

node*next;

}；

voidIkinsert^iode*head,elemtypeq

{node*s,*p;

s=newnode;

sH>data=x;

p=4iead-^>next;

v^iile0=^ULQ8&(pH>data!f)

p=rH>next;

if

cout?"不存在結(jié)點(diǎn)a!

else{s">next=p^>next;

rH>nexns;

六.算法設(shè)計題

(1)寫一個對單循環(huán)鏈表進(jìn)行遍歷(打印每個結(jié)點(diǎn)的值)的算法,

已知鏈表中任意結(jié)點(diǎn)的地址為Po

解：

voidShewC^istNode*D

{ListNode*t=^

do

{printfC%:",t->dat^);

t=t->reai;

}

while(t!=J);

}

(2)對給定的帶頭結(jié)點(diǎn)的單鏈表L編寫一個刪除L中值為x的結(jié)

點(diǎn)的直接前趨結(jié)點(diǎn)的算法。

解：

voiddelete(J^istbfode*D

{ListNode*q;

if^H>next-^>data=^

{

printf(“值為x的結(jié)點(diǎn)是第一個結(jié)點(diǎn)，沒有直接前

趨結(jié)點(diǎn)可以刪除")；

return;

For^=next->data!贄q=Rp=pfnext);〃刪除指針p

所指向的結(jié)點(diǎn)

q-^nexl^H^ext;

deleteg

}

(3)已知一個單向鏈表，編寫一個函數(shù)從單鏈表中刪除自第i個結(jié)

點(diǎn)起的k個結(jié)點(diǎn)。

解：

voidDel(pode*headtinti,int2

(

node*p)*q;

intj;

if(i=D

for(j=l;j依j-H)，刪除前k個元素

(

產(chǎn)head;“P指向要刪除的結(jié)點(diǎn)

hea<Miea(H>next;

deleteR

}

else

{

p=4iea(^

for(j=l;j—i—2;j44)

尸吁next;〃P指向要刪除的結(jié)點(diǎn)的前

一個結(jié)點(diǎn)

forG=l;j4H)

{

q=p>next;〃q指向要刪除的結(jié)點(diǎn)

pH>next=q-^>next;

deleteq;

(4)有一個單向鏈表(不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相同)，其頭指針為

head,編寫一個函數(shù)計算值域為x的結(jié)點(diǎn)個數(shù)。

解：/本題是遍歷單鏈表的每個結(jié)點(diǎn)，每遇到一個結(jié)點(diǎn)，結(jié)點(diǎn)個數(shù)加

1,結(jié)點(diǎn)個數(shù)存儲在變量n中。實現(xiàn)本題功能的函數(shù)如下：

intcounter

node*hea4

{node

intFF=(^

p=4iea(^

while(pl^LLQ

{if

n4-H

p=pH>next;

return?;

}

(5)有兩個循環(huán)單向鏈表，鏈頭指針分別為headl和head2,編寫

一個函數(shù)將鏈表headl鏈接到鏈表head2,鏈接后的鏈表仍是循環(huán)鏈

表。

解：/本題的算法思想是：先找到兩鏈表的尾指針，將第一個鏈表的

尾指針與第二個鏈表的頭結(jié)點(diǎn)鏈接起來，使之成為循環(huán)的。函數(shù)如下:

node*1ink(node*headl,*head?

{node*p>

p=4ieadl;

while^H>next!=headl)

p=5>^>next;

cp4iead2;

v^iile(q-^>next!=hea?

cpq-^>next;

p-^>next=4iead2;

q-^>next=4ieadl;

return^ieadl);

單元練習(xí)3

一.判斷題(下列各題，正確的請在前面的括號內(nèi)打，;錯誤的打X)

(M)(1)棧是運(yùn)算受限制的線性表。

(M)(2)在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生下溢

出。

(X)(3)棧一定是順序存儲的線性結(jié)構(gòu)。

(M)(0棧的特點(diǎn)是“后進(jìn)先出”。

(X)(5)空棧就是所有元素都為0的棧。

(義)(6在做GH語言中設(shè)順序棧的長度為NKXLEN則top^XLEN

時表示隊滿。

(，)(7)鏈棧與順序棧相比，其特點(diǎn)之一是通常不會出現(xiàn)棧

滿的情況。

(義)(的一個棧的輸入序列為：ABCD可以得到輸出序列：

CARD

(義)(9)遞歸定義就是循環(huán)定義。

(M)(10)將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。

二.填空題

(1)在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。

(2)在順序棧中，當(dāng)棧頂指針top-ia寸，表示棧空。

(3)在有此元素的棧中，進(jìn)棧操作的時間復(fù)雜度為0(D。

(4)在棧中，出棧操作的時間復(fù)雜度為：0(1)o

(5)已知表達(dá)式，求它的后綴表達(dá)式是棧的典型應(yīng)用。

(⑥在一個鏈棧中，若棧頂指針等于NULL則表示棧空。

(7)向一個棧頂指針為t。由勺鏈棧插入一個新結(jié)點(diǎn)*,寸，應(yīng)執(zhí)行

p^>next=top;和topp=p;操作。

(8)順序棧存儲在數(shù)組2(121@［0一此這［舊^1］中，進(jìn)棧操作

時要執(zhí)行的語句有：

SH>top-H-0(或=S_4>top+1)

(9)鏈棧LS,指向棧頂元素的指針是L沁next。

(1。從一個棧刪除元素時，首先取出棧頂元素，然后再移動

棧頂指針。

(11)由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置一頭

結(jié)點(diǎn)。

(12)已知順序棧S在對S進(jìn)行進(jìn)棧操作之前首先要判斷

滿。

(13)已知順序棧S在對S講行出棧操作之前首先要判斷棧是否

空。

(14)若內(nèi)存空間充足，鏈?？梢圆欢x棧滿運(yùn)算。

(15)鏈棧L畀空的條件是L沁next*ULL。

(16)鏈棧L和棧頂元素是鏈表的首元素。

(17)同一棧的各元素的類型相同。

(18)若進(jìn)棧的次序是ARG口目執(zhí)行三次出棧操作以后，棧

頂元素為B。

(12)的后綴表達(dá)式是：ABQ4DEn.

(20)四個元素按ABGD質(zhì)序進(jìn)皺，執(zhí)行兩次Pop(S,自

運(yùn)算后，那I值是C。

三.選擇題

(1)插入和刪除只能在一端進(jìn)行的線性表，稱為(C)。

A隊列R循環(huán)隊列C棧D循環(huán)棧

(2)設(shè)有編號為1,2,3,珀勺四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)

的站臺，下列不可能的出站順序為(D)

A1234B1243C1324D1423

(3)如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時(B)

A必須判別棧是否滿B.必須判別棧是否空

C必須判別棧元素類型D.隊棧可不做任何判別

(4)元素ABCD衣次進(jìn)棧以后，棧頂元素是(D)

AARBCCDD

(5)順序棧存儲空間的實現(xiàn)使用(B)存儲棧元素。

A鏈表B,數(shù)組C循環(huán)鏈表D變

量

(6)在或GH語言中，一個順序棧一旦被聲明，其占用空間的

大小(A)o

A已固定R不固定C可以改變D動態(tài)

變化

(7)帶頭結(jié)點(diǎn)的鏈棧L爭勺示意圖如下，棧頂元素是(A)

1LS

HABCDA

AAB.BCCDD

(8)鏈棧與順序棧相比，有一個比較明顯的優(yōu)點(diǎn)是(B)o

A插入操作更加方便B通常不會出現(xiàn)棧滿的

情況。

C不會出現(xiàn)?？盏那闆rD刪除操作根加方便

(9)從一個棧頂指針為to由勺鏈棧中刪除一個結(jié)點(diǎn)時，用嫄存

被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列(D)命令。

A.x=top;top^top-^>next;

Btofr=top-4>next;許top~^>data;

Cx=topH>data;

D^top->data;top^top-^xiext;

(10)在一個棧頂指針為卿勺鏈棧中，將一個牙旨針?biāo)傅慕Y(jié)點(diǎn)

入棧，應(yīng)執(zhí)行下列(B)命令。

A.HSH>next=^

BS->next^EISH>next;HSH>next=^

C.S-4>next=HSH>next;HS=S;

Dext#IS;HS=4IS-^>next;

(ID四個元素按ARG1M序進(jìn)/，執(zhí)行兩次Pop(S,自

運(yùn)算后，棧頂元素的值是(B)o

AARBCCDD

(12)元素ABC旅次進(jìn)棧以后，棧底元素是(A)o

AABBCCDD

(13)經(jīng)過下列棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是

(A)o

InitStack(s)(初始化棧)；Push(s,a);Push(s,b);Pop(s)

AaBbC1D0

(14)經(jīng)過下列棧的運(yùn)算后，珀勺值是(B)o

InitStack(s)(初始化棧)；Push(s,a);Push(s,b);

ReadTop(s);Pop(s,x);

AaBbC1D0

(15)經(jīng)過下列棧的運(yùn)算后，珀勺值是(B)o

InitStack(s)(初始化

棧)；Push(s,a);Pop(s,旬;Push(s,b);Pop(s,x);

AaBbC1D0

(16)經(jīng)過下列棧的運(yùn)算后，SHnpty(s)的值是(C)。

InitStack(s)(初始化棧)；Push(s,a);

Push(s,b);Pop(s,X)；Pop(s,x);

AaRbC1D0

(17)向順序棧中壓入元素時，(B)o

A先存入元素，后移動棧頂指針R先移動棧頂指針，

后存入元素

C誰先誰后無關(guān)緊要D同時進(jìn)行

(18)初始化一個空間大小為5的順序棧詬，2top的值是

(B)o

A0B-1C不再改變D動

態(tài)變化

(19)一個棧的入棧次序ABCDE則棧的不可能的輸出序列是

(C)o

AEDCBAB.DECBACDCEAB

DABCDE

(20)設(shè)有一個順序棧S,元素ABGDEF,依次進(jìn)棧，如果六

個元素出棧的順序是BRCF,耳A則棧的容量至少應(yīng)是

(A)o

A3B4C5D6

四.應(yīng)用題

(1)設(shè)有一個棧，元素進(jìn)棧的次序為：ABCnE用味

示進(jìn)棧操作，(衰示出棧操作，寫出下列出棧的操作序列。

①CBADE②AC

BED

解：①nioooioio

②IOIIOOI100

(2)求后綴表達(dá)式

①AABAon

解：ABACAD/

②

解：OABC*+DE/+

③A*(M)*D-E

解：ABC+*D*E—

④(^B)*G-E/(F-KMi)~D

解：AB+C*EFGH/+/—D—

⑤"(5+2)-6

解：852+/6一

六.算法設(shè)計題

(1)設(shè)用一維數(shù)組stacks表示一個堆棧，若堆棧中每個元素

需占用Mb數(shù)組單元(N>1)-

①試寫出其入棧操作的算法。

②試寫出其出棧操作的算法。

解：/用一整型變量top表示棧頂指針，top為0時表示棧為空。棧

中元素從S田開始存放元素。

/①入棧算法：

voidpush《harx)

(

if((to冏^XLEPM)

printf("堆棧溢出！”);

else

{

if(top==Q)

{

top-H;

S代阻不

)

else

top=top4M

s代阻不

/②出棧算法：

voidpopCharq

{

if(top=

printf("堆棧為空棧!”);

else

{

if(top==1)

(

S[top];

top;

}

else

(

*=S[top];

top=topM

(2)設(shè)計一個算法，要求判別一個算術(shù)表達(dá)式中的圓括號配對

是否正確。

解：/設(shè)表達(dá)式在字符數(shù)組a口中，使用一堆棧S來幫助判斷。

intcorrect《hara[])

(

stacks;

InitStack(s);/調(diào)用初始化棧函

數(shù)

for(i=Qi<strlen(^);i-H)

if=3()

Push(s,'();

else

ifQ[i]=NV)

{

ifStackBipty(s)/調(diào)用判?？蘸?/p>

數(shù)

returnQ/若棧為空返回《否

則出棧

else

Pop(s);

if^tackBipty(s))/調(diào)用判?？蘸瘮?shù)

printf(“配對正確！”);/若?？眨f明配對

正確，并返回1

else

printf("配對錯誤！”);對錯誤返回0

(3)設(shè)計一個將十進(jìn)正整數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的算法，并要求上機(jī)調(diào)

試通過。

解：#include<stdiQh>

#include<stdlib.h>

typedefstructstacknode公義棧的

存儲結(jié)構(gòu)

{

intdata;

structstacknode*next;

}stacknod^

typedefstruct

{

stacknode/定義棧頂?shù)?/p>

指針

}1inkstack;

voidConversion(intn)的應(yīng)

用：十一一十六進(jìn)制轉(zhuǎn)換

{1inkstacks;

int蘇

s.top=^SLLL;棧

空

do

{x=n^16;余

數(shù)

戶r)/16;/取新的商

stacknode*p=mewstacknod^小請新結(jié)點(diǎn)

pH>next=s.top;/I修改棧頂

指針

s.top=5);

s.top->data=x;/余數(shù)入棧

while(h);

printfC7Z7轉(zhuǎn)換后的十六進(jìn)制數(shù)值為：";

while(s.top)/出棧處

理

{if(s.top->data<lQ);

printfC%!",s.topH>data);

else

switch(s.topH>dat4)

case10:printf'A);break;

case11:printf'g);break;

case12printf(%",zC);break;

case13:printfC%:",zH);break;

case14printfC%:",7E，);break;

case15:printf'F);break;

}

stacknode*p=s.top;

s.top=s.top->next;

free?;棧一個余

數(shù)，收回一個結(jié)

}

printf("\p\p")；

)

voidmain0

(

intn;

printfC77't請輸入一個十進(jìn)制正整數(shù)：%

scanfC%1",&rj);

Conversion?;

}

單元練習(xí)4

一.判斷題(下列各題，正確的請在前面的括號內(nèi)打，;錯誤的打X)

(M)(1)隊列是限制在兩端進(jìn)行操作的線性表。

(M)(2)判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向

同一個結(jié)點(diǎn)。

(X)(3)在鏈隊列上做出隊操作時，會改變front指針的值。

(，)(4在循環(huán)隊列中，若尾指針rear大于頭指針front,其元

素個數(shù)為rear—fronto

(X)(5)在單向循環(huán)鏈表中，若頭指針為h,那么p所指結(jié)點(diǎn)為尾

結(jié)點(diǎn)的條件是小

(M)(⑥鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。

(x)(7)在循環(huán)鏈隊列中無溢出現(xiàn)象。

(x)(6棧和隊列都是順序存儲的線性結(jié)構(gòu)。

(x)(9)在隊列中允許刪除的一端稱為隊尾。

(x)(10)順序隊和循環(huán)隊關(guān)于隊滿和隊空的判斷條件是一樣

的。

二.填空題

(1)在隊列中存取數(shù)據(jù)應(yīng)遵循的原則是先進(jìn)先出。

(2)隊列是被限定為只能在表的一端進(jìn)行插入運(yùn)算,在

表的另一端進(jìn)行刪除運(yùn)算的線性表。

(3)在隊列中，允許插入的一端稱為隊尾。

(4)在隊列中，介許刪除的一端稱為隊首(或隊頭)。

(5)隊列在進(jìn)行出隊操作時，首先要判斷隊列是否為

空。

(6)順序隊列在進(jìn)行入隊操作時，首先要判斷隊列是否為

滿O

(7)順序隊列初始化后，front=reax—1。

(8)解決順序隊列“假溢出”的方法是采用循環(huán)隊列。

(9)循環(huán)隊列的隊首指針為front,隊尾指針為rear,則隊空的條

件為front-rear。

(10)鏈隊列皿空時，LD^front->next=NULLo

(11)設(shè)長度為由勺鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指

針，則入隊操作的時間復(fù)雜度為0(n)。

(12)設(shè)長度為由勺鏈隊列用單循環(huán)鏈表表示，若只設(shè)尾指

針，則出隊操作的時間復(fù)雜度為0(1)。

(13)在一個鏈隊列中，若隊首指針與隊尾指針的值相同，

則表示該隊列為空。

(14)設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear

指向隊尾元素后的一個空閑元素，隊列的最大空間為

MXXLEN,則隊滿標(biāo)志為：

f1on(rear+1)(WIAXLEN。

(15)在一個鏈隊列中，若隊首指針為front,隊尾指針為

rear,則判斷該隊列只有一個結(jié)點(diǎn)的條件為：

front=rear儆front!NULL。

(或front=rear&&frontONJLL)

(16)向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指

針一,然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。

(17)讀隊首元素的操作不改變(或不影響)隊列元素的

個數(shù)。

(18)設(shè)循環(huán)隊列的容量為40(序號從0到39,現(xiàn)經(jīng)過一系列的入

隊和出隊運(yùn)算后，有front=ll,rear-19,則循環(huán)隊列中還有8

個元素。

(L=C4I-rear—front)%N=(4CH-19—11)%40=6)

(19)隊列Q,經(jīng)過下列運(yùn)算：InitQueueQ(初始化隊

列)；InQueueQa);InQueueQb);OutQueueQ電；

ReadFrontQ舟；QBnpty。：后的值是0。

(20)隊列Q經(jīng)過InitQueueQ(初始化隊

列)；InQueueQa;IrQieueQt>);ReadFrontQ力后，x的值是

三.選擇題

(1)隊列是限定在(D)進(jìn)行操作的線性表。

A中間R隊首C隊尾D端點(diǎn)

(2)隊列中的元素個數(shù)是(B)。

A不變的R可變的C任意的D0

(3)同一隊列內(nèi)各元素的類型(A)。

A必須一致B.不能一致C可以不一致

D不限制

(4)隊列是一個(C)線性表結(jié)構(gòu)。

A不加限制的B.推廣了的C加了限制的

D非

(5)當(dāng)利用大小為由勺數(shù)組順序存儲一個隊列時，該隊列的最后

一個元素的下標(biāo)為(B)o

An—2Rn—1CnDrH-1

(6)一個循環(huán)隊列一旦說明，其占用空間的大小(A)。

A已固定B.可以變動C,不能固定

D動態(tài)變化

(7)循環(huán)隊列占用的空間(A)。

A必須連續(xù)R不必連續(xù)C,不能連續(xù)

D可以不連續(xù)

(S存放循環(huán)隊列元素的數(shù)組dat猜1外元素，則dat嗷組的

下標(biāo)范圍是(B)。

A0..10R0..9C1..9

D1..10

(9)若進(jìn)隊的序列為：AB,QQ則出隊的序列是(C)o

AB.CDABAGED

CABCDDCBDA

(10)四個元素按：ABCDIM序連續(xù)進(jìn)隊Q則隊尾元素是

(D)。

AABB

CCDD

(11)四個元素按：ABCE?序連續(xù)進(jìn)隊Q執(zhí)行一次OutQueueQ

操作后，隊頭元素是(B)。

AARBCCDD

(12)四個元素按：A,BC；］>序連續(xù)進(jìn)隊Q執(zhí)行四次OutQueueQ

操作后，再執(zhí)行QBnptyQ;后的值是(B)。

A0R1C2D3

(13)隊列Q經(jīng)過下列運(yùn)算后，x的值是(B)o

InitQueueQ(初始化隊歹！J);InQueueQa);

InQueueQb);OutQueueQx);

ReadFrontQx);

AaBbC