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