数据结构与算法第四章测试_智慧树知到答案2021年

第四章 串：(1)串的相关概念。(2)串的顺序存储结构和链式存储结构的优缺点。(3)顺序串运算算法设计。(4)链串运算算法设计。(5)BF模式匹配算法设计。(6)KMP算法设计，KMP算法是提高串匹配效率的。4.1串的基本概念:(1)串是若干个字符的有限序列，空串是长度为零的串。(2)串可以看成是一种特殊的线性表，其逻辑关系为线性关系。(3)串的长度是指串中所含字符的个数。(4)含n个不同字符的串的子串个数为n(n+1)/2+1。
4.2串的存储结构:(1)串主要有顺序串和链串两种存储结构。(2)顺序串的算法设计和顺序表类似，链串的算法设计和单链表类似。
4.3串的模式匹配:(1)在串匹配中一般将主串称为目标串，将子串称为模式串。(2)BF模式匹配算法中需要回溯，时间复杂度为O(m×n)，而KMP算法消除了回溯， 时间复杂度为O(m+n)。

[单选题]若串S=“software”，则其子串数目是____，其中空串和S串本身这两个字符串也算作S的字串
37
36
8
9
答案：37
[单选题]串的长度是指____。
串中所含字符的个数
串中所含非空格字符的个数
串中所含不同字符的个数
串中所含不同字母的个数[单选题]下面关于串的叙述中，哪一个是不正确的____。
串既可以采用顺序存储，也可以采用链式存储
串是字符的有限序列
空串是由空格构成的串
模式匹配是串的一种重要运算[单选题]串是一种特殊的线性表，其特殊性体现在____。
数据元素是一个字符
可以链式存储
数据元素是多个字符
可以顺序存储[单选题]在用KMP算法进行模式匹配时，模式串“ababaaababaa”的next数组值为____。
-1，0，1，2，3，4，5，6，7，8，9，9
-1，0，0，1，2，3，1，1，2，3，4，5
-1，0，1，2，1，2，1，1，1，1，2，1
-1，0，1，2，3，0，1，2，3，2，2，3