数据结构模拟试卷1.pdfVIP

数据结构模拟试卷1

(总分：44.00，做题时间：90分钟)

一、单项选择题(总题数：12，分数：24.00)

1.(江苏大学)下面关于串的叙述中，()是不正确的。

A.串是字符的有限序列

B.空串是由空格构成的串√

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

选项A：串是零个或多个字符组成的有限序列，一般记为：S=aa…a，S称为串名，双引号括起

12nn

来的字符序列是串值，将串值括起来的双引号本身不属于串，它的作用是避免串与常数或标识符混淆，故

A选项正确。选项B：窒皇是指长度为零的串，它不包括任何字符。但是考生要注意与空白串进行区分，

空白串是指由一个或者多个空格组成的串，故B选项错误。选项C：模式匹配是一个比较复杂的串操作，

是子串在主串中的定位操作。常用的模式匹配算法有朴素的原始匹配算法和经过优化改进的无回溯算法，

故C选项正确。选项D：串是特殊的线性表，所以串的存储结构与线性表的存储结构类似。串的顺序存储

结构简称顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。串

的链式存储就是用单链表的方式存储串值，故D选项正确。

2.(华中科技大学)若若串串，其子串的个数是()。

A.15

B.95

C.35

D.106√

对于长度为n的字符串来说，其子串的个数为{n(n+1)／2}+1(最后+1是因为空串是任何串的子串)，记住

即可。此题n=14，所以其子串的个数是106。

3.(中国科学院)串是一种特殊的线性表，其特殊性体现在()。

A.数据元素是一个字符√

B.可以顺序存储

C.数据元素可以是多个字符

D.可以链式存储

选择这道题的原因是它被多所学校(武汉大学、中科院、大连理工、江苏大学等)原题考查，考生只需记住

一句话：串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。

4.(中南大学)求字符串T在字符串S中首次出现的位置的操作称为()。

A.求串的长度

B.求子串

C.串的模式匹配√

D.串的连接

第一题已经讲过，子串在主串中的定位操作称为模式匹配。例如A和B分分别别为：为：

B=is…则B是A的子串，B在A中出现了两次。其中首次出现对应的主串位置是3。因此称B在A中的

序号(或位置)是3。

5.(江苏大学)串“ababaaababaa’的next数组为()。

A.-1，0，1，2，3，4，5，6，7，8，8，8

B.-1，0，1，0，1，0，0，0，0，1，0，1

C.-1，0，0，1，2，3，1，1，2，3，4，5√

D.-1，0，1，2，-1，0，1，2，1，1，2，3，4

做出模式串以及对应字符下标，如下表所示。S串长度为0时，next[0]=-1；S串长度为1时，next[1]=0；

S串长度为2时，S串为“ab”next[2]=0；S串长度为3时，S串为“aaba”next[3]=1；(S串中下画线

标出了其串首位置以及末尾位置的最长匹配串对，由此可求得当前next值)S串长度为4时，S串为“abab”

next[4]=2;S串长度为5时，S串为“ababa”next[5]=3；S串长度为6时，S串为“，ababaa”next[6]=1；

S串长度为7时，S串为“a_babaaa”next[7]=1；S串长度为8时，S串为“ababaaab”next[8]=2；S

串长度为9时，S串为“ababaaaba”next[9]=3；S串长度为10时，S串为“ababaaabab”next[10]=4；

S串长度为11时，S串为“ababaaababa”next[11]=5；综上，next数组值为：-1，0，0，1，2，3，1，