2023年7月20日发(作者：)

计算机专业基础综合数据结构（串）历年真题试卷汇编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. 串既可以采用顺序存储，也可以采用链式存储

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###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分)】

3. 判断题

1. KMP算法的特点是在模式匹配时指示主串的指针不会变小。( )【北京邮电大学2002一、4(1分)】

A. 正确 B. 错误

2. 空串与空格串相同。( )【暨南大学201 1三、11(1分)】

A. 正确 B. 错误

3. 串是一种数据对象和操作都特殊的线性表。( )【大连海事大学2001 1、L(1分)】【烟台大学2007二、4(1分)】

A. 正确 B. 错误

4. 串长度是指串中不同字符的个数。( )【中南大学2005三、1(2分)】

A. 正确 B. 错误

5. 改进的KMP算法中，字符串"abaaaba"的nextval数组值是"0101110"。( )【北京邮电大学2005二、4(1分)】

A. 正确 B. 错误

6. 字符串"aababaaaba"的改进失败函数nextval数组值是。( )【北京邮电大学2006二、4(1分)】

A. 正确 B. 错误