算法设计与分析习题解答

第1章算法引论
习题1—1实参交换
习题1—2方法头签名
习题1—3数组排序判定
习题1—4函数的渐近表达式
习题1—5O（1）和O（2）的区别
习题1—6按渐近阶排列表达式
习题1—7算法效率
习题1—8硬件效率
习题1—9函数渐近阶
习题1—10n！的阶
习题1—11平均情况下的计算时间复杂性
算法实现题1—1统计数字问题
算法实现题1—2字典序问题
算法实现题1—3最多约数问题
算法实现题1—4金币阵列问题
算法实现题1—5最大间隙问题
第2章递归与分治策略
习题2—1Hanoi塔问题的非递归算法
习题2—27个二分搜索算法
习题2—3改写二分搜索算法
习题2—4大整数乘法的O（nmlog（3／2）算法
习题2—55次n／3位整数的乘法
习题2—6矩阵乘法
习题2—7多项式乘积
习题2—8不动点问题的O（logn）时间算法
习题2—9主元素问题的线性时间算法
习题2—10无序集主元素问题的线性时间算法
习题2—11O（1）空间子数组换位算法
习题2—12O（1）空间合并算法
习题2—13√n段合并排序算法
习题2—14自然合并排序算法
习题2—15最大值和最小值问题的最优算法
习题2—16最大值和次大值问题的最优算法
习题2—17整数集合排序
习题2—18第k小元素问题的计算时间下界
习题2—19非增序快速排序算法
习题2—20随机化算法
习题2—21随机化快速排序算法
习题2—22随机排列算法
习题2—23算法qSort中的尾递归
习题2—24用栈模拟递归
习题2—25算法select中的元素划分
习题2—26O（nlogn）时间快速排序算法
习题2—27最接近中位数的k个数
习题2—28X和Y的中位数
习题2—29网络开关设计
习题2—30带权中位数问题
习题2—31构造Gray码的分治算法
习题2—32网球循环赛日程表
算法实现题2—1输油管道问题
算法实现题2—2众数问题
算法实现题2—3邮局选址问题
算法实现题2—4马的Hamilton周游路线问题
算法实现题2—5半数集问题
算法实现题2—6半数单集问题
算法实现题2—7士兵站队问题
算法实现题2—8有重复元素的排列问题
算法实现题2—9排列的字典序问题
算法实现题2—10集合划分问题（一）
算法实现题2—11集合划分问题（二）
算法实现题2—12双色Hanoi塔问题
算法实现题2—13标准二维表问题
算法实现题2—14整数因子分解问题
算法实现题2—15有向直线2中值问题
第3章动态规划
习题3—1最长单调递增子序列
习题3—2最长单调递增子序列的O（nlogn）算法
习题3—3漂亮打印
习题3—4整数线性规划问题
习题3—5二维背包问题
习题3—6 Ackermann函数
算法实现题3—1独立任务最优调度问题
算法实现题3—2最少硬币问题
算法实现题3—3序关系计数问题
算法实现题3—4多重幂计数问题
算法实现题3—5编辑距离问题
算法实现题3—6石子合并问题
算法实现题3—7数字三角形问题
算法实现题3—8乘法表问题
算法实现题3—9租用游艇问题
算法实现题3—10汽车加油行驶问题
算法实现题3—11圈乘运算问题
算法实现题3—12最少费用购物
算法实现题3—13最大长方体问题
算法实现题3—14正则表达式匹配问题
算法实现题3—15双调旅行售货员问题
算法实现题3—16最大k乘积问题
算法实现题3—17最小m段和问题
算法实现题3—18红黑树的红色内结点问题
第4章贪心算法
习题4—1 活动安排问题的贪心选择
习题4—2背包问题的贪心选择性质
习题4—3特殊的0—1背包问题
习题4—4程序最优存储问题
习题4—5最优装载问题的贪心算法
习题4—6 Fibonacci序列的Huffman编码
习题4—7最优前缀码的编码序列
习题4—8任务集独立性问题
习题4—9矩阵拟阵
习题4—10最小权最大独立子集拟阵
习题4—11整数边权Prim算法
习题4—12最大权最小生成树
习题4—13最短路径的负边权
习题4—14整数边权Dijkstra算法
算法实现题4—1会场安排问题
算法实现题4—2最优合并问题
算法实现题4—3磁带最优存储问题
算法实现题4—4磁盘文件最优存储问题
算法实现题4—5程序存储问题
算法实现题4—6最优服务次序问题
算法实现题4—7多处最优服务次序问题
算法实现题4—8 d森林问题
算法实现题4—9汽车加油问题
算法实现题4—10 区间覆盖问题
算法实现题4—11硬币找钱问题
算法实现题4—12删数问题
算法实现题4—13数列极差问题
算法实现题4—14嵌套箱问题
算法实现题4—15套汇问题
算法实现题4—16信号增强装置问题
算法实现题4—17磁带最大利用率问题
算法实现题4—18非单位时间任务安排问题
算法实现题4—19多元Huffman编码问题
算法实现题4—20多元Huffman编码变形
算法实现题4—21 区间相交问题
算法实现题4—22任务时间表问题
第5章回溯法
习题5—1装载问题改进回溯法（一）
习题5—2装载问题改进回溯法（二）
习题5—3 0一1背包问题的最优解
习题5—4最大团问题的迭代回溯法
习题5—5旅行售货员问题的费用上界
习题5—6旅行售货员问题的上界函数
算法实现题5—1子集和问题
算法实现题5—2最小长度电路板排列问题
算法实现题5—3最小重量机器设计问题
算法实现题5—4运动员最佳匹配问题
算法实现题5—5无分隔符字典问题
算法实现题5—6无和集问题
……
第6章分支限界法
第7章概率算法
第8章NP完全性理论
第9章近似算法
第10章算法优化策略
第11章在线算法设计
参考文献