數(shù)據(jù)結(jié)構(gòu)練習(xí) 第三章 棧和隊列

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)第三章 棧和隊列一、選擇題1棧和隊列的共同特點(diǎn)是( )。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒有共同點(diǎn)2向順序棧中壓入新元素時，應(yīng)當(dāng)（ ）。A先移動棧頂指針，再存入元素 B先存入元素，再移動棧頂指針C先后次序無關(guān)緊要 D同時進(jìn)行3允許對隊列進(jìn)行的操作有( )。A. 對隊列中的元素排序 B. 取出最近進(jìn)隊的元素C. 在隊頭元素之前插入元素 D. 刪除隊頭元素4用鏈接方式存儲的隊列，在進(jìn)行插入運(yùn)算時( ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改5設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（ ）。A. 必須

2、判別棧是否為滿B. 必須判別棧是否為空C. 判別棧元素的類型 D.對棧不作任何判別6設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔槪羔樧兞縮指向?qū)⒁腙犃械慕Y(jié)點(diǎn)X，則入隊列的操作序列為（ ）。A.front->next=s；front=s；B. s->next=rear；rear=s；C. rear->next=s；rear=s；D. s->next=front；front=s；7設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ ）。A.top=top+1;B. top=top-1;C. top->next=

3、top; D. top=top->next;8隊列是一種（ ）的線性表。A. 先進(jìn)先出B. 先進(jìn)后出C. 只能插入D. 只能刪除9設(shè)輸入序列1、2、3、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。A. n-i B. n-1-i C. n+l -i D.不能確定10設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。A. 5，3，4，6，1，2B. 3，2，5，6，4，1C. 3，1，2，5，4，6 D. 1，5，4，6，2，311隊列的刪除操作是在（ ）進(jìn)行。A隊首 B隊尾 C隊前 D隊后12當(dāng)利用大小為N 的數(shù)組順序存儲

4、一個棧時，假定用top = = N表示?？?，則退棧時，用（ ）語句修改top指針。Atop+; Btop=0; Ctop-; Dtop=N;13隊列的插入操作是在（ ）進(jìn)行。A隊首 B隊尾 C隊前 D隊后14若已有一個棧，輸入序列為A，B，C，D，E，那么下面哪種序列不可能得到？（ ）AABCDE BEDCBA CBAEDC DECDBA(d) 注意: 入棧和出棧操作可以交替進(jìn)行，因此就可能有多種輸出序列了。15棧和隊列共同具有的特點(diǎn)是（）A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)進(jìn)行操作運(yùn)算 D.既能先進(jìn)先出，也能先進(jìn)后出16若用一個有6個單元的數(shù)組來實(shí)現(xiàn)循環(huán)隊列，rear和front

5、的初值分別為0和3。則從隊列中刪除一個元素，再添加兩個元素后，rear和front的值分別為（）A.1和5 B.2和4C.4和2 D.5和117一個棧的入棧序列是a，b，c，d，e，則棧的輸出序列不可能是( )A. dceab B. decbaC. edcba D. abcde18元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應(yīng)修改為( )A. top=topB. top=n-1 C. top=top-1D. top=top+119設(shè)有一個棧，按A、B、C、D的順序進(jìn)棧，則可能為出棧序列的是( )A.DCBA B.CDAB C

6、.DBAC D.DCAB20在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當(dāng)做出棧處理時，top變化為( )A.top+ B.top- C.top不變 D.top=021. 關(guān)于棧和隊列的說法中正確的是（ ）A棧和隊列都是線性結(jié)構(gòu)B.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)C.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)D.棧和隊列都不是線性結(jié)構(gòu)22. 設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（ ）Aa，b，c，dB.a，b，d，cC.d，c，b，a D.c，d，a，b 23. 在具有m個單元的循環(huán)隊列中，隊頭指針為front

7、，隊尾指針為rear，則隊滿的條件是（ ）Afront=rearB.(front+1)%m=rearC.rear+1=front D.(rear+1)%m=front24. 循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為( D)。A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)25. 順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為（）A.s.elemtop=e；B.s.elemtop+1=e；s.top=s.top+1

8、； s.top=s.top+1；C.s.top=s.top+1；D.s.top=s.top+1；s.elemtop+1=e； s.elemtop=e；26. 循環(huán)隊列sq中，用數(shù)組elem0··25存放數(shù)據(jù)元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾元素的當(dāng)前位置，設(shè)當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊列中的元素個數(shù)為（）A.8 B.16 C.17 D.1827. 有關(guān)棧的描述，正確的是（）A.棧是一種先進(jìn)先出的特殊的線性表B.只能從棧頂執(zhí)行插入、刪除操作C.只能從棧頂執(zhí)行插入、棧底執(zhí)行刪除D.棧頂和棧底均可執(zhí)行插入、刪除操作

9、28. 設(shè)順序循環(huán)隊列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（ ）。A. R-F B. F-R C. (R-F+M)M D. (F-R+M)M29. 設(shè)一數(shù)列的輸入順序?yàn)?,2,3,4,5,6，通過棧操作不可能排成的輸出序列為（ ）。A3,2,5,6,4,1 B1,5,4,6,2,3C2,4,3,5,1,6 D4,5,3,6,2,130. 設(shè)有一個棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E，則下列（ ）是不可能的出棧序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D

10、,C,B,A31在具有N個單元的順序存儲循環(huán)隊列中，假定front和rear分別為對頭指針和對尾指針，則判斷對滿的條件為（ ）。Afront= rear B(rear+1)%MAXSIZE=frontCfront-rear=1 Drear%MAXSIZE=front32一個元素進(jìn)入隊列的時間復(fù)雜度是（ ）。 AO(1) BO(n) CO(n2) DO(log2n)33若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）種情況。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，234假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是（ ）。A.front=N

11、ULL B.front!=NULL C.rear!=NULL D.front=rear35若讓元素a，b，c依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）種情況。Acba Bbac Ccab Dacb36在一個鏈隊列中，假定front和rear分別為隊頭和隊尾指針，則插入*s結(jié)點(diǎn)的操作應(yīng)執(zhí)行（ ）。Afront->next=s; front=s; Bs->next=rear; rear=s;C rear->next=s; rear=s; Ds->next=front; front=s;37棧的插入與刪除操作在（ ）進(jìn)行。A.棧頂 B.棧底 C.任意位置 D.指定位置38當(dāng)利用大小

12、為N的一維數(shù)組順序存儲一個棧時，假定用top=1表示?？眨瑒t向這個棧插入一個元素時，首先應(yīng)執(zhí)行（ ）語句修改top指針。 Atop+； Btop-； Ctop=NULL ； Dtop；39當(dāng)采用順序存儲方式存儲隊列時，可能出現(xiàn)存儲空間剩余，而不允許繼續(xù)入隊的情況，稱為（ ）。A溢出 B 假溢出 C隊列不能用順序存儲方式 D數(shù)組存儲空間過小40當(dāng)利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為（ ）。 A.N-2 B.N-1 C.N D.N+141從一個循環(huán)順序隊列刪除元素時，首先需要（ ）。A.前移一位隊首指針 B.后移一位隊首指針C.取出隊首指針?biāo)肝恢蒙系脑?D.取出隊尾

13、指針?biāo)肝恢蒙系脑?2循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為( )。A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)434個園盤的Hahoi塔，總的移動次數(shù)為( )。A.7 B. 8 C.15 D.1644對于棧操作數(shù)據(jù)的原則是（ ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序45有六個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2

14、 1 D. 2 3 4 1 5 646設(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， E. 3，2，1，4，47如進(jìn)棧序列1，2，3，4，5?？赡艿玫降某鰲Ｐ蛄袨? ) A1,2,5,3,4 B3,1,2,5,4 C3,2,5,4,1 D1,4,2,3,5 E都不可能48一個棧的入棧序列為A,B,C,D,E，則棧的不可能的出棧序列是( )。A. ABCDE B. EDCBA C. DECBA D.DCEAB 49function calc(x,y :integer) : integer;

15、beginif y=1 then calc :=xelse calc := calc (x,y-1)+x end;a,b均為正整數(shù)，則 calc(a,b)=( )A.a*(b-1) B. a*b C. a+b D. a+a50執(zhí)行完下列語句段后，i值為：（ ）。int f(int x) return (x>0) ? x* f(x-1):2);int i ;i =f(f(1);A2 B. 4 C. 8 D. 無限遞歸51表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd52允許對隊列進(jìn)行的操作有( )。 A. 對

16、隊列中的元素排序 B. 取出最近進(jìn)隊的元素C. 在隊頭元素之前插入元素 D. 刪除隊頭元素53用不帶頭結(jié)點(diǎn)的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點(diǎn)，隊尾指針指向隊尾結(jié)點(diǎn)，則在進(jìn)行出隊操作時( ) A僅修改隊頭指針 B.僅修改隊尾指針C隊頭，隊尾指針都可能要修改 D.隊頭，隊尾指針都要修改54對于循環(huán)隊列( )。 A. 無法判斷隊列是否為空 B. 無法判斷隊列是否為滿C. 隊列不可能滿 D. 以上說法都不是55循環(huán)隊列A0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是( )。A. (rear-front+m)%m B. rear-front+1 C. re

17、ar-front-1 D. rear-front56若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( )A. 1和 5 B. 2和4 C. 4和2 D. 5和157棧和隊的共同點(diǎn)是( )。 A. 都是先進(jìn)后出 B. 都是后進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)58設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進(jìn)隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。A 6

18、B. 4 C. 3 D. 2594個園盤的Hahoi塔，總的移動次數(shù)為( ).A.7 B.-8 C.15 D.1660和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是（ ）。A. 通常不會出現(xiàn)棧滿的情況 B. 通常不會出現(xiàn)?？盏那闆rC. 插入操作更容易實(shí)現(xiàn) D. 刪除操作更容易實(shí)現(xiàn)61執(zhí)行（ ）操作時，需要使用隊列作輔助存儲空間。A. 查找哈希(Hash)表 B. 廣度優(yōu)先搜索網(wǎng) C. 先序(根)遍歷二叉樹 D. 深度優(yōu)先搜索網(wǎng)62設(shè)有一順序棧已經(jīng)含有3個元素，如圖3.1所示元素a4正等待進(jìn)棧。下列不可能出現(xiàn)的出棧序列是（ A ）A.a3,a1,a4,a2 B. a3,a2,a4,a1 C.

19、 a3,a4,a2,a1 D. a4,a3,a2,a1 a1a2Topa3     63在一個鏈隊中，若f,r分別為隊首、隊尾指針，則插入s所指結(jié)點(diǎn)的操作為（ B）A.f->next=s;f=s; B.r->next=s;r=s;C.s->next=r;r=s; D.s->next=f;f=s;64若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊列，且當(dāng)rear和front的值分別是0和3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear 和front 的值分別是（A ）A. 2和4 B. 1和5 C. 4和2 D. 5和165有六

20、個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（ C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6二、填空題1后綴算式9 2 3 +- 10 2 / -的值為_。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_。-1，3 4 X * + 2 Y * 3 / -2下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if (stack

21、.top=m-1) printf(“overflow”);else _;_; stack.top+，stack.sstack.top=x3設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_種不同的輸出序列。54不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為_。O(1)5設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素；當(dāng)前實(shí)際存儲_個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。m-1，(R-F+M)%M6設(shè)有一個順序共享?xiàng)0：n-1，其中第一個棧項(xiàng)指針top1的初值為-1，第二個棧頂指針top2的

22、初值為n，則判斷共享?xiàng)M的條件是_。top1+1=top27棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為_表；隊列的插入和刪除運(yùn)算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為_表。FILO，F(xiàn)IFO8設(shè)某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中最多存儲_隊列元素。m-19設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_。F=R10從一個棧刪除元素時，首先取出 ，然后再前移一位 。棧頂元素、棧頂指針11后綴表達(dá)式“2 10 + 5 * 6 9

23、/”的值為 。612中綴表達(dá)示3+X*（2.4/5-6）所對應(yīng)的后綴表達(dá)示為_。3 x 2.4 5 6 *13用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342的出棧順序，相應(yīng)的S和X操作串為_SXSSXSXX_。14在循環(huán)隊列中，存儲空間為0n-1,設(shè)隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么隊滿標(biāo)志為front=(rear+1)%n，隊空標(biāo)志為_front=rear_。15對于棧只能在_棧頂位置_插入和刪除元素。16設(shè)輸入元素的順序是A，B，C，D，通過棧的變換，在輸出端可得到各種排列。若輸出序列的第一個元素為D，則輸出序列為_DCB

24、A_。17隊列中允許進(jìn)行刪除的一端為_隊頭_。18我們通常把隊列中允許插入的一端稱為_隊尾_。19隊列的原則是 。先進(jìn)先出；20順序存儲的隊列如果不采用循環(huán)方式，則會出現(xiàn) 問題。假溢出21棧的原則是 。先進(jìn)后出。22對于一個順序棧作進(jìn)棧運(yùn)算時，應(yīng)先判斷棧是否為 ，判斷的條件是 ，作出棧運(yùn)算時，應(yīng)先判斷棧是否為 ，判斷的條件是 。滿 ;top=MAXSIZE-1 ;空 ;top=-1。23在長度為Maxsize的循環(huán)隊列中，刪除一個新元素，修改front隊頭指針為 。front=(front+1)/Maxsize 24在鏈隊列中，與入隊相關(guān)的指針是 、與出隊有關(guān)的指針是 （頭指針或尾指針）。尾指

25、針 、 頭指針 25當(dāng)用長度為N的一維數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿的條件為 。top = = 026向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點(diǎn)*P果，應(yīng)執(zhí)行 和 操作。p->next = HS 、HS = p27從一個棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時，應(yīng)執(zhí)行 操作。HS = HS->next28假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結(jié)點(diǎn)的條件為 。( front = = rear ) && ( front <>NULL )29中綴算術(shù)表達(dá)式3+4/(2

26、5-(6+15)*8 所對應(yīng)的后綴算術(shù)表達(dá)式為 。3 4 25 6 15 + - / 8 * +30后綴算術(shù)表達(dá)式24 8 + 3 * 4 10 7 - * / 所對應(yīng)的中綴算術(shù)表達(dá)式為 ，值為 。(24+8)*3/(4*(10-7) 、831在一個具有n個單元的順序棧中，假定以地址高端（即下標(biāo)為n的單元）作為棧底，以top作為棧頂指針，則當(dāng)向棧中壓入一個元素時，top的變化是top=_。  top-132在作進(jìn)棧運(yùn)算時應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容量為_(3)_。為了增加內(nèi)存空間的利用率和

27、減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應(yīng)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時才產(chǎn)生溢出。(1)滿 (2)空 (3)n (4)棧底 (5)兩棧頂指針相鄰（即值之差的絕對值為1）33多個棧共存時，最好用_作為存儲結(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)34順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_。if(top!=n) data+top=x；35循環(huán)隊列的引入，目的是為了克服_。假溢出時大量移動數(shù)據(jù)元素。36設(shè)a=6, b=4, c=2, d=3, e=2, 則后綴表達(dá)式abc-/de*+的值為_。937在循環(huán)隊列中，隊列長度為n ,存儲位置從0

28、到n-1編號，以rear指示實(shí)際的隊尾元素，現(xiàn)要在此隊列中插入一個新元素，新元素的位置是（ ）。  rear=(rear+1)%n38已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是_。s=(LNode *)malloc(sizeof(Lnode)；    s->data=x;s->next=r->next；r->next=s；r=s；39區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是_和_。犧牲一個存儲單元 設(shè)標(biāo)記40已知一循環(huán)隊列的存儲空間為m.n，其中nm，隊頭和隊尾指針分別為front和rear，則此循環(huán)隊列判滿的條件是( )

29、 (rear+1)%(n-m+1)=front41設(shè)有元素序列的入棧次序?yàn)椋海╝1,a2,an）,其出棧的次序?yàn)?ap1,ap2,apn) 現(xiàn)已知pl=n,則pi=_。n-i+142用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是 _和_；若只設(shè)尾指針，則出隊和入隊的時間復(fù)雜度分別是_和_。O(1),O(n),O(1),O(1)43下面程序的功能是用遞歸算法將一個整數(shù)按逆序存放到一個字符數(shù)組中。如123存放成321。請?zhí)羁眨?include<stdio.h>void convert(char *a, int n) int i;if(i=n/10) conv

30、ert(_,i);*a=_;main()int number; char str10=”;scanf(“%d”,&number);convert(str,number); puts(str); a+1 n%1044寫出下面程序的運(yùn)行結(jié)果 program priout(input，output);procedure print(f1,f2:integer);var f3:integer;begin if fl<=f2 then begin if f2 mod fl=0 then f3:=f1+1 else f3:=f1+3；print(f3,f2-1);endwriteln(fl,

31、f2);endbegin print (4,16); end. (13 11),(12 12),(9 13),(6 14),(5 15),(4 16) 輸出每組兩個數(shù)占一行，也沒括號三、判斷題1（ ）不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。T2（ ）在循環(huán)順序隊列中插入新元素不需要判斷隊列是否滿了。× 3( )入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時不需要考慮棧溢出的情況。T 4（ ）棧是一種先進(jìn)后出的線性表。 5（ ）消除遞歸不一定需要使用棧。6（ ）棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。7（ ）設(shè)棧采用順序存貯結(jié)構(gòu)。若已有i-1

32、0;個元素進(jìn)棧，則將第i個元素進(jìn)棧時，進(jìn)棧算法的時間復(fù)雜性為O(i)。×8（ ）在鏈隊列中，即使不設(shè)置尾指針也能進(jìn)行入隊操作。9（ ）設(shè)尾指針的循環(huán)鏈表表示隊列,則入隊和出隊算法的時間復(fù)雜度均為O(1)。10（ ）棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。11（ ）隊列在程序調(diào)用時必不可少，因此遞歸離不開隊列。×12( ) ?？梢宰鳛閷?shí)現(xiàn)程序設(shè)計語言過程調(diào)用時的一種數(shù)據(jù)結(jié)構(gòu)。13（ ）棧又稱后進(jìn)先出表，隊列又稱為先進(jìn)先出表。14（ ）棧和隊列都是限制存取點(diǎn)的線性結(jié)構(gòu)。四、簡答題1簡述棧和隊列的共同點(diǎn)和不同點(diǎn)。它們與線性表有什么關(guān)系？2在一般的順序隊列中，什么是假

33、溢出？怎樣解決假溢出問題？當(dāng)隊尾到達(dá)數(shù)組最后一個單元時，就認(rèn)為隊滿，但此時數(shù)組前面可能還有空單元，因此叫假溢出。解決的辦法采用循環(huán)隊列。3簡述棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。棧和隊列都是操作受限的線性表。棧是先進(jìn)后出，操作在一端進(jìn)行；隊列是先進(jìn)先出，插入在一端，刪除在另一端進(jìn)行。4如題31圖所示，輸入元素為A，B，C，在棧的輸出端得到一個輸出序列ABC，試寫出在棧的輸入端三個可能的輸入序列。 ABC；CBA；ACB5如題32圖所示，在棧的輸入端有6個元素，順序?yàn)锳，B，C，D，E，F(xiàn)。能否在棧的輸出端得到序列DCFEBA及EDBFCA？若能，給出棧操作的過程，若不能，簡述其理由。 DC

34、FEBA可以：push(A),push(B),push(C),push(D),pop(D),pop(C),pust(E).,Push(F),pop(F),pop(E),pop(B),pop(A)EDBFCA：根據(jù)入棧順序B不能在C前面出棧。6什么是循環(huán)隊列？用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），容易造成“假溢出”現(xiàn)象，即隊尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再入隊，然而隊列中元素個數(shù)小于隊列的長度（容量）。循環(huán)隊列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊列下，通常采用“犧牲一個存儲單元”或“作標(biāo)記”的方法解決“隊滿”和“隊空”的判定

35、問題。應(yīng)該指出，除特別說明，循環(huán)隊列通常是指順序存儲結(jié)構(gòu)，而不是鏈?zhǔn)酱鎯Y(jié)構(gòu)。7有5個元素，其入棧次序?yàn)锳,B,C,D,E,在各種可能的出棧序列中，第一個出棧元素為C且第二個出棧元素為D的出棧序列有哪幾個？三個：CDEBA，CDBEA，CDBAE8簡述遞歸思想?，F(xiàn)有兩個正整數(shù)M和N，如果采用遞歸方法解決M×N運(yùn)算，試結(jié)合遞歸思想，說明其終止條件和遞歸語句是什么？遞歸是程序設(shè)計中的重要技術(shù)。利用遞歸技術(shù)編寫的程序結(jié)構(gòu)清晰、易讀、且其正確性容易證明。當(dāng)問題的定義是遞歸的、數(shù)據(jù)結(jié)構(gòu)是遞歸的和問題的解法是遞歸的時，最好利用遞歸。求解遞歸問題時，要先寫出問題求解的遞歸定義。遞歸定義由基本項(xiàng)和歸

36、納項(xiàng)組成?；卷?xiàng)描述了一個或幾個遞歸過程的終結(jié)狀態(tài)，即不需要繼續(xù)遞歸就可直接求解的狀態(tài)。歸納項(xiàng)描述了從當(dāng)前狀態(tài)向終結(jié)狀態(tài)的轉(zhuǎn)換。遞歸過程的實(shí)質(zhì)是將復(fù)雜問題分解成若干子問題，子問題與原問題具有相同特征，但是簡單了。子問題解決了，原問題迎刃而解。本題求解兩個整數(shù)M和N相乘，可以利用遞歸技術(shù)變?yōu)镸個N相加?；卷?xiàng)是M=1,歸納項(xiàng)是(M-1)個N相乘。其遞歸過程如下：long MultiToAdd(int m,int n) 用遞歸算法求m*n if(m=1) return (n); else return (MultiToAdd(m-1,n)+n); 9設(shè)輸入序列為a,b,c,d,試寫出借助一個?？傻?/p>

37、到的兩個輸出序列和兩個不能得到的輸出序列。 n個元素的排列有n!種，但借助棧結(jié)構(gòu)，n個入棧元素只可得到1/(n+1)(2n)！/（n!*n!）)種出棧序列，這個數(shù)小于n!。本題4個元素，可有14種出棧序列，abcd和dcba就是其中兩種；有10(4!-14=10)種排列得不到，其中，dabc和adbc是不可能得到的兩種。10隊列可以用循環(huán)單鏈表來實(shí)現(xiàn)，故可以只設(shè)置一個頭指針或者只設(shè)置一個尾指針。請你分析對于循環(huán)單鏈表實(shí)現(xiàn)的隊列，用哪種方案更合適。循環(huán)單鏈表若只設(shè)頭指針，則出隊操作時間復(fù)雜度是O(1)，而入隊操作時間復(fù)雜度是O(n)；若只設(shè)尾指針，則出隊和入隊操作時間復(fù)雜度都是O(1)。11試推

38、導(dǎo)出當(dāng)總盤數(shù)為n的Hanoi塔的移動次數(shù)。設(shè)Hn為n個盤子的Hanoi塔的移動次數(shù)。(假定n個盤子從鋼針X移到鋼針Z，可借助鋼針Y)則 Hn =2Hn-1+1 先將n-1個盤子從X移到Y(jié)，第n個盤子移到Z，再將那n-1個移到Z =2（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 · · · = 2k Hn-k+2k-1 +2k-2 +21 +20 =2n-1 H1+2n-2+2n-3+21+20 因?yàn)镠1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1故總盤數(shù)為n的Hanoi塔的移動次

39、數(shù)是2n-1。12  用一個數(shù)組S（設(shè)大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為SMAX，則一個棧頂指針為-1，另一個棧頂指針為MAX時，棧為空。 用C寫的入棧操作push（i，x）如下： const MAX=共享?xiàng)？赡苓_(dá)到的最大容量 typedef struct node elemtype sMAX； int top2； anode； anode ds; int pu

40、sh(int I,elemtype x)ds為容量有MAX個類型為elemtype的元素的一維數(shù)組，由兩個棧共享其空間。I的值為0或1x為類型為elemtype的元素。本算法將x壓入棧中。如壓棧成功，返回1；否則，返回0 if（ds.top1-ds.top0=1）printf（“棧滿n”）；return（0）； switch（i） case 0：ds.s+ds.topi=x；break； case 1：ds.s-ds.topi=x； return（1）；入棧成功 13用棧實(shí)現(xiàn)將中綴表達(dá)式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達(dá)式，畫出棧的變化過程圖。中綴表達(dá)式8-(3+5)*(5-6/2)

41、的后綴表達(dá)式是： 8 3 5 + 5 6 2 / - * - 棧的變化過程圖略，表達(dá)式生成過程為： 中綴表達(dá)式exp1轉(zhuǎn)為后綴表達(dá)式exp2的規(guī)則如下：設(shè)操作符棧s，初始化為空棧，壓入優(yōu)先級最低的操作符#。對中綴表達(dá)式從左向右掃描，遇操作數(shù)，直接寫入exp2；若是操作符（記為w），分如下情況處理，直至表達(dá)式exp1掃描完畢。（1）w為一般操作符（+，-，*，/等），要與棧頂操作符比較優(yōu)先級，若w優(yōu)先級高于棧頂操作符，則入棧；否則，棧頂運(yùn)算符退棧到exp2，w再與新棧頂操作符作上述比較處理，直至w入棧。（2）w為左括號（），w入棧。（3）w為右括號（），操作符棧退棧并進(jìn)入exp2，直到

42、碰到左括號為止，左括號退棧（不能進(jìn)入exp2），右括號也丟掉，達(dá)到exp2中消除括號的目的。（4）w為#，表示中綴表達(dá)式exp1結(jié)束，操作符棧退棧到exp2，直至碰到#，退棧，整個操作結(jié)束。14有字符串次序?yàn)?*-y-a/y2,利用棧，給出將次序改為3y-*ay2/-的操作步驟。（可用X代表掃描該字符串過程中順序取一個字符進(jìn)棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）XSXXXSSSXXSXXSXXSSSS15計算算術(shù)表達(dá)式的值時，可用兩個棧作輔助工具。對于給出的一個表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符

43、放入棧S2中，但每次掃描到運(yùn)算符時，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)先級比較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級不高于棧頂運(yùn)算符的優(yōu)先級時，取出棧S1的棧頂和次棧頂?shù)膬蓚€元素，以及棧S2的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入棧S1中（得到的結(jié)果依次用T1、T2等表示）。為方便比較，假設(shè)棧S2的初始棧頂為®（®運(yùn)算符的優(yōu)先級低于加、減、乘、除中任何一種運(yùn)算）。現(xiàn)假設(shè)要計算表達(dá)式： A-B*C/D+E/F。寫出棧S1和S2的變化過程。步驟棧S1棧S2輸入的算術(shù)表達(dá)式（按字符讀入）初始 ®A-B*C/D+E/F®1A®A-B*C/D+E/F®2A&#

44、174;-B*C/D+E/F®3AB®-B*C/D+E/F®4AB®-*C/D+E/F®5ABC®-*C/D+E/F®6AT1（注：T1=B*C）®-/D+E/F®7AT1D®-/D+E/F®8AT2（注：T2=T1/D）T3 （注：T3=A-T2）®-®+E/F®9T3E®+E/F®10T3E®+/F®11T3EF®+/F®12T3T4（注：T4=E/F）T5（注：T5= T3+ T4）

45、4;+®®16簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。設(shè)順序存儲隊列用一維數(shù)組qm表示，其中m為隊列中元素個數(shù)，隊列中元素在向量中的下標(biāo)從0到m-1。設(shè)隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當(dāng)front等于-1時隊空，rear等于m-1時為隊滿。由于隊列的性質(zhì)（“刪除”在隊頭而“插入”在隊尾），所以當(dāng)隊尾指針rear等于m-1時，若front不等于-1，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。其解決辦法有二，一是將隊列元素向前“平移”（占用0至rear-fr

46、ont-1）；二是將隊列看成首尾相連，即循環(huán)隊列（0.m-1）。在循環(huán)隊列下，仍定義front=rear時為隊空，而判斷隊滿則常用兩種辦法，一是用“犧牲一個單元”，即rear+1=front（準(zhǔn)確記是（rear+1）%m=front，m是隊列容量）時為隊滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時導(dǎo)致front=rear為隊空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊滿。17如果用一個循環(huán)數(shù)組q0.m-1表示隊列時，該隊列只有一個隊列頭指針front，不設(shè)隊列尾指針rear，而改置計數(shù)器count用以記錄隊列中結(jié)點(diǎn)的個數(shù)。編寫實(shí)現(xiàn)隊列的三個基本運(yùn)

47、算：判空、入隊、出隊（3分）隊列中能容納元素的最多個數(shù)是多少？（1分）typedef structElemType qm; int front,count; front是隊首指針，count是隊列中元素個數(shù)cqnode; 定義類型標(biāo)識符。(1)判空：int Empty(cqnode cq) cq是cqnode類型的變量 if(cq.count=0) return(1)；else return(0); 空隊列入隊: int EnQueue(cqnode cq，ElemType x)if(count=m)printf(“隊滿n”)；exit(0); cq.q(cq.front+count)%m=x

48、; x入隊 count+; return(1); 隊列中元素個數(shù)增加1,入隊成功出隊: int DelQueue(cqnode cq)if(count=0)printf(“隊空n”)；return(0); printf(“出隊元素”，cq.qcq.front); x=cq.qcq.front;cq.front=(cq.front+1)%m; 計算新的隊頭指針return(x)(2) 隊列中能容納的元素的個數(shù)為m。隊頭指針front指向隊頭元素。18給出循環(huán)隊列中元素個數(shù)的計算式(設(shè)隊最大長度為N,隊首指針FRONT，隊尾指針REAR) 循環(huán)隊列中元素個數(shù)為（REAR-FRONT+N）%N。其中FRONT是隊首指針，指向隊首元素的前一位置；REAR是隊尾指針，指向隊尾元素；N是隊列最大長度。19若以1、2、3、4作