2023年7月20日发(作者：)

圣才电子书

十万种考研考证电子书、题库视频学习平台第4章　串一、选择题1．下面关于串的叙述中，不正确的是( ）。A．串是字符的有限序列

B．空串是由空格构成的串C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储【答案】B【解析】空格构成的串称空格串。空串用φ表示。零个字符的串称为空串，空格也是一个字符，因此B项不正确。2．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。A．求子串 B．判断是否相等 C．模型匹配 D．连接【答案】C【解析】常用的串的基本操作有七种，INDEX(s,t)是其中的定位函数，这种运算就是所说的模式匹配。3．已知串S=ˊaaabˊ，其Next数组值为（ ）。A．0123 B．1123 C．123l D．1211【答案】A【解析】KMP算法的next数组建立的原则 1 / 18

圣才电子书

十万种考研考证电子书、题库视频学习平台4．若串S=ˊsoftwareˊ，其子串的数目是（ ）。A．8 B．37 C．36 D．9【答案】B【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>O），长为n的子串有l个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）／2十l=37。故选B。5．串的长度是指（ ）。A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数【答案】B【解析】串中字符的数目n称为字符的长度，不必考虑其中单个字符是否相等。6．串是一种特殊的线性表，其特殊性体现在（ ）。A．数据元素是一个字符 B．可以顺序存储C．数据元素可以是多个字符 D．可以链接存储【答案】A 2 / 18

圣才电子书

十万种考研考证电子书、题库视频学习平台7．在下列表述中，正确的是（ ）A．含有一个或多个空格字符的串称为空格串B．对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C．选择排序算法是不稳定的D．平衡二叉树的左右子树的结点数之差的绝对值不超过l【答案】C【解析】平衡二叉树的左右子树的深度之差的绝对值不超过l。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。二、判断题1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ）【答案】√【解析】KMP算法是一种字符串匹配的算法，KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。2．设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）【答案】√【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。 3 / 18

圣才电子书

十万种考研考证电子书、题库视频学习平台3．串是一种数据对象和操作都特殊的线性表。（ ）【答案】√【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。4．两个长度不相同的串有可能相等。（ ）【答案】×【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。5．串长度是指串中不同字符的个数。（ ）【答案】×【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。三、填空题1．空格串是指＿＿，其长度等于＿＿。【答案】由空格字符（ASCIl值32）所组成的字符串；空格个数2．组成串的数据元素只能是＿＿。【答案】字符 4 / 18

圣才电子书

十万种考研考证电子书、题库视频学习平台3．一个字符串中＿＿称为该串的子串。【答案】任意个连续的字符组成的子序列4．INDEX（ˊDATASTRUCTUREˊ，ˊSTRˊ）=＿＿。【答案】55．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为＿＿。【答案】O（m+n）6．模式串P=ˊabaabcacˊ的next函数值序列为＿＿。【答案】011223127．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为＿＿，又称P为＿＿。【答案】模式匹配；模式串8．串是一种特殊的线性表，其特殊性表现在＿＿；串的两种最基本的存储方式是＿＿、＿＿；两个串相等的充分必要条件是＿＿。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等 5 / 18

圣才电子书

十万种考研考证电子书、题库视频学习平台9．已知U=ˊxyxyxyxxyxyˊ；t=’xxyˊ；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））:ASSIGN（m，ˊwwˊ），求REPLACE（S，V，m）=＿＿。【答案】ˊxyxyxywwyˊ10．实现字符串拷贝的函数strcpy为：【答案】s++=*t++或（*s++=*t++）!=ˊ＼0ˊ11．完善算法：求KMP算法．next数组。END；【答案】0；next[k]12．试利用下列栈和串的基本操作完成下述填空题。initstack（S） 置S为空栈；push（S，X） 元素X入栈；pop（S） 出栈操作； 6 / 18