13．根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid
if low≤high then
mid←?(low?high)/2?
if x=A(mid) then j←mid; endif
if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x 14．作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。 Procedure ThriSearch(A, x, n, j) integer low, high, p1, p2 low←1; high←n while low≤high do p1←?(2low?high)/3? ; p2←?(low?2high)/3? case :x=A(p1): j←p1; return :x=A(p2): j←p2; return :x :else: low←p1+1; high←p2-1 end case repeat j←0 end ThriSearch ?g(n)T(n)= ??T(n/3)?f(n) n足够小否则 g(n)= O(1) f(n)= O(1) 成功: O(1), O(log3(n)), O(log3(n)) 最坏 最好， 平均， 失败: O(log3(n)), O(log3(n)), O(log3(n)) 最好， 平均， 最坏 15．对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。 证明：数学归纳法 ①当n=1时，易知E=2，I=0，所以E=I+2n成立； ②假设n≤k(k>0)时，E=I+2n成立； ③则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展 树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=Ik+2k，考察原树的外部路径长度为Ek+1= Ek-（h-1）+2h，内部路径长度为Ik+1=Ik+（h-1），所以Ek+1= Ik+2k+h+1= Ik+1+2k+2= Ik+1+2(k+1)， 综合①②③知命题成立。 16．以比较为基础（基本操作）的分类算法最坏情况的时间下界是什么？ 答： ?（nlogn） 17对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是什么？简要说明理由。 答： ?log(n?1)? 对线性存储的有序表中元素的以比较为基础的检索算法的执行过程都可以用二元判定树来描述。该树的每个内结点表示一次元素比较，因此对检索的最坏情况而言，该树最少含有n个不同的内结点。检索算法最坏时间不大于该树中由根到一个叶子的最长路径长（树高）。对有n个结点的二元树其最小树高为 ?log(n?1)?，所以对线性存储的有序表中元素的以比较为基础的检索算法最坏时间的下界是?log(n?1)?。 18．简要说明选择问题算法中二次取中值规则的作用。 答：通过选择划分元素V使其尽量靠近元素集合的中间可以得到一个最坏情况时间复杂度是O（n）的选择算法。使用二次取中值规则可以选出满足要求的划分元素V。 19．给出斯特拉森矩阵乘法算法执行时间的递归关系式，并对其求解计算时间复杂度。 答：斯特拉森矩阵乘法算法执行时间的递归关系式为： ?bn?2 T(n)= ? 2n?2?7T(n/2)?an其中a和b是常数。 求解这个递归式，得 T(n)?7[7T(n/4)?a(n/2)]?an?7T(n/4)?an(1?7/4) 2222 ?7[7T(n/8)?a(n/4)]?an(1?7/4) 222?7T(1)?an[1?7/4?(7/4)?...?(7/4)?7?an[(7/4)?1]/(7/4?1)k2kk22k?1] ?(c?1)7?(c?1)nk log7?O(n?O(nlog7) ) 2.8120．通过手算证明（4.9）和(4.10)式确实能得到C11,C12,C21和C22的正确值。 P=(A11+A22)(B11+B22) T=(A11+A12)B22 Q=(A21+A22)B11 U=(A21-A11)(B11+B12) R=A11(B12-B22) V=(A12-A22)(B21+B22) S=A22(B21-B11) C11=P+S-T+V =(A11+A22)(B11+B22) +A22(B21-B11) -(A11+A12)B22 +(A12-A22)(B21+B22) =A11B11+A22B11+A11B22+A22B22+A22B21 -A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22 =A11B11 +A12B21 C12=R+T = A11B12-A11B22 +A11B22+A12B22 = A11B12 +A12B22 C21=Q+S = A21B11+A22B11 +A22B21-A22B11 = A21B11 +A22B21 C22=P+R-Q+U =(A11+A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11 +(A21-A11)(B11+B12) =A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12 -A11B11-A11B12 =A22B22+A21B12 21．过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？ 最好情况：是对有序文件进行排序。 分析：在此情况下归并的次数不会发生变化----log(n)次 归并中比较的次数会发生变化（两个长n/2序列归并） 最坏情况 两个序列交错大小，需要比较n-1次 最好情况 一个序列完全大于/小于另一个序列，比较n/2次 差异都是线性的，不改变复杂性的阶 因此最好情况也是nlogn, 平均复杂度nlogn。 可以说归并分类的时间是Θ(nlogn) 22．写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。 答：见《数据结构》 算法MPass（R，n，1ength．X） MP1 [初始化] i?1 ． MP2 [合并相邻的两个长度为length的子文件] WHILE i ≤ n – 2*length + 1 DO （Merge（R，i，i＋length–l，i＋2*length–1．X）. i?i＋2*length ） ． MP3 [处理余留的长度小于2*length的子文件] IF i+length–1 < n THEN Merge（R，i，i+length–1，n. X） ELSE FOR j = i TO n DO Xj←Rj ▌ 算法MSort(R，n) // 直接两路合并排序算法，X是辅助文件，其记录结构与R相同 MS1 [初始化] length?1 ． MS2 [交替合并] WHILE length < n DO （MPass（R，n，length．X）. length?2*length if length > n then FOR j = 1 TO n DO Rj←Xj else MPass（X，n，length．R）. length?2*length） endif )▌ 23．什么是约束条件？什么是可行解？什么是目标函数？什么是最优解？并举例说明。 答：有一类问题，解由输入的某个子集组成，但是这个子集必须满足某些事先给定的条件。那些必须满足的条件称为约束条件。 满足约束条件的子集称为可行解。 为了衡量可行解的优劣，事先也给出一定的标准，这些标准一般以函数形式给出，称为目标函数。 使目标函数取极值的可行解称为最优解。 26．什么是贪心方法? 给出使用SPARKS语言描述的贪心方法的抽象化控制。 答：对求取最优解问题，选取一种度量标准，将输入按度量标准排序，并按此序
相关推荐：
loading