第五章  串
一、名词解释
（1）字符串
（2）空白串
(3) 空串
(4)顺序串
(5)链式串
(6)模式匹配
二、判断题（下列各题，正确的请在前面的括号内打“√”；错误的打“╳”）
（ ╳  ）（1）串的长度是指串中不同字符的个数。
（ ╳  ）（2）串是N个字母的有限序列。
（ √  ）（3）空串不等于空白串。
（ ╳  ）（4）如果两个串含相同的字符，则说明它们相等。
（ ╳  ）（5）如果一个串中相同的字符均在另一个串中出现，则说明前者是后者的子串。
（  √ ）（6）串的堆分配存储是一种动态存储结构。
三．填空题
1、设两个字符串分别为：s1=”Today is”,s2=”30 July,2003”,concatstr(s1,s2)的结果：“Today is30 July,2003”
2、通常在程序中使用的字符串可分为串常量和串变量；而字符串按存储方式又可分为 定长顺序存储 、堆分配存储 和 块链存储 等几种。
3、串的顺序存储 非紧凑 格式，一个存储单元只存放字符串中的一个字符，其缺点是浪费存储空间。
4、串的顺序存储紧凑格式优点是 空间利用率高 ，缺点是 对串中字符处理的效率低 。
5、串链接存储优点是插入、删除运算方便 ，缺点是 存储、检索效率低 。
6、两个串相等的充分必要条件是 长度相等，对应字符相同。
7、设S=“A:/Document/Mary.Doc”,则LenStr(s)= 20  ，”/”的字符定位的位置为  3  。
8、子串的定位运算称为串的模式匹配， 主串  称为目标串， 子串 称为模式。
字符串长度17模式串长度
9、设目标T=”abccdcdccbaa”，模式p=”cdcc”,则第 6  次匹配成功。
四．选择题
1． 串是一种特殊的线性表，其特殊体现在（ B  ）。
    A． 可以顺序存储                    B、数据元素是以一个字符
C、可以链接存储                      D、数据元素可以是多个字符
2． 设有两个串p和q，求q在p中首次出现的位置的运算称作（ B  ）
A．链接    B、模式匹配    C、求子串      D、求串长
3．设两个字符串的串值分别为s1=”ABCDEFG”,S2=”PQRST”, 则ConcatStr(SubStr(s1,2,LenStr(s2)),SubStr(s1,LenStr(s2),2))的结果串（ D   ）
A、BCDEF    B、BCDEFG        C、BDPQRST        D、BCDEFEF
4、 串是（  D   ）
A、不少于一个字母的序列        B、任意个字符的序列
    C、不少与一个字符的序列        D、有限个字符的序列
5、 设有两个串s1和s2，求s2在s1中首次出现的位置的运算是（  C  ）
    A、串链接  B、求子串      C、模式匹配        D、串比较
6、 以下论断正确的是（ A  ）
  A、” ” 是空串 ，”  ”是空格串    B、”beijing”是”bei jing”的子串
  C、”something”<” Something”        D、”BIT”==”BITE”
7、 若字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为（ D  ）
  A、20%      B、40%      C、50%    D、33.3%
8． 上题若需提高存储密度至50%，则每个结点应存储（ A  ）个字符（假设字符串的结束标志也占用1个字节）
  A、2          B、3          C、4          D、5
9、 某串的长度小于一个常数，则采用（  B ）存储方式最节省空间。
    A、链式        B、顺序          C、 堆结构          D、无法确定
10、在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ C  ）存储方式比较合适。
      A、链式        B、顺序          C、 堆结构          D、无法确定
五．编程题
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
# define MAXLEN 100
typedef struct
{ char vec[MAXLEN];
int len;
}str;
（1）
Void replace (Str *r, char ch1,char ch2) //将串r中所有值为ch1的字符换成ch2的字符
{ for(int i=0;i<r->len;i++)
  if  (r->vec[i]==ch1)  r->vec[i]=ch2;
return;
}
(2)
Void converse(str *r) //将串r中所有字符按照相反的次序存放在r 中
{ for(int i=0;i<(r->len/2);i++)
  {Char ch=r->vec[i];  r->vec[i]=r->vec[r->len-1-i]; r->vec[r->len-1-i]=ch;}
  Return;
}
(3)
Void delete(str *r,char ch) //从串r中删除其值等于ch的所有字符
{ int i=0; int len=r.len;
While (i<len)
{ if (r->vec[i]==ch}
{ for(j=i; j<len-1; j++)  r->vec[j]=r-vec[j+1];
len--;}
else
  i++;
}
return;
}
(4)
int position(str r1,int index,char r2) //从串r1中第index 个字符起求出首次与字符r2相同的子串的起始位置
{ if (index<1||index>r.len) return ERROR;
int i=index;
while (r,vec[i]!=r2&&i<r.len)  i++;
if (i=r.len)  {cout<<”不存在”;return; }
return i+1;
}
(5)

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