一章 7、10
7 . 使用扩展递归技术求解下列递推关系式 :
二章 1、3、5
1 . 求下列问题的平凡下界, 并指出其下界是否紧密。 ( 1) 求数组中的最大元素;
(2 ) 判断邻接矩阵表示的无向图是不是完全 图; ( 3 ) 确定数组中的元素是否都是惟一的; (4 ) 生成一个具有 n 个元素集合的所有子集 。 3 . 画出在 3 个数 a , b, c 中求中值 问题的决策树 。
5 . 假设某算法的时间复杂性为 T( n) = 2n , 在计算机 C1 和 C2 上运行这个算法 , C2 的速度是 C1 的 100 倍 。若该算法在 C1 上运行的时间为 t , 可处理的问题规模为 n , 在 C2上运行同样的时间可处理的问题规模是多少 ? 如果 T ( n) = n^2, 在 C2 上运行 同样的时间可处理的问题规模是多少 ? 3: 6、7、8
6 . 为 3 .4 .1 节中生成排列对象算法设计程序上机实现 , 能对这个算法进行改进吗 ? 7 . 最近对问题也可以以 k 维空间的形式出现 , k 维空间中的两个点
维空间的最近对 问题设计蛮力算法 , 并分析其时间性能。
8 . 对于一个平面上 n 个点的集合 S , 设计蛮力算法求集合 S 的凸包的一个极点。
四章 1、3、棋盘覆盖、最大子段和
1 . 设计分治算法求一个数组中最大元素的位置 , 建立该算法的递推式并求解 。 3 . 设计递归算法生成 n 个元素的所有排列对象。 五
章
3
、
6
、
8
3 . 拿子游戏 。考虑下面这个游戏 : 桌子上有一堆火柴 , 游戏开始时共有 n 根火柴 , 两个玩家轮流拿走 1、2 、3 或 4 根火柴 , 拿走最后一根火柴的玩家为获胜方。请为先
走的玩家设计一个制胜的策略( 如果该策略存在) 。
6 . 在 120 枚外观相 同的硬 币中, 有一枚是假 币, 并且 已知假 币与真 币的重量不 同, 但不知道假 币与真 币相 比较轻还是较重。可 以通过一架天平来任意比较两组硬 币, 最坏情况下, 能不能只比较 5 次就检测出这枚假 币 ?
8 . 竞赛树是一棵完全二叉树 , 它反映了一系列“淘汰赛”的结果 : 叶子代表参加 比赛的 n 个选手 , 每个 内部结点代表 由该结点的孩子结点所代表的选手中的胜者 , 显然 , 树的
根结点就代表了淘汰赛的冠军。请 回答下列问题 : ( 1) 这一系列的淘汰赛中比赛的总场数是多少 ?
(2 ) 设计一个高效的算法 , 它能够利用 比赛中产生的信息确定亚军。
六章 1、2、TSP、多段图
1 . 动态规划法和分治法之间有什么共 同点 ? 有什么不同点 ?
2 . 用动态规划法求图中从顶点 0 到顶点 15 的最短路径 , 写出求解过程 。
七章 TSP、图着色
八章 1、4、背包问题、TSP
1 . 用递归函数设计 图着色 问题的回溯算法。
4 . 对 图 8 .14 使用回溯法求解 图着色 问题 , 画 出生成的搜索空间。