數(shù)據(jù)結(jié)構(gòu) 習(xí)題課2

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

2、到3而不能得到2；能得到1432,依照以下入、出棧序列即可得到：push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop()2鏈棧中為何不設(shè)置頭結(jié)點(diǎn)？【答案】棧的操作位置就是棧頂一個(gè)位置，不設(shè)置頭結(jié)點(diǎn)，插入、刪除更方便。3循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它為空和滿(mǎn)？【答案】(1)循環(huán)隊(duì)列結(jié)構(gòu)解決了假溢出問(wèn)題； (2)采用少用一個(gè)存儲(chǔ)單元的策略，讓隊(duì)頭指針指向?qū)嶋H隊(duì)頭，隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置。 隊(duì)空的判定條件：Q-frontQ-rear 隊(duì)滿(mǎn)的判定條件：Q-front（Q-rear+1）%Queuesize4設(shè)計(jì)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈

3、表表示，若只設(shè)頭指針，則入隊(duì)、出隊(duì)的時(shí)間為何？若只設(shè)尾指針呢？【答案】 若只設(shè)頭指針，則出隊(duì)的時(shí)間為O(1),入隊(duì)時(shí)需要掃描整個(gè)鏈表，所用的時(shí)間為O(n)；若只設(shè)尾指針，則入隊(duì)、出隊(duì)的時(shí)間均為O(1)。5指出下述程序段的功能是什么？void demo(Seqstack *S) int i, arr64,n0; while (!stackempty(S) arrn+pop(S); for (i0;in;i+) push(S,arri); /demo1【答案】程序段的功能是：利用工作數(shù)組arr 將棧S中的元素序列逆置。Seqstack S1,S2,temp;Datatype x; /假設(shè)已作過(guò)初始

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

5、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【答案】見(jiàn)同步練習(xí)題。CirQueue Q1,Q2;int x,i,m0;/假設(shè)Q1已有內(nèi)容Q2已作過(guò)初始化while (!QueueEmpty(&Q1)xDelqueue(&Q1); Enqueue(Q2,

6、x);m+ ;for (i0;im:i+) xDelqueue(&Q2); Enqueue(Q1,x);Enqueue(Q2,x) ;【答案】程序段的功能是：把隊(duì)列Q1的內(nèi)容復(fù)制到隊(duì)列Q2中。算法設(shè)計(jì)題6回文是指正讀和反讀均相同的字符序列，例如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文(提示：將一半字符入棧)?！敬鸢浮克惴ㄈ缦拢篿nt revers(char t )Seqstack *S; char ch; int k,n; Initstack(S) nstrlen(t); for(k0;ktop1-1;S-top2maxsize;（

7、2）雙向棧入棧算法viod push(Seqstack *S,datatype x,int i) if (S-top1+1S-top2) erroe(overflow); else if(i0) S-top1+; S-dataS-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 );elser

8、eturn S-dataS-top2; 11Ackerman函數(shù)的定義如下： n+1 當(dāng)m0 時(shí) AKM(m,n) AKM(m-1,1) 當(dāng)m0,n0時(shí) AKM(m-1,AKM(m,n-1) 當(dāng)m0, n0時(shí)請(qǐng)寫(xiě)出遞歸算法。 【答案】算法如下：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用第二種方法，既少用一個(gè)元素空間的方法來(lái)區(qū)別循環(huán)隊(duì)列的空和滿(mǎn)，試為其設(shè)計(jì)置隊(duì)空、判斷隊(duì)空、判斷隊(duì)滿(mǎn)、出隊(duì)、入隊(duì)、取隊(duì)頭元素等六個(gè)基本操作的算

9、法。 【答案】算法如下：#defin maxsize 100 typedef struct node datatype datamaxsize;int front,rear;Seqqueue; （1） 置隊(duì)空操作void Initqueue(Seqqueue *Q)Q-front0; Q-rear0;（2） 判斷隊(duì)空操作 int Queueempty(Seqqueue Q) return O.frontQ.rear ; （3）判斷隊(duì)滿(mǎn)操作 int Queuefull(Seqqueue Q) return O.front(Q.rear+1) %maxsize; （4）出隊(duì)操作datatype d

10、elquequ(Seqqueue *Q)datatype temp;if(O-frontQ-rear) error(downflow); tempQ-dataQ-front; Q-front(Q-front+1)%maxsize; return temp; （5）入隊(duì)操作 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）取隊(duì)頭操作 datatype delquequ(Seqqueue *

11、Q)datatype temp;if(O-frontQ-rear) error(downflow); return Q-dataQ-front; 13假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只是一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)，試編寫(xiě)相應(yīng)的置隊(duì)空、判斷隊(duì)空、出隊(duì)和入隊(duì)等算法。 typedef struct node datatype data;struct node *next;Linknode; typedef struct Linknode *rear; Linkqueue; （1） 置隊(duì)空操作void Initqueue(Linkqueue *Q) Q-rear(linknode*)malloc(

12、sizeof(Linknode)Q-rear-nextQ-reqr;（2） 判斷隊(duì)空操作 int Queueempty(Seqqueue Q) return Q.rear-nextQ.reqr ; （3）出隊(duì)操作datatype delquequ(Linkqueue *Q)datatype temp; Linknode *p;if(O-rear-nextQ-rear) error(downflow); pQ-rear-next-next; tempp-data; Q-rear-next-nextp-next; if (pQ-rear) Q-rearQ-rear-next; free(p); r

13、eturn temp; （4）入隊(duì)操作 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對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫(xiě)出求隊(duì)列長(zhǎng)度的公式?！敬鸢浮垦h(huán)隊(duì)列求隊(duì)列長(zhǎng)度的公式為：(Q.rear-Q.front+maxsize)%maxsize15假設(shè)循環(huán)隊(duì)列中只設(shè)rear和quelen來(lái)分別指示隊(duì)尾元素的位置和隊(duì)中元素的個(gè)數(shù)，試給出循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件，并寫(xiě)出相應(yīng)的入隊(duì)和

14、出隊(duì)算法，要求出隊(duì)時(shí)需返回隊(duì)頭元素?！敬鸢浮浚?）隊(duì)滿(mǎn)條件：Q.quelenmaxsize（2）入隊(duì)算法： void enqueue(cirqueue *Q,datatype x) if (O-quelenmaxsize)error(overflow);Q-rear(Q-reae+1)%maxsize;Q-dataQ-rearx; （3）出隊(duì)算法： datatype delqueue(cirqueue *Q) datatype x;if (O-quelen0)error(downflow);xQ-data(Q-reae+maxsize-Q-quelen+1)%maxsize;Q-quelen-

15、;return x; 串一、選擇題1 下所述中正確的是（ ）2001A 串是一種特殊的線性表 B串的長(zhǎng)度必須大于零C 串中元素只能是字母 D 空串就是空白串答案A2若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為n/3，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（）2001AO(n/3) BO(n) CO(n2) DO(n3)分析最壞情況下模式匹配的時(shí)間復(fù)雜度為O(n-n/3+1)*n/3),由于n和n/3是同階的，所以，時(shí)間復(fù)雜度可寫(xiě)為O(n2)。答案C3設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱(chēng)作（ ）2003A聯(lián)接 B求子串 C字符定位 D子串定位分析該題考核點(diǎn)是串的基本操作。答案D4

16、為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運(yùn)算是（ ） 2002 A插入 B刪除 C串聯(lián)接 D子串定位答案D5已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長(zhǎng)度為j的子串，函數(shù)Scopy(s,t)的功能為復(fù)制串t到s。若字符串S=SCIENCESTUDY，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7)后得到( )2002 AP=SCIENCE BP=STUDY CS=SCIENCE DS=STUDY分析該題考核點(diǎn)是串的基本操作，函數(shù)Scopy(P,Sub(S,1,7)將串中子串SCIENCE復(fù)制到P中，而串S值未變。正確答案為A。答案A二、填空題6在串S=structure

17、中，以t為首字符的子串有個(gè)。2001分析該題考核點(diǎn)是子串的概念。其中存在兩個(gè)長(zhǎng)度為1的子串。答案127串S=I am a worker的長(zhǎng)度是_。2002分析該題考核點(diǎn)是串長(zhǎng)度的概念。答案138設(shè)S1=good,S2= ,S3=book，則S1，S2和S3依次聯(lián)接后的結(jié)果是_。2003分析該題考核點(diǎn)是串的連接操作及空白串的概念。答案good book三、算法閱讀題9下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為： -1 s1s2請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。2001int comstr(linkstring s1,linkstring s2)/s1和s2為兩個(gè)鏈串的頭指針 while(s1&s2)

18、 if(s1-datadata) return 1;if(s1-datas2-data) return 1; if( ) return 1; if( ) return 1; ;分析該題考核點(diǎn)是串的比較操作。While型循環(huán)通過(guò)指針s1、s2將兩個(gè)串中字符逐一比較，若發(fā)現(xiàn)不等字符，則不等字符的大小就是兩個(gè)串的大??；若所比較字符均相等，直到有串被掃描完為止，退出循環(huán)。然后判斷，若某個(gè)串未被掃描完，則其值大，若兩個(gè)串同時(shí)被掃描完，則兩個(gè)串相等。答案s1=s1-next; s2=s2-next; s2(或s2!=NULL) s1(或s1!=NULL) return 0同步練習(xí)題一、 選擇題1下列有關(guān)字

19、符串的描述，正確的是（ ）A. 字符串是0個(gè)或多個(gè)字符構(gòu)成的有限序列；B. 字符串是0個(gè)或多個(gè)字母不同的有限序列；C. 字符串中最少要有一個(gè)子符；D. 字符串中不能有空格字符。2 字符串S=string中，包含的子串的個(gè)數(shù)是（ ）A. 20 B. 21 C. 22 D. 233目標(biāo)串為T(mén)=this is a string,模式串P=string,進(jìn)行模式匹配，有效位移是（ ）（起始位置為0）。 A. 9 B. 10 C. 11 D. 124已知串S= string，T=this,執(zhí)行運(yùn)算strlen(strcopy(S,T)的結(jié)果是（ ） A. 4 B. 6 C. 10 D. 2 5目標(biāo)串為T(mén)

20、=this is a string,模式串P=string,進(jìn)行模式匹配，所有的無(wú)效位移數(shù)是（ ） A. 6 B. 10 C. 16 D. 116下列命題正確的是（ ） A. 空串就是空白串； B. 空串不是串； C. 空串是長(zhǎng)度為0的字符串 D. 串相等指的是長(zhǎng)度相等7若字符串采用鏈?zhǔn)酱鎯?chǔ)，每個(gè)字符占用一個(gè)字節(jié)，每個(gè)指針在占用四個(gè)字節(jié)，則該字符串的存儲(chǔ)密度為（ ） A. 50% B. 25% C. 75% D. 20%8當(dāng)目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為m時(shí)，樸素的模式匹配算法最壞情況下字符的比較次數(shù)（ ） A . n B. n*m C. (n-m+1)*m D. m9當(dāng)目，模式串的長(zhǎng)度為m

21、時(shí)，樸素的模式匹配算法最好情況下字符的比較次數(shù)（ ） A. n B. m C. n+m D n-m10字符串是一種特殊的線性表，它與一般線性表的區(qū)別是（ ）A. 字符串是一種線性結(jié)構(gòu)； B. 字符串可以進(jìn)行復(fù)制操作；C. 字符串由字符構(gòu)成并且通常作為整體參與操作；D. 字符串可以順序存儲(chǔ)也可以鏈?zhǔn)酱鎯?chǔ)。二、填空題1空串的長(zhǎng)度為 ，空格串（空白串）的長(zhǎng)度為 。2子串的定位運(yùn)算又稱(chēng)為 ，通常把主串又稱(chēng)為 子串又稱(chēng)為 。3成功匹配的起始位置稱(chēng)為 ，匹配失敗的起始位置稱(chēng)為 。 4設(shè)目標(biāo)串為T(mén)=abccdadeef，模式串P=ade，則第 趟匹配成功。5已知串T=abccdadeef，P=abccyde

22、,函數(shù)strcmp(T,P)的運(yùn)算結(jié)果是 。 6串樸素的模式匹配算法在順序串和鏈串上運(yùn)行，時(shí)間復(fù)雜度 。7 已知串T=abccdadeef,T中包含以b打頭的子串有 個(gè)。8通常在程序設(shè)計(jì)中，串分為 和 。9按存儲(chǔ)結(jié)構(gòu)通常分為 和 。10設(shè)s1=GOOD,s2= ,s3=BYE!，則s1,s2,和s3連接后的結(jié)果是 。三閱讀程序題1 指出程序功能int stringcmp(Hstring S,Hstring T)int i=0,tag=1; if (S.length!=T.length) tag=0; else while(iS.length&tag)if (S.chi=T.chi) i+;el

23、se tag=0; return tag; 2閱讀程序int stringpatindex (Hstring S,Hstring T)int i,j,k; for(i=0;iS.length;i+) for(j=i,k=0;k=T.length) return i;return 1; （1）指出程序功能；（2）設(shè)S中存儲(chǔ)there are a string ，T中存儲(chǔ)?r函數(shù)的返回值是什么？3閱讀程序指出程序功能void restring(Hstring S)char *p,*q,c; p=S.ch;q=S.ch+S.length-1; while(pq) c=*p;*p=*q;*q=c;p+

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

25、,Hstring T)char *p,*q; p=S.ch+S.length; q=t.ch; while(pS.ch+maxsize&qT.ch+T.length) *p+ =*q+; if(qT.ch+maxsize) S.lengh=maxsize; else S.length=S.lengh+T.length; 刪除主串中所有指定子串算法：void delsubstring(Hstring S,Hstring T)int i=0,j,k; while(iS.length) for(j=i,k=0;k=T.length) while(jS.length) S.chj-T.length=S

26、.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) return 1;return 0;課后習(xí)題解答基礎(chǔ)知識(shí)題1 簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空白串；串常量和串變量；主串和子串；靜態(tài)分配的順序串和動(dòng)態(tài)分配的順序串5、目標(biāo)考核模式串；有效位移和無(wú)效位移?！敬鸢浮柯?假設(shè)有如下的串說(shuō)明char s130=Stocktom,CA,s2=March 5,1999,s330,*

27、p;(1) 在執(zhí)行下列語(yǔ)句后，P的值是什么？p=strchr(s1,t); p=str(s3,9); p=strchr(s2,6);(2) 在執(zhí)行下列語(yǔ)句后，S3的值是什么？strcpy(s3,s1); strcat(s3,); strcat(s3,s2);(3) 調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么？(4) 調(diào)用函數(shù)strcmp(&s15,tom)的返回值是什么？(5) 調(diào)用函數(shù)strlen(strcat(s1,s2)的返回值是什么？【答案】（1）p的值依次為字符t在串s1中的位置,字符9在串s3中的位置，字符6在串s2中的位置。（2）執(zhí)行語(yǔ)句strcpy(s3,s1); 后，S

28、3的值是：Stocktom,CA執(zhí)行語(yǔ)句strcat(s3,); 后，S3的值是：Stocktom,CA,執(zhí)行語(yǔ)句strcat(s3,s2); 后，S3的值是：Stocktom,CA,March 5,1999（3）調(diào)用函數(shù)strcmp(s1,s2)的返回值是：大于0；（4）調(diào)用函數(shù)strcmp(&s15,tom)的返回值是：大于0（5）調(diào)用函數(shù)strlen(strcat(s1,s2)的返回值是：s1和s2聯(lián)接后的串長(zhǎng)度：233 T0.n-1=abaabaabcaabaa，P0.m-1=aab。當(dāng)用模式串P匹配目標(biāo)串，請(qǐng)給出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一

29、個(gè)位移?！敬鸢浮克械挠行灰埔来螢椋?，5，9；算法NaiveStrMatch(T,P)返回的位移是：2算法設(shè)計(jì)題4 利用C的庫(kù)函數(shù)strlen,strcpy和strcat寫(xiě)一個(gè)算法void strinsert(char *S，char *T,int i)，將串T插入到串S的第i個(gè)位置上。若i大于S的長(zhǎng)度，則插入不執(zhí)行?！敬鸢浮?include string.h#defin maxsize 256void strinsert(char *S，char *T,int i)int slen; char sbufmaxsize; slen=strlen(S); if (islen) printf(

30、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利用的庫(kù)函數(shù)strlen,strcpy和strcat寫(xiě)一個(gè)算法void strdelete(char *S,int i,int m)，刪去串S中從第i個(gè)字符開(kāi)始的連續(xù)m個(gè)字符。若istrlen(S)，則沒(méi)有字符被刪除，若i+mstrlen(S)，。則將串S中從第i個(gè)字符開(kāi)始直到末尾的字符刪去?！敬鸢浮?defin max

31、size 256#include string.hvoid strdelete(char *S,int i,int m)int slen; char sbuf1maxsize,sbuf2maxsize; slen=strlen(S); if (i=slen) printf(invalid para in); else if (i+m-1=slen) 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 為存

32、儲(chǔ)表示，寫(xiě)一個(gè)求子串的算法?！敬鸢浮?defin maxsize 256#include string.hvoid substr(Hstring S,Hstring *T,int i,int len)int k; if (i=S.length) printf(invalid para in); elseT-ch=(char *)malloc(maxsize*sizeof(char); for(k=0;kchk=S.chi+k; T-length=len; 7一個(gè)文本串可用事先給定的字符映像表進(jìn)行加密。例如，設(shè)字符映像表為： abcdefghijklmnopqrstuvwxyz ngzqtcob