習題三

一、選擇題

1．若將整數1，2，3，4依次進棧，則不可能得到的出棧序列是（　）。

A．1234

B．1324

C．4321

D．1423

2．元素a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是（　）。

A．3

B．4

C．5

D．6

3．設n個元素進棧序列是p1，p2，p3，…，pn，其輸出序列是1，2，3，…，n。若pn=1，則pi（1≤i≤n-1）的值是（　）。

A．n-i+1

B．n-i

C．i

D．有多種可能

4．在順序棧中，若棧頂指針top指示棧頂元素的存儲單元，且順序棧的最大容量是MaxSize，則順序棧的判空和判滿的條件分別是（　）。

A．top==0

B．top==-1

C．top==MaxSize

D．top==MaxSize-1

5．為解決計算機主機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是（　）。

A．棧

B．隊列

C．樹

D．圖

6．已知循環隊列存儲在一維數組A[0…n]中，且隊列非空時front和rear分別指向隊首元素和隊尾元素。若初始隊列為空，且要求第一個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（　）。

A．0，0

B．0，n-1

C．n-1，0

D．n-1，n-1

7．若用一個容量為6的數組來實現循環隊列，且當前rear和front的值分別為4和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（　）。

A．6和4

B．5和5

C．0和2

D．0和4

8．已知循環順序隊列的存儲空間為數組A[0…20]，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front指向隊首元素的前一個位置，rear指向隊尾元素。假設當前front和rear的值分別為8和3，則該隊列的長度為（　）。

A．5

B．6

C．16

D．17

9．設長度為n的鏈隊列采用單循環鏈表加以表示，若只設一個頭指針指向隊首元素，則入隊操作的時間復雜度為（　）。

A．O（1）

B．O（n）

C．O（log2n）

D．O（n2）

10．某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a，b，c，d，e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是（　）。

A．bacde

B．dbace

C．dbcae

D．ecbad

11．一個問題的遞歸算法求解和其相對應的非遞歸算法求解相比，（　）。

A．遞歸算法通常效率高一些

B．非遞歸算法通常效率高一些

C．兩者效率相同

D．無法比較

12．在對表達式求值時，要設立操作數棧。假設操作數棧只用兩個存儲單元，則在下列表達式求值過程中，棧不會發生溢出的是（　）。

A．A-B*（C-D）

B．（A-B）*C-D

C．（A-B*C）-D

D．（A-B）*（C-D）

二、填空題

1．棧是一種操作受限的特殊線性表，其特殊性體現在其插入和刪除操作都限制在________進行。允許插入和刪除操作的一端稱為________，而另一端稱為________。棧具有________的特點。

2．棧也有兩種存儲結構，一種是________，另一種是________。以這兩種存儲結構存儲的棧分別稱為________和________。

3．在順序棧S中，假設棧頂指針top是指示棧頂元素的下一個存儲單元在數組base中的下標，則順序棧判空的條件是________；棧頂元素的訪問形式是________。

4．在不帶表頭結點的鏈棧中，若棧頂指針top直接指向棧頂元素，則將一個新結點p入棧時修改鏈的兩個對應語句為________；________。

5．在不帶表頭結點的鏈棧中，若棧頂指針top直接指向棧頂元素，則棧頂元素出棧時的修改鏈的對應語句為________。

6．隊列也是一種操作受限的線性表，它與棧不同的是，隊列中所有的插入操作均限制在表的一端進行，而所有的刪除操作都限制在表的另一端進行，允許插入的一端稱為________，允許刪除的一端稱為________。隊列具有________的特點。

7．設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出棧的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是________。

8．循環順序隊列是將順序隊列的存儲區域看成是一個首尾相連的環，首尾相連的狀態是通過數學上的________運算來實現的。循環順序隊列的引入，目的是為了避免________。

9．在循環順序隊列Q中，若規定當Q.front==Q.rear時，循環隊列為空；當Q.front==（Q.rear+1）%MAXQSIZE時，循環隊列為滿，則入隊操作時的隊尾指針變化的相應語句是________；出隊操作時的隊首指針變化的相應語句是________。

10．無論是順序棧還是順序隊列，插入元素時必須先進行________判斷，刪除元素時必須先進行________判斷；而鏈棧或鏈隊列中，插入元素無須進行棧或隊列是否為滿的判斷，只要在刪除元素時先進行________判斷。

三、判斷題

1．消除遞歸不一定需要使用棧。

2．有n個數順序（依次）進棧，出棧的序列有種，。

3．設棧采用順序存儲，若已有i-1個元素進棧，則將第i個元素進棧時，進棧算法的時間復雜度為O（i）。

4．棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an，若ai=n（1≤i≤n），則有ai＞ai+1＞…＞an。

5．用單鏈表表示的鏈棧的棧頂在鏈表的表頭位置。

6．隊列在邏輯上是一個前端和后端既能增加又能減少的線性表。

7．循環順序隊列和循環鏈隊列都存在存儲空間溢出問題。

8．優先隊列的入隊操作一定在隊列的尾部進行。

9．雙端隊列是插入和刪除操作允許在兩端進行的隊列。

10．隊列在函數調用時必不可少，因此遞歸調用離不開隊列。

四、算法設計題

1．設計算法，要求借助一個棧把一個數組中的數據元素逆置。

2．設計算法，判斷一個字符序列是否為回文序列。所謂回文序列，就是正讀與反讀都相同的字符序列，例如：abba和abdba均是回文序列。要求只使用棧來實現。

3．設計算法，判斷一個表達式中的花括號、圓括號和方括號是否配對。

4．假設以一個數組實現兩個棧：一個棧以數組的第一個存儲單元作為棧底，另一個棧以數組的最后一個存儲單元作為棧底，這種棧稱為雙向順序棧或共享棧。試設計3個算法：一個是棧的初始化操作算法InitStack（&S，maxSize），此算法完成構造一個容量為maxSize的雙向順序空棧；一個是實現進棧操作的算法Push（&S，i，x），此算法完成將數據元素x壓入到第i（i=0或1）號棧中的操作；一個是實現出棧操作的算法Pop（&S，i），此算法完成將第i號棧的棧頂元素出棧的操作。

5．假設循環順序隊列定義為：以域變量rear和length分別指示循環隊列中隊尾元素的位置和內含元素的個數。試設計實現相應的入隊和出隊的操作算法。

6．假設采用帶頭結點的循環鏈表來表示隊列，并且只設一個指向隊尾元素的指針（不設隊首指針），試設計相應的隊列初始化、隊列清空、隊列判空、入隊和出隊的操作算法。

7．設計算法，實現雙端隊列“隊尾刪除”和“隊首插入”的操作算法，并且約定隊首指針指向隊首元素的前一位置，隊尾指針指向隊尾元素。

8．已知遞歸函數（其中DIV為整除）：

（1）寫出求F（m）的遞歸算法；

（2）寫出求F（m）的非遞歸算法。