发布时间 : 星期五 文章计算机专业基础综合数据结构(串)历年真题试卷汇编3更新完毕开始阅读
计算机专业基础综合数据结构（串）历年真题试卷汇编3
(总分：60.00，做题时间：90分钟)
一、 单项选择题(总题数：13，分数：26.00)
1.已知字符串S为“abaabaabacacaabaabcc”，模式串t为”abaabc”，采用KMP算法进行匹配，第一次出现“失配”(s[i]!=t[i])时，i=j=5，则下次开始匹配时，i和j的值分别是( )。【2015年全国试题8(2)分】
（分数：2.00） A.i=1，j=0 B.i=5，j=0 C.i=5，j=2 √ D.i=6，j=2
解析：解析：本题f串的存储下标从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)))，其结果为( )。【北方交通大学1 999一、5(25／7分)】 （分数：2.00） A.ABC###G0123 B.ABCD###2345 C.ABC###4G2345 D.ABC###2345 E.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 123 C.1231 D.1211 解析：
6.串‘ababaaababaa’的next数组为( )。【中山大学1999一、7】【江苏大学2006一、1(2分)】 （分数：2.00） A.012345678999
B.012121 1 1 1212 C.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.(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 2 B.0 1 1 1 2 1 2 1 1 2 3 4 5 6 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分)】 （分数：2.00） A.20 B.21 C.22 √ D.23 解析：
10.若串S=\，其子串的数目是( )。【西安电子科技大学2001应用一、2(2分)】 （分数：2.00） A.8 B.37 √ C.36 D.9
解析：解析：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n(n>0)，长为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分)】 （分数：2.00） A.2n-1 B.n2
C.(n2／2)+(n／2) D.(n2／2)+(n／2)一1 √ E.(n2／2)一(n／2)一1 解析：
12.串是一种特殊的线性表，其特殊性体现在( )。【暨南大学2010一、11(2分)】 （分数：2.00） A.可以顺序存储
B.数据元素是一个字符 √ C.可以链接存储
D.数据元素可以是多个字符 解析：
13.在下列表述中，( )是错误的。【华中科技大学2006二、2(2分)】 （分数：2.00）
A.含有一个或多个空格字符的串称为空格串
B.对n(n>0)个顶点的网，求出权最小的n-1条边便可构成其最小生成树 √ C.选择排序算法是不稳定的
D.平衡二叉树的左右子树的结点数之差的绝对值不超过1 √
解析：解析：B错误在于权最小的n一1条边可能形成环，D错误在于平衡二叉树的左右子树的结点数之差的绝对值不超过1，应是任意结点的左右子树高度之差的绝对值不超过1。
二、 填空题(总题数：11，分数：22.00)
14.两个字符串相等的充分必要条件是__________。【北京交通大学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）
__________________________________________________________________________________________ 正确答案：(正确答案：任意个连续的字符组成的子序列) 解析：
18.INDEX(’DATASTRUCTURE\1998二、4(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：5) 解析：
19.设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为__________。【重庆大学2000一、4】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：O(m+n)) 解析：
20.模式串P=\的next函数值序列为__________。【西安电子科技大学2001软件一、6(2分)】 （分数：2.00）
__________________________________________________________________________________________ 正确答案：(正确答案：1122312) 解析：
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)的返回值是__________。【北京理工大学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算法中，字符串\的nextval数组值是\。( )【北京邮电大学2005二、4(1分)】
（分数：2.00）
A.正确 B.错误 √ 解析：
30.字符串\的改进失败函数nextval数组值是0020200320。( )【北京邮电大学2006二、4(1分)】
（分数：2.00） A.正确 √ B.错误 解析：