数据结构（海南联盟）第四章测试_智慧树知到答案2021年

第四章 串：在非数值处理、事务处理等问题常涉及到一系列的字符操作。计算机的硬件结构主要是反映数值计算的要求，因此，字符串的处理比具体数值处理复杂。本章中我们将来讨论串的定义、存储结构及其模式匹配算法。4.1导读:本节为串的导读
4.2串的定义:我们目前只知道字符与串有关，它们之间具体的联系我们通过对本节当中所将要讲解的串的基本概念及抽象数据类型定义来理解。
4.3串的定长顺序存储表示:串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作，首先我们在这节当中来讨论串的定长顺序存储表示的C语言实现方式和在这种存储表示方式下的连接算法及子串删除算法。
4.4堆分配和块链存储表示:本节当中我们来学习串的对分配存储表示和块链存储表示。首先分别介绍这两种存储表示方式的基本概念和C语言实现，着重讨论堆分配存储表示的连接算法和求子串算法。
4.5模式匹配简单算法:模式匹配是一个较为复杂的串操作过程，迄今为止，人们对串的模式匹配提出了许多思想和效率各不相同的计算机算法。本节课我们先来讨论模式匹配简单算法的C语言实现，并通过算法分析来理解其模式匹配过程，最终通过例题讲解来巩固对模式匹配简单算法的理解。
4.6模式匹配KMP算法:本节要学习一种高效率的模式匹配算法，KMP算法。首先我们来讨论他与模式匹配简单算法在匹配过程当中的区别，再接着来看KMP算法当中关键的next[j]函数的定义，以便推导出来模式串指针的指向。

[单选题]串的长度是指（   ）
串中所含不同字符的个数
串中所含非空格字符的个数
串中所含字符的个数
串中所含不同字母的个数
答案：串中所含字符的个数
[单选题]设有串t='I am a good student '，那么Substr(t,6,6)=（  ）
good
a good
student
a good s[单选题]串“ababaaababaa”的next数组为（ ）
011234223456
0123012322345
012345678999
012121111212[单选题]函数substr(“DATASTRUCTURE”，5，9)的返回值为（    ）
“DATASTRUCTURE”
“DATA”
“STRUCTURE”
“ASTRUCTUR”[单选题]设有两个串p和q，求q在p中首次出现的位置的运算称作（   ）
求串长
模式匹配
求子串
连接[单选题]设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（     ）
BCDEFEF
BCDEFG
BCDEF
BCPQRST[单选题]若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）  
ABC###G1234

ABCD###2345

ABC###G2345

ABC###G0123[单选题]主串为’abaababaddecab’ ,模式串为’abad’。使用KMP算法需要（  ）次匹配成功。
4 
10
5
12[判断题]不包含任何字符的串称为空白串。
对
错[判断题]在串的模式匹配运算中，被匹配的主串称为模式。
错
对[判断题]组成串的数据元素只能是字符。
对
错[判断题]串不能采用顺序存储结构进行存储。
错
对[判断题]模式匹配简单算法时间复杂度是O(m*n)。
错
对[判断题]空格串与空串的没有区别。
错
对[判断题]设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O(m+n) 。
对
错[判断题]两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。
对
错[判断题]串是一种非线性结构。
错
对[判断题]串的模式匹配算法只能采用串的链式存储结构来实现。
错
对