算法设计与分析试卷(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