数据结构课后习题第四章.doc

《数据结构课后习题第四章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串习题4一、选择题1.串是一种特殊的线性表，其特殊性体现在（）。A.可以顺序存储B.数据元素是一个字符C.可以连接存储D.数据元素可以是多个字符2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。A.模式匹配B.联接C.求子串D.求串长3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。A.n²B.（n²/2）+（n/2）C.（n²/2）+（n/2）-1D.（n²/2）-（n/2）-14.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i

2、，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength（s2）），subString(s1，Strlength（s2），2)））的结果串是（）。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF5.顺序串中，根据空间分配方式的不同，可分为（）。A.直接分配和间接分配B.静态分配和动态分配C.顺序分配和链式分配D.随机分配和固定分配6.设串S=“abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。A.8B.37C.36D.357.设主串的长度为

3、n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。A.O(m)B.O（n）C.O（m+n）D.O（n*m）8.已知串S=“aaab”，其next数组值为（）。A.0123B.1123C.1231D.1211二丶填空题1.在空串和空格串中，长度不为0的是（）。2.空格串是指（），其长度等于（）。3.按存储结构的不同，串可分为（）、（）和（）。4.C语言中，以字符（）表示串值的终结。5.在块链串中，为了提高存储密度，应该增大（）。6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。7.串操作虽然较多，但都可以通过五中基本操作（）、（

4、）、（）、（）和（）构成的最小子集中的操作来实现。8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。10.字符串“ababaaab”的nextval函数值为（）。11.两个字符串相等的充分必要条件是（）。12.实现字符串复制的函数strcpy为：Voidstrcpy（char*s，char*t）//copyttos{while（）{t[i]=s[i],i++,}}三、问答题与算法题1.简述下列每对术语的区别。空串和空格串：串常量和串变量：主串和子串：

5、目标串和模式串。2.在C语言中假设有如下的串说明：chars1[30]=“Stocktom”,s2[30]=“March51999”,s3[30]。(1)在执行下列语句后，s3的只是什么？strcpy(s3,s1);strcat(s3,“，”);strcat(s3,s2);(2)调用函数strcmp(s1,s2)的返回值是什么？(3)调用函数strcmp(s1[5],“Ton”)的返回值是什么？(4)调用函数strlen(strcat(s1,s2))的返回值是什么？3.利用C的库函数strlen，strcpy和strcat写一个算法，将串T插入到串S的第i个位置上。若i大于S的长度，则

6、插入不执行。voidStrInsert(char*s,char*T,inti)4.利用C的库函数strlen和strcpy写一个算法删去串S中从位置i开始的连续m个字符。若i≥strlen（S）,则没有字符被删除；若i+m≥strlen（S），则将S中从位置i开始直至末尾的字符均删去。voidStrDelete(char*s,inti,intm)5.若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。Intindexst(LinkListS,linkListT)6.在KMP算法中，求下列模式串的next[j]。(1)“abaabcac

7、”;(2)“aaabaaba”。7.设目标位t=“abcaabbabcabaacbacba”，模式为p=“abcabaa”。(1)计算模式p的naxtval函数值；(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。8.写一个递归算法，实现字符串逆序存储，要求不另设串存储空间。