计算机专业基础综合数据结构（串）历年真题试卷汇编3
(总分60,考试时间90分钟)
1. 单项选择题
1. 已知字符串S为“abaabaabacacaabaabcc”，模式串t为”abaabc”，采用KMP算法进行匹配，第一次出现“失配”(s[i]!=t[i])时，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=2
2. 下面关于串的叙述中，哪一个是不正确的?( )【北方交通大学2001一、5(2分)】【江苏大学2005一、6(2分)】
A. 串是字符的有限序列 B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储
字符串长度17模式串长度83. 若串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###G1234
4. 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( )。【中南大学2005一、3(2分)】
A. 求子串 B. 判断是否相等
C. 模型匹配 D. 连接
5. 已知串S=‘aaab’，其Next数组值为( )。【西安电子科技大学1996一、7(2分)】
A. 0123 B. 1 123
C. 1231 D. 1211
6. 串‘ababaaababaa’的next数组为( )。【中山大学1999一、7】【江苏大学2006一、1(2分)】
A. XX9 B. 012121 1 1 1212
C. 01 1234223456 D. XX4
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 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分)】
A. 20 B. 21
C. 22 D. 23
10. 若串S="software"，其子串的数目是( )。【西安电子科技大学2001应用一、2(2分)】
A. 8 B. 37
C. 36 D. 9
11. 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串(非空且不同于S本身)的个数为( )。【中科院计算所1997】【烟台大学2007一、7(2分)】
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分)】
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
13. 在下列表述中，( )是错误的。【华中科技大学2006二、2(2分)】
A. 含有一个或多个空格字符的串称为空格串
B. 对n(n>0)个顶点的网，求出权最小的n-1条边便可构成其最小生成树
C. 选择排序算法是不稳定的
D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1
2. 填空题
1. 两个字符串相等的充分必要条件是__________。【北京交通大学2005二、10(2分)】
2. 空格串是指__________，其长度等于__________。【西安电子科技大学2001软件一、4(2分)】
3. 组成串的数据元素只能是__________。【中山大学1998一、5(1分)】【北京邮电大学2006一、5(2分)】
4. 一个字符串中__________称为该串的子串。【华中理工大学2000一、3(1分)】
5. INDEX(’DATASTRUCTURE"，‘STR")= __________。【福州大学1998二、4(2分)】
6. 设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为__________。【重庆大学2000一、4】
7. 模式串P="abaabcac"的next函数值序列为__________。【西安电子科技大学2001软件一、6(2分)】
8. 字符串"ababaaab"的nextval函数值为__________。【北京邮电大学2001二、4(2分)】
9. 设目标串T=‘abccdcdccbaa’，模式P=‘cdcc’，则第__________ 次匹配成功。【东南大学2005数据结构部分二、2(1分)】
10. 模式串r=‘abcaabbcabcabcaabdab’的next函数值为__________。【北京交通大学2006二、4(2分)】
11. 字符运算Index(&t pos)的返回值是__________。【北京理工大学2007二、1(1分)】
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论