算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題三（答案）

習(xí)題三

一、選擇題

1.一個(gè)棧的序列是：a,b,c,d,e,則棧的不可能輸出的序列是（C）。

A.a,b,c,d,eB.d,e,c,b,aC.d,c,e,a,bD.e,d,c,b,a

2.若一個(gè)棧的輸人序列是1,2,3,…，n,輸出序列的第一個(gè)元素是n,則第k個(gè)輸

出元素是（C）。

A.kB.n-k-1C.n-k+1D.不確定

3.判定一個(gè)棧S（最多有n個(gè)元素）為空的條件是（B）o

A.S->top1=0B.S->top==0C.S->top!=nD.S->top==n

4.判定一個(gè)棧S（最多有n個(gè)元素）為滿的條件是（D）o

A.S->top!=0B.S->top==0C.S->top!=nD.S->top==n

5.向一個(gè)棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（B）o

A.top->next=S；B.S->next=top；top=S；

C.S->next=top->next；top->next=S；D.S->next=top；top=S->next；

6.向一個(gè)帶頭結(jié)點(diǎn)、棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句

（C）o

A.top->next=S；B.S->next=top；top=S；

C.S->next=top->next：top->next=S；D.S->next=top；top=S->next；

7.判定一個(gè)隊(duì)列Q（最多有n個(gè)元素）為空的條件是（C）。

A.Q->rear-Q->front==nB.Q->rear-Q->front+1==n

C.Q->rear==Q->frontD.Q->rear+1==Q->front

8.判定一個(gè)隊(duì)列Q（最多有n個(gè)元素）為滿的條件是（A）。

A.Q->rear-Q->front==nB.Q->rear-Q->front+1==n

C.Q->rear==Q->frontD.Q->rear+1==Q->front

9.判定一個(gè)循環(huán)隊(duì)列Q（最多有n個(gè)元素）為空的條件是（A）o

A.Q->rear==Q->frontB.Q->rear==Q->front+1

C.Q->front==（Q->rear+l）%nD.Q->front==（Q->rear-1）%n

10.判定一個(gè)循環(huán)隊(duì)列Q（最多有n個(gè)元素）為滿的條件是（C）。

A.Q->rear==Q->frontB.Q->rear==Q->front+l

C.Q->front==（Q->rear+l）%nD.Q->front==（Q->rear-l）%n

11.在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)*S的

操作是（C）?

A.front=front->nextB.S->next=rear；rear=S

C.rear->next=S；rear=SD.S->next=front；front=S

12.在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，刪除一個(gè)結(jié)點(diǎn)的操

作是（A）o

A.front=front->nextB.rear=rear->next

C.rear->next=frontD.front->next=rear

13.棧與隊(duì)列都是（C）。

A.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)

C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)

14.若進(jìn)棧序列為1,2,3,4,則（C）不可能是一個(gè)出棧序列。

A.3,2,4,1B.1,2,3,4C.4,2,3,1D.4,3,2,1

15.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖

區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫人該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩

沖區(qū)應(yīng)該是一個(gè)（B）結(jié)構(gòu)。

A.堆棧B.隊(duì)列C.數(shù)組D.線性表

二、填空回

I.棧（stack）是限定在表尾一端進(jìn)行插人或刪除操作的線性表。在棧中，允許插人和

刪除操作的一端稱為棧頂,而另一端稱為棧底。不含元素的棧稱為空棧

2.在棧的運(yùn)算中，棧的插人操作稱為進(jìn)?；蛉霔５膭h除操作稱為退?；?；I1.棧。

3.根據(jù)棧的定義，卷一次進(jìn)棧的元素都在原棧頂元素之上,并成為新的棧頂元素;每

一次出棧的元素總是當(dāng)前的棧頂元素,因此最后進(jìn)棧的元素總是最先;11棧,所以棧也稱為卮

進(jìn)先出線性表,簡(jiǎn)稱為L(zhǎng)IFO表。

4.棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有順序和鏈?zhǔn)?/p>

兩種存儲(chǔ)結(jié)構(gòu)，分別稱為、順序棧和鏈棧。

5.當(dāng)棧滿的時(shí)候，再進(jìn)行人棧操作就會(huì)產(chǎn)生畫1，這種情況的溢出稱為上渣當(dāng)棧

空的時(shí)候，如果再進(jìn)行出棧操作，也會(huì)溢出,這種情況下的溢出稱為下溢。

6.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈枝，是一種一特殊的單鏈表。

7.人們?nèi)粘Ｓ?jì)算用到的表達(dá)式都被稱為中綴表達(dá)式，這是由于這種算術(shù)表達(dá)式的運(yùn)算

符被置于兩個(gè)操作數(shù)中間。

8.計(jì)算機(jī)中通常使用后綴表達(dá)式,這是一種將運(yùn)算符置于兩個(gè)操作數(shù)后面的算術(shù)表達(dá)

式。這種表達(dá)式是由波蘭科學(xué)家謝維奇提出的，因此又稱為波蘭式。

9.隊(duì)列（Queue）也是一種特殊的線性表，但它與棧不同，隊(duì)列中所有的插人均限定

在表的一端進(jìn)行，而所有的刪除則限定在表的另一端進(jìn)行。允許插人的一端稱為隊(duì)尾,允許

刪除的一端稱為隊(duì)頭.

10.隊(duì)列的特點(diǎn)是先進(jìn)先出,因此隊(duì)列又被稱為先進(jìn)先出.的線性表，或稱為FIFO表。

11.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)又稱為順序隊(duì)列,是用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列

中的元素。

12.由于隊(duì)列中的元素經(jīng)常變化，對(duì)于隊(duì)列的刪除和插人分別在隊(duì)頭和隊(duì)尾進(jìn)行，因此

需要設(shè)置兩個(gè)指針分別指向隊(duì)頭元素和隊(duì)尾元素,這兩個(gè)指針又稱為隊(duì)頭指針和隊(duì)尾指針

O

13.循環(huán)順序隊(duì)列（CircularSequenceQueue）經(jīng)常簡(jiǎn)稱為循環(huán)隊(duì)列,它是將存儲(chǔ)順序

隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的一個(gè)環(huán)，即將隊(duì)首和隊(duì)尾元素連接起來形成一個(gè)環(huán)形

表。首尾相連的狀態(tài)是通過數(shù)學(xué)上的、取模運(yùn)算來實(shí)現(xiàn)的。

14.在算法或程序中，當(dāng)一個(gè)函數(shù)直接調(diào)用自己或通過一系列語句間接調(diào)用自己的時(shí)

候，則稱這個(gè)函數(shù)為遞歸函數(shù),也稱為自調(diào)用函數(shù)。函數(shù)直接調(diào)用自己，則稱為直接遞歸調(diào)

也；當(dāng)一個(gè)函數(shù)通過另一個(gè)函數(shù)來調(diào)用自己則稱為間接遞歸調(diào)用。

15.在循環(huán)隊(duì)列中規(guī)定：當(dāng)Q->rear==Q->front的時(shí)候循環(huán)隊(duì)列為空一,當(dāng)

（Q->rear+l）%MAXSIZE=front的時(shí)候循環(huán)隊(duì)列為避。

16.用鏈表方式表示的隊(duì)列稱為鏈隊(duì)列。

17.已知棧的輸人序列為1,2,3,…，n,輸出序列為a”a2，…，an>符合a2==n

的輸出序列共有止1。

18.一個(gè)棧的輸人序列是12345,則棧的輸出序列為43512是不可能的

（填是否可能）。

19.一個(gè)棧的輸人序列是12345,則棧的輸出序列為12345是可能的（填是否可能）。

20.設(shè)sq[l..maxsize]為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，則作入棧

操作的條件是top!=maxsizeo

21.設(shè)sq[L.maxsize]為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，如果把棧

頂元素彈出并送到X中，則需執(zhí)行語句x=sq[top];tor）=top-l。

22.棧的特性是先進(jìn)后

23.對(duì)棧進(jìn)行退棧時(shí)的操作是先取出元素，后移動(dòng)棧頂指針。

24.設(shè)s[L.max]為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂位置，棧為滿的條件是

top==max。

25.設(shè)鏈棧的棧頂指針為top,則棧非空的條件是top!=nil

26.已知循環(huán)隊(duì)列用數(shù)組data[l...n]存儲(chǔ)元素值，用f,r分別作為頭尾指針，則當(dāng)前

元素個(gè)數(shù)為（n+r-f）modn。

27.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。（前一個(gè)或后一個(gè)）

28.隊(duì)列中允許進(jìn)行刪除的一端稱為隊(duì)首。

29.鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表（1..n）,尾指針指向該

單鏈表的第n_個(gè)元素。

30.設(shè)雙向鏈表鏈列為lq,lq的頭指針為Iq.Front,尾指針為Iq.Rear,則隊(duì)列為空的條

件是lq->front==lq->rear。

31.從循環(huán)隊(duì)列中刪除一個(gè)元素，其操作是先取出一個(gè)元素，后移動(dòng)棧頂指針。

32.隊(duì)列中允許進(jìn)行插入