习题
一、单项选择题
1. 空串与空格字符组成的串的区别在于（  ）。
A.没有区别                        B.两串的长度不相等
C.两串的长度相等                    D.两串包含的字符不相同
2. 一个子串在包含它的主串中的位置是指（  ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
3. 下面的说法中，只有（  ）是正确的。
A.字符串的长度是指串中包含的字母的个数
B.字符串的长度是指串中包含的不同字符的个数
C.若T包含在S中，则T一定是S的一个子串
D.一个字符串不能说是其自身的一个子串
4. 两个字符串相等的条件是（  ）。
A.两串的长度相等                         
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同
D.两串的长度相等，并且对应位置上的字符相同
5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（  ）。
A. “ijing”                        B. “jing＆” 
C. “ingNa”                        D. “ing＆N”
6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（  ）。
A.2              B.3              C.4                  D.5
7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（  ）。
A. “Nanjing＆Shanghai”            B. “Nanjing＆Nanjing”
C. “ShanghaiNanjing”              D. “Shanghai＆Nanjing”
8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（  ）。
A.i＞0                          B. i≤n     
C.1≤i≤n                      D.1≤字符串长度的正确表示i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（  ）。
A.链表的长度为1
B.链表中只存放1个字符   
C.链表的每个链结点的数据域中不仅只存放了一个字符
D.链表的每个链结点的数据域中只存放了一个字符
二、填空题
1. 两个字符串相等的充要条件是_____________________和___________________。
2. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
3. 串是指___________________。
4. 空串是指___________________，空格串是指___________________。
三、算法设计题
1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m<s，t<(s-m)，并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。
2. 设s和t是表示成单链表的两个串，试编写一个出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。
第三章习题参考答案
一、单项选择题
1．C  2．C  3．B  4．D  5．C    6．A
二、填空题
1．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇
2．2、3
3．O(1)
三、算法设计题
本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：
（1）插入（即入队）算法：
insert(LinkList *rear, elemtype x)
{  //设循环链队列的队尾指针为rear,x为待插入的元素
  LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(rear= =NULL)  //如为空队，建立循环链队列的第一个结点
{  rear=p;
rear->next=p;  //链接成循环链表
}
else  //否则在队尾插入p结点
  {  p->next=rear->next;
rear->next=p;
      rear=p;
}
}
（2）删除（即出队）算法：
delete(LinkList  *rear)
{  //设循环链队列的队尾指针为rear
if (rear= =NULL)  //空队
      printf("underflow\n");
if(rear->next= =rear)  //队中只有一个结点
  { free(rear);
rear=NULL;}
else
  { p=rear->next;
rear->next=rear->next->next;  //rear->next指向的结点为循环链队列的队头结点
free(p);}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。