计算机图形学算法答案(7)

乘法总次数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

1. 对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11

a. 构造它们的开散列表

32

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) c.

33

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