算法设计与分析试卷(2010)

算法设计与分析试卷(A卷)

一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分）

（1）计算机算法的正确描述是： B、D

A．一个算法是求特定问题的运算序列。

B．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。

C．算法是一个对任一有效输入能够停机的图灵机。

D．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C、D

A．算法设计的策略 B．问题的规模

C．编译程序产生的机器代码质量 D．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A

A．时间复杂度 B．空间复杂度 C．处理器复杂度 D．通信复杂度 （4）时间复杂性为多项式界的算法有：

A．快速排序算法 B．n-后问题 C．计算?值 D．prim算法 （5）对于并行算法与串行算法的关系，正确的理解是：

A．高效的串行算法不一定是能导出高效的并行算法 B．高效的串行算法不一定隐含并行性

C．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A

A．算法复杂度 B．问题复杂度 C．解的最优近似度 D．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD

A．该问题的规模缩小到一定的程度就可以容易地解决； B．该问题可以分解为若干个规模较小的相同问题；

C．利用该问题分解出的子问题的解可以合并为该问题的解 D．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有：

A．概率算法 B．回溯法 C．分支限界法 D．动态规划法 （9）下列哪些问题是典型的NP完全问题：

A．排序问题 B．n-后问题 C．m-着色问题 D．旅行商问题 （10）适于递归实现的算法有： C

A．并行算法 B．近似算法 C．分治法 D．回溯法

二、算法分析题（每小题5分，共10分）

（11）用展开法求解递推关系：

1n?1?T(n)?? ?2T(n?1)?1n?1

（12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。

1

三、简答题（每小题5分，共10分）

（13）算法的复杂度分析涉及哪些方面？ （14）动态规划法的指导思想是什么？

四、计算题（每小题8分，共24分）

（15）用动态规划法求A10*30B30*20C20*10D10*200运算量最小的乘积顺序。要求写出求解过程，并将结果填入数组m[4][4]中。 (16) 用贪心法求下图的最小生成树

1 9 8 10 4 7 2 7 5 6 5 3 6 3 8 4 图16

（17）马步问题：在n*n的方棋盘中，马只能走“日”字。马从初始位置（x0,y0）出发，

把棋盘的每一格都走一次，且只走一次（遍历）。求出n=5时马的行走路线。

五、分析设计题（每小题8分，共16分）

（18）有16个选手参加循环赛，循环赛一共进行15天，每个选手必须与其他的 15个选手

各赛一场，每个选手一天只比赛一次；设计一个满足上述要求的比赛日程表。 （19）某市场营销人员从他所在城市(顶点1)出发，到其他5个城市去做市场调查，如下图

19所示。请设计行走路线。

1 9 8 1 2 4 7 7 5 6 5 3 6 3 8 图19

4 六、算法设计题（每小题10分，共20分）

（20）将一组无序数据重新排列成有序序列，写一算法实现；并分析你所写算法的时间复杂性，简要说明该算法适用于什么情形？不适用于什么情形？ （21）写一贪心算法，求解0-1背包问题。 0-1背包问题描述：

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。问如何选择装入背包的物品，使得装入背包中物品的总价值最大?

若进一步讨论：就0-1背包问题的应用作简单的描述。

2

本文来源：https://www.bwwdw.com/article/hrs3.html