【文章內(nèi)容簡介】 的值分別為0，3。當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ ）。A. 1和5 B. 2和4 C. 4和2 D. 5和1隊(duì)列的插入操作是在（ ）。A. 隊(duì)尾 B. 隊(duì)頭 C. 隊(duì)列任意位置 D. 隊(duì)頭元素后循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear，則判斷循環(huán)隊(duì)列為空的條件是（ ）。A. front==rear B. front==0 C. rear==0 D. front=rear+1一個順序棧S，其棧頂指針為top，則將元素e入棧的操作是（ ）。A. *Stop=e。Stop++。 B. Stop++。*Stop=e。 C. *Stop=e D. Stop=e。表達(dá)式a*(b+c)d的后綴表達(dá)式是（ ）。A. abcd+　 B. abc+*d C. abc*+d D. +*abcd1將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時(shí)，通常需要使用（ ）來保存中間結(jié)果。A. 隊(duì)列 B. 棧 C. 鏈表 D. 樹1棧的插入和刪除操作在（ ）。 A. 棧底 B. 棧頂 C. 任意位置 D. 指定位置1五節(jié)車廂以編號1，2，3，4，5順序進(jìn)入鐵路調(diào)度站（棧），可以得到（ ）的編組。 A. 3，4，5，1，2 B. 2，4，1，3，5 C. 3，5，4，2，1 D. 1，3，5，2，41判定一個順序棧S（?？臻g大小為n）為空的條件是（ ）。A. Stop==0 B. Stop!=0 C. Stop==n D. Stop!=n1在一個鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點(diǎn)s的操作為（ ）。A. front=frontnext B. snext=rear。rear=sC. rearnext=s。rear=s。 D. snext=front。front=s。1一個隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的出隊(duì)序列是（ ）。 A. 1，2，3，4　 B. 4，3，2，1 C. 1，4，3，2 D. 3，4，1，21依次在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì)頭元素是（ ）。A. a B. b C. c D. d1正常情況下，刪除非空的順序存儲結(jié)構(gòu)的堆棧的棧頂元素，棧頂指針top的變化是（ ）。A. top不變 B. top=0 C. top=top+1 D. top=top11判斷一個循環(huán)隊(duì)列Q（空間大小為M）為空的條件是（ ）。A. Qfront==Qrear B. QrearQfront1==M C. Qfront+1=Qrear D. Qrear+1=Qfront設(shè)計(jì)一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A. 線性表的順序存儲結(jié)構(gòu) B. 隊(duì)列 C. 棧 D. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2當(dāng)用大小為N的數(shù)組存儲順序循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為（ ）。A. N　 B. N+1 C. N1 D. N22隊(duì)列的刪除操作是在（ ）。A. 隊(duì)首　 B. 隊(duì)尾 C. 隊(duì)前 D. 隊(duì)后2若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能是（ ）。A. 3，2，1　 B. 2，1，3 C. 3，1，2 D. 1，3，22循環(huán)隊(duì)列用數(shù)組A[0，m1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個數(shù)是（ ）。 A. (rearfront+m)%m B. rearfront+1 C. rearfront1 D. rearfront2在解決計(jì)算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A. 堆棧 B. 隊(duì)列 C. 數(shù)組 D. 線性表2棧和隊(duì)列都是（ ）。A. 鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu) C. 限制存取點(diǎn)的線性結(jié)構(gòu) D. 限制存取點(diǎn)的非線性結(jié)構(gòu)2在一個鏈隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，刪除一個結(jié)點(diǎn)的操作是（ ）。A. front=frontnext B. rear= rearnext C. rearnext=front D. frontnext=rear2隊(duì)和棧的主要區(qū)別是（ ）。A. 邏輯結(jié)構(gòu)不同 B. 存儲結(jié)構(gòu)不同C. 所包含的運(yùn)算個數(shù)不同 D. 限定插入和刪除的位置不同二、填空題設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進(jìn)入隊(duì)列Q，若6個元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應(yīng)該是 。答案：3一個循環(huán)隊(duì)列Q的存儲空間大小為M,其隊(duì)頭和隊(duì)尾指針分別為front和rear，則循環(huán)隊(duì)列中元素的個數(shù)為： 。答案：(rearfront+M)%M在具有n個元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有 個元素。答案：n1設(shè)循環(huán)隊(duì)列的容量為70，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)操作后，front為20，rear為11，則隊(duì)列中元素的個數(shù)為 。答案：61已知循環(huán)隊(duì)列的存儲空間大小為20，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，且該隊(duì)列的當(dāng)前的長度為_______。三、判斷題棧和隊(duì)列都是受限的線性結(jié)構(gòu)。P在單鏈表中，要訪問某個結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。O以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。P四、程序分析填空題已知棧的基本操作函數(shù)： int InitStack(SqStack *S)。 //構(gòu)造空棧 int StackEmpty(SqStack *S)。//判斷?？?int Push(SqStack *S,ElemType e)。//入棧 int Pop(SqStack *S,ElemType *e)。//出棧函數(shù)conversion實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，請將函數(shù)補(bǔ)充完整。void conversion(){ InitStack(S)。 scanf(“%d”,amp。N)。 while(N){ （1） 。 N=N/8。}while( （2） ){ Pop(S,amp。e)。 printf(“%d”,e)。}}//conversion答案：（1）Push(S,N%8) （2）!StackEmpty(S)寫出算法的功能。int function(SqQueue *Q,ElemType *e){ if(Qfront==Qrear) return ERROR。 *e=Qbase[Qfront]。 Qfront=(Qfront+1)%MAXSIZE。 return OK。}閱讀算法f2,并回答下列問題：（1）設(shè)隊(duì)列Q=（1，3，5，2，4，6）。寫出執(zhí)行算法f2后的隊(duì)列Q。（2）簡述算法f2的功能。void f2(Queue *Q){ DataType e。 if (!QueueEmpty(Q)){ e=DeQueue(Q)。 f2(Q)。 EnQueue(Q,e)。 }}答案：（1）6,4,2,5,3,1 （2）將隊(duì)列倒置五、綜合題假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，請寫出相應(yīng)的入隊(duì)列算法（用函數(shù)實(shí)現(xiàn)）。答案：void EnQueue(Lnode *rear, ElemType e) { Lnode *new。 New=(Lnode *)malloc(sizeof(Lnode))。If(!new) return ERROR。newdata=e。 newnext=rearnext。 rearnext=new。 rear =new。 }已知Q是一個非空隊(duì)列，S是一個空棧。編寫算法，僅用隊(duì)列和棧的ADT函數(shù)和少量工作變量，將隊(duì)列Q的所有元素逆置。棧的ADT函數(shù)有：void makeEmpty(SqStack s)。 置空棧void push(SqStack s,ElemType e)。 元素e入棧ElemType pop(SqStack s)。 出棧，返回棧頂元素int isEmpty(SqStack s)。 判斷棧空隊(duì)列的ADT函數(shù)有：void enQueue(Queue q,ElemType e)。 元素e入隊(duì)ElemType deQueue(Queue q)。 出隊(duì)，返回隊(duì)頭元素int isEmpty(Queue q)。 判斷隊(duì)空答案：void QueueInvent(Queue q) { ElemType x。 makeEmpty(SqStack s)。while(!isEmpty(Queue q)){x=deQueue(Queue q)。push(SqStack s, ElemTypex)。}while(!isEmpty(SqStack s)){x=pop(SqStack s)。 enQueue(Queue q, ElemType x)。} }對于一個棧，給出輸入項(xiàng)A,B,C,D，如果輸入項(xiàng)序列為A,B,C,D，試給出全部可能的輸出序列。答案：出棧的可能序列： ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA第四章 串一、選擇題設(shè)有兩個串S1和S2，求串S2在S1中首次出現(xiàn)位置的運(yùn)算稱作（ C ）。A. 連接 B. 求子串 C. 模式匹配 D. 判斷子串已知串S=’aaab’，則next數(shù)組值為（ A ）。A. 0123 B. 1123 C. 1231 D. 1211串與普通的線性表相比較，它的特殊性體現(xiàn)在（ C ）。A. 順序的存儲結(jié)構(gòu) B. 鏈?zhǔn)酱鎯Y(jié)構(gòu) C. 數(shù)據(jù)元素是一個字符 D. 數(shù)據(jù)元素任意設(shè)串長為n，模式串長為m，則KMP算法所需的附加空間為（ A ）。 A. O(m) B. O(n) C. O(m*n) D. O(nlog2m)空串和空格串（ B ）。 A. 相同 B. 不相同 C. 可能相同 D. 無法確定與線性表相比，串的插入和刪除操作的特點(diǎn)是（ ）。 A. 通常以串整體作為操作對象 B. 需要更多的輔助空間 C. 算法的時(shí)間復(fù)雜度較高 D. 涉及移動的元素更多設(shè)SUBSTR(S,i,k)是求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=’Beijingamp。Nanjing’，SUBSTR(S,4,5)=（ B ）。A. ‘ijing’ B. ‘jingamp。’ C. ‘ingNa’ D. ‘ingamp。N’二、判斷題（ ）造成簡單模式匹配算法BF算法執(zhí)行效率低的原因是有回溯存在。（√ ）KMP算法的最大特點(diǎn)是指示主串的指針不需要回溯。（√ ）完全二叉樹某結(jié)點(diǎn)有右子樹，則必然有左子樹。三、填空題求子串在主串中首次出現(xiàn)的位置的運(yùn)算稱為 模式匹配 。設(shè)s=’I︺AM︺A︺TEACHER’,其長度是____。兩個串相等的充分必要條件是兩個串的長度相等且 對應(yīng)位置字符相同 。四、程序填空題函數(shù)kmp實(shí)現(xiàn)串的模式匹配，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start1,j=0。 while(islenamp。amp。jtlen) if(j==1||sdata[i]==tdata[j]){ i++。j++。 } else j= 。 if(j=tlen) return( )。 else return(1)。}函數(shù)實(shí)現(xiàn)串的模式匹配算法，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int index_bf(sqstring*s,s