第七章
习题7.1
1.分步计数算法是稳定的吗？
解：
分步计数算法是稳定的。

习题7.2
3.用Horspool算法在一个1000个0构成的二进制文本中查找下列模式时，分别需要进行多少次字符比较？
a.00001;
b.10000;
c.01010;
5
解：
a.
比较次数：(1000/5)*1=200
b.
比较次数：[(1000-5+1]*5=4980
c.
比较次数：[(1000-3)/2]*2=996 (1000-3)/2取整数部分
4.用Horspool算法在一个长度为n的文本中查找一个长度为m(n>=m)的模式。

请分别给出下面两种例子。

a.最差输入；
b.最优输入。

解：
a.模式的每次一移动的举例均为1，且没有匹配成功，或者到最后一次匹配才成功。

b.模式不需要移动，且比较了m次即成功。

7.用Boyer-Moore算法在一个1000个0构成的二进制文本中查找
列模式时，分别需要进行多少次字符比较？
a.00001;
b.10000;
c.01010;
解：
a.
坏符号移动表：
后缀移动表：
d1=max{t1(0),1}=1,d2=5
模式移动max(d1,d2)=5，所以每次移动5位，且每次只比较一次。

比较次数为:1000/5=200
b.
坏符号移动表：
后缀移动表：
d1=max{t1(0)-4,1}=1,d2=1
模式移动max(d1,d2)=1,所以每次都移动一位，比较5次。

比较次数：[(1000-5+1]*5=4980
c.
坏符号移动表：
后缀移动表：
d1=max{t1(0)-1,1}=1,d2=2
模式移动max(d1,d2)=2,所以每次都能移动2位，比较2次。

比较次数：[(1000-3)/2]*2=996
习题7.3
2.对于输入30,20,56,75,31,19和散列函数h(K)=K mod11
a.构造它们的闭散列表；
b.求在本表中成功查找的最大键值比较次数；
c.求在本表中成功查找的平均键值比较次数；
解：a.
b.最大的键值是19，k(19)=8，先将散列地址为8的中的键30与75比较，其次是散列地址为10的75与75比较，所以成功查找的比较次数是6。

c.
查找成功的平均键值比较次数为：(1+1+1+2+3+6)/6=7/3。