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

时间:2025-07-11

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

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仅有一个字符的情况)的数倍,而且长串就好象是由数个短串经过连接操作得到的。

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

专升本数据结构试题解析(20).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219