第4章串答案.doc（最新文档）.doc

一、选择题

1如下陈述中正确的是(A).

A.串是一种特殊的线性表B串的长度必须大于0

C串中元素只能是字母D空串就是空格串

2串的长度是指(B).

A串中所有不同字母的个数B串中所有字符的个数

c.串中所含不同字符的个数D串中所有非空格字符的个数

3设有两个串p和q,求q在p中首次出现的位置的运算称作

(B)o

A连接B模式匹配C求子串D求串长

4.(D)是(2语言中abed321ABCD的子串.

A.abedB.321ABC.abcABCD.21AB

5若串s=nsofrwaren,其子串的数目是(B37).

A.8B.37C.36D.9

6下而关于串的叙述中，哪个是不正确的？(B).

A串是字符的有限序列

B空串是由空格构成的串

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

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

7.设串S=nabcdefgh,S的所有非平凡子串的个数是(C)

A.8B.37C.36D.35

设S为一个长度为n的字符串，其中的字符各不相同，s中的互异的非平凡子串的个数是（C）

A.川B.%+%—1 C.%+% D.%—%—1

设主串的长度为m,模式串的长度是n,串匹配的B算法时间复杂度是（D）

A.o（n2） B?o（〃）C?o（〃+nt）D?o（m*n）

10?顺序串中，根据空间分配方式的不同，可分为（B）

A.直接分配和间接分配B.静态分配和动态分配

C.顺序分配和链式分配D.随机分配和固定分配

二、基本知识题

1空串与空格串有何区别？空串是指长度是零的串，空格串中可

以包含一个或多个空白符

2己知有两个串为

A=naccabcabcbbca

B=abc

判断B串是否是A串的子串，如果是其子串，说明起始点是A串的第几个字符。是9

3.串是一种特殊的线性表，其特殊性体现在什么地方?数据元素是一个字符

4串的两种基本的存储方式是什么？顺序和链接

5两个串相等的充分必要条件是什么？串长相等且对应位置的字符相同

三、算法设计题

1对于采用顺序结构有储的串r,编写一个函数删除其值等于ch的所有字符.

2对于采用顺序结构有储的串r,编写一个函数删除r中第i个字符开始的j个字符.

3对于采用顺序结构有储的串r,设计一算法将串逆置.

4采用单链表结构存储的串r,编写一个函数将其中所有的c，宇符替挟成s，宇符.

5己如两个采用单链表结构存储的串A和Bo试编写个函数将串B插入串A中第k个字符之后。

6采用顺序结构寸储串，编写一个实现串比较运算的函数Strcmp(s,t),取比较以词典方式进行，当s大于1时返回1,s与t相等时返回0,s小于t时返回-1。