数据结构 习题课2

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