1、计算机专业基础综合数据结构（串）历年真题试卷汇编 1 及答案与解析一、单项选择题1 已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t 为”abaabc”，采用 KMP 算法进行匹配，第一次出现“ 失配 ”(si!=ti)时，i=j=5，则下次开始匹配时，i 和 j 的值分别是( ) 。 【2015 年全国试题 8(2)分】（A）i=1 ，j=0（B） i=5，j=0（C） i=5，j=2 （D）i=6 ，j=22 下面关于串的叙述中，哪一个是不正确的?( ) 【北方交通大学 2001 一、5(2 分)】【江苏大学 2005 一、6(2 分)】（A）串是字符的有限序列（
2、B）空串是由空格构成的串（C）模式匹配是串的一种重要运算（D）串既可以采用顺序存储，也可以采用链式存储3 若串 S1=ABCDEFG， =9898，S3=#，S4=012345 ，执行concat(replace(S1，substr(S1，lengthCS2)，length(S3)，S3) ，substr(S4，index(S2，8)，lengthCS2) ，其结果为( )。【北方交通大学 1 999 一、5(25 7 分) 】（A）ABC#G0123（B） ABCD#2345（C） ABC#4G2345 （D）ABC#2345（E）AB#G12344 设有两个串 S1 和 S2，求 S2 在
3、 S1 中首次出现的位置的运算称作 ( )。【中南大学 2005 一、3(2 分) 】（A）求子串（B）判断是否相等（C）模型匹配（D）连接5 已知串 S=aaab，其 Next 数组值为( )。【西安电子科技大学 1996 一、7(2 分) 】（A）0123（B） 1 123（C） 1231 （D）12116 串ababaaababaa的 next 数组为( )。【中山大学 1999 一、7】【江苏大学 2006一、1(2 分) 】（A）012345678999（B） 012121 1 1 1212（C） 01 1234223456 （D）0123012322347 字符串ababaabab
4、的 nextval 为( )。【北京邮电大学 1999 一、1(2 分)】【烟台大学 2007 一、8(2 分) 】（A）(0 ，1，0，1，0，4，1，0，1)（B） (0，1，0，1，0，2，1，0，1)（C） (0，1，0，1，0，0，0，1，1)（D）(0 ，1，0，1，0，1，0，1，1)8 模式串 t=abcaabbcabcaabdab，该模式串的 next 数组的值为( )，nextval 数组的值为( )。【 北京邮电大学 1998 二、3(2 分) 】（A）011 12 2 1 11 2 3 4 5 6 7 1 2（B） 0 1 1 1 2 1 2 1 1 2 3 4 5 6
5、 1 1 2（C） 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 01（D）0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2（E）0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 9 若串 S=“myself”，其子串的数目是( )。【北京理工大学 2007 一、6(1 分)】（A）20（B） 21（C） 22（D）2310 若串 S=software，其子串的数目是( )。【西安电子科技大学 2001 应用一、2(2 分)】（A）8（B） 37（C） 36 （D）911 设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异
6、的非平凡子串(非空且不同于 S 本身)的个数为( )。【中科院计算所 1997】【烟台大学 2007一、7(2 分) 】（A）2n-1（B） n2（C） (n22)+(n2)（D）(n2 2)+(n2)一 1（E）(n22)一(n2)一 1 12 串是一种特殊的线性表，其特殊性体现在( )。【暨南大学 2010 一、11(2 分)】（A）可以顺序存储（B）数据元素是一个字符（C）可以链接存储（D）数据元素可以是多个字符13 在下列表述中，( ) 是错误的。【华中科技大学 2006 二、2(2 分)】（A）含有一个或多个空格字符的串称为空格串（B）对 n(n0)个顶点的网，求出权最小的 n-1
7、条边便可构成其最小生成树（C）选择排序算法是不稳定的（D）平衡二叉树的左右子树的结点数之差的绝对值不超过 1二、填空题14 两个字符串相等的充分必要条件是_。【北京交通大学 2005 二、10(2分)】15 空格串是指_，其长度等于_。【西安电子科技大学 2001 软件一、4(2 分) 】16 组成串的数据元素只能是_。【中山大学 1998 一、5(1 分)】【北京邮电大学 2006 一、5(2 分) 】17 一个字符串中_称为该串的子串。【华中理工大学 2000 一、3(1 分)】18 INDEX(DATASTRUCTURE，STR)= _。【福州大学 1998 二、4(2分)】19 设正文
8、串长度为 n，模式串长度为 m，则串匹配的 KMP 算法的时间复杂度为_。【重庆大学 2000 一、4】20 模式串 P=abaabcac的 next 函数值序列为_。【西安电子科技大学2001 软件一、6(2 分) 】21 字符串ababaaab的 nextval 函数值为_。【北京邮电大学 2001 二、4(2分)】22 设目标串 T=abccdcdccbaa，模式 P=cdcc，则第_ 次匹配成功。【东南大学 2005 数据结构部分二、2(1 分)】23 模式串 r=abcaabbcabcabcaabdab的 next 函数值为 _。【北京交通大学2006 二、4(2 分) 】24 字符
9、运算 Index(&t pos)的返回值是_ 。【北京理工大学 2007 二、1(1分)】三、判断题25 KMP 算法的特点是在模式匹配时指示主串的指针不会变小。( )【北京邮电大学 2002 一、4(1 分) 】（A）正确（B）错误26 空串与空格串相同。( )【暨南大学 201 1 三、11(1 分)】（A）正确（B）错误27 串是一种数据对象和操作都特殊的线性表。( )【大连海事大学 2001 1、L(1 分)】【烟台大学 2007 二、4(1 分)】（A）正确（B）错误28 串长度是指串中不同字符的个数。( )【中南大学 2005 三、1(2 分)】（A）正确（B）错误29 改进的 K
10、MP 算法中，字符串 abaaaba的 nextval 数组值是0101110。( )【北京邮电大学 2005 二、4(1 分)】（A）正确（B）错误30 字符串aababaaaba 的改进失败函数 nextval 数组值是 0020200320。( )【北京邮电大学 2006 二、4(1 分) 】（A）正确（B）错误计算机专业基础综合数据结构（串）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 本题 f 串的存储下标从 0 开始，其 next 函数值是：一 100112。2 【正确答案】 B3 【正确答案】 E4 【正确答案】 C5 【正确答案】 A6 【正确
11、答案】 C【试题解析】 本章求串的 next 函数和 nextval 函数，下标都从 1 开始。若从 0 开始，相应值减 1。7 【正确答案】 A8 【正确答案】 D,E9 【正确答案】 C10 【正确答案】 B【试题解析】 子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为 n(n0)，长为 n 的子串有 1 个，长为 n 一 1 的子串有 2 个，长为 n 一 2 的子串有 3 个，长为 1的子串有，2 个。由于空串是任何串的子串，所以本题的答案为：8*(1+8)2+1=37。故选 B。但有的教科书上认为“空串是任意串的子串”无意
12、义，所以认为选 C。为避免考试中的二义性，编者认为第 11 题出得好。11 【正确答案】 D12 【正确答案】 B13 【正确答案】 B,D【试题解析】 B 错误在于权最小的 n 一 1 条边可能形成环， D 错误在于平衡二叉树的左右子树的结点数之差的绝对值不超过 1，应是任意结点的左右子树高度之差的绝对值不超过 1。二、填空题14 【正确答案】 串的长度相等并且两串对应字符相等。或者说两个串的串值相等15 【正确答案】 (1)由空格字符(ASCII 值 32)所组成的字符串 (2)空格个数16 【正确答案】 字符17 【正确答案】 任意个连续的字符组成的子序列18 【正确答案】 519 【正确答案】 O(m+n)20 【正确答案】 112231221 【正确答案】 101042122 【正确答案】 623 【正确答案】 011 1223 112345345671224 【正确答案】 子串 T 在主串 S 的第 pos 个字符之后第一次出现的位置，若没出现，返回 0三、判断题25 【正确答案】 A26 【正确答案】 B27 【正确答案】 A28 【正确答案】 B29 【正确答案】 B30 【正确答案】 A
