《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案

本文格式為Word版，下載可任意編輯——《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案-第3章棧和隊列

一、選擇題

1、對于棧，操作數(shù)據(jù)的原則是（）。

A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序

2、要求數(shù)據(jù)遵循FIFO（先進(jìn)先出）原則的數(shù)據(jù)結(jié)構(gòu)是（）。A.線性表B.鏈表C.隊列D.棧

3、若進(jìn)棧的序列為1,2,3,4，則以下哪一個不可能是一個出棧序列。A.3,2,4,1B.3,2,1,4C.4,2,3,1D.1,3,2,44、有六個元素6，5，4，3，2，1的順序進(jìn)棧，問以下哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.234156

5、設(shè)棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。

A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，6、在一個鏈隊列中，若f，r分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為()(A)f->next=c；f=s(B)r->next=s；r=s(C)s->next=r；r=s(D)s->next=f；f=s

7、一個棧的輸入序列為12345，則以下序列中不可能是棧的輸出序列的是（）。A.23415B.54132C.23145D.154328、數(shù)字1、2依次入棧，則出棧的順序可能有（）種狀況；數(shù)字1、2依次進(jìn)入隊列，則出隊列的順序可能有（）種狀況。A.1,2B.2,1C.2,2D.1,19、設(shè)一個棧的輸入序列是1，2，3，4，5，則以下序列中，是棧的合法輸出序列的是（）。A.51234B.45132C.43125D.3215410、某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b

11、順序存儲的棧和隊列中已經(jīng)各有N個結(jié)點，要刪除一個結(jié)點分別需要移動數(shù)據(jù)（）

次和（）次。

A.N/2,NB.N,N/2C.0,ND.N,012、設(shè)有三個元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），以下得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX13、一個遞歸算法必需包括（）。

A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分

1

14、如下四個選項中，那個選項是能夠正確判斷循環(huán)隊列是否排滿元素的操作（其中

MAXQSIZE表示隊列的容量）（）：A．if(Q.rear==Q.front)…

B．if(Q.rear==(Q.front+MAXQSIZE))C．if(Q.rear==(Q.front+1)%MAXQSIZE)D．if(Q.front==(Q.rear+1)%MAXQSIZE)15、假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊列中

的元素個數(shù)為（）。

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m

16、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)

從隊列中刪除一個元素，再參與兩個元素后，rear和front的值分別為多少？()A.1和5B.2和4C.4和2D.5和117、利用棧進(jìn)行十進(jìn)制數(shù)1348轉(zhuǎn)換成八進(jìn)制數(shù)，則入棧的數(shù)依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,218、最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front

19、棧和隊列的共同點是（）。

A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素D.沒有共同點

二、填空題

1、棧是___操作受限（或限定僅在表尾進(jìn)行插入和刪除操作）的線性表，其運算遵循___后進(jìn)先出____的原則。2、隊列的插入操作在_隊尾__進(jìn)行，刪除操作在隊頭___進(jìn)行，其特點是__先進(jìn)先出__。3、用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為___S×SS×S××__。4、表達(dá)式求值是___棧____應(yīng)用的一個典型例子。5、棧和隊列在本質(zhì)上都是同一種基本數(shù)據(jù)結(jié)構(gòu)的特例，這種基本的數(shù)據(jù)結(jié)構(gòu)就是線性表。6、在作進(jìn)棧運算時，應(yīng)先判別棧是否.滿，在作退棧運算時應(yīng)先判別棧是否空。當(dāng)棧中元素為n個，作進(jìn)棧運算時發(fā)生上溢，則說明該棧的最大容量為n。

2

三、簡答題

1、簡要表達(dá)循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，分析循環(huán)隊列的隊頭指針和隊尾指針與循環(huán)隊列元素之間的關(guān)系，寫出InitQueue()、QueueLength()、EnQueue()、DeQueue()等循環(huán)隊列的基本操作算法，并舉例說明循環(huán)隊列的操作函數(shù)的應(yīng)用。參考答案：

（1）隊列：是一種先進(jìn)先出(firstinfirstout，簡稱FIFO表)的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除元素。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端稱為隊頭(front)。假設(shè)隊列為q=（a1,a2,?an），則a1為隊頭元素，an為隊尾元素。

隊列的順序存儲結(jié)構(gòu)稱為順序隊列。順序隊列用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素。

由于隊列的隊頭和隊尾的位置是變化的，因而需要附設(shè)兩個指針front和rear以指示隊頭和隊尾元素在隊列中的位置。

在C語言中為了便利描述，約定：初始化創(chuàng)立空隊列時，令front=rear=0(頭尾指針相等)。每當(dāng)插入新的隊尾元素時，rear指針增1。每當(dāng)刪除隊頭元素時，front指針增1。因此，在非空隊列中，頭指針front始終指向隊頭元素，而尾指針rear始終指向隊尾元素的下一位置。循環(huán)隊列：用順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），簡單造成“假溢出〞現(xiàn)象，即隊尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊中元素個數(shù)小于隊列的長度（容量）。

循環(huán)隊列為了解決上述“假溢出〞現(xiàn)象，可采用犧牲一個存儲單元（即少用了隊列的一個元素空間）的方法解決“隊滿〞和“隊空〞的判定問題，并規(guī)定:隊空時：front==rear；隊滿時：(rear+1)%MAXQSIZE==front。

循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)

#defineMAXQSIZE100//最大隊列長度typedefstruct{

QElemType*base;//指向初始化的動態(tài)分派存儲空間

intfront;//頭指針,若隊列不空，指向隊列頭元素

intrear;//尾指針,若隊列不空，指向隊列尾元素的下一個位置}Sueue;

（2）循環(huán)隊列的隊頭指針和隊尾指針與循環(huán)隊列元素之間的關(guān)系見如下示意圖：

3

循環(huán)隊列為了戰(zhàn)勝“假溢出〞現(xiàn)象，少用了隊列的一個元素空間。在循環(huán)隊列中，指針和隊列元素之間的關(guān)系不變。每當(dāng)插入新的隊尾元素時，rear指針增1。每當(dāng)刪除隊頭元素時，front指針增1。并規(guī)定:

隊空時：front==rear；隊滿時：(rear+1)%MAXQSIZE==front。

（3）基本操作的算法描述

StatusInitQueue(Sueueif(!Q.base)exit(OVERFLOW);//存儲分派失敗Q.front=Q.rear=0;returnOK;}

intQueueLength(SueueQ)

{//返回隊列Q的元素個數(shù)，即隊列的長度

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}

StatusEnQueue(Sueue//隊列滿Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

4

returnOK;}

StatusDeQueue(Sueue否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;returnOK;}

注意:上述函數(shù)代碼要很好把握！

（4）循環(huán)隊列的操作函數(shù)的應(yīng)用舉例（略）

注意:上述操作要很好理解和把握,能靈活應(yīng)用！

2、若元素的進(jìn)棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？答案：

能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：

若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。

3、有字符串次序為3*-y-a/y^2,利用棧，給出將次序改為3y-*ay2^/-的操作步驟。（可用X代表掃描該字符串過程中順序取一個字符進(jìn)棧的操作，用S代表從棧中取出一個字符參與到新字符串尾的出棧操作。例如，