1、習題課2棧1設將整數1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序加入其中，請回答下述問題：(1)若入、出棧次序為push(1),pop(),push(2),push(3),pop(),pop(),push(4),pop(),出棧的數字序列為何(這里push(i)表示進棧pop()表示出棧)？(2)能否得到出棧序列1423和1432？并說明為什么不能得到或者如何得到。(3)請分析1，2，3，4的24中排列中，哪些序列是可以通過相應的入出棧操作得到的。【答案】（1）1，3，2，4；（2）不能得到1423序列，因為要得到4必須2，3入棧，才能4入棧，然后4出棧，而這時，只能得

2、到3而不能得到2；能得到1432,依照以下入、出棧序列即可得到：push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop()2鏈棧中為何不設置頭結點？【答案】棧的操作位置就是棧頂一個位置，不設置頭結點，插入、刪除更方便。3循環隊列的優點是什么？如何判別它為空和滿？【答案】(1)循環隊列結構解決了假溢出問題； (2)采用少用一個存儲單元的策略，讓隊頭指針指向實際隊頭，隊尾指針指向隊尾元素的下一個位置。 隊空的判定條件：Q->frontQ->rear 隊滿的判定條件：Q->front（Q->rear+1）%Queuesize

3、4設計長度為n的鏈隊列用單循環鏈表表示，若只設頭指針，則入隊、出隊的時間為何？若只設尾指針呢？【答案】 若只設頭指針，則出隊的時間為O(1),入隊時需要掃描整個鏈表，所用的時間為O(n)；若只設尾指針，則入隊、出隊的時間均為O(1)。5指出下述程序段的功能是什么？void demo(Seqstack *S) int i, arr64,n0; while (!stackempty(S) arrn+pop(S); for (i0;i<n;i+) push(S,arri); /demo1【答案】程序段的功能是：利用工作數組arr 將棧S中的元素序列逆置。Seqstack S1,S2,temp;

4、Datatype x; /假設已作過初始化 while(!Stackempty(&S1) xpop(&S1);push(&temp,x);while(!Stackempty(&temp) xpop(&temp);push(&S1,x);push(&S2,x); 【答案】程序段的功能是：利用工作棧temp將棧S1復制到棧S2。(3) void demo2(Seqstack *S,int m) Seqstack T;int i; Initstack(&T);while (!stackempty(S) if (ipop(S)!m) pu

5、sh(&T,i) ;while(!Stackempty(&T) ipop(&T);push(S,i);/demo2【答案】程序段的功能是：利用工作棧t將棧S中的值為m的元素濾掉。 (4) void demo3(CirQueue *Q) int x; Seqstack S;Initstack(&S); while (!QueueEmpty(Q)xDelqueue(Q); push(&S,x) ;while(!Stackempty(&S) xpop(&S);Enqueue(Q,x);/demo3【答案】見同步練習題。CirQueue Q1,Q

6、2;int x,i,m0;/假設Q1已有內容Q2已作過初始化while (!QueueEmpty(&Q1)xDelqueue(&Q1); Enqueue(Q2,x);m+ ;for (i0;i<m:i+) xDelqueue(&Q2); Enqueue(Q1,x);Enqueue(Q2,x) ;【答案】程序段的功能是：把隊列Q1的內容復制到隊列Q2中。算法設計題6回文是指正讀和反讀均相同的字符序列，例如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文(提示：將一半字符入棧)。【答案】算法如下：int rever

7、s(char t )Seqstack *S; char ch; int k,n; Initstack(S) nstrlen(t); for(k0;k<n/2;k+) push(S,tk); kk+n%2; while (!stackempty(S) chpop(S); if (chtk) k+; else return 0; retuen 1;7利用棧的基本操作，寫一個將棧S中所有元素均出棧的算法void Clearstack(Seqstack *S)，并說明S為何要作為指針參數？【答案】算法如下：void Clearstack(Seqstack *S) while(!stackempt

8、y(S) pop(S); 說明：出棧操作為加工型操作，需要將操作后的結果帶回主調程序段，所以S要作為指針參數。8利用棧的基本操作，寫一個返回棧S中結點個數的算法int stacksize(Seqstack S)，并說明S為何不用作為指針參數？【答案】算法如下：int stacksize(Seqstack S)return S.top+1;說明：統計結點個數操作為引用型操作，棧S的內容沒有被修改，所以S不用作為指針參數。由于C語言數組下標從0開始，故結點個數為S.top+1。9設計算法判斷一個算術表達式的圓括號是否正確配對 。 （提示：凡遇（就進棧，遇）就退掉棧頂的（，表達式掃描完畢，棧應為空）

9、 int bracketsmatch(char a ) /設算術表達式以字符串形式存儲在數組中 Seqstack *S;Initstack(S);int k0;while(ak!0) if (ak() Push(S,(); else if (ak) if (Stackempty(S) return 0; else Pop(S); if (Stackempty(S) return 1;else return 0;10一個雙向棧S是在同一向量空間里實現的兩個棧，它們的棧底分別設在向量空間的兩端。試為此雙向棧設計初始化Initstack(S)、入棧push(S,x,i)和出棧pop(i)算法，其中，

10、i為0或1用于指示棧號。【答案】 #defin maxsize 100 typedef struct node datatype datamaxsize;int top1,top2;Seqstack; （1）雙向棧的初始化viod Initstack(Seqstack *S) S->top1-1;S->top2maxsize;（2）雙向棧入棧算法viod push(Seqstack *S,datatype x,int i) if (S->top1+1S->top2) erroe(overflow); else if(i0) S->top1+; S->data

11、S->top1x; else S->top2-; S->dataS->top2x; （3）雙向棧出棧算法 datatype pop(Seqstack *S,int i)if (i0) if(S->top1-1) error(downflow); else return S->dataS->top1 elseif (S->top2maxsize)error(downflow );elsereturn S->dataS->top2; 11Ackerman函數的定義如下： n+1 當m0 時 AKM(m,n) AKM(m-1,1) 當m0,

12、n0時 AKM(m-1,AKM(m,n-1) 當m0, n0時請寫出遞歸算法。 【答案】算法如下：int akm(int n,int m)if(m0) return n+1; else if (n0&&m!0) return akm(m-1,1); else return akm(m-1,akm(m,n-1);12用第二種方法，既少用一個元素空間的方法來區別循環隊列的空和滿，試為其設計置隊空、判斷隊空、判斷隊滿、出隊、入隊、取隊頭元素等六個基本操作的算法。 【答案】算法如下：#defin maxsize 100 typedef struct node datatype data

13、maxsize;int front,rear;Seqqueue; （1） 置隊空操作void Initqueue(Seqqueue *Q)Q->front0; Q->rear0;（2） 判斷隊空操作 int Queueempty(Seqqueue Q) return O.frontQ.rear ; （3）判斷隊滿操作 int Queuefull(Seqqueue Q) return O.front(Q.rear+1) %maxsize; （4）出隊操作datatype delquequ(Seqqueue *Q)datatype temp;if(O->frontQ->re

14、ar) error(downflow); tempQ->dataQ->front; Q->front(Q->front+1)%maxsize; return temp; （5）入隊操作 void enqueue(Seqqueue *Q,datatype x) if (Q->front(Q->rear+1)%maxsize) error(overflow); Q->dataQ->rearx; Q->rear(Q->rear+1)%maxsize; （6）取隊頭操作 datatype delquequ(Seqqueue *Q)dataty

15、pe temp;if(O->frontQ->rear) error(downflow); return Q->dataQ->front; 13假設以帶頭結點的循環鏈表表示隊列，并且只是一個指針指向隊尾元素結點，試編寫相應的置隊空、判斷隊空、出隊和入隊等算法。 typedef struct node datatype data;struct node *next;Linknode; typedef struct Linknode *rear; Linkqueue; （1） 置隊空操作void Initqueue(Linkqueue *Q) Q->rear(linkn

16、ode*)malloc(sizeof(Linknode)Q->rear->nextQ->reqr;（2） 判斷隊空操作 int Queueempty(Seqqueue Q) return Q.rear->nextQ.reqr ; （3）出隊操作datatype delquequ(Linkqueue *Q)datatype temp; Linknode *p;if(O->rear->nextQ->rear) error(downflow); pQ->rear->next->next; tempp->data; Q->rear

17、->next->nextp->next; if (pQ->rear) Q->rearQ->rear->next; free(p); return temp; （4）入隊操作 void enqueue(Linkqueue *Q,datatype x) Linknode *p; p(Linknode*)malloc(sizeof(Linknode); p->datax; p->nextQ->rear->next; Q->rear->nextp; Q->rearp; 14對于循環向量中的循環隊列，寫出求隊列長度的公式

18、。【答案】循環隊列求隊列長度的公式為：(Q.rear-Q.front+maxsize)%maxsize15假設循環隊列中只設rear和quelen來分別指示隊尾元素的位置和隊中元素的個數，試給出循環隊列的隊滿條件，并寫出相應的入隊和出隊算法，要求出隊時需返回隊頭元素。【答案】（1）隊滿條件：Q.quelenmaxsize（2）入隊算法： void enqueue(cirqueue *Q,datatype x) if (O->quelenmaxsize)error(overflow);Q->rear(Q->reae+1)%maxsize;Q->dataQ->rear

19、x; （3）出隊算法： datatype delqueue(cirqueue *Q) datatype x;if (O->quelen0)error(downflow);xQ->data(Q->reae+maxsize-Q->quelen+1)%maxsize;Q->quelen-;return x; 串一、選擇題1 下所述中正確的是（ ）2001A 串是一種特殊的線性表 B串的長度必須大于零C 串中元素只能是字母 D 空串就是空白串答案A2若目標串的長度為n，模式串的長度為n/3，則執行模式匹配算法時，在最壞情況下的時間復雜度是（）2001AO(n/3) BO(

20、n) CO(n2) DO(n3)分析最壞情況下模式匹配的時間復雜度為O(n-n/3+1)*n/3),由于n和n/3是同階的，所以，時間復雜度可寫為O(n2)。答案C3設有兩個串T和P，求P在T中首次出現的位置的串運算稱作（       ）2003A聯接           B求子串       C字符定位      

21、D子串定位分析該題考核點是串的基本操作。答案D4為查找某一特定單詞在文本中出現的位置，可應用的串運算是（   ） 2002  A插入        B刪除      C串聯接        D子串定位答案D5已知函數Sub(s,i,j)的功能是返回串s中從第i個字符起長度為j的子串，函數Scopy(s,t)的功能為復制串t到s。若字符串S="SCIENCESTUDY&

22、quot;，則調用函數Scopy(P,Sub(S,1,7)后得到(   )2002  AP="SCIENCE"        BP="STUDY"  CS="SCIENCE"        DS="STUDY"分析該題考核點是串的基本操作，函數Scopy(P,Sub(S,1,7)將串中子串SCIENCE復制到P中，而串S值未變。正確答案為

23、A。答案A二、填空題6在串S="structure"中，以t為首字符的子串有個。2001分析該題考核點是子串的概念。其中存在兩個長度為1的子串。答案127串S="I am a worker"的長度是_。2002分析該題考核點是串長度的概念。答案138設S1="good",S2="  ",S3="book"，則S1，S2和S3依次聯接后的結果是_。2003分析該題考核點是串的連接操作及空白串的概念。答案"good  book"三、算法閱讀題9下列算法的功能是

24、比較兩個鏈串的大小，其返回值為： -1 s1<s2 comstr(s1,s2)= 0 s1=s21 s1>s2請在空白處填入適當的內容。2001int comstr(linkstring s1,linkstring s2)/s1和s2為兩個鏈串的頭指針 while(s1&&s2) if(s1->data<s2->data) return 1;if(s1->data>s2->data) return 1; if( ) return 1; if( ) return 1; ;分析該題考核點是串的比較操作。While型循環通過指針s1、s

25、2將兩個串中字符逐一比較，若發現不等字符，則不等字符的大小就是兩個串的大小；若所比較字符均相等，直到有串被掃描完為止，退出循環。然后判斷，若某個串未被掃描完，則其值大，若兩個串同時被掃描完，則兩個串相等。答案s1=s1->next; s2=s2->next; s2(或s2!=NULL) s1(或s1!=NULL) return 0同步練習題一、 選擇題1下列有關字符串的描述，正確的是（ ）A. 字符串是0個或多個字符構成的有限序列；B. 字符串是0個或多個字母不同的有限序列；C. 字符串中最少要有一個子符；D. 字符串中不能有空格字符。2 字符串S=string中，包含的子串的個數

26、是（ ）A. 20 B. 21 C. 22 D. 233目標串為T=this is a string,模式串P=string,進行模式匹配，有效位移是（ ）（起始位置為0）。 A. 9 B. 10 C. 11 D. 124已知串S= string，T=this,執行運算strlen(strcopy(S,T)的結果是（ ） A. 4 B. 6 C. 10 D. 2 5目標串為T=this is a string,模式串P=string,進行模式匹配，所有的無效位移數是（ ） A. 6 B. 10 C. 16 D. 116下列命題正確的是（ ） A. 空串就是空白串； B. 空串不是串； C. 空

27、串是長度為0的字符串 D. 串相等指的是長度相等7若字符串采用鏈式存儲，每個字符占用一個字節，每個指針在占用四個字節，則該字符串的存儲密度為（ ） A. 50% B. 25% C. 75% D. 20%8當目標串的長度為n，模式串的長度為m時，樸素的模式匹配算法最壞情況下字符的比較次數（ ） A . n B. n*m C. (n-m+1)*m D. m9當目，模式串的長度為m時，樸素的模式匹配算法最好情況下字符的比較次數（ ） A. n B. m C. n+m D n-m10字符串是一種特殊的線性表，它與一般線性表的區別是（ ）A. 字符串是一種線性結構； B. 字符串可以進行復制操作；C.

28、字符串由字符構成并且通常作為整體參與操作；D. 字符串可以順序存儲也可以鏈式存儲。二、填空題1空串的長度為 ，空格串（空白串）的長度為 。2子串的定位運算又稱為 ，通常把主串又稱為 子串又稱為 。3成功匹配的起始位置稱為 ，匹配失敗的起始位置稱為 。 4設目標串為T=abccdadeef，模式串P=ade，則第 趟匹配成功。5已知串T=abccdadeef，P=abccyde,函數strcmp(T,P)的運算結果是 。 6串樸素的模式匹配算法在順序串和鏈串上運行，時間復雜度 。7 已知串T=abccdadeef,T中包含以b打頭的子串有 個。8通常在程序設計中，串分為 和 。9按存儲結構通常分

29、為 和 。10設s1=GOOD,s2= ,s3=BYE!，則s1,s2,和s3連接后的結果是 。三閱讀程序題1 指出程序功能int stringcmp(Hstring S,Hstring T)int i=0,tag=1; if (S.length!=T.length) tag=0; else while(i<S.length&&tag)if (S.chi=T.chi) i+;else tag=0; return tag; 2閱讀程序int stringpatindex (Hstring S,Hstring T)int i,j,k; for(i=0;i<S.lengt

30、h;i+) for(j=i,k=0;k<T.length;j+,k+) if(S.chj!=T.chk&&|Tk!=?)break;if(k>=T.length) return i;return 1; （1）指出程序功能；（2）設S中存儲there are a string ，T中存儲?r函數的返回值是什么？3閱讀程序指出程序功能void restring(Hstring S)char *p,*q,c; p=S.ch;q=S.ch+S.length-1; while(p<q) c=*p;*p=*q;*q=c;p+;q-; 四、程序設計題1 編寫算法實現兩個串的

31、連接。2 設計算法刪除主串中所有指定子串3 編寫算法判斷串是否為回文同步練習題答案一、選擇題1A 2C3C4A5B6C7D8C9B10C二、 填空題10， 包含空格的的數；2模式匹配，目標串，模式串；3有效位移，無效位移；46；50；6O(m+n); 79；8串常量，串變量；9順序串，鏈串；10GOOD BYE!三閱讀程序題1【答案】判斷兩個串是否相等，若相等返回1，否則返回0。2【答案】（1）帶通配符？的子串定位函數；（2）返回值為1。3【答案】將一個串逆置。四、程序設計題 實現兩個串的連接算法:void stringcat(Hstring S,Hstring T)char *p,*q; p

32、=S.ch+S.length; q=t.ch; while(p<S.ch+maxsize&&q<T.ch+T.length) *p+ =*q+; if(q<T.ch+maxsize) S.lengh=maxsize; else S.length=S.lengh+T.length; 刪除主串中所有指定子串算法：void delsubstring(Hstring S,Hstring T)int i=0,j,k; while(i<S.length) for(j=i,k=0;k<T.length;j+,k+) if(S.chj!=T.chk)break;i

33、f(k>=T.length) while(j<S.length) S.chj-T.length=S.chj; j+; S.length=S.length-T.length;elsei+; 3判斷串是否為回文算法：int tringcomp(Hstring S,Hstring T)char *p,*q; p=S.ch;q=S.ch+S.length-1; while(p<q&&*p=*q) p+;q-;if(p>=q) return 1;return 0;課后習題解答基礎知識題1 簡述下列每對術語的區別：空串和空白串；串常量和串變量；主串和子串；靜態分配的

34、順序串和動態分配的順序串5、目標考核模式串；有效位移和無效位移。【答案】略2假設有如下的串說明char s130=Stocktom,CA,s2=March 5,1999,s330,*p;(1) 在執行下列語句后，P的值是什么？p=strchr(s1,t); p=str(s3,9); p=strchr(s2,6);(2) 在執行下列語句后，S3的值是什么？strcpy(s3,s1); strcat(s3,); strcat(s3,s2);(3) 調用函數strcmp(s1,s2)的返回值是什么？(4) 調用函數strcmp(&s15,tom)的返回值是什么？(5) 調用函數strlen(

35、strcat(s1,s2)的返回值是什么？【答案】（1）p的值依次為字符t在串s1中的位置,字符9在串s3中的位置，字符6在串s2中的位置。（2）執行語句strcpy(s3,s1); 后，S3的值是：Stocktom,CA執行語句strcat(s3,); 后，S3的值是：Stocktom,CA,執行語句strcat(s3,s2); 后，S3的值是：Stocktom,CA,March 5,1999（3）調用函數strcmp(s1,s2)的返回值是：大于0；（4）調用函數strcmp(&s15,tom)的返回值是：大于0（5）調用函數strlen(strcat(s1,s2)的返回值是：s1

36、和s2聯接后的串長度：233 T0.n-1=abaabaabcaabaa，P0.m-1=aab。當用模式串P匹配目標串，請給出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一個位移。【答案】所有的有效位移依次為：2，5，9；算法NaiveStrMatch(T,P)返回的位移是：2算法設計題4 利用C的庫函數strlen,strcpy和strcat寫一個算法void strinsert(char *S，char *T,int i)，將串T插入到串S的第i個位置上。若i大于S的長度，則插入不執行。【答案】#include string.h#defin maxsize 256

37、void strinsert(char *S，char *T,int i)int slen; char sbufmaxsize; slen=strlen(S); if (i<0|i>slen) printf(invalid para in); else strcpy(sbuf1,S,i); strcat(sbuf1,T); strcpy(sbuf2,S+i); strcat(sbuf1,sbuf2);strcpy(S,sbuf1); printf(string S：%s,S); 5利用的庫函數strlen,strcpy和strcat寫一個算法void strdelete(char

38、*S,int i,int m)，刪去串S中從第i個字符開始的連續m個字符。若istrlen(S)，則沒有字符被刪除，若i+mstrlen(S)，。則將串S中從第i個字符開始直到末尾的字符刪去。【答案】#defin maxsize 256#include string.hvoid strdelete(char *S,int i,int m)int slen; char sbuf1maxsize,sbuf2maxsize; slen=strlen(S); if (i<0|i>=slen) printf(invalid para in); else if (i+m-1>=slen)

39、 Si=0; else strcpy(sbuf1,S,i); strcpy(sbuf2,S+i+m); strcat(sbuf1,sbuf2); strcpy(S,sbuf1); printf(string S：%s,S); 6 Hstring 為存儲表示，寫一個求子串的算法。【答案】#defin maxsize 256#include string.hvoid substr(Hstring S,Hstring *T,int i,int len)int k; if (i<0|i+len-1>=S.length) printf(invalid para in); elseT->

40、ch=(char *)malloc(maxsize*sizeof(char); for(k=0;k<m;k+)T->chk=S.chi+k; T->length=len; 7一個文本串可用事先給定的字符映像表進行加密。例如，設字符映像表為： abcdefghijklmnopqrstuvwxyz ngzqtcobmuhelkpdawxfyivrsj則字符串encrypt被加密為tkzwsdf。試寫一算法將輸入的文本串進行加密后輸出；另寫一算法將輸入的已加密的文本串進行解密后輸出。【答案】 char key =ngzqtcobmuhelkpdawxfyivrsj； void f1(char *s) int j=0; while(sj!=0)if (sj>=a&&sj<=z) sj=keysj-a； j+; void f2(char *s) int j=0,k; whi