算法设计技巧与分析答案-

【9A 文】算法设计技巧与分析答案 1、【MeiWei_81 重点借鉴文档】算法设计技巧与分析参考答案第 1 章算法分析基本概念 1.1(a)6(b)5(c)6(d)61.4 算法执行了7+6+5+4+3+2+1=28次比较453324451212241245454545454545333333333333332424242424244545454545451212121212121212121212242424241212121212121224242445241212121.5(a)算法 MODSELECTIONSORT 执行的元素赋值的最少次 2、数是 0,元素已按非降序排列的时候到达最小值。(b)算法MODSELECTIONSORT 执行的元素赋值的最多次数是,元素已按非升序排列的时候到达最小值1.7431256729344444333334121212121212555556667724321 次 9761次 2 次 2 次 6 次 2 次 2 次 由 上 图 可 以 看 到 执 行 的 比 较 次 数 为1+1+2+2+2+6+2=16次。1.1119247519171312118154581113172191348111512715712175211195172481371512217 3、19513114815127 比较均为 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) 4、用 O 符号和符号表示算法 BUBBLESORT 的运行时间：，(f)不行以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示 。1.27 不能用关系来比较和增长的阶。 不是的，即不能用关系来比较和增长的阶。1.32(a)当 n 为 2 的幂时，第六步执行的最大次数是：时，(b)由(a)可以得到：当每一次循环 j 都为 2 的幂时，第六步执行的次数最大，则当〔其中取整〕时，(c)用符号表示的算法的时间冗杂性是已证明 n=2k 的状况，下面证明 n=2k+1 的状况：由于有 5、所以 n=2k+1 时，第六步执行的最大次数仍是 nlogn。(d)用符号表示的算法的时间冗杂性是。当满足取整为奇数时，算法执行的次数是次，其他状况算法执行次数均大于。(e)O 更适合表示算法的时间冗杂性。由于本算法时间冗杂性从到，而是表示精确阶的 。1.38 对个数进行排序。第 5 章归纳法 5.3〔此题不仅有以下一个答...