四川理工 算法设计与分析 作者-王红梅期
末考试试题
__________________________________________________ 一章 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 个元素的所有排列对象。
__________________________________________________
四川理工 算法设计与分析 作者-王红梅期末考试试题资料讲解
