精品好文档，推荐学习交流
一章 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
仅供学习与交流，如有侵权请联系网站删除 谢谢1
精品好文档，推荐学习交流
6 . 为 3 .4 .1 节中生成排列对象算法设计程序上机实现 , 能对这个算法进行改进吗 ? 7 . 最近对问题也可以以 k 维空间的形式出现 , k 维空间中的两个点
维空间的最近对 问题设计蛮力算法 , 并分析其时间性能。
8 . 对于一个平面上 n 个点的集合 S , 设计蛮力算法求集合 S 的凸包的一个极点。
四章 1、3、棋盘覆盖、最大子段和
1 . 设计分治算法求一个数组中最大元素的位置 , 建立该算法的递推式并求解 。 3 . 设计递归算法生成 n 个元素的所有排列对象。 五8
章
3
、
6
、
3 . 拿子游戏 。考虑下面这个游戏 : 桌子上有一堆火柴 , 游戏 开始时共有 n 根火柴 ,
仅供学习与交流，如有侵权请联系网站删除 谢谢2
精品好文档，推荐学习交流
两个玩家轮流拿走 1、2 、3 或 4 根火柴 , 拿走 最后一根火柴的玩家为获胜方。请为先走的玩家设计一个制胜的策略( 如果该策略存在) 。
6 . 在 120 枚外观相 同的硬 币中, 有一枚是假 币, 并且 已知假 币与真 币的重量不 同, 但不知道假 币与真 币相 比较轻还是较重。可 以通过一架天平来任意比较两组硬 币, 最坏情 况下, 能不能只比较 5 次就检测出这枚假 币 ?
8 . 竞赛树是一棵完全二叉树 , 它反映了一系列“淘汰赛”的结果 : 叶子代表参加 比赛 的 n 个选手 , 每个 内部结点代表 由该结点的孩子结点所代表的选手中的胜者 , 显然 , 树的
根结点就代表了淘汰赛的冠军。请 回答下列问题 : ( 1) 这一系列的淘汰赛中比赛的总场数是多少 ?
(2 ) 设计一个高效的算法 , 它能够利用 比赛中产生的信息确定亚军。
六章 1、2、TSP、多段图
仅供学习与交流，如有侵权请联系网站删除 谢谢3
精品好文档，推荐学习交流
1 . 动态规划法和分治法之间有什么共 同点 ? 有什么不同点 ?
2 . 用动态规划法求图中从顶点 0 到顶点 15 的最短路径 , 写出求解过程 。
七章 TSP、图着色
八章 1、4、背包问题、TSP
1 . 用递归函数设计 图着色 问题的回溯算法。
4 . 对 图 8 .14 使用回溯法求解 图着色 问题 , 画 出生成的搜索空间。
勾股
定理专题
考点一 证明三角形是直角三角形
仅供学习与交流，如有侵权请联系网站删除 谢谢4
精品好文档，推荐学习交流
例1、已知：如图，在△ABC中，CD是AB边上的高，且CD=AD·BD.求证：△ABC是直角三角形.
2
针对训练：1、已知：在△ABC中，∠A、∠B、∠C的对边分别是a、b、c，满足a+b+c+338=10a+24b+26c.试判断△ABC的形状.
2、如图，已知：在ΔABC中，?C=90?，M是BC的中点，MD?AB于D，求证：AD=AC+BD.
A 2
2
2
2
2
2
D C M B 考点二 运用勾股定理的逆定理进行计算 例2、如图，等腰△ABC中，底边BC＝20，D为AB上一点，CD＝16，BD＝12，
求△ABC的周长。
仅供学习与交流，如有侵权请联系网站删除 谢谢5
最新四川理工 算法设计与分析 作者-王红梅期末考试试题
