单元练习5
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ㄨ）（1）串是n个字母的有限序列。
（√）（2）串的数据元素是一个字符。
（ㄨ）（3）串的长度是指串中不同字符的个数。
（ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。
（ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。
printf函数的执行顺序（√）（6）串的堆分配存储是一种动态存储结构。
（ㄨ）（7）“DT”是“DATA”的子串。
（ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。
（√）（9）子串的定位运算称为模式匹配。
（√）（10）在链串中为了提高存储密度，应该增大结点的大小。
二．填空题
（1）由零个或多个字符组成的有限序列称为 字符串（或串） 。
（2）字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。
（3）串的顺序存储结构简称为 顺序串 。
（4）串顺序存储非紧凑格式的缺点是： 空间利用率低 。
（5）串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。
（6）串链接存储的优点是插入、删除方便，缺点的 空间利用率低 。
（7）在C或C++语言中，以字符 \0 表示串值的终结。
（8）空格串的长度等于 空格的个数 。
（9）在空串和空格串中，长度不为0的是 空格串 。
（10）两个串相等是指两个串相长度等，且对应位置的 字符都相同 。
（11）设S="My Music"，则LenStr(s)= _ 8 。
（12）两个字符串分别为：S1="Today is"，S2="30 July,2005",ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。
（13）求子串函数SubStr("Today is 30 July,2005",13,4)的结果是： July 。
（14）在串的运算中，EqualStr(aaa,aab)的返回值为 <0 。
（15）在串的运算中，EqualStr(aaa,aaa)的返回值为 0 。
（16）在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。
（17）模式匹配成功的起始位置称为： 有效位移 。
（18）设S="abccdcdccbaa"，T="cdcc"， 则第 6 次匹配成功。
（19）设S="c:/mydocument/text1.doc"，T= "mydont "，则字符定位的位置为 0 。
（20）若n为主串长度，m为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复杂度为：
(n-m+1)*m 。
三．选择题
（1）串是一种特殊的线性表，其特殊性体现在（ B ）。
A.可以顺序存储 B．数据元素是一个字符
C.可以链接存储 D．数据元素可以是多个字符
（2）某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。
A．链式 B．顺序 C．堆结构 D．无法确定
（3）以下论述正确的是（ C ）。
A．空串与空格串是相同的 B．"tel"是"Teleptone"的子串
C．空串是零个字符的串 D. 空串的长度等于1
（4）以下论述正确的是（ B ）。
A．空串与空格串是相同的 B．"ton"是"Teleptone"的子串
C．空格串是有空格的串 D. 空串的长度等于1
（5）以下论断正确的是( A )。
A．""是空串，" "空格串 B．"BEIJING"是"BEI JING"的子串
C．"something"<"Somethig" D．"BIT"="BITE"
（6）设有两个串S1和S2，则EqualStr(S1,S2)运算称作( D )。
A. 串连接 B．模式匹配
C. 求子串 D．串比较
（7）串的模式匹配是指（ D ）。
A．判断两个串是否相等 C．某字符在主串中第一次出现的位置
B．对两个串比较大小 D．某子串在主串中第一次出现的第一个字符位置
（8）若字符串"ABCDEFG"采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为( D )。
A．20％ B．40％ C．50％ D．33．3％
（9）若字符串"ABCDEFG"采用链式存储，假设每个指针占用2个字节，若希望存储密度50％，则每个结点应存储( A )个字符。
A．2 B．3 C．4 D．5
（10）设串S1="I AM"，S2="A SDUDENT",则ConcatStr(S1,S2)=( B )。
A．"I AM" B．"I AM A SDUDENT"
C．"IAMASDUDENT" D. "A SDUDENT"
（11）设S=""，则LenStr（S）=（ A ）。
A．0 B．1 C．2 D．3
（12）设目标串T="AABBCCDDE"，模式P="ABCDE"，则该模式匹配的有效位移为 ( A )。
A．0 B．1 C．2 D．3
（13）设目标串T="AABBCCDDEEFF"，模式P="CCD"，则该模式匹配的有效位移为 ( D )。
A．2 B．3 C．4 D. 5
（14）设目标串T="aabaababaabaa"，模式P="abab",朴素匹配算法的外层循环进行了( D )次。
A．1 B．9 C．4 D．5
（15）朴素模式匹配算法在最坏情况下的时间复杂度是( D )。
A．O（m） B．O（n） C．0（m+n） D．0（m*n）
（16）S="morning"，执行求子串函数SubStr(S,2,2)后的结果为( B )。
A．"mo" B．"or" C．"in" D．"ng"
（17）S1="good"，S2="morning"，执行串连接函数ConcatStr(S1,S2)后的结果为( A )。
A．"goodmorning" B．"good morning"
C．"GOODMORNING" D．"GOOD MORNING"
（18）S1="good"，S2="morning"，执行函数SubStr(S2,4,LenStr(S1))后的结果为( B )。
A．"good" B．"ning"
C．"go" D．"morn"
（19）设串S1="ABCDEFG"，S2="PQRST" ,
则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为( D )。
A．BCDEF B．BCDEFG C．BCPQRST D. BCDEFEF
（20）若串S="SOFTWARE"，其子串的数目最多是：（ C ） 。
A．35 B．36 C．37 D．38
（8+7+6+5+4+3+2+1+1=37）
四．程序题填空（每空2分，共50分）
1．下面程序是把两个串r1和r2首尾相连的程序，即：r1=r1+r2，试完成程序填空。
typedef Struct
{ char vec[MAXLEN]; // 定义合并后串的最大长度
int len; // len为串的长度
}St ;
void ConcatStr(Str *r1,Str *r2) // 字符串连接函数
{ int i;
cout << r1->vec<<r2->vec;
if(r1->len+r2->len> MAXLEN )
cout<< "两个串太长，溢出！";
else
{ for(i=0;i< r2->len ;i++) // 把r2连接到r1
r1->vec[ r1->len+i ]=r2->vec[i];
r1->vec[r1->len+i]= '\0' ; // 添上字符串结束标记
r1->len= r1->len+r2->len ; // 修改新串长度
}
}
2. 设x和y两个串均采用顺序存储方式，下面的程序是比较x 和y两个串是否相等的函数，试完成程序填空。
#define MAXLEN 100
typedef struct
{ char vec[MAXLEN]; len;
} str;
int same (x,y)
str *x,*y;
{ int i=0,tag=1;
if (x->len != y->len) return (0); // (或 <> )
else
{ while ( i<x->len && tag )
{ if ( x->vec[i] != y->vec[i] ) tag=0 ;
i++ ; （ 或 i=i+1 ）
}
return (tag);
}
}
3．下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。
解： #include "stdio.h"
typedef struct
{ char vec[MAXLEN];
int len;
}str;
void Palindrome (str s)
{ int i=0;
ing j= s.len-1 ;
发表评论