数据结构习题(95页) 下载本文

int EmptyStack( DuStack *S, int i ) /*判栈空(栈号 i) */

{return (i == 0 && S->top[0] == -1|| i == 1 && S->top[1] == STACKSIZE) ; }

int FullStack( DuStack *S)

/*判栈满,满时肯定两头相遇*/ {return (S->top[0] == S-top1-1); }

void Push(DuStack *S, int i, ElemType x) /*进栈(栈号i) */ {if (FullStack( S ))

Error(\上溢、退出运行*/ if ( i == 0) S->Data[ ++ S->top0]= x; /*栈0入栈*/ if ( i == 1) S->Data[ -- S->top[1] ]= x; /* 栈1入栈*/ }

ElemType Pop(DuStack *S, int i) /*出栈(栈号i) */

{if (EmptyStack ( S,i) )

Error(\下溢退出*/ if( i==0 )

return ( S->Data[ S->top0--] );/*返回栈顶元素,指针值减1*/ if( i==1 )

return ( S->Data[ S->top[1] ++] ); /*该栈是以另一端为底的,所以指针加1*/ }

8.回文是指正读反读均相同的字符序列,如\和\均是回文,但\不是回文。设计一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈) 【算法源代码】

void sympthy(LinkList head, stack *s)/*判断长为n的字符串是否中心对称*/ { int i=1;

LinkList p=head->next;

while(i<=n/2) /* 前一半字符进栈*/ { push(s,p->data); p=p->next; }

if(n%2!==0) p=p->next;/* 奇数个结点时跳过中心结点*/ while(p&&p->data==pop(s)) p=p->next; if (p==NULL) printf(\链表中心对称\ else printf(\链表不是中心对称\} /* 算法结束*/

9.用标志位方式设计出在循环队列中进行插入和删除运算的算法。 【算法分析】

可引入标志位flag,且规定当flag=0时表示队列空,当flag=1时表示队列非空。同时设front,rear和MAXSIZE分别为队头指针,队尾指针和队列的长度。其中,队头指针指向队头元素所在的实际存储单元的前一个位置,队尾指针指向队尾元素所在的位置。从而可得队满的条件是:(rear==front)&&(flag==1) 【算法源代码】

int flag; /*设置全局变量flag作为标志位*/ enqueue(SqQueue*sq,ElemType x) {

/*将x插入循环队列sq中,sq具有队头和队尾指针*/ if((flag==1)&&(sq->rear==sq->front)) /*判断队满*/ printf(\ else

{sq->rear=(sq->rear+1)%MAXSIZE; sq->data[sq->rear]=x; } if(flag==0) flag=1;

17

}

ElemType dequeue(SqQueue*sq) /*删除队列sq的队头元素,并返回该元素*/ {ElemType x;

if(flag==0) printf(\ /*判断队空*/

else{sq->front=(sq->front+1)%MAXSIZE; x=sq->data[sq->front]; } if(sq->front==sq->rear) flag=0; return x; }

第4章 串

4.1 选择题

1.下面关于串的的叙述中,哪一个是不正确的?( ) A)串是字符的有限序列 B)空串是由空格构成的串

C)模式匹配是串的一种重要运算

D)串既可以采用顺序存储,也可以采用链式存储 【答案】B

【解析】空串是不含任何字符的串,即空串的长度是零。空格串是由空格组成的串,其长度等于空格的个数。

2.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( ) A)求子串 B)联接 C)匹配 D)求串长

【答案】C

3.若串s=\,其子串个数是( )

A)8 B)37 C)36 D)9 【答案】C

【解析】s的长度为8,长度为8的子串有1个,长度为7的子串有2个,长度为6的子串有3个,长度为5的子串有4个,?,长度为1的子串有8个,共有(1+8)*8/2=36个。

4.串的长度是指( )

A)串中所含不同字母的个数 B)串中所含字符的个数

C)串中所含不同字符的个数 D)串中所含非空格字符的个数 【答案】B

5.若串S1=\,S2=\,S3=\,S4=\,则执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))其结果为( )

A)ABC###G0123 B)ABCD###2345 C)ABC###G2345 D)ABC###G1234 【答案】D 【解析】函数concat(x,y)返回x和y的连接串,substr(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,length(s)返回串s的长度。replase(s,t,v)用v替换s中出现的所有与t相等的子串,index(s,t,i)当s中存在与t值相同的子串时,返回它在s中的第i个字符之后第一次出现的位置。 substr(S1,length(S2),length(S3))=substr(S1,4,3)= \

replase(S1,substr(S1,length(S2),length(S3)),S3)=replase(S1, \substr(S4,index(S2, '8'),length(S2))=substr(S4,2,4)= \

18

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, '8'),length(S2)))=concat(\

4.2 填空题

1.空格串是指_____________,其长度等于_____________。 【答案】(1)由空格字符(ASCII值32)所组成的字符串 (2)空格个数

2.组成串的数据元素只能是_____________。 【答案】字符

【解析】串是一种特殊的线性表,其特殊性在于串中的元素只能是字符型数据。 3.设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为_____________。

【答案】O(m+n)

【解析】朴素的模式匹配(Brute-Force)时间复杂度是O(m*n),KMP算法有一定改进,时间复杂度达到O(m+n)。

4.两个字符串相等的充分必要条件是_____________。

【答案】两串的长度相等且两串中对应位置上的字符也相等。

5.一个字符串中_____________称为该串的子串 。 【答案】任意个连续的字符组成的子序列

4.3 判断题

1.KMP算法的特点是在模式匹配时指示主串的指针不会变小( ) 【答案】√

【解析】KMP算法的改进在于:每当一趟匹配过程中出现字符比较不相等时,不需回溯主串指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。

2.串是一种数据对象和操作都特殊的线性表( ) 【答案】√

【解析】串是一种特殊的线性表,其特殊性在于串中的元素只能是字符型数据。字符型数据的操作符合字符型数据的操作规范,具有它的特殊性。

3.如果一个串中的所有字符均在另一串中出现,那么说明前者是后者的子串( ) 【答案】× 【解析】一个字符串中任意个连续的字符组成的子序列称为该串的子串,注意其中字符的连续性。

4.4 应用题

1.描述以下概念的区别:空格串与空串。

【答案】空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。

2.设S1,S2为串,请给出使S1/*S2=S2/*S1成立的所有可能的条件(/*为连接符)。 【答案】

(1)s1和s2均为空串; (2)两串之一为空串;

(3)两串串值相等(即两串长度相等且对应位置上的字符相同)。

(4)两串中一个串长是另一个串长(包括串长为1仅有一个字符的情况)的数倍,而且长串就好象是由数个短串经过连接操作得到的。

19

3.已知:s =\+*\,t =\+z)*y\。试利用联结、求子串和置换等基本运算,将 s 转化为 t 。

【答案】本题有多种解法,下面是其中的一种: (1) s1=substr(s,3,1) /*取出子串:\(2) s2=substr(s,6,1) /*取出子串:\

(3) s3=substr(s,1,5) /*取出子串:\ (4) s4=substr(s,7,1) /*取出子串:\

(5) s5=replace(s3,3,1,s2)/*形成部分串:\

(6) s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下: /*:连接函数,将两个串连接成一个串 substr(s,i,j):取子串函数,从串s的第i个字符开始,取连续j个字符形成子串 replace(s1,i,j,s2):置换函数,用s2串替换s1串中从第i个字符开始的连续j个字符

4.4 应用题

1.描述以下概念的区别:空格串与空串。

【答案】空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。

2.设S1,S2为串,请给出使S1/*S2=S2/*S1成立的所有可能的条件(/*为连接符)。 【答案】

(1)s1和s2均为空串; (2)两串之一为空串;

(3)两串串值相等(即两串长度相等且对应位置上的字符相同)。

(4)两串中一个串长是另一个串长(包括串长为1仅有一个字符的情况)的数倍,而且长串就好象是由数个短串经过连接操作得到的。 3.已知:s =\+*\,t =\+z)*y\。试利用联结、求子串和置换等基本运算,将 s 转化为 t 。

【答案】本题有多种解法,下面是其中的一种: (1) s1=substr(s,3,1) /*取出子串:\(2) s2=substr(s,6,1) /*取出子串:\

(3) s3=substr(s,1,5) /*取出子串:\ (4) s4=substr(s,7,1) /*取出子串:\

(5) s5=replace(s3,3,1,s2)/*形成部分串:\

(6) s=s5/*s4/*s1 /*形成串t即\【解析】题中所给操作的含义如下: /*:连接函数,将两个串连接成一个串 substr(s,i,j):取子串函数,从串s的第i个字符开始,取连续j个字符形成子串 replace(s1,i,j,s2):置换函数,用s2串替换s1串中从第i个字符开始的连续j个字符

4.5 算法设计题

1.设s、t为两个字符串,分别放在两个一维数组中,m、n分别为其长度,判断t是否为s的子串。如果是,输出子串所在位置(第一个字符),否则输出0。 【算法分析】

判断字符串t是否是字符串s的子串,称为串的模式匹配,其基本思想是对串s和t各设一个指针i和j,i的值域是0..m-n,j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始,若s0==t0,则i和j指针增加1,若在某个位置si!=tj,则主串指针i回溯到i=i-j+1,j仍从0开始,进行下一轮的比较,直到匹配成功(j>n-1),返回子串在主串的位置(i-j)。否则,当i>m-n则为匹配失败。

20