乘法总次数M(n)
加法总次数A(n)
31
习题7.1
3.假设列表的可能值属于集合{a,b,c,d},用分布计数算法对下面的列表按照字母顺序排序.
b,c,d,c,b,a,a,b
解:
输入A: b,c,d,c,b,a,a,b
频率: 分布值:
4.分布计数算法是稳定的吗? 是稳定的.
因为算法从右至左扫描输入,等值元素也是被从右至左地放入排序好的数组里.
习题7.2
1. 应用Horspool算法在下面的文本中查找模式BAOBAB: BESS_KNEW_ABOUT_BAOBABS 解:字符移动表:
匹配过程:
4.用Horspool算法在一个长度为n的文本中查找一个长度为m的模式,请分别给出下面两种例子.
a.最差输入 b.最优输入 hints:
a. 在n个”0”组成的文本中查找”10..0”(长度为m),查找次数Cw=m(n-m+1) b. 在n个”0”组成的文本中查找由m个”0”组成的模式,查找次数Cb=m
习题7.3
32
1. 对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11
a. 构造它们的开散列表
b. 求在本表中成功查找的最大键值比较次数 c. 求在本表中成功查找的平均比较次数 Hints:
键值列表: 30,20,56,75,31,19 Hash 函数: h(K)=Kmod11 Hash 地址:
开散列表:
b.3(查找键值31) c.
2.(题略)
a. 键值列表: 30,20,56,75,31,19 Hash 函数: h(K)=Kmod11 Hash 地址:
闭散列表:
b.6(查找键值19)
33
c.
34
第8章 动态规划 习题8.1 1.a.动态规划与分治法有什么共同点?(基于分解为更小的子问题) b.这两种技术之间有什么主要的不同点? 分治法分解出的子问题相对独立,而动态规划则相互交叠; 分治法通常不需要保存子问题的结果,而动态规划则保存 2. a.应用动态规划求解C(6,3) b. 为了计算C(n,k),需要填充算法的动态规划表,在填表时是否可以一列接一列地填,而不是一行接一行地填? 解:a. b.可以.每一列从主对线由1开始,自上而下填表. 3.证明: 解: (k?1)k2?k(n?k)?nk?1212k?2k 对n,k>=0,显然: nk?12k2?12k?nk 成立. 对n>=2, 0<=k<=n,则有: nk?112k2?2k?nk?12nk?112k2n?14nk 习题8.2 1.对由下面邻接矩阵定义的有向图,应用warshall算法求它的传递闭包 ?0100?? ?0001???0001? ??0000??解: 35