数据结构单元练习5.doc

单元练习5 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （ㄨ）（1）串是n个字母的有限序列。 （√）（2）串的数据元素是一个字符。 （ㄨ）（3）串的长度是指串中不同字符的个数。 （ㄨ）（4）如果两个串含有相同的字符，则说明它们相等。 （ㄨ）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 （√）（6）串的堆分配存储是一种动态存储结构。 （ㄨ）（7）“DT”是“DATA”的子串。 （ㄨ）（8）串中任意个字符组成的子序列称为该串的子串。 （√）（9）子串的定位运算称为模式匹配。 （√）（10）在链串中为了提高存储密度，应该增大结点的大小。 二．填空题 由零个或多个字符组成的有限序列称为 字符串（或串） 。 字符串按存储方式可以分为：顺序存储、链接存储和 堆分配存储 。 串的顺序存储结构简称为 顺序串 。 串顺序存储非紧凑格式的缺点是： 空间利用率低 。 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。 串链接存储的优点是插入、删除方便，缺点的 空间利用率低 。 在C或C++语言中，以字符 \0 表示串值的终结。 空格串的长度等于 空格的个数 。 在空串和空格串中，长度不为0的是 空格串 。 两个串相等是指两个串相长度等，且对应位置的 字符都相同 。 设S=My Music，则LenStr(s)= _ 8 。 两个字符串分别为：S1=Today is，S2=30 July,2005,ConcatStr(S1,S2)的结果是： Today is 30 July,2005 。 求子串函数SubStr(Today is 30 July,2005,13,4)的结果是： July 。 在串的运算中，EqualStr(aaa,aab)的返回值为 0 。 在串的运算中，EqualStr(aaa,aaa)的返回值为 0 。 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。 模式匹配成功的起始位置称为： 有效位移 。 设S=abccdcdccbaa，T=cdcc， 则第 6 次匹配成功。 设S=c:/mydocument/text1.doc，T= mydont ，则字符定位的位置为 0 。 若n为主串长度，m为子串长度，且nm，则模式匹配算法最坏情况下的时间复杂度为： (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．somethingSomethig 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