算法设计与分析基础习题参考答案

5.a.

二叉查找树中最大值和最小值分别是树中最右边和最左边的结点.因此,从根开始,沿着向左的路径一直走到这样的结点:它的左孩子为空.这个结点里的值就是最小值.同理,可以找到最大值.最后,这两个值做一次减法运算即可. 算法的效率: Θ(logn)+ Θ(logn)+ Θ(1)= Θ(logn) b.错误.

8.

不成立.

例如:列表{A,B},查找A,二分查找只做1次比较.而在2-3树中查找则要做2次比较 习题6.4 1.

29

a.b. c. 错误.对于列表{1,2,3} 按自顶向下:{3,1,2} 自底向上:{3,2,1} 5.a.设计一个算法,寻找并删除堆中最小元素,然后确定其时间效率 Hints: 最小元素一定在堆的叶子中. 在堆H[1..n]的后半部分,(H[ n/2 +1],?,H[n])中查找最小元素,并与最后的元素H[n]互换,删除最后的元素.堆规模降1,如果必要的话,调整元素H[n],使其满足双亲优势. 效率分析: 查找:Θ(n) 交换并删除: Θ(1)+ Θ(1) 调整为堆:O(logn) b.设计一个算法,在给定的堆H中寻找并删除一个包含给定值v的元素,然后确定其时间效率. Hints: 在H中顺序查找满足条件的第一个元素H[i]. H[i]与H[n]互换. 删除最后元素 堆规模降1 调整元素H[n]使其满足双亲优势 效率分析: 查找:Θ(n) 交换并删除: Θ(1)+ Θ(1) 调整为堆:O(logn) 习题6.5 1. 30

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