版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计技巧与分析答案精品文档算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a)6(b)5(c)6(d)61.4算法执行了 7+6+5+4+3+2+1=28次比较4 3 2 4 1 1 2 11 3 2 4 4 1 2 11 1 2 4 4 3 2 11 1 1 4 4 3 2 21 1 1 2 4 3 4 21 1 1 2 2 3 4 41 1 1 2 2 3 4 41 1 1 2 2 3 4 41.5(a)算法MODSELECTIONSORT 执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。收集于网络,如有侵权请联系管理员删除精品文档(b)算法MODSELECTIONSORT执行的元素赋值的最多次数是3n(n1),元素已按非升序排列的时候达到最小值。21.7431567291次341次3412次34512次345612次3456716次23456712次23456791由上图可以看到执行的比较次数为 1+1+2+2+2+6+2=16次。1.11收集于网络,如有侵权请联系管理员删除精品文档比较9次24578111111比较为624581111711比较为3251148117112 1 5 1 1 1 4 8 1 1 7比较均为2 1 19 5 1 1 4 8 15 1 7由上图可以得出比较次数为 5+6+6+9=26次。1.13FTF,TTT,FTF,TFF,FTF1.16执行该算法,元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b)执行该算法,元素比较的最多次数是n(n1)。元素已2按非升序排列时候达到最大值。执行该算法,元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d)执行该算法,元素赋值的最多次数是3n(n1)。元素已2按非升序排列时候达到最大值。(e)n用O符号和符号表示算法BUBBLESORT的运行时间:tO(n2),t(n)收集于网络,如有侵权请联系管理员删除精品文档(f)不可以用 符号来表示算法的运行时间: 是用来表示算法的精确阶的,而本算法运行时间由线性到平方排列,因此不能用这一符号表示。1.27不能用p关系来比较 n2和100n2增长的阶。∵limn2120n100n100n2不是o(100n2)的,即不能用 p关系来比较 n2和100n2增长的阶。1.32(a)当n为2的幂时,第六步执行的最大次数是:n2k,j2k1时,nnk[logn]nlogni1i1(b)由(a)可以得到:当每一次循环j都为2的幂时,第六步执行的次数最大,则当n3k,j3k2m(其中3k取整)时,22nnmi[log(3k1)]nlog(n1)i1i1(c)用 符号表示的算法的时间复杂性是 O(nlogn)已证明n=2k的情况,下面证明n=2k+1的情况:因为有2k2k122所以n=2k+1时,第六步执行的最大次数仍是 nlogn。收集于网络,如有侵权请联系管理员删除O(nlogn)精品文档用符号表示的算法的时间复杂性是(n)。当n满足jn/2取整为奇数时,算法执行的次数是n次,其他情况算法执行次数均大于n。O更适合表示算法的时间复杂性。因为本算法时间复杂性从 (n)到 ,而 是表示精确阶的。1.38对n个数进行排序。第5章归纳法5.3(本题不仅有以下一个答案)1.max(n)过程:max(i)ifn=1returna[1]t=max(i-1)ifa[i-1]>treturna[i-1]elsereturntendif收集于网络,如有侵权请联系管理员删除精品文档5.6最多次数:0,n 1C(n)c(n 1) (n 1),n 2n(n1)C(n) jj1 2最少次数:0,n 1C(n)C(n 1) 1,n 2C(n)=n-15.7参考例5.15.14(a)不稳定,例如:1 4 4 21 4 4 21 2 4 41 2 4 4可见SELECTIONSORT中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用
Pn(x) xPn1(x) a0收集于网络,如有侵权请联系管理员删除精品文档取x3,P5(3)P4(3)P3(3)P2(3)P1(3)P0(3)P2(3)3*P1(3)437P1(3)3*P0(3)211P0(3)3P3(3)3*P2(3)1112P4(3)3*P3(3)2338P5(3)3*P4(3)510195.18(a)p(2,5)p(2,2)p(2,1)p(2,0)y42*2y224y12*2y1第6章分治6.3输入:A[1,2, n]输出:max,min1.fori=1tomidj=high-iifa[i]>a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomidifa[i+1]<a[low],thenexchangea[low],a[i+1]7.endfor8.fori=mid+1tohighifa[i+1]>a[high],thenexchangea[high],a[i+1]10.endfor6.5收集于网络,如有侵权请联系管理员删除精品文档输入:一个整数数组 A[1,2, ,n]输出:sum1.ifhigh-low=1thensum=a[low]+a[high]3.elsemid=(low+high)/2sum1=sum(low,mid)sum2=sum(mid+1,high)sum=sum1+sum28.endif9.returnsum算法需要的工作空间为 3收集于网络,如有侵权请联系管理员删除精品文档6.10.收集于网络,如有侵权请联系管理员删除精品文档31111125111112353114111251115311253111112513111125311111253111112512115341231111181223345121153412311112535112341211534123111219351241312115341231125115314231121541121541收集于网络,如有侵权请联系管理员删除精品文档6.312 1 3 1 4 1 1 52 1 3 1 4 1 1 52 1 3 1 4 1 1 52 1 1 3 4 1 1 52 1 1 3 4 1 1 52 1 1 1 4 3 1 52 1 1 1 1 3 4 51 1 1 1 2 3 4 5彩色代表i,j所指的数字j总在i前6.36收集于网络,如有侵权请联系管理员删除精品文档23214161112511111112342256111111111111111111111111111132452725526325273245526325 2725 27272745 52 6345 52 6352 6352 6363收集于网络,如有侵权请联系管理员删除 6311 12 14 16 18 19 23 25 27 32 45 52 6精品文档6.42Quicksort不是稳定的。6.43bcefg均为适应的,a、h不是适应的。第7章动态规划7.1(c),算法BOTTOMUPSORT7.5字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列长度为 4,共有6个最长公共子序列,分别是:① zyyx②zyzz③zyzx④xyyx⑤xyzz⑥xyzx7.9C[1,5]=C[1,1]+C[2,5]+r[1]*r[2]*r[6]=307C[1,5]=C[1,2]+C[3,5]+r[1]*r[3]*r[6]=252C[1,5]=C[1,3]+C[4,5]+r[1]*r[4]*r[6]=372C[1,5]=C[1,4]+C[5,5]+r[1]*r[5]*r[6]=260所以最优括号表达式为( M1M2)((M3M4)M5)7.150513D1[i,j]min{D0[i,j],D0[i,1]D0[1,j]}120911D4402316200716D10940241820D2[i,j]min{D1[i,j],D1[i,2]D1[2,j]}收集于网络,如有侵权请联系管理员删除精品文档0716D20940241820D3[i,j]min{D2[i,j],D2[i,3]D2[3,j]}0513130911D340241620D4[i,j]min{D3[i,j],D3[i,4]D3[4,j]}0513120911D4402316207.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23当物品体积为负值时,运行算法会发生溢出错误。第八章贪心算法8.121sa23t收集于网络,如有侵权请联系管理员删除精品文档由算法从s到t要选择先到a然后到t,其结果为4,而从s到t距离为2,所以探索不总是产生从 s到t的距离8.1319224114532641351593192241145326413515932019224114532641931554133811922614145326241835154313
8192241145326413515438119226154221436841351543138.23(共有4棵最小生成树,此处仅举一例)收集于网络,如有侵权请联系管理员删除精品文档135135135246
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 民政职业技能鉴定(墓地管理员、殡葬管理)考试题库及答案
- 2026年一级注册建筑师之建筑设计考试题库及答案
- 2026年行车工考试题库及答案
- 2026年植物生长模拟试题模拟试卷带答案
- 2026年渭柳中学笔试题库及答案
- 2026年养老财务规划师考试题库及参考答案
- 水利五大员施工员质检员资料员材料员安全员考试题库带答案
- 2026年驾考宝典科一题库及答案
- 2026年15二建水利模拟试题带答案
- 2026年叉车锦州模拟考试卷带答案
- 学校各岗位消防安全的责任书
- 2026年国家电网招聘之其他工学类考试题库(含答案)
- 2026全国税收执法资格考试题库及答案
- 2026年职业技能鉴定国家题库维修电工中级理论知识题库及答案
- 2026年海南省中考数学试卷真题及答案详解(精校打印版)
- T/HAEPCI 115-2019重金属矿山酸性废水污染控制技术规范
- 甲状腺癌教学课件
- 智能机器人设计与实践(北京航空航天大学)知到智慧树章节测试掌握度答案
- 2026年突发环境事件应急笔试试题(含答案)
- 石油化工自动化仪表选型设计规范
- 《土木工程制图》-02-投影基础课件
评论
0/150
提交评论