《算法与数据结构》习题四.docx

习题四 一、选择项
1 .空串与空格串（ ）oA,相同B.不相同 C.可能相同D.无法确定
2 .设有两个申S1与S2,求串S2在S1中首次出现位置的运算称作（）。
A.连接B.求子串 C.模式匹配 D.判子串
3 .设有串S= "Computer\那么其子串的数目是（）。
A. 36B. 37 C. 8D. 9
4 . 一个广义表的表头总是一个广义表，这种说法（ ）oD.以上均不对

D.以上均不对
A.正确B.错误C.无法确定
5 . 一个广义表的表尾总是一个广义表，这种说法（ ）oA.正确B.错误C.无法确定
6 .广义表（（a））的表头是（ ）o

A.正确B.错误C.无法确定
7 .广义表（（a））的表头是（ ）o
A. ( )B. aC. (a)
8 .广义表((a))的表尾是( )o
A. ()B. aC. (a)
9 .广义表((a), a)的表头是( )o
A. ( )B. aC. (a)
10 .广义表((a), a)的表尾是( )o
A. ()B. aC. (a)
11 .广义表(a, b, c)的表头是( )o
A. aB. (a)C. a, b
12 .广义表（a, b, c）的表尾是（
)o
A. b, c
B. (b, c)
C. a. b, c
D.以上均不对
D. ((a))
D. ((a))
D. ((a))
D. ((a))
D. (a, b)
D. (a, b， c)

12.广义表 A 满足 Head （）二 Tail （）,那么 A为（）。
A.()
B.(())
C ((),())
D.((),(),())

二、境空题
1 .串是由零个或多个字符组成的 o通常记作：s= "C|, C2,…，Cn"（n=>0）,其中，S称为—；串中的G （l<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起 来的局部是.即串S的内容。
2 .串中字符的个数称为串的。
3 .不含有任何字符的串称为—,它的长度为—o
4 .由一个或多个空格构成的串称为,它的长度为—o
5 .串中任意多个连续字符组成的子序列称为该串的_；包含—的串称为主串。
6 .字符在序列中的序号称为该字符在串中的—o
7 .两个字符串相等是指两个字符串的，也就是说这两个字符串不仅—,而且对应位 置上—的字符也。
8 .两个串的比拟实际上是—的比拟。两个串从第一个位置上的字符开始进行比拟， 当第一次出现 大的串为大，假设比拟过程中出现一个字符串结束的情况，那么另一个串为、O
9 .串的 就是把串所包含的字符序列，依次存人连续的存储单元中去。
10 .有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种。
11 .串的 是以存储单元为存储单位，一个存储单元中只存放 O在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放 O
12 .串在非紧缩方式下，串长度的存储是隐式的2 即串的长度。
13. 一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每 个存储单元存放 的分配方式，这种方式就是一种。这种方式一般不需要存放 的存储单元，而需要以程序中各变量值所 的字符为结束符。
14 .串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城: 数据域和 域。其中 域用于存放数据，域用于存放下一个结点的指针。
15 .子串定位Strindex （s, t）,也称为,是返回串t在s主串中的位置。 三、判断回.子串是主串中字符构成的有限序列。（
2. KMP算法的最大特点是指示主串的指针不需要回溯。（—）.串中的元素只能是字符。（上
3 .串中的元素只可能是字母。（.）
4 .串是一种特殊的线性表。（_）
5 .串中可以包含有空白字符。（_）
6 .串的长度不能为零。（_）
7 .两个串相等必有串长度相同。（）
8 .两个串相等那么各位置上字符必须对应相等。（_ ）