1、7291次2次6次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。1.1119171311815比较均为1次,共5次比较为3次,2次,1次比较为6次比较9次由上图可以得出比较次数为5+6+6+9=26次。1.13FTF,TTT,FTF,TFF,FTF1.16(a) 执行该算法,元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b) 执行该算法,元素比较的最多次数是。元素已按非升序排列时候达到最大值。(c) 执行该算法,元素赋值的最少次数是0。(d) 执行该算法,元素赋值的最多次数是。(e)用O符号和符号表示算法BUBBLESORT的运行时间:,(f)不可以用符号
2、来表示算法的运行时间:是用来表示算法的精确阶的,而本算法运行时间由线性到平方排列,因此不能用这一符号表示。1.27不能用关系来比较和增长的阶。不是的,即不能用关系来比较和增长的阶。1.32(a)当n为2的幂时,第六步执行的最大次数是:时,(b)由(a)可以得到:当每一次循环j都为2的幂时,第六步执行的次数最大,则当(其中取整)时,(c)用符号表示的算法的时间复杂性是已证明n=2k的情况,下面证明n=2k+1的情况:因为有所以n=2k+1时,第六步执行的最大次数仍是n log n。(d) 用符号表示的算法的时间复杂性是。当满足取整为奇数时,算法执行的次数是次,其他情况算法执行次数均大于。(e)
3、O更适合表示算法的时间复杂性。因为本算法时间复杂性从到,而是表示精确阶的。1.38对个数进行排序。第5章 归纳法5.3(本题不仅有以下一个答案)1.max(n) 过程:max(i)if n=1 return a1t=max(i-1)if ai-1t return ai-1else return t end if 5.6最多次数:最少次数:C(n)=n-15.7参考例5.15.14(a)不稳定,例如:可见SELECTIONSORT中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用取,5.18(a) 第6章 分 治6.3输入:A1,2,n输出:max,min1.for i=
4、1 to mid2. j=high-i 3. if aiaj, then exchange ai,aj4.end for5.for i=low to mid6. if ai+1ahigh, then exchange ahigh,ai+110.end for6.5一个整数数组A1,2,nsum1.if high-low=1 then2. sum=alow+ahigh3.else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+sum28.end if9.return sum算法需要的工作空间为36.1
5、0.32142551323718226.3127311653彩色代表i,j所指的数字j总在i前6.362363526.42Quicksort不是稳定的。6.43bcefg均为适应的,a、h不是适应的。第7章 动态规划7.1(c),算法BOTTOMUPSORT7.5字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列长度为4,共有6个最长公共子序列,分别是:zyyx zyzz zyzx xyyx xyzz xyzx7.9C1,5=C1,1+C2,5+r1*r2*r6=307C1,5=C1,2+C3,5+r1*r3*r6=252C1,5=C1,3+C4,5+r1*r4*r6=372C1,5=C1,4+C5,5+r1*r5*r6=260所以最优括号表达式为(M1M2)(M3M4)M5)7.157.211107.23当物品体积为负值时,运行算法会发生溢出错误。第八章贪心算法8.12ats由算法从s到t要选择先到a然后到t,其结果为4,而从s到t距离为2,所以探索不总是产生从s到t的距离8.1320288.23(共有4棵最小生成树,此处仅举一例)8.24(共有4棵最小生成树,此处仅举一例)8.3138dcbfe每一个二叉树都取左边为0,右边为1则最优编码为a:10 b:001 c:0001 d:0000 e:01 f:注意:编码不唯一回溯法
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2