计算机专业基础综合数据结构(串)历年真题试卷汇编3

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