算法设计与分析基础第七章作业(共5页).docx

精选优质文档-倾情为你奉上第七章习题7.11. 分步计数算法是稳定的吗？解：分步计数算法是稳定的。习题7.23.用Horspool算法在一个1000个0构成的二进制文本中查找下列模式时，分别需要进行多少次字符比较？a.00001;b.10000;c.01010;5解：a.字符c01移动距离t(c)15比较次数：(1000/5)*1=200b.字符c01移动距离t(c)14比较次数：(1000-5+1*5=4980 c.字符c01移动距离t(c)21比较次数：(1000-3)/2*2=996 (1000-3)/2取整数部分4.用Horspool算法在一个长度为n的文本中查找一个长度为m(n=m)的模式。请分别给出下面两种例子。a.最差输入；b.最优输入。解：a.模式的每次一移动的举例均为1，且没有匹配成功，或者到最后一次匹配才成功。b.模式不需要移动，且比较了m次即成功。7.