数据结构：串期末单元测试与答案

一、单选题1、‌串是一种特殊的线性表，其特殊性体现在（）。A.数据元素可以是多个字符串B.数据元素是一个字符C.可以顺序存储D.可以链式存储正确答案：B2、‍串下面关于串的的叙述中，（）是不正确的？A.串既可以采用顺序存储，也可以采用链式存储B.串是字符的有限序列C.模式匹配是串的一种重要运算D.空串是由空格构成的串正确答案：D3、‌串“ababaaababaa”的next数组为（）。A.0,1,1,2,3,4,2,2,3,4,5,6B.0,1,2,3,4,5,6,7,8,9,9,9C.0,1,2,3,0,1,2,3,2,2,3,4,5D.0,1,2,1,2,1,1,1,1,2,1,2正确答案：A4、‎串“ababaabab”的nextval为（）。A.0,1,0,1,0,4,1,0,1B.0,1,0,1,0,1,0,1,1C.0,1,0,1,0,0,0,1,1D.0,1,0,1,0,2,1,0,1正确答案：A5、‎串的长度是指（）。A.串中所含不同字符的个数B.串中所含非空格字符的个数C.串中所含字符的个数D.串中所含不同字母的个数正确答案：C6、​有n个字符的字符串的非空子串个数最多有（）。A.n(n-1)/2B.n-1C.nD.n(n+1)/2正确答案：D7、‌以下（）是”abcd321ABCD”串的子串。A.“21AB”B.321ABC.abcdD.“abcABC”正确答案：A8、‌两个串相等必有串长度相等且（）。A.两个所含字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.串的各位置字符任意正确答案：B9、‍若串s="software"，其子串的个数是（）。A.36B.37C.9D.8正确答案：B10、‎函数SubStr(S,m,n)是从S的第m(>0)个字符幵始，连续取n个字符构成子串返回的运算，若设串S="tsinghua"，则用SubStr(S，3，4)抽取的子串是（）。A."ghua"B."tsin"C."nghu"D."ingh"正确答案：C11、‌设S=”aaaaaacaaaca”，P=”aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。A.7B.2C.3D.4正确答案：D12、​在使用BF算法进行模式匹配的过程中，当模式串P的第j位与目标串S的第i位比较失配时，新一趟匹配开始，在目标串的位移公式是（）。A.i=i+1B.i=i-j+1C.i=i-j+2D.i=i-j正确答案：B13、‎使用KMP算法进行模式匹配的过程中，如果某趟匹配失败，i指示主串中失配的位置，j指示模式串中失配的位置，若k=next[j]，则下一趟匹配比较时，模式串的第（）位与主串中第i个位置对齐。A.kB.j+kC.j-1D.j-k正确答案：A14、​已知P="ababaabab"，根据KMP算法，该模式串的next函数值为（）。A.-1,0,1,2,3,4,5,6,7B.-1,0,1,2,0,0,1,1,1C.-1,0,0,1,2,3,1,2,1D.-1,0,1,0,1,0,0,1,1正确答案：C二、判断题1、‌串是由有限个字符构成的序列，子串是主串中任意字符构成的有限序列。正确答案：×2、‎串通常有顺序存储和链式存储两种存储结构。正确答案：√3、‎在C语言中定义的字符串尾部都有一个'\0'，该字符不计入串长度。正确答案：√4、‏应用KMP算法进行模式匹配时，next函数值序列的产生仅与模式串有关。正确答案：√5、