数据结构第四章串习题及答案

数据结构第四章串习题及答案

习题四 串

一、单项选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）

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

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

2．串是一种特殊的线性表，其特殊性体现在（ ）。

A．可以顺序存储 B．数据元素是一个字符

C．可以链接存储 D．数据元素可以是多个字符

3．串的长度是指（ ）

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

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

4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长

5．若串S=“software”,其子串的个数是（ ）。

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

二、填空题

1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。

2．空格串是指__ __，其长度等于__ __。

3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。

4．INDEX（‘DATASTRUCTURE’， ‘STR’）=________。

5．模式串P=‘abaabcac’的next函数值序列为________。

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

{int i=0,j=0; while (s[j])(2)___ _____;

for(j--; i<j && s[i]==s[j]; i++,j--); return((3)___ ____)

}

7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

void maxcomstr(orderstring *s,*t; int index, length)

{int i,j,k,length1,con;

index=0;length=0;i=1;

数据结构第四章串习题及答案

while (i<=s.len)

{j=1;

while(j<=t.len)

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

{ k=1;length1=1;con=1;

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

if (length1>length) { index=i; length=length1; } (3)__ __;

} else (4) ___;

} (5) __

} }

第四章 串

一、单项选择题

1．B

2. B

3．B

4．C

5. C

二、填空题

1．空、字符

2． 由空格字符（ASCII值32）所组成的字符串 空格个数

3．长度、相等、子、主

4．5

5．01122312

6．（1）char s[ ] (2) j++ (3) i >= j

7．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。

(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a）

(2) con=0 (3) j+=k (4) j++ (5) i++