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

單元練習(xí)1

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

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

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

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

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

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

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

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

(V)(8)數(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é)點以外，其余每個結(jié)點只有1個前趨結(jié)點。

(6)在圖形結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(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)系,

(II)圖形結(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,R),其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有

限集合。

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

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

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

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

的函數(shù)。

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

(nlog2n)o

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

（20）數(shù)點結(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）。

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

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

構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

存儲方式。

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

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

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

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

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)

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

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

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

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

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

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

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

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

A,0(1)B.0(n)C.0(log2n)D.O(n2)

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

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

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

c[i][j]=i+j；

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

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

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

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

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

A.計算方法B.排序方法

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

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

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

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

解：0(n*m)

(2)s=0;

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

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

s+=B[i][j];

sum=s;

解：0(n2)

(3)T=A；

A二B；

B二T；

解：0(1)

(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={}

解:a

o

c

oa8

屬于集合

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

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

R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}(尖括號表示結(jié)點之間關(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>)

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

6

屬于圖結(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

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

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

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

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

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

(X)(5)線性鏈表的刪除算法簡單.，因為當(dāng)刪除鏈中某個結(jié)點后，計算機(jī)會自動地將后續(xù)

的各個單元向前移動。

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

(V)(7)線性表鏈?zhǔn)酱鎯Φ奶攸c是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。

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

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

(><)(10)插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也

經(jīng)常使用。

—.填空題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

個元素。

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

址存放在前驅(qū)結(jié)點的指針域中。

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

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

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

(17)在雙向鏈表中，每個結(jié)點都有兩個指針域，它們一個指向其前驅(qū)結(jié)點,另一

個指向其—后繼結(jié)點。

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

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

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

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

個結(jié)點，則可用下列兩個語句：S->next->next=P->next;和P->next=S;

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

三.選擇題

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

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

點

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

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

P

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

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

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

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

則第i個結(jié)點的地址為(A)。

A.B+(i-l)*mB.B+i*mC.B-i*mD.B+(i+l)*m

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

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

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

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

A.P==LB.P->Llink==LC.P==NULL1).P->Rlink==L

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

件是(B)?

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

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

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

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

同

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

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

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

結(jié)構(gòu)

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

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

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

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

（L）的值是（C）0

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

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

H|八|

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

A.LB.PC.QD.R

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

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

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

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

（C）。

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

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

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

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

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

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

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

（18）鏈表不具備的特點是（A）。

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

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

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

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

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

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

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

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

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

四.分析下述算法的功能、、

ListNode*Demol(LinkListL,ListNode*p)

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

ListNode*q=L->next;

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

q=q->next;

if(q)

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

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

DataTypetemp;

解：temp=p->data;

(i)p->data=q->data;

(2)q->data=temp;g)o

)

五.程序填空

(1)已知線性表中的元素是無序的，并以帶表頭結(jié)點的單鏈表作存儲。試寫一算法，刪除

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

Voiddelete(Iklisthead;datatypemin,max)

{q=head->next;

while(p!=NULL)

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

{q=p；P=P->next;}

else

{q->next=p->next;

delete(p);

p=q->next;}

(2)在帶頭結(jié)點head的單鏈表的結(jié)點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=p->next_____;

if(p==NULL)

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

else{s->nexl=D->nexl;

p?>next=s;

)

)

六.算法設(shè)計題

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

地址為PO

解：

voidShow(ListNode*P)

{ListNode*t=P;

do

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

t=t->rear;

)

while(t!=P);

)

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

算法。

解：

voiddelete(ListNode*L)

{ListNode*p=L,*q;

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

{

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

return;

}

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

q->next=p->next;

deletep;

}

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

解：

voidDel(node*head,inti,intk)

node

intj;

if(i==l)

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

(

p=head;//p指向要刪除的結(jié)點

head=head->next;

deletep;

)

else

(

p=head;

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

p=p->next;〃p指向要刪除的結(jié)點的前一個結(jié)點

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

(

q=p->next;//q指向要刪除的結(jié)點

p->next=q->next;

deleteq;

)

)

}

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

數(shù)計算值域為x的結(jié)點個數(shù)。

解：//本題是遍歷單鏈表的每個結(jié)點，每遇到一個結(jié)點，結(jié)點個數(shù)加1,結(jié)點個數(shù)存儲在變

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

intcounter(head)

node*head；

{node*p;

intn=0;

p=head；

while(p!=NULL)

{if(p->data==x)

p=p->next;

}

return(n);

}

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

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

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

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

node*link(node*headl,*head2)

{node*p,*q;

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

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

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

(V)(2)在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢出。

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

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

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

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

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

(乂)(8)一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D。

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

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

二.填空題

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

(2)在順序棧中，當(dāng)棧頂指針top=-l時，表示?？?。

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

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

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

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

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

top=p；操作。

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

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

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

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

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

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

(13)已知順序棧S,在對5進(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)四個元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運(yùn)算后，x的值是

C

三.選擇題

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

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

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

能的出站順序為(D)

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

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

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

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

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

A.AB.BC.CD.D

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

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

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

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

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

LS

HABcDA

A.AB.BC.CD.D

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

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

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

(9)從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(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)在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點入棧，應(yīng)執(zhí)行下列-

(B)命令。

A.HS->next=S;B.S->nextz:HS->next;HS->next=S;

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

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

素的值是(B)。

A.AB.BC.CD.I)

(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)向順序棧中壓入元素時，(B)。

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

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

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

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

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

A.EDCBAB.DECBAC.DCEABD.ABCDE

(20)設(shè)有一個順序棧S,元素人,8,(：,口，￡廳，依次進(jìn)棧，如果六個元素出棧的順序

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

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

四.應(yīng)用題

(1)設(shè)有一個棧，元素進(jìn)棧的次序為：A,B,C,D,E,用I表示進(jìn)棧操作，0表示

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

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

解：①1110001010

@1011001100

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

①A"B"C/D

解：AB*C*D/

②-A+B+C+D/E

解：0A-BC*+DE/+

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

解：ABC+*D*E-

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

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

⑤8/(5+2)-6

解：852+/6-

六.算法設(shè)計題

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

(M>1)。

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

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

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

元素。

//①入棧算法：

voidpush(charx)

(

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

printf(“堆棧溢出！”)；

else

{

if(top==0)

(

top++;

S[top]=x;

}

else

(

top=top+M;

S[top]=x;

〃②出棧算法：

voidpop(charx)

(

if(top==0)

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

else

(

if(top==1)

(

x=S[topj;

top--;

else

x=Sftop];

top=top-M;

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

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

inicorrect(chara[])

(

stacks;

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

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

if(a[i]==C)

Push(s,'(');

else

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

(

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

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

else

Pop(s)；

)

if(StackEmpty(s))〃調(diào)用判?？蘸瘮?shù)

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

else

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

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

解：#include<stdio.h>

#include<stdlib.h>

typedefstructstacknode〃定義棧的存儲結(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;〃置棧空

do

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

n=n/16;〃取新的商

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

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("%d",s.top->data);

else

switch(s.top->data)

(

case10:printf("%c",'A');break;

case11:printf("％c",'B');break;

case12:printf(',%cn/C');break;

case13:printf(H%c"/D');break;

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

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

)

stacknode*p=s.top;

s.top=s.top->next;

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

)

printf(M\n\n");

)

voidmain()

(

intn;

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

scanf(n%d",&n);

Conversion(n);

單元練習(xí)4

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

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

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

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

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

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

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

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

(X)(8)棧和隊列都是順序存儲的線性結(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)行入隊操作時，首先要判斷隊列是否為滿。

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

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

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

rear

(10)鏈隊列LQ為空時，LQ->front->next"NULL

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

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

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

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

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

5o

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

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

front==(rear+1)%MAXLEN。

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

有一個結(jié)點的條件為：front==rear&&front1NULL。

(或front==rear&&front＜〉NULL)

(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=(N+rear-front)%N=(40+19-11)%40=8)

(19)隊列Q,經(jīng)過下