算法與數(shù)據(jù)結構習題三(答案)

習題三

一、選擇題

1.一個棧的序列是：a,b,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.若一個棧的輸人序列是1,2,3,…，n,輸出序列的第一個元素是n,則第k個輸

出元素是（C）。

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

3.判定一個棧S（最多有n個元素）為空的條件是（B）。

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

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

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

5.向一個棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執(zhí)行語句（B）。

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.向一個帶頭結點、棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執(zhí)行語句

（C）。

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.判定一個隊列Q（最多有n個元素）為空的條件是（C）。

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

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

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

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

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

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

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

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

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

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

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

11.在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，則插入一個結點*S的

操作是（C）。

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

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

12.在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結點的操

作是（A）。

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

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

13.棧與隊列都是（C）o

A.鏈式存儲的線性結構B.鏈式存儲的非線性結構

C.限制存取點的線性結構D.限制存取點的非線性結構

14.若進棧序列為1,2,3,4,則（C）不可能是一個出棧序列。

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

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

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

沖區(qū)應該是一個（B）結構。

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

二、填空回

1.棧（stack）是限定在表星一端進行插入或刪除操作的線性表。在棧中，允許插人和

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

2.在棧的運算中，棧的插人操作稱為進?；蛉霔５膭h除操作稱為退?；虺鰲?。

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

一次出棧的元素總是當前的棧頂元素,因此最后進棧的元素總是最先出棧,所以棧也稱為后

進先出線性表,簡稱為LIFO表。

4.棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有順序和鏈式.

兩種存儲結構，分別稱為、順序棧.和鏈棧。

5.當棧滿的時候，再進行人棧操作就會產(chǎn)生畫i，這種情況的溢出稱為上溢一；當棧

空的時候，如果再進行出棧操作，也會逛出這種情況下的溢出稱為工灌。

6.棧的鏈式存儲結構簡稱為鏈找，是一種一特殊的單鏈表。

7.人們日常計算用到的表達式都被稱為中綴表達式，這是由于這種算術表達式的運算

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

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

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

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

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

刪除的一端稱為隊頭。

10.隊列的特點是先進先出,因此隊列又被稱為先進先出.的線性表，或稱為FIFO表。

11.隊列的順序存儲結構又稱為順序隊列,是用一組地址連續(xù)的存儲單元依次存放隊列

中的元素。

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

需要設置兩個指針分別指向隊頭兀素和隊尾元素,這兩個指針又稱為隊頭指針和隊尾指針

O

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

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

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

14.在算法或程序中，當一個函數(shù)直接調用自己或通過一系列語句間接調用自己的時

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

見；當一個函數(shù)通過另一個函數(shù)來調用自己則稱為間接遞歸調用。

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

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

16.用鏈表方式表示的隊列稱為鏈隊列。

17.已知棧的輸人序列為1.2,3,…，n,輸出序列為a“a?,…，an,符合a2==n

的輸出序列共有上1。

18.一個棧的輸人序列是12345,則棧的輸出序列為43512是丕回遞的

（填是否可能）。

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

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

操作的條件是top!-maxsizeo

21.設sq[l..maxsize]為一個順序存儲的棧，變量top指示棧頂元素的位置，如果把棧

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

22.棧的特性是先進后出。

23.對棧進行退棧時的操作是先取出元素，后移動棧頂指針。

24.設s[l..max]為一個順序存儲的棧，變量top指示棧頂位置，棧為滿的條件是

tor）==max。

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

O

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

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

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

28.隊列中允許進行刪除的一端稱為M直。

29.鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表（1一n）,尾指針指向該

單鏈表的第魚個元素。

30.設雙向鏈表鏈列為lq,lq的頭指針為Iq.Front,尾指針為Iq.Rear,則隊列為空的條

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

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

32.隊列中允許進行插入的一端稱為隊尾。

三、