-习题参考答案

if l>r return -1 else m← (l+r)/2 if K=A[m] return m else if K< A[m] return BSR(A[l..m-1],K) else if K> A[m] return BSR(A[m+1,r],K) 8.设计一个只使用两路比较的折半查找算法，即只用≤和=, 或者只用≥和=. Algorithms TwoWaysBinarySearch(A[o..n-1],K) //二路比较的折半查找 //有序子数组A[l..r]和查找键值K //查找成功则输出其下标，否则输出-1 l←0, r←n-1 while l

=2n+1 7.设计一个算法计算有根有序树的高度. Algorithms height(T) //递归计算有根有序树的高度 //输入:一棵有根有序树的高度T //输出:T的高度 i=NumChildren(T) //根的孩子个数 if i=0 return 0 else return max{height(T1),height(T2),…,height(Ti)}+1 8.下面的算法试图计算一棵二叉树中叶子的数量 Algorithms LeafCount(T) //递归计算二叉树中叶子的数量 //输入:一棵二叉树 //输出:T中叶子的数量 if T=NULL return 0 else return LeafCount(TL)+LeafCount(TR) 应为: if T=NULL return 0 //empty tree else if TL =NULL AND TR=NULL return 1 //single-node tree else return LeafCount(TL)+LeafCount(TR) //general case 习题4.6 1.a.为最近对问题的一维版本设计一个直接基于分治技术的算法,并确定它的效率类型 b.对于这个问题,它是一个好算法吗? 解: a. Algorithms ClosestNumber(A[l..r]) //分治计算最近对问题的一维版本 //输入:升序排列的实数子数组A[l..r] //输出:最近数对的距离 If r=l return ∞ Else if r－l=1 return A[r]－A[l] Else return min{ClosestNumber(A[l… (l+r)/2 ]), ClosestNumber(A[ (l+r)/2 ...r]) A[ (l+r)/2 +1]－A[ (l+r)/2 ] } 设递归的时间效率为T(n): 对n=2k, 则: T(n)=2T(n/2)+c 利用主定理求解.T(n)=Θ(n) 2.(题略) 18

习题5.1

2.a.设计一个递归的减一算法,求n个实数构成的数组中最小元素的位置. b.确定该算法的时间效率,然后把它与该问题的蛮力算法作比较 Algorithms MinLocation(A[0..n-1])

//find the location of the smallest element in a given array //an array A[0..n-1] of real numbers

//An index of the smallest element in A[0..n-1] if n=1 return 0

else temp←MinLocation(A[0..n-2])

if A[temp]1 C(1)=0

4.应用插入排序对序列example按照字母顺序排序

5.a.对于插入排序来说,为了避免在内部循环的每次迭代时判断边界条件j>=0,应该在待排序数组的第一个元素前放一个什么样的限位器? b.带限位器版本和原版本的效率类型相同吗?

解: a. 应该在待排序数组的第一个元素前放-∞或者小于等于最小元素值的元素. b. 效率类型相同.对于最差情况(数组是严格递减):

7.算法InsertSort2(A[0..n-1])

19

for i←1 to n-1 do j←i-1

while j>=0 and A[j]>A[j+1] do swap(A[j],A[j+1]) j←j+1

分析:在教材中算法InsertSort的内层循环包括一次键值赋值和一次序号递减,而算法InsertSort2的内层循环包括一次键值交换和一次序号递减,设一次赋值和一次序号递减的时间分别为ca和cd,那么算法InsertSort2和算法InsertSort运行时间的比率是(3ca+cd)/(ca+cd) 习题5.2 1.a.(略) b.

4.

习题5.3 1.

DFS的栈状态:

退栈顺序: efgbcad 拓扑排序: dacbgfe

20