中国铁道出版社数据结构（第二版）单元5练习参考答案

单元练习5

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）

（ㄨ）（1）串是n个字母的有限序列。 （√）（2）串的数据元素是一个字符。 （ㄨ）（3）串的长度是指串中不同字符的个数。

（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。

（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （√）（6）串的堆分配存储是一种动态存储结构。 （ㄨ）（7）“DT”是“DATA”的子串。

（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。 （√）（9）子串的定位运算称为模式匹配。

（√）（10）在链串中为了提高存储密度，应该增大结点的大小。

二．填空题

（1） 由零个或多个字符组成的有限序列称为 字符串（或串） 。 （2） 字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。 （3） 串的顺序存储结构简称为 顺序串 。

（4） 串顺序存储非紧凑格式的缺点是： 空间利用率低 。 （5） 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。 （6） 串链接存储的优点是插入、删除方便，缺点的 空间利用率低 。 （7） 在C或C++语言中，以字符 \\0 表示串值的终结。 （8） 空格串的长度等于 空格的个数 。 （9） 在空串和空格串中，长度不为0的是 空格串 。

（10） 两个串相等是指两个串相长度等，且对应位置的 字符都相同 。 （11） 设S=\，则LenStr(s)= _ 8 。

（12） 两个字符串分别为：S1=\is\，S2=\July,2005\

的结果是： Today is 30 July,2005 。

（13） 求子串函数SubStr(\is 30 July,2005\的结果是：

July 。

（14） 在串的运算中，EqualStr(aaa,aab)的返回值为 <0 。 （15） 在串的运算中，EqualStr(aaa,aaa)的返回值为 0 。

（16） 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。 （17） 模式匹配成功的起始位置称为： 有效位移 。

（18） 设S=\，T=\， 则第 6 次匹配成功。

（19） 设S=\，T= \，则字符定位的位置为 0 。 （20） 若n为主串长度，m为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复杂度为： (n-m+1)*m 。

三．选择题

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

A.可以顺序存储 B．数据元素是一个字符 C.可以链接存储 D．数据元素可以是多个字符 （2）某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A．链式 B．顺序

C．堆结构

D．无法确定

（3）以下论述正确的是（ C ）。 A．空串与空格串是相同的 C．空串是零个字符的串

B．\是\的子串 D. 空串的长度等于1

B．\是\的子串 D. 空串的长度等于1

B．\是\的子串 D．\ B．模式匹配 D．串比较

C．找某字符在主串中第一次出现的位置

D．找某子串在主串中第一次出现的第一个字符位置

（4）以下论述正确的是（ B ）。 A．空串与空格串是相同的 C．空格串是有空格的串

（5）以下论断正确的是( A )。 A．\是空串，\ \空格串 C．\ A. 串连接

（6）设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。 C. 求子串 （7）串的模式匹配是指（ D ）。

A．判断两个串是否相等 B．对两个串比较大小

（8）若字符串\采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为( D )。 A．20％ B．40％

C．50％ D．33．3％

（9）若字符串\采用链式存储，假设每个指针占用2个字节，若希望存储密度50％，则每个结点应存储( A )个字符。 A．2 B．3 A．\

C．4

D．5

（10）设串S1=\，S2=\则ConcatStr(S1,S2)=( B )。

B．\

D. \ C．2 D．3 C．2 D．3

C．\

A．0 A．0

（11）设S=\，则LenStr（S）=（ A ）。

B．1 B．1

（12）设目标串T=\，模式P=\，则该模式匹配的有效位移为 ( A )。 （13）设目标串T=\，模式P=\，则该模式匹配的有效位移为 ( D )。

A．2 ( D )次。

A．1 B．9

C．4 D．5

B．3 C．4 D. 5

（14）设目标串T=\，模式P=\朴素匹配算法的外层循环进行了

（15）朴素模式匹配算法在最坏情况下的时间复杂度是( D )。 A．O（m） B．O（n）

A．\ ( A )。

A．\

B．\

C．\ D．\

（18）S1=\，S2=\，执行函数SubStr(S2,4,LenStr(S1))后的结果为( B )。 A．\

B．\

C．\ D．\（19）设串S1=\，S2=\

则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( D )。

A．BCDEF B．BCDEFG C．BCPQRST D. BCDEFEF （20）若串S=\，其子串的数目最多是：（ C ） 。 A．35 B．36 C．37 D．38 （8+7+6+5+4+3+2+1+1=37）

C．0（m+n）

D．0（m*n）

（16）S=\，执行求子串函数SubStr(S,2,2)后的结果为( B )。

B．\

C．\ D．\

（17）S1=\，S2=\，执行串连接函数ConcatStr(S1,S2)后的结果为

四．程序题填空（每空2分，共50分）

1．下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。

typedef Struct

{ char vec[MAXLEN]; // 定义合并后串的最大长度 int len; // len为串的长度 }St ;

void ConcatStr(Str *r1,Str *r2) // 字符串连接函数 { int i; cout << r1->vec<vec; if(r1->len+r2->len> MAXLEN ) cout<< \两个串太长，溢出！\ else

{ for(i=0;i< r2->len ;i++) // 把r2连接到r1 r1->vec[ r1->len+i ]=r2->vec[i]; r1->vec[r1->len+i]= '\\0' ; // 添上字符串结束标记 r1->len= r1->len+r2->len ; // 修改新串长度 } }

2. 设x和y两个串均采用顺序存储方式，下面的程序是比较x 和y两个串是否相等的函数，试完成程序填空。

#define MAXLEN 100 typedef struct

{ char vec[MAXLEN]; len; } str;

int same (x,y) str *x,*y; { int i=0,tag=1;

if (x->len != y->len) return (0); // (或 <> ) else

{ while ( ilen && tag )

{ if ( x->vec[i] != y->vec[i] ) tag=0 ; i++ ; （ 或 i=i+1 ） } return (tag); } }

3．下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。 解： #include \

typedef struct { char vec[MAXLEN]; int len; }str;

void Palindrome (str s) { int i=0;

ing j= s.len-1 ; while ( j-i>=1 )

{ if ( s.vec[i]== s.vec[j] )

{i++; j-- ;continue} // (或 j=j+1 ) else break; }

if ( j-i>=1 )

cout<<\ else

cout<<\}

五．编程题

1．设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写下列算法： #define MAXLEN 100 typedef struct

{ char vec[MAXLEN]; int len; } str;

（1） 将串中r中所有其值为ch1的字符换成ch2的字符。 （2） 将串中r中所有字符按照相反的次序仍存放在r中。 （3） 从串r中删除其值等于ch的所有字符。

（4） 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。 （5） 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数）。 （6） 编写一个比较x 和y两个串是否相等的函数。

2．设计一算法判断字符串是否为回文（即正读和倒读相同） 3．设计一算法从字符串中删除所有与字串\del\相同的子串 4．设计一算法统计字符串中否定词\not\的个数

1．解：

（1）算法思想：从头至尾扫描r串，对于值为ch1的元素直接替换成ch2即可。 str *trans (r,ch1,ch2) str *r;

char ch1,ch2; { int i;

for (i=0;ilen;i++)

if (r->vec[i]==ch1)

r-vec[i]=ch2;

return(r); }

（2）算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，依次类推，便将该串的所有字符反序了。

str *invert (r) str *r;

{ int i; char x;

for (i=0;i< (r->len%2) ;i++) { x=r->vec[i];

r->vec[i]=r->[r->len-i+1]; r->vec[r->len-i+1]=x; }

return (r ); }

（3）算法思想：从头到尾扫描r串，对于值为ch的元素用移动的方式进行删除。

str *delall (r,ch)

str *r; char ch; { int i,j;

for (i=0;ilen;i++) if (r->vec[i]==ch) {

for (j=i;jlen;j++) r->vec[i]=r->vec[i+1]; r->len=r->len-1; }

return (r );

}

（4）算法思想：从第index个元素开始扫描r1，当其元素值与r2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到r2结束为止，若都相同则返回，否则继续上述过程直到r1扫描完为止。

int partposition(r2,r1,index) str *r2, *r1; int index;

{ int i,j,k;

for (i=index;r1->vec[i];i++)

for (j=i,k=0;r1->vec[j]==r2->vec[k];j++,k++) if (!r2->vec[k+1]) return(i); return(-1); }

（5）算法思想：从位置1开始调用第（4）小题的函数partposition（），若找到了一个相同子串，则调用delsubstring（），再相同的方法查找后面位置的相同子串。 str *delstringall(r,r3) str *r, *r3; { int i=0;

while (ilen)

{ if (partposition(r,r3,i)!=-1)

delsubstring(r,i,r3->len) i++; }

}

（6）两个串相等的条件是两个串的长度相等，且两个串的对应的字符必须都相同。

int same(x,y) str *x,*y;

{ int i=0,tag=1;

if (x->len!=y->len)

return(0); else

{ while (ilen && tag)

{ if (x->vec[i]!=y->vec[i])

tag=0;

i++; }

return(tag); } }

2．解：#include \

typedef struct { char *head; int length; }Hstring;

void isPalindrome(Hstring s) {

int i=0;

int j=s.length-1; while (j-i>=1) {

if (s.head[i]==s.head[j]) {i++; j--; continue;} else break; }

if (j-i>=1)

printf(\ else

printf(\}

3．解：#include \

#include \typedef struct { char *head; int length; }Hstring;

char *DeleteSubString(Hstring S,Hstring T) {

int i=0; int j,k;

int Slength=S.length; int Tlength=T.length; char *tail;

while (i<=Slenght-Tlength) {

j=0;k=i;

while (j

if (j==Tlength) // 若匹配则执行下面的程序 {

if (i==0) // 若位于头位置则改变头指针 {

S.head=S.head+Tlength; S.length-=Tlength; Slength-=Tlength; i=0; } else

if (i+Tlength

{

tail=S.head+i+Tlength; strcpy(S.head+i,tail); S.length-=Tlength; Slength-=Tlength; }

else // 若位于尾部则割去 strncpy(S.head+i,”\\0”,1); }

else // 若不匹配则i加1 i++; }

return S.head; }

4．解：#include \

#include \

int Find_word(char *text, const char *word) {

int textlength=strlen(text); int wordlength=strlen(word); int i,j,k; int count=0;

for (i=0;i

while (j

if (j==wordlength && word[j]==’\\0 ’) // 匹配成功计数器加1 count ++; }

return count; }

模拟考题

1．下列程序是在字符串s的第i个字符起，连续删除长度为j的子串，试完成程序填空。 #include \

typedef struct { char vec[MAXLEN];

int len; }str;

void DelStr(Str *s,int i,int j) { int k;

if (i+j-1> s->len )

cout<<\所要删除的子串超界！\\n\else

{ for (k=i+j;k< s->len ;k++,i++) } } main（）

{ cout<< \请输入从第几个字符开始：\cin>>i;

cout<<\请输入删除的连续字符数：\cin>>j;

DelStr(s, i-1 ,j);

}

2．下列程序是在字符串s的第i个字符前，插入一个子串s1，试完成程序填空。

#include \typedef struct {char vec[MAXLEN];

int len; }str;

Str *InsStr(Str *s,Str *s1,int i) { int k; if (i>=s->len|| s->len+s1->len >MAXLEN) printf(\不能插入!\\n\ else

{for (k=s->len-1;k>=i; k-- ) s->vec[ s1->len+k ]=s->vec[k]; for (k=0;k< s1->len ;k++)

s->vec[i]=s->vec[ k ]; s->len=s->len-j;

s->vec[s->len]=' \\0 ';

s->vec[i+k]=s1->vec[k]; s->len= s->len+s1->len ; s->vec[s->len]='\\0'; } return s; }

main()

{ cout<< \请输入在第几个字符前插入：\cin>>i;

cout<< \请输入所要插入的字符串：\s1=CseateStr(&b); InsStr(s,s1,i-1); }

3．下列程序是在字符串s的第i个字符起，取出长度为j的子串，试完成程序填空。

#include \typedef struct {char vec[MAXLEN];

int len; }str;

void SubStr(Str *s,int i,int j) { int k; Str a;

Str *s1=&a;

if (i+j-1> s->len )

{ cout<< \子串超界!\\n\ return; } else

{ for(k=0; k

s1->vec[k]=s->vec[ i+k-1 ]; s1->len= j ;

s1->vec[s1->len]='\\0'; }

cout<< \取出字符为：\ puts(s1->vec); }

main()

{ cout<< \请输入从第几个字符开始：\ cin>>i;

cout<< \请输入取出的连续字符数：\ cin>>j;

SubStr (s,i,j); }

s->vec[i+k]=s1->vec[k]; s->len= s->len+s1->len ; s->vec[s->len]='\\0'; } return s; }

main()

{ cout<< \请输入在第几个字符前插入：\cin>>i;

cout<< \请输入所要插入的字符串：\s1=CseateStr(&b); InsStr(s,s1,i-1); }

3．下列程序是在字符串s的第i个字符起，取出长度为j的子串，试完成程序填空。

#include \typedef struct {char vec[MAXLEN];

int len; }str;

void SubStr(Str *s,int i,int j) { int k; Str a;

Str *s1=&a;

if (i+j-1> s->len )

{ cout<< \子串超界!\\n\ return; } else

{ for(k=0; k

s1->vec[k]=s->vec[ i+k-1 ]; s1->len= j ;

s1->vec[s1->len]='\\0'; }

cout<< \取出字符为：\ puts(s1->vec); }

main()

{ cout<< \请输入从第几个字符开始：\ cin>>i;

cout<< \请输入取出的连续字符数：\ cin>>j;

SubStr (s,i,j); }

本文来源：https://www.bwwdw.com/article/j14o.html