實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第三版)課后答案

單元練習(xí)1

判斷題（下列各題，正確的請?jiān)谇懊娴睦ㄌ?hào)內(nèi)打J；錯(cuò)誤的打X）

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

（J）（2）一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。

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

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

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

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

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

（V）（8）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。

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

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

二.填空題

（1）數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(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)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前趨結(jié)點(diǎn)。

（6）在圖形結(jié)構(gòu)中，錘個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

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

（8）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。

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

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

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

（12）數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法（或運(yùn)算）三個(gè)方面的

內(nèi)容。

（13）數(shù)據(jù)結(jié)構(gòu)被定義為（D,R）,其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有

限集合。

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

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

（16）一個(gè)算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。

（17）算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間，它是該算法求解問題規(guī)模n

的函數(shù)。

（18）若一個(gè)算法中的語句頻度之和為T（n）=6n+3nlog2n,則算法的時(shí)間復(fù)雜度為

（nlogzn）。

（19）若一個(gè)算法中的語句頻度之和為T（n）=3n+nlog2n+n2,則算法的時(shí)間復(fù)雜度為

（n2）o

（20）數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象，以及

它們之間的關(guān)系和運(yùn)算的學(xué)科。

三.選擇題

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

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

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

A.動(dòng)態(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ì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為

（C）。

A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)

構(gòu)

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

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

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

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

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

（5）鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（A）。

A.分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

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

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

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

（6）算法的計(jì)算量大小稱為算法的（C

A.現(xiàn)實(shí)性B.難度C.時(shí)間復(fù)雜性D.效率

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

A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.文件

（8）每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，這種

存儲(chǔ)結(jié)構(gòu)稱為（A）結(jié)構(gòu)。

A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.索引存儲(chǔ)D.散列存儲(chǔ)

（9）每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素,還包含一組指針，該存儲(chǔ)方式是（B）

存儲(chǔ)方式。

A.順序B.鏈?zhǔn)紺.索引D.散列

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

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

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

A.物理結(jié)構(gòu)B.存儲(chǔ)結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.邏輯和存

儲(chǔ)結(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)容、相對位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（A

A.邏輯結(jié)構(gòu)B.存儲(chǔ)結(jié)構(gòu)C.邏輯實(shí)現(xiàn)D.存儲(chǔ)實(shí)現(xiàn)

（14）每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)存放在連續(xù)的存儲(chǔ)空間，另外有一組

指明結(jié)點(diǎn)存儲(chǔ)位置的表，該存儲(chǔ)方式是（C）存儲(chǔ)方式。

A.順序B.鏈?zhǔn)紺.索引D.散列

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

A.正確性B.易讀性C.健壯性D.高效性

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

A.正確性B.易讀性C.健壯性D.高效性

（17）下列時(shí)間復(fù)雜度中最壞的是（D）。

0(n2)

A.0（1）B.0（n）C.0（log2n）D.

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

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

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

c[i]Ul=i+j；

0(n2)

A.0(1)B.0(n)C.0(log2n)D.

（19）算法分析的兩個(gè)主要方面是（A）o

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

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

（20）計(jì)算機(jī)算法必須具備輸入、輸出和（C

A.計(jì)算方法B.排序方法

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

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

(1)for(i=0;i〈n;i++)

for(j=0;j<m;j++)

A[i][j]

解:0(n*m)

(2)s=0;

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

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

s+=

sum=s;

解：0(n2)

(3)T=A；

A二B；

B=T；

解：。⑴

(4)si(intn)

{intp=l,s=0;

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

{p*=i;s+=p;}

return(s);

)

0(n)

(5)s2(intn)

x=0;

y=0；

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

x++;

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

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

y++;

解:0(n2)

五.根據(jù)二元組關(guān)系，畫出對應(yīng)邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。

(1)A=(D,R),其中：

D={a,b,c.d,e}.

R={}

解：aQd

屬于集合

(2)B=(D,R),其中：

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

R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}(尖括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的)

解：

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

(3)F=(D,R),其中：

D={50,25,64,57,82,36,75,55},R={r}

R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>}

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

(4)C=(D,R),其中：

D={1,2,345,6},R={r}

R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}(園括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的)

解:

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

(5)E=(D,R),其中:

D={a,b,c,d,e,f,g,h},R={r}

R={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}

解：

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

單元練習(xí)2

判斷題(下列各題，正確的請?jiān)谇懊娴睦ㄌ?hào)內(nèi)打J；錯(cuò)誤的打X)

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

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

(J)(3)在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。

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

(X)(5)線性鏈表的刪除算法簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)

的各個(gè)單元向前移動(dòng)。

(義)(6)順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。

(V)(7)線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用?組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。

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

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

(X)(10)插入和刪除操作是數(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é)省存儲(chǔ)和隨機(jī)存取。

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

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

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

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

(8)在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P,其時(shí)間復(fù)雜度為0(1)。

(9)在單鏈表中要在已知結(jié)點(diǎn)*P之前插入一個(gè)新結(jié)點(diǎn)，需找到*P的直接前趨結(jié)點(diǎn)的地

址，其杳找的時(shí)間復(fù)雜度為0(n)。

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

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

(12)在一個(gè)長度為n的順序表中刪除第i個(gè)元素，要移動(dòng)n-i個(gè)元素。

(13)在一個(gè)長度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移n-i+1

個(gè)元素。

(14)在無頭結(jié)點(diǎn)的單鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其它結(jié)點(diǎn)的存儲(chǔ)地

址存放在前趨結(jié)點(diǎn)的指針域中。

(15)當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存

取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。

(16)在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過指針決定的。

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

個(gè)指向其—后繼結(jié)點(diǎn)。

（18）對一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為官。

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

D->prior->next=p->next。

（20）在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩

個(gè)結(jié)點(diǎn)，則可用卜列兩個(gè)語句：S->next->ncxt=P->next;和P->next=S;

來實(shí)現(xiàn)該操作。

三.選擇題

（1）在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)（A）的操作，其算法的時(shí)間復(fù)雜度都是O（n）。

A.遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn)B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)

點(diǎn)

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

（2）設(shè)a、b、c為三個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，則如下的存儲(chǔ)結(jié)構(gòu)稱為（B）。

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

（3）單鏈表的存儲(chǔ)密度（C）。

A.大于1B.等于1C.小于1D.不能確定

（4）已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為B,

則第i個(gè)結(jié)點(diǎn)的地址為（A）。

A.B+（i-l）*mB.B+i*mC.B-i*mD.B+（i+l）*m

（5）在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為（B）。

2

A.0（1）B.0（n）C.0（n）D.0（log2n）

（6）設(shè)Uink、Rlink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的元素是

雙循環(huán)鏈表L的尾元素的條件是（D）。

A.P==LB.P->Llink==LC.P==NULLD.P->Rlink==L

（7）兩個(gè)指針P和Q,分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條

件是（B）0

A.P->next==Q-〉nextB.P->next==QC.Q->next==PD.P==Q

（8）用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是（C）0

A.便于隨機(jī)存取B.花費(fèi)的存儲(chǔ)空間比順序表少

C.便于插入和刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相

同

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

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

C.方便運(yùn)算的實(shí)現(xiàn)D.說明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

結(jié)構(gòu)

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

A.順序表必須占一片地址連續(xù)的存儲(chǔ)單元B.順序表可以隨機(jī)存取任一元素

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

(11)L是線性表，已知LengthList(L)的值是5,經(jīng)DelList(L,2)運(yùn)算后，LengthList

(L)的值是(C)o

A.2B.3C.4D.5

（12）單鏈表的示意圖如下：

指向鏈表Q結(jié)點(diǎn)的前趨的指針是（B）。

A.LB.PC.QD.R

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

A.找不到B.查找時(shí)間復(fù)雜度為0（1）

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

（14）等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為

（C）。

A.nB.（n-l）/2C.n/2D.（n+l）/2

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

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

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

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

（17）在雙鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為（A）。

A.0（1）B.0（n）C.0（n"）D.0（logan）

（18）鏈表不具備的特點(diǎn)是（A）。

A.隨機(jī)訪問B.不必事先估計(jì)存儲(chǔ)空間

C.插入刪除時(shí)不需移動(dòng)元素D.所需空間與線性表成正比

（19）以下關(guān)于線性表的論述，不正確的為（C）。

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

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

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

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

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

A.插入B.根據(jù)序號(hào)查找C.刪除D.根據(jù)元素查找

四.分析下述算法的功能

(1)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("*pnotinL");

}

(2)voidDemo2(ListNode*p,ListNode*q)

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

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)的單鏈表作存儲(chǔ)。試寫一算法，刪除

表中所有大于min,小于max的元素，試完成下列程序填空。

Voiddelete(Iklisthead;datatypemin,max)

{q=head->next;

while(p!=NULL)

{if((p->data<=min)11(D->data>=max)

{q=p;p=p->next：}

else

{q->next=p->next;

delete(p);

p=q->next;}

)

)

(2)在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x,試完成下列程序填空。

structnode

{elemtypedata;

node*next;

);

voidIkinsert(node*head,elemtypex)

{node*s,*p;

s=newnode;

s->data=x:

p=head->next;

while(p!=NULL)&&(p->data!=a)

p=l)_>next_____;

if(p==NULL)

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

else{s?>next=p->next;

D->nex仁s;

六.算法設(shè)計(jì)題

(1)寫?個(gè)對單循環(huán)鏈表進(jìn)行遍歷(打印每個(gè)結(jié)點(diǎn)的值)的算法，已知鏈表中任意結(jié)點(diǎn)的

地址為PO

解：

voidShow(ListNode*P)

{ListNode*t=P;

do

{printf(,,%c,,,t->data);

t=t->rear;

)

while(t!=P);

)

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

算法。

解：

voiddelete(ListNode*L)

{ListNode*p=L,*q;

if(L->next->data==X)

{

printf(“值為x的結(jié)點(diǎn)是第?個(gè)結(jié)點(diǎn)，沒有直接前趨結(jié)點(diǎn)可以刪除”)；

return;

)

For(p->next->data!=X;q=p;p=p->next);//刪除指針p所指向的結(jié)點(diǎn)

q->next=p->next;

deletep;

)

(3)已知一個(gè)單向鏈表，編寫?個(gè)函數(shù)從單鏈表中刪除自第i個(gè)結(jié)點(diǎn)起的k個(gè)結(jié)點(diǎn)。

解：

voidDel(node*head,inti,intk)

(

node*p,*q;

intj;

if(i==l)

for(j=l;j<=k;j++)//刪除前k個(gè)元素

(

p=head;〃p指向要?jiǎng)h除的結(jié)點(diǎn)

head=head->next;

deletep;

)

else

(

p=head;

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

p=p->next;〃p指向要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

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

(

q=p->next;//q指向要?jiǎng)h除的結(jié)點(diǎn)

p->next=q->next;

deleteq;

)

)

)

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

數(shù)計(jì)算值域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。

解：〃本題是遍歷單鏈表的每個(gè)結(jié)點(diǎn)，每遇到?個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加1,結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變

量n中。實(shí)現(xiàn)本題功能的函數(shù)如下：

intcounter(head)

node*head；

{node*p;

intn=0;

p=head；

while(p!=NULL)

{if(p->data==x)

n++；

p=p->next;

return(n);

(5)有兩個(gè)循環(huán)單向鏈表，鏈頭指針分別為headl和head2,編寫一個(gè)函數(shù)將鏈表headl鏈

接到鏈表head2,鏈接后的鏈表仍是循環(huán)鏈表。

解：〃本題的算法思想是：先找到兩鏈表的尾指針，將第-個(gè)鏈表的尾指針與第二個(gè)鏈表的

頭結(jié)點(diǎn)鏈接起來，使之成為循環(huán)的。函數(shù)如下：

node*link(node*headl,*head2)

{node

p=head1;

while(p->next!=head1)

p=p->next;

q=head2;

while(q->next!=head2)

q=q->next;

p->next=head2;

q->next=headl;

return(headl);

單元練習(xí)3

一.判斷題(下列各題，正確的請?jiān)谇懊娴睦ㄌ?hào)內(nèi)打，；錯(cuò)誤的打X)

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

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

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

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

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

(X)(6)在C或C++語言中設(shè)順序棧的長度為MAXLEN,則top=MAXLEN時(shí)表示隊(duì)滿。

(V)(7)鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。

(X)(8)?個(gè)棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D。

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

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

二.填空題

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

(2)在順序棧中，當(dāng)棧頂指針top=T時(shí)，表示?？铡?/p>

(3)在有n個(gè)元素的棧中，進(jìn)棧操作的時(shí)間復(fù)雜度為0(1)。

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

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

(6)在一個(gè)鏈棧中，若棧頂指針等于NULL,則表示?？?。

(7)向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p->nexl=top；和

top=p；操作。

(8)順序棧S存儲(chǔ)在數(shù)組S->data[0..MAXLENT]中，進(jìn)棧操作時(shí)要執(zhí)行的語句有：

S->top++。(或=S->top+l)

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

(10)從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng)棧頂指針。

(11)由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置頭結(jié)點(diǎn)。

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

(13)已知順序棧S,在對$進(jìn)行出棧操作之前首先要判斷棧是否空。

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

(15)鏈棧LS是空的條件是LS->next=NULL-

(16)鑄棧LS的棧頂元素是鏈表的首元素。

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

(18)若進(jìn)棧的次序是A、B、C、D、E,執(zhí)行三次出棧操作以后，棧頂元素為B。

(19)A+B/C-D*E的后綴表達(dá)式是：ABC/+DE*-。

(20)四個(gè)元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運(yùn)算后，x的值是

C

三.選擇題

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

A.隊(duì)列B.循環(huán)隊(duì)列C.棧D.循環(huán)棧

（2）設(shè)有編號(hào)為1,2,3,4的四輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可

能的出站順序?yàn)椋―）

A.1234B.1243C.1324D.1423

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

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

C.必須判別棧元素類型D.隊(duì)?？刹蛔鋈魏闻袆e

（4）元素A,B,C,D依次進(jìn)棧以后,棧頂元素是（D）

A.AB.BC.CD.D

（5）順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（B）存儲(chǔ)棧元素。

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

（6）在C或C++語言中，?個(gè)順序棧一旦被聲明，其占用空間的大小（A）。

A.已固定B.不固定C.可以改變D.動(dòng)態(tài)變化

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

ILS

HABCDA

A.AB.BC.CD.D

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

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

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

（9）從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)

執(zhí)行下列（D）命令。

A.x=top;top=top->next;B.top=top->next;x=top->data;

C.x=top->data;D.x=top->data;top=top->next;

（10）在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列一

（B）命令。

A.HS->next=S;B.S->next=HS->next;IIS->next=S;

C.S->next=HS->next;HS=S;D.S->next=HS;HS=HS->next;

（11）四個(gè)元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop（S,x）運(yùn)算后，棧頂元

素的值是（B）。

A.AB.BC.CD.D

（12）元素A,B,C,D依次進(jìn)棧以后，棧底元素是（A）。

A.AB.BC.CD.D

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

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

A.aB.bC.1D.0

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

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

A.aB.bC.1D.0

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

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

A.aB.bC.1D.0

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

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

A.aB.bC.1D.0

(17)向順序棧中壓入元素時(shí)，(B)。

A.先存入元素，后移動(dòng)棧頂指針B.先移動(dòng)棧頂指針，后存入元素

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

(18)初始化一個(gè)空間大小為5的順序棧S后，S->top的值是(B)。

A.0B.-1C.不再改變D.動(dòng)態(tài)變化

(19)一個(gè)棧的入棧次序ABCDE,則棧的不可能的輸出序列是(C)。

A.EDCBAB.DECBAC.DCEABD.ABCDE

(20)設(shè)有一個(gè)順序棧S,元素A,B,C,D,E,F,依次進(jìn)棧，如果六個(gè)元素出棧的順序

是B,D,C,F,E,A,則棧的容量至少應(yīng)是(A)。

A.3B.4C.5D.6

四.應(yīng)用題

(1)設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)椋篈,B,C,D,E,用I表示進(jìn)棧操作，0表示

出棧操作，寫出下列出棧的操作序列。

①C,B,A,D,E②A,C,B,E,D

解：①HI00010I0

(2)1011001100

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

①A"B'C/D

解：AB*C*D/

②-A+B+C+D/E

解：0A-BC*+DE/+

③A*(B+C)*1)-E

解：ABC+*D*E-

④(A+B)*C-E/(F+G/H)-D

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

⑤8/(5+2)-6

解：852+/6-

六.算法設(shè)計(jì)題

(1)設(shè)用一維數(shù)組stack[n]表示一個(gè)堆棧，若堆棧中每個(gè)元素需占用M個(gè)數(shù)組單元

(M>1)。

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

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

解：〃用一整型變量top表示棧頂指針，top為0時(shí)表示棧為空。棧中元素從S⑴開始存放

元素。

〃①入棧算法：

voidpush(charx)

(

if((top+M)>MAXLEN-1)

printf(“堆棧溢出！”)；

else

(

if(top==0)

{

top++;

SLtopJ=x;

)

else

(

top=top+M;

S[topl=x;

〃②出棧算法：

voidpop(charx)

(

if(top==0)

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

else

(

if(top==1)

{

x=S[topJ;

top--;

)

else

(

x=S[top];

top=top-M;

（2）設(shè)計(jì)一個(gè)算法，要求判別一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對是否正確

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

inicorrect(chara[])

(

stacks;

InitStack(s);〃調(diào)用初始化棧函數(shù)

for(i=0;i<strlen(a);i++)

if(a[i]=='(')

Push(s,'(');

else

if(a[i]==')')

(

ifStackEmpty(s)〃調(diào)用判棧空函數(shù)

return0;〃若棧為空返回0:否則出棧

else

Pop⑸；

)

if(StackEmpty(s))〃調(diào)用判棧空函數(shù)

printf(“配對正確！”);〃若棧空，說明配對正確，并返回1

else

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

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

解：#include<stdio.h>

#include<stdlib.h>

typedefstructstacknode〃定義棧的存儲(chǔ)結(jié)構(gòu)

(

intdata;

structstacknode*next;

}stacknode;

typedefstruct

(

stacknode*top;〃定義棧頂?shù)闹羔?/p>

}linkstack;

voidConversion(intn)〃棧的應(yīng)用：十——十六進(jìn)制轉(zhuǎn)換

{linkstacks;

intx;

s.top=NULL;〃置?？?/p>

do

{x=n%16;〃取余數(shù)

n=n/16;〃取新的商

stacknode*p=newstacknode;〃申請新結(jié)點(diǎn)

p->next=s.top;〃修改棧頂指針

s.top=p;

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

)

while(n);

printf("\n\t\t轉(zhuǎn)換后的十六進(jìn)制數(shù)值為：”；

while(s.top)〃出棧處理

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

printf(n%dM,s.top->data);

else

switch(s.top->data)

(

case10:printf(,'%c'VA,);break;

case11:printf(,,%c,',,B,);break;

case12:printf(”％c"；C');break;

case13:printf("％c",'D');break;

case14:printf("%c",'E');break;

case15:printf("%c",'F');break;

)

stacknode*p=s.top;

s.top=s.top->next;

free(p);〃出棧一個(gè)余數(shù)，收回一個(gè)結(jié)

)

printf(”\n\n“)；

)

voidmain()

(

intn;

printf(n\n\t\t請輸入一個(gè)十進(jìn)制正整數(shù)：”)；

scanf(u%d",&n);

Conversion(n);

單元練習(xí)4

判斷題(下列各題，正確的請?jiān)谇懊娴睦ㄌ?hào)內(nèi)打J；錯(cuò)誤的打X)

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

(V)(2)判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個(gè)結(jié)點(diǎn)。

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

(V)(4)在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front,其元素個(gè)數(shù)為rear-front1>

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

(V)(6)鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。

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

(X)(8)棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。

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

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

二.填空題

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

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

除運(yùn)算的線性表。

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

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

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

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

(7)順序隊(duì)列初始化后，front=rear=7。

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

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

rear

(10)鏈隊(duì)列LQ為空時(shí)，LQ-〉front->next=NULL。

(11)設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間

復(fù)雜度為0(n)。

(12)設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間

復(fù)雜度為0(1)。

(13)在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為

￡。

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

個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN,則隊(duì)滿標(biāo)志為：

front==(rear+1)%MAXLEN。

(15)在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為front,隊(duì)尾指針為rear,則判斷該隊(duì)列只

有一個(gè)結(jié)點(diǎn)的條件為：front==rear&&front!NULL?

(或front==re