串(习题答案).doc

第五章 串一、 名词解释（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、子串的定位运算称为串的模式匹配， 主串 称为目标串， 子串 称为模式。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、BCDEFEF4、 串是（ 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、59、 某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A、链式 B、顺序 C、 堆结构 D、无法确定10、在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ C ）存储方式比较合适。 A、链式 B、顺序 C、 堆结构 D、无法确定五编程题1 设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写下列算法：# define MAXLEN 100typedef struct char vecMAXLEN;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 100typedef struct char vecMAXLEN;int len;str;（1）Void replace (Str *r, char ch1,char ch2) /将串r中所有值为ch1的字符换成ch2的字符 for(int i=0;ilen;i+) if (r-veci=ch1) r-veci=ch2; return;(2)Void converse(str *r) /将串r中所有字符按照相反的次序存放在r 中 for(int i=0;ilen/2);i+) Char ch=r-veci; r-veci=r-vecr-len-1-i; r-vecr-len-1-i=ch; Return;(3)Void delete(str *r,char ch) /从串r中删除其值等于ch的所有字符 int i=0; int len=r.len;While (iveci=ch for(j=i; jvecj=r-vecj+1; len-; else i+;return;(4) int position(str r1,int index,char r2) /从串r1中第index 个字符起求出首次与字符r2相同的