2021年数据结构考试题库含答案.doc

第四章 串

一、选取题

1．下面关于串论述中，哪一种是不对的？（ ）【北方交通大学 一、5（2 分）】

A．串是字符有限序列 B．空串是由空格构成串

C．模式匹配是串一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储

2 若串 S

1

=‘ABCDEFG’，S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))

其成果为（ ）【北方交通大学 1999 一、5 （25/7 分）】

A．0123 B．1123 C．1231 D．1211

5．串 ‘ababaaababaa’ next 数组为（ ）。【中山大学 1999 一、7】

A． B． C． D．5

6．字符串‘ababaabab’ nextval 为（ ）

A．(0,1,0,1,04,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 )

【北京邮电大学 1999 一、1（2 分）】

7．模式串 t=‘abcaabbcabcaabdab’，该模式串 next 数组值为（ ），nextval 数组值为 （ ）。

A．0 1 1 1 2 2 1 1 1 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 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2

9．设 S 为一种长度为 n 字符串，其中字符各不相似，则 S 中互异非平凡子串（非空且不同于 S 自身）个数

为（ ）。【中科院计算所 1997 】

A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其她状况

10．串长度是指（ ）【北京工商大学 一、6 （3 分）】

A．串中所含不同字母个数 B．串中所含字符个数

C．串中所含不同字符个数 D．串中所含非空格字符个数

2．设模式串长度为 m,目的串长度为 n，当 n≈m 且解决只匹配一次模式时，朴素匹配（即子串定位函数）

算法所花时间代价也许会更为节约。（ ）【长沙铁道学院 1998 一、1 (1 分)】

3．串是一种数据对象和操作都特殊线性表。（ ）【大连海事大学 1、L (1 分)】

二、填空题

1．空格串是指__(1)__，其长度等于___(2)__。 【西安电子科技大学 软件 一、4（2 分）】

2．构成串数据元素只能是________。 【中山大学 1998 一、5 （1 分）】

3．一种字符串中________称为该串子串 。 【华中理工大学 一、3（1 分）】

4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。【福州大学 1998 二、4 (2 分)】

5．设正文串长度为 n，模式串长度为 m，则串匹配 KMP 算法时间复杂度为________。

【重庆大学 一、4】

10．两个字符串相等充分必要条件是_______。 【西安电子科技大学 1999 软件 一、1 （2 分）】

11．知 U=‘xyxyxyxxyxy’；t=‘xxy’；

ASSIGN（S，U）；

ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；

ASSIGN（m，‘ww’）

求 REPLACE（S，V，m）= ________。 【东北大学 1997 一、1 (5 分)】

12．实现字符串拷贝函数 strcpy为：

void strcpy(char *s ，char *t) /*copy t to s*/

{ while (________)

} 【浙江大学 1999 一、5 (3 分)】

13．下列程序判断字符串s 与否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；

14．下列算法实现求采用顺序构造存储串 s 和串 t 一种最长公共子串。

程序（a）

PROCEDURE maxcomstr(VAR s,t ：orderstring；VAR index,length ：integer);

VAR i,j,k,length1:integer； con:boolean;

BEGIN

index :=0；length :=0； i :=1;

WHILE(i<=s.len) DO

WHILE (j<=t.len) DO

(3)____；

ELSE (4)____;

]

END;

程序(b)

{ if (s[i]= =t[j])

while(con)

if (1) _ { length1=length1+1;k=k+1；} else (2) __;

if (length1>length) { index=i； length=length1；}

(3)____；

else (4) ___;

}

(5) __

j:=1；k:=(1)__； next[1]:=0;

WHILE j<t.len DO

IF k=0 OR t.ch[j]=t.ch[k] THEN BEGIN j:=j+1；k:=k+1；next[j]:=k;END

ELSE k:=(2)___;

END;

【中山大学 1998 四、1 （4 分）】

16．下面函数 index 用于求 t 与否为 s 子串，若是返回 t 第一次出当前 s 中序号(从 1 开始计)，否则返回

0。

mt,ms

ELSE [ (3)___；(4)_ ]

IF j>mt THEN return (5)____；ELSE return (6)__

ENDF;

【南京理工大学 1999 三、2 （6 分）】

17．阅读下列程序阐明和 pascal 程序,把应填入其中（ ）处字句写在答题纸上。

程序阐明：

本程序用于鉴别输入字符串与否为如下形式字符串:

W&M$ 其中,子字符串 M 是子字符串 W 字符反向排列,在此假定 W 不具有字符&和字符$,字符&用作 W

与 M 分隔符,字符$用作字符串输入结束符。

例如,对输入字符串 ab&ba$、11&12$、ab&dd$、&$,程序将分别输出 Ok.(是),No.(不是)。