专升本数据结构试题解析(20)

数据结构上机实验与习题解析 亱店↘打烊oO

3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_____________。

【答案】O(m+n)

【解析】朴素的模式匹配（Brute－Force）时间复杂度是Ｏ（m*n），KMP算法有一定改进，时间复杂度达到Ｏ（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仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。

3．已知：s ＝" (xyz)＋*"，t ＝" (x＋z)*y"。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。

【答案】本题有多种解法，下面是其中的一种：

（1） s1=substr（s,3,1） /*取出子串："y"

（2） s2=substr（s,6,1） /*取出子串："+"

（3） s3=substr（s,1,5） /*取出子串：" (xyz) "

（4） s4=substr（s,7,1） /*取出子串："*"

（5） s5=replace（s3,3,1,s2）/*形成部分串：" (x+z) "

（6） s=s5/*s4/*s1 /*形成串t即" (x+z)*y"

【解析】题中所给操作的含义如下：

/*：连接函数，将两个串连接成一个串

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则为匹配失败。