CH4习题参考答案.docx

CH4习题参考答案习题4解答 判断题： 1空串是由空白字符组成的串 2. 串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。(TRUE ) 3串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。 4串中StrInsert(&S,pos,T)基本操作是最小的操作子集 5.串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(FALSE) (错：子串是主串中连续的字符构成的有限序列) (题源：胡元义，C版数据结构课程辅导与习题解析，p80，4.2.1(判断题)_1) 6.如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。(FALSE) ( 错：是否连续是关键) (题源：陈明，C版实用数据结构基础，p109，(判断题)_2) 7.串类型的最小操作子集不能利用其他串操作来实现，反之，其他串操作均可在最小操作子集上实现。(TRUE) (题源：根据教材p72自编) 单项选择题： 8下列那些为空串 A）S=“ ” B）S=“” C）S=“” D）S=“” 答案：B 9S1=“ABCD”，S2=“CD”则S2在S3中的位置是 A）1 B）2 C）3 D）4 答案：C 10.假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是 A）2 B）6 C）11 D）0 答案：B 11.在串中，对于SubString(&Sub,S,pos,len)基本操作，pos和len的约束条件是 A）0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1 B）0<pos<StrLength(S)+1且0<=len<=StrLength(S)-pos-1 C）1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D）1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-1 答案：C 12. 串是一种特殊的线性表，其特殊性体现在( )。 (题源：李春葆，C版题解，p102，4.2.1(单选)_2) A可以顺序存储 B. 数据元素是一个字符 C可以链接存储 D. 数据元素可以是多个字符 答：B 1 13. 串是( )。 (题源：陈明，C版实用数据结构基础，p109，习题(单选)_1) A少于一个字母的序列 B. 任意个字母的序列 C不少于一个字符的序列 D. 有限个字符的序列 答：D 14. 串的长度是( )。 (题源：陈明，C版实用数据结构基础，p109，习题(单选)_3) A串中不同字母的个数 B. 串中不同字符的个数 C串中所含的字符的个数 D. 串中所含字符的个数，且大于0 答：C 15. 设有S1=ABCDEFG，S2=PQRST，函数con(x，y)返回x和y串的连接串，subs(I，j)返回串S的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2)，subs(S1，len(S2)，2)的结果是( )。 (题源：李春葆，C版题解，p102，4.2.1(单选)_4) ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答：D 16. 若某串的长度小于一个常数，则采用( )存储方式最为节省空间。 (题源：胡元义，C版数据结构课程辅导与习题解析，p90，4.3.1习题(4.3) A链式 B. 堆结构 C. 顺序表 答：C 填空题： 17串是每个结点仅由一个字符组成的。 答：线性表 18在串中，SubString (“student”,5,0) 的结果是 答：“” 19假设S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace (S,T,V)结果是 答：“axaxaax” 20在串中，对于StrCompare(S,T)基本操作，若S<T，返回值 答：<0 21在串顺序存储结构中，实现串操作的原操作为 答：字符序列的复制 22. 串与线性表在逻辑结构上极为相似，区别仅在于 ；在基本操作上差别很大，线性表的基本操作大多数以 作为操作对象，而串的基本操作通常以 作为操作对象。 (题源：根据教材p71页自编) 答：串的数据对象约束为字符集 “单个元素” “串的整体” 23两个串相等的充分必要条件是 且 。 (题源：根据教材p70页自编) 答：两个串的串长相等 各个对应位置的字符都相等 24.空串是指_，空格串是指_。 (题源：宁正元C版题解p40(4.1(填空)_5 ) 答：不含任何字符的串 仅含空格字符的串 2 简答题： 25已知串s=(xyz)*，t=(x+z)*y，试利用串的基本运算将s串转化为t串，t串转化为s串。 (题源：宁正元，C版题解，p40，4.2_3) 答：concat ( replace (substring (sub,s,1,5),y,+), replace (substring (sub,s,6,1),*，*y) concat(replace(substring(sub,t,1,5),+,y),replace(substring(sub,t,6,2),*y,*) 26串是字符组成的，长度为1的串和字符是否概念相同？为什么？ (题源：朱战立，C版题解，p86，4.2.1(典型题解)_2) 答：由于字符的长度固定为1，长度概念可以隐含，所以存储时只需存储该字符即可；而长度为1的串其长度概念不能隐含，必须显示地表示出来，所以存储时要同时存储该字符和值为1的长度值。 算法设计题： 27设串s和串t采用顺序存储结构，编写函数实现串s和串t的比较操作，要求比较结果包括大于、小于和等于三种情况。 (题源：朱战立，C版题解，p87，4.2.1(典型题解)_7) 提示 算法思想：循环逐个比较两个串，一旦两个串的某个字符比较不相等则说明两个串不相等，此时进一步比较这两个不相等字符的大于和小于情况来决定串s和串t比较的大于和小于情况；当串s的n个字符和串t的m个字符比较全部相等时，还需进一步判断此时串s或串t是否还有剩余字符没有比较，来决定串s和串t比较的大于和小于情况；若所有字符比较均相等，并且串s的字符个数n和串t的字符个数m也相等时，说明串s等于串t。当串s大于串t时函数返回1，当串s小于串t时函数返回-1，当串s等于串t时函数返回 0。 解：int StrCompare(SStrType s,SStrType t) int n=s.length, m=t.length, i,j,tag; i=0; j=0; while(i<n &&j<m) if(s.stri=t.strj) /*继续比较下一个字符*/ i+;j+; else if(s.stri>t.strj) tag=1; /*说明s>t,退出比较*/ return tag; else tag=-1; /*说明s<t，退出比较*/ return tag; 3 if(n=m) tag=0; /*若所有字符比较均相等则tag=0*/ else if(n>m) tag=1; /*若串t只和串s的前m个字符相等则s>t*/ else if(n<m) tag=-1;/*若串s只和串t的前n个字符相等则s<t*/ return tag; 28输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。 (题源：宁正元，C版题解，p44，4.2_12) 提示：要统计单词的个数先要解决如何判断一个单词，应该从输入行的开头一个字符一个字符地去辨别。假定把一个文本行放在数组r中，那么就相当于从r0开始逐个检查数组元素，当经过若干个空格符之后，找到第一个字母就是一个单词的开头，此时利用一个统计计数器进行累加1运算，在此之后若连续读到的是非空格符，则这些字符属于刚统计到的那个单词，因此不应将计数器累加1，下一次计数应该是在读到一个或几个空格后再遇到非空格字符之时进行。因此，统计一个单词时不仅要满足当前所检查的这个字符是非空格，而且要满足所检查的前一个字符是空格。 解：int count(r) char r80; char prec,nowc; int num,j; prec= ; num=0; for(j=0;j<80;j+) nowc=rj; if(nowc!= )&&(prec= ) num+; prec=nowc; return num; /*count*/ 29编写算法，求串s所含不同字符的总数和每种字符的个数。 (题源：严蔚敏，C版习题集，p29，4.18) 解：typedef struct char ch; int num; mytype; void StrAnalyze(Stringtype S) /统计串S中字符的种类和个数 mytype TMAXSIZE; /用结构数组T存储统计结果 for(i=1;i<=S0;i+) 4 c=Si;j=0; while(Tj.ch && Tj.ch!=c) j+; /在结构数组T中逐元素查找当前字符c是否已记录过. /当循环停止时，再看是什么原因造成的停止。 if(Tj.ch) Tj.num+; /循环停止时Tj.ch不等于NULL,说明是由于Tj.ch=c所致 /若是 Tj.ch =c所致则说明字符c在串s中已经出现过 /故将其个数加1. else Tj=c,1; /否则为首次出现，将其出现次数记为1. /for for(j=0;Tj.ch;j+) /打印每个字符在串s中的出现次数。 printf(“%c: %dn”,Tj.num); /StrAnalyze 5