第四章 串 习题4
一、选择题
1. 串是一种特殊的线性表，其特殊性体现在（ ）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符
2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（ ）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength（s2）），subString(s1，Strlength（s2），2)））的结果串是（ ）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的不同，可分为（ ）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和固定分配 6.设串S=“abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。
A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（ ）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（ ）。 A.0123 B.1123 C.1231 D.1211
二丶填空题
1.在空串和空格串中，长度不为0的是（ ）。 2.空格串是指（ ），其长度等于（ ）。 3.按存储结构的不同，串可分为（ ）、（ ）和（ ）。 4.C语言中，以字符（ ）表示串值的终结。
5.在块链串中，为了提高存储密度，应该增大（ ）。
6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（ ）个字节。
7.串操作虽然较多，但都可以通过五中基本操作（ ）、（ ）、（ ）、（ ）和（ ）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（ ），Index（S,T,1）=（ ）。
9.在KMP算法中，next[j]只与（ ）串有关，而与（ ）串无关。 10.字符串“ababaaab”的nextval函数值为（ ）。 11.两个字符串相等的充分必要条件是（ ）。 12.实现字符串复制的函数strcpy为：
Void strcpy（char *s，char*t）//copy t to s {while （ ）{t[i]=s[i],i++,}}
三、问答题与算法题
1.简述下列每对术语的区别。 空串和空格串： 串常量和串变量： 主串和子串：
目标串和模式串。
2.在C语言中假设有如下的串说明：
char s1[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的长度，则插入不执行。 void StrInsert(char *s,char *T,int i)
4.利用C的库函数strlen和strcpy写一个算法删去串S中从位置i开始的连续m个字符。若i≥strlen（S）,则没有字符被删除；若i+m≥strlen（S），则将S中从位置i开始直至末尾的字符均删去。 void StrDelete(char *s, int i,int m)
5.若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 Int indexst(LinkList S, linkList T)
6.在KMP算法中，求下列模式串的next[j]。 (1)“abaabcac”; (2)“aaabaaba”。
7.设目标位t=“abcaabbabcabaacbacba” ，模式为p=“abcabaa” 。 (1)计算模式p的naxtval函数值；
(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 8.写一个递归算法，实现字符串逆序存储，要求不另设串存储空间。
