【正文】 空格處將算法補充完整。 if(j=tlen) return( )。j++。amp。int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start1,j=0。兩個串相等的充分必要條件是兩個串的長度相等且 對應位置字符相同 。三、填空題求子串在主串中首次出現(xiàn)的位置的運算稱為 模式匹配 。（√ ）KMP算法的最大特點是指示主串的指針不需要回溯?！? C. ‘ingNa’ D. ‘ingamp。Nanjing’，SUBSTR(S,4,5)=（ B ）。 A. 相同 B. 不相同 C. 可能相同 D. 無法確定與線性表相比，串的插入和刪除操作的特點是（ ）。A. 順序的存儲結構 B. 鏈式存儲結構 C. 數(shù)據(jù)元素是一個字符 D. 數(shù)據(jù)元素任意設串長為n，模式串長為m，則KMP算法所需的附加空間為（ A ）。A. 連接 B. 求子串 C. 模式匹配 D. 判斷子串已知串S=’aaab’，則next數(shù)組值為（ A ）。} }對于一個棧，給出輸入項A,B,C,D，如果輸入項序列為A,B,C,D，試給出全部可能的輸出序列。}while(!isEmpty(SqStack s)){x=pop(SqStack s)。while(!isEmpty(Queue q)){x=deQueue(Queue q)。 判斷隊空答案：void QueueInvent(Queue q) { ElemType x。 元素e入隊ElemType deQueue(Queue q)。 出棧，返回棧頂元素int isEmpty(SqStack s)。 置空棧void push(SqStack s,ElemType e)。編寫算法，僅用隊列和棧的ADT函數(shù)和少量工作變量，將隊列Q的所有元素逆置。 rear =new。 newnext=rearnext。If(!new) return ERROR。答案：void EnQueue(Lnode *rear, ElemType e) { Lnode *new。 EnQueue(Q,e)。 if (!QueueEmpty(Q)){ e=DeQueue(Q)。（2）簡述算法f2的功能。}閱讀算法f2,并回答下列問題：（1）設隊列Q=（1，3，5，2，4，6）。 Qfront=(Qfront+1)%MAXSIZE。int function(SqQueue *Q,ElemType *e){ if(Qfront==Qrear) return ERROR。 printf(“%d”,e)。}while( （2） ){ Pop(S,amp。 while(N){ （1） 。 scanf(“%d”,amp。//出棧函數(shù)conversion實現(xiàn)十進制數(shù)轉換為八進制數(shù)，請將函數(shù)補充完整。//判斷?？?int Push(SqStack *S,ElemType e)。P四、程序分析填空題已知棧的基本操作函數(shù)： int InitStack(SqStack *S)。P在單鏈表中，要訪問某個結點，只要知道該結點的地址即可；因此，單鏈表是一種隨機存取結構。答案：61已知循環(huán)隊列的存儲空間大小為20，且當前隊列的頭指針和尾指針的值分別為8和3，且該隊列的當前的長度為_______。答案：(rearfront+M)%M在具有n個元素的循環(huán)隊列中，隊滿時具有 個元素。A. 邏輯結構不同 B. 存儲結構不同C. 所包含的運算個數(shù)不同 D. 限定插入和刪除的位置不同二、填空題設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應該是 。A. 鏈式存儲的線性結構 B. 鏈式存儲的非線性結構 C. 限制存取點的線性結構 D. 限制存取點的非線性結構2在一個鏈隊列中，假定front和rear分別為隊頭指針和隊尾指針，刪除一個結點的操作是（ ）。該緩沖區(qū)應該是一個（ ）結構。A. 3，2，1　 B. 2，1，3 C. 3，1，2 D. 1，3，22循環(huán)隊列用數(shù)組A[0，m1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是（ ）。A. N　 B. N+1 C. N1 D. N22隊列的刪除操作是在（ ）。A. Qfront==Qrear B. QrearQfront1==M C. Qfront+1=Qrear D. Qrear+1=Qfront設計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結構最佳。A. a B. b C. c D. d1正常情況下，刪除非空的順序存儲結構的堆棧的棧頂元素，棧頂指針top的變化是（ ）。1一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（ ）。 D. snext=front。rear=sC. rearnext=s。A. Stop==0 B. Stop!=0 C. Stop==n D. Stop!=n1在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（ ）。 A. 棧底 B. 棧頂 C. 任意位置 D. 指定位置1五節(jié)車廂以編號1，2，3，4，5順序進入鐵路調度站（棧），可以得到（ ）的編組。A. abcd+　 B. abc+*d C. abc*+d D. +*abcd1將遞歸算法轉換成對應的非遞歸算法時，通常需要使用（ ）來保存中間結果。 C. *Stop=e D. Stop=e。 B. Stop++。A. *Stop=e。A. 隊尾 B. 隊頭 C. 隊列任意位置 D. 隊頭元素后循環(huán)隊列的隊頭和隊尾指針分別為front和rear，則判斷循環(huán)隊列為空的條件是（ ）。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ ）。A. head==NULL　 B. headnext==NULL C. headnext!=NULL D. head!=NULL一個棧的輸入序列為：1,2,3,4，則棧的不可能輸出的序列是（ ）。A. Qrear==Qfront B. Qrear==Qfront+1 C. Qfront==(Qrear+1)%n D. Qfront==(Qrear1)%n設計一個判別表達式中括號是否配對的算法，采用（ ）數(shù)據(jù)結構最佳。第三章 棧和隊列一、選擇題一個棧的輸入序列為：a，b，c，d，e，則棧的不可能輸出的序列是（ ）。 } } }在帶頭結點的循環(huán)鏈表L中，結點的數(shù)據(jù)元素為整型，且按值遞增有序存放。 }else{q=p。 free(p)。 q=p。 free(p)。 (pdatay)}i++。while(!p) {if(pdatax) amp。p=head。答案：void Delete_list(Lnode *head, ElemType x, ElemType y) {Lnode *p, *q。}答案： (3,7,2,1,8) 刪除順序表中重復的元素已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。 k++。j++)。amp。i++){ for(j=0。for(i=0。 void f2(SeqList *L){ int i,j,k。 }假設線性表采用順序存儲結構，表中元素值為整型。va[i]=x。j=I。while(xva[i]) i++。 if(x=va[i])va[n]=x。答案：void Insert_sq(Sqlist va[], ElemType x) {int i, j, n。}}答案： (1) (a2, a4, …, ) (2)將循環(huán)單鏈表中偶數(shù)結點位置的元素值寫入順序表A設順序表va中的數(shù)據(jù)元數(shù)遞增有序。Adata[Alength ++]=pdata。Alength=0。閱讀以下程序段，并回答問題：（1）寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素；（2）簡要敘述該程序段的功能。 }設單鏈表的長度（數(shù)據(jù)結點數(shù)）為N，則該算法的時間主要花費在查找鏈表最后一個結點上（算法中的while循環(huán)），所以該算法的時間復雜度為O（N）。while(pnext!=NULL)p=pnext。 p=head。 } }編寫算法,將一個頭指針為head不帶頭結點的單鏈表改造為一個單向循環(huán)鏈表，并分析算法的時間復雜度。 snext=r。 p=pnext。amp。 p=r。if(rdata=pdata) {rnext=p。 while(q){r=q。 q=pnext。答案：void assending(Lnode *head) {Lnode *p,*q , *r, *s。 pnext =L2。while(qnext!=L2)q=qnext。答案：void merge(Lnode *L1, Lnode *L2) {Lnode *p,*q 。 headnext=p。 q=qnext。 pnext =NULL。 p=headnext。答案：void invent(Lnode *head) {Lnode *p,*q。 } return(n)。 while(p!=NULL) { p=pnext。 node *p。int L(head){ node * head。 return OK。 *s=qdata。 q=pnext。j++。amp。j=0。 int j。}答案：（1）Lslist[k+1] （2） LLength 函數(shù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法補充完整。 （2） LLength 。kLlength1。 if(i1||iLlength) return ERROR。}/*ListInsert*/答案：(1)snext=pnext (2)pnext=s函數(shù)ListDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。 (2) pnext=s 。 sdata=e。 } if(p==NULL||ji1) return ERROR。(ji1)){ p=pnext。 while((p!=NULL)amp。 p=L。int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s。return OK。}if(!p||ji) return ERROR。ji){ p=pnext (1) 。 while(pamp。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；p=Lnext。O鏈式存儲的線性表可以隨機存取。P順序存儲方式只能用于存儲線性結構。 P在具有頭結點的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結點（的存儲位置）。pnext=_qnext ___。答案：Lprior==Lnext==L帶頭結點的單鏈表head為空的條件是 headnext==null 。答案：qnext=pnext pnext=q線性表的邏輯結構是 線性結構 ，其所含元素的個數(shù)稱為線性表的 長度 。A. p指向頭結點　 B. p指向尾結點 C. p的直接后繼是頭結點 D. p的直接后繼是尾結點二、填空題設單鏈表的結點結構為（data,next）。 D. p=pnextnext。 B. pnext=pnextnext。 1在單鏈表中，指針p指向元素為x的結點，實現(xiàn)刪除x的后繼的語句是（ ）。 D. pnex