數據結構基礎(第三版)課后答案7

單元練習1

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

(V)(I)數據的邏輯結構與數據元素本身的內容和形式無關。

(V)(2)一個數據結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。

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

(X)(4)數據的邏輯結構和數據的存儲結構是相同的。

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

(V)(6)從邏輯關系上講，數據結構主要分為線性結構和非線性結構兩類。

(V)(7)數據的存儲結構是數據的邏輯結構的存儲映像。

(V)(8)數據的物理結構是指數據在計算機內實際的存儲形式。

(X)(9)數據的邏輯結構是依賴于計算機的。

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

二.填空題

(1)數據有邏輯結構和存儲結構兩種結構。

(2)數據邏輯結構除了集合以外，還包括：線性結構、樹形結構和圖形結構。

(3)數據結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構。

(4)樹形結構和圖形結構合稱為非線性結構。

(5)在樹形結構中，除了樹根結點以外，其余每個結點只有1個前趨結點。

(6)在圖形結構中，每個結點的前趨結點數和后續(xù)結點數可以任意多個。

(7)數據的存儲結構又叫物理結構。

(8)數據的存儲結構形式包括：順序存儲、鏈式存儲、索引存儲和散列存儲。

(9)線性結構中的元素之間存在一對一的關系。

(10)樹形結構結構中的元素之間存在?對多的關系,

(II)圖形結構的元素之間存在多對多的關系。

(12)數據結構主要研究數據的邏輯結構、存儲結構和算法(或運算)三個方面的

內容。

(13)數據結構被定義為(D,R),其中D是數據的有限集合，R是D上的關系的有

限集合。

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

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

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

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

的函數。

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

(nlog2n)o

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

（20）數點結構是?一門研究非數值計算的程序設計問題中計算機的操作對象，以及

它們之間的關系和運算的學科。

（1）數據結構通常是研究數據的（A）及它們之間的相互聯(lián)系。

A.存儲結構和邏輯結構B.存儲和抽象C.聯(lián)系和抽象D.聯(lián)系與邏輯

（2）在邏輯上可以把數據結構分成：（C）。

A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構

C.線性結構和非線性結構D.內部結構和外部結構

（3）數據在計算機存儲器內表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為

（C

A.存儲結構B.邏輯結構C.順序存儲結構D.鏈式存儲結

構

（4）非線性結構中的每個結點（D）。

A.無直接前趨結點

B.無直接后繼結點

C.只有一個直接前趨結點和一個直接后繼結點

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

（5）鏈式存儲的存儲結構所占存儲空間（A）。

A.分兩部分，一部分存放結點的值，另一部分存放表示結點間關系的指針

B.只有一部分，存放結點的值

C.只有一部分，存儲表示結點間關系的指針

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

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

A.現實性B.難度C.時間復雜性D.效率

（7）數據的基本單位是（B）0

A.數據結構B.數據元素C.數據項D.文件

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

存儲結構稱為（A）結構。

A.順序存儲B.鏈式存儲C.索引存儲D.散列存儲

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

存儲方式。

A.順序B.鏈式C.索引D.散列

（10）以下任何兩個結點之間都沒有邏輯關系的是（D）。

A.圖形結構B.線性結構C.樹形結構D.集合

（11）在數據結構中，與所使用的計算機無關的是（C）。

A.物理結構B.存儲結構C.邏輯結構D.邏輯和存

儲結構

（12）下列四種基本邏輯結構中，數據元素之間關系最弱的是（A）。

A.集合B.線性結構C.樹形結構D.圖形結構

（13）與數據元素本身的形式、內容、相對位置、個數無關的是數據的（A）。

A.邏輯結構B.存儲結構C.邏輯實現D.存儲實現

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

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

A.順序B.鏈式C.索引D.散列

（15）算法能正確的實現預定功能的特性稱為算法的（A）。

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

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

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

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

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

（18）下列算法的時間復雜度是（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.空間復雜性和時間復雜性B,正確性和簡明性

C.可讀性和文檔性D.數據復雜性和程序復雜性

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

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

C.解決問題的有限運算步驟D.程序設計方法

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

(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)

五.根據二元組關系，畫出對應邏輯圖形的草圖，指出它們屬于何種數據結構。

(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>}(尖括號表示結點之間關系是有向的)

解：

屬于線性結構。

(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)}(園括號表示結點之間關系是有向的)

6

屬于圖結構

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

解：

屬于樹結構。

單元練習2

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

(X)(1)線性表的鏈式存儲結構優(yōu)于順序存儲。

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

(J)(3)在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。

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

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

的各個單元向前移動。

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

(V)(7)線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數據元素。

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

(X)(9)順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。

(><)(10)插入和刪除操作是數據結構中最基本的兩種操作，所以這兩種操作在數組中也

經常使用。

—.填空題

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

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

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

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

(5)采用順序存儲結構的線件表叫順序表。

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

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

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

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

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

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

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

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

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

個元素。

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

址存放在前驅結點的指針域中。

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

取線性表中的元素時，應采用順序存儲結構。

(16)在線性表的鏈式存儲中，元素之間的邏輯關系是通過指針決定的。

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

個指向其—后繼結點。

(18)對一個需要經常進行插入和刪除操作的線性表，采用鏈式存儲結構為宜。

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

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

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

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

來實現該操作。

三.選擇題

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

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

點

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

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

P

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

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

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

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

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

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

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

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

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

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

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

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

件是(B)?

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

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

A.便于隨機存取B.花費的存儲空間比順序表少

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

同

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

A.使單鏈表至少有一個結點B.標志表中首結點的位置

C.方便運算的實現D.說明該單鏈表是線性表的鏈式存儲

結構

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

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

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

（11）L是線性表，已知LengthList（L）的值是5,經DelList（L,2）運算后，LenglhList

（L）的值是（C）0

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

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

H|八|

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

A.LB.PC.QD.R

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

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

C.查找時間復雜度為0（n）D.查找結點的次數約為n

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

（C）。

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

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

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

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

A.基地址B.結點大小C.向量大小D.基地址和結點大小

（17）在雙鏈表中做插入運算的時間復雜度為（A）0

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

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

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

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

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

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

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

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

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

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

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

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

ListNode*Demol(LinkListL,ListNode*p)

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

ListNode*q=L->next;

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

q=q->next;

if(q)

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

{〃p,*q是鏈表中的兩個結點

DataTypetemp;

解：temp=p->data;

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

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

)

五.程序填空

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

表中所有大于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)在帶頭結點head的單鏈表的結點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?”不存在結點a!”；

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

p?>next=s;

)

)

六.算法設計題

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

地址為PO

解：

voidShow(ListNode*P)

{ListNode*t=P;

do

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

t=t->rear;

)

while(t!=P);

)

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

算法。

解：

voiddelete(ListNode*L)

{ListNode*p=L,*q;

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

{

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

return;

}

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

q->next=p->next;

deletep;

}

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

解：

voidDel(node*head,inti,intk)

node

intj;

if(i==l)

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

(

p=head;//p指向要刪除的結點

head=head->next;

deletep;

)

else

(

p=head;

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

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

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

(

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

p->next=q->next;

deleteq;

)

)

}

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

數計算值域為x的結點個數。

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

量n中。實現本題功能的函數如下：

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,編寫一個函數將鏈表headl鏈

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

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

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

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);

單元練習3

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

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

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

(X)(3)棧一定是順序存儲的線性結構。

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

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

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

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

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

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

(V)(10)將十進制數轉換為二進制數是棧的典型應用之一。

二.填空題

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

(2)在順序棧中，當棧頂指針top=-l時，表示?？铡?/p>

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

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

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

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

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

top=p；操作。

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

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

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

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

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

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

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

(14)若內存空間充足，鏈棧可以不定義棧滿運算。

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

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

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

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

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

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

C

三.選擇題

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

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

(2)設有編號為1,2,3,4的四輛列車，順序進入一個棧結構的站臺，下列不可

能的出站順序為(D)

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

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

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

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

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

A.AB.BC.CD.D

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

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

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

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

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

LS

HABcDA

A.AB.BC.CD.D

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

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

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

(9)從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應

執(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指針所指的結點入棧，應執(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順序進S棧，執(zhí)行兩次Pop(S,x)運算后，棧頂元

素的值是(B)。

A.AB.BC.CD.I)

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

A.AB.BC.CD.D

(13)經過下列棧的運算后，再執(zhí)行ReadTop(s)的值是(A)。

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

A.aB.bC.1D.0

(14)經過下列棧的運算后，x的值是(B)。

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

A.aB.bC.1D.0

(15)經過下列棧的運算后，x的值是(B)。

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

A.aB.bC.1D.0

(16)經過下列棧的運算后，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.誰先誰后無關緊要D.同時進行

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

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

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

A.EDCBAB.DECBAC.DCEABD.ABCDE

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

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

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

四.應用題

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

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

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

解：①1110001010

@1011001100

(2)求后綴表達式

①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-

六.算法設計題

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

(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)設計個算法，要求判別個算術表達式中的圓括號配對是否正確。

解：〃設表達式在字符數組中，使用一堆棧S來幫助判斷。

inicorrect(chara[])

(

stacks;

InitStack(s);〃調用初始化棧函數

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

if(a[i]==C)

Push(s,'(');

else

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

(

ifStackEmpty(s)〃調用判?？蘸瘮?/p>

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

else

Pop(s)；

)

if(StackEmpty(s))〃調用判?？蘸瘮?/p>

printf(“配對正確！”);〃若?？眨f明配對正確，并返回1

else

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

(3)設計一個將十進正整數轉換為十進制數的算法，并要求上機調試通過。

解：#include<stdio.h>

#include<stdlib.h>

typedefstructstacknode〃定義棧的存儲結構

(

intdata;

structstacknode*next;

}stacknode;

typedefstruct

(

stacknode*top;〃定義棧頂的指針

}linkstack;

voidConversion(intn)〃棧的應用：十——十六進制轉換

{linkstacks;

intx;

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

do

{x=n%16;〃取余數

n=n/16;〃取新的商

stacknode*p=newstacknode;〃申請新結點

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

s.top=p;

s.top->data=x;〃余數入棧

)

while(n);

printf("\n\t\t轉換后的十六進制數值為：”；

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);〃出棧一個余數，收回一個結

)

printf(M\n\n");

)

voidmain()

(

intn;

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

scanf(n%d",&n);

Conversion(n);

單元練習4

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

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

(V)(2)判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結點。

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

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

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

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

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

(X)(8)棧和隊列都是順序存儲的線性結構。

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

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

二.填空題

(1)在隊列中存取數據應遵循的原則是先進先出。

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

除運算的線性表。

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

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

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

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

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

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

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

rear

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

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

復雜度為0(n)。

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

復雜度為。(1)。

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

5o

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

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

front==(rear+1)%MAXLEN。

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

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

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

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

針所指的位置寫入新的數據。

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

(18)設循環(huán)隊列的容量為40(序號從0到39),現經過一系列的入隊和出隊運算后，有

front=ll,rear=19,則循環(huán)隊列中還有8個元素。

(L=(N+rear-front)%N=(40+19-11)%40=8)

(19)隊列Q,經過下