搜索
1算法设计与分析试卷一、选择题（选择1-4个正确的答案,每题2分，共20分）（1）计算机算法的正确描述是：A．一个算法是求特定问题的运算序列。B．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。C．算法是一个对任一有效输入能够停机的图灵机。D．一个算法，它是满足5个特性的程序，这5个特性是：有限性、确定性、能行性、有0个或多个输入且有1个或多个输出。（2）影响程序执行时间的因素有哪些？A．算法设计的策略B．问题的规模C．编译程序产生的机器代码质量D．计算机执行指令的速度（3）用数量级形式表示的算法执行时间称为算法的A．时间复杂度B．空间复杂度C．处理器复杂度D．通信复杂度（4）时间复杂性为多项式界的算法有：A．快速排序算法B．n-后问题C．计算值D．prim算法（5）对于并行算法与串行算法的关系，正确的理解是：A．高效的串行算法不一定是能导出高效的并行算法B．高效的串行算法不一定隐含并行性C．串行算法经适当的改造有些可以变化成并行算法D.用串行方法设计和实现的并行算法未必有效（6）衡量近似算法性能的重要标准有：A．算法复杂度B．问题复杂度C．解的最优近似度D．算法的策略（7）分治法的适用条件是，所解决的问题一般具有这些特征：A．该问题的规模缩小到一定的程度就可以容易地解决；B．该问题可以分解为若干个规模较小的相同问题；C．利用该问题分解出的子问题的解可以合并为该问题的解D．该问题所分解出的各个子问题是相互独立的。（8）具有最优子结构的算法有：A．概率算法B．回溯法C．分支限界法D．动态规划法（9）下列哪些问题是典型的NP完全问题：A．排序问题B．n-后问题C．m-着色问题D．旅行商问题（10）适于递归实现的算法有：A．并行算法B．近似算法C．分治法D．回溯法二、算法分析题（每小题5分，共10分）（11）用展开法求解递推关系：（12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。11)1(211)(nnTnnT2三、简答题（每小题5分，共10分）（13）算法的复杂度分析涉及哪些方面？（14）动态规划法的指导思想是什么？四、计算题（每小题8分，共24分）（15）用动态规划法求A10*30B30*20C20*10D10*200运算量最小的乘积顺序。要求写出求解过程，并将结果填入数组m[4][4]中。(16)用贪心法求下图的最小生成树15624397471038658图16（17）马步问题：在n*n的方棋盘中，马只能走“日”字。马从初始位置（x0,y0）出发，把棋盘的每一格都走一次，且只走一次（遍历）。求出n=5时马的行走路线。五、分析设计题（每小题8分，共16分）（18）有16个选手参加循环赛，循环赛一共进行15天，每个选手必须与其他的15个选手各赛一场，每个选手一天只比赛一次；设计一个满足上述要求的比赛日程表。（19）某市场营销人员从他所在城市(顶点1)出发，到其他5个城市去做市场调查，如下图19所示。请设计行走路线。1562439747138658图19六、算法设计题（每小题10分，共20分）（20）将一组无序数据重新排列成有序序列，写一算法实现；并分析你所写算法的时间复杂性，简要说明该算法适用于什么情形？不适用于什么情形？（21）写一贪心算法，求解0-1背包问题。0-1背包问题描述：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。问如何选择装入背包的物品，使得装入背包中物品的总价值最大?若进一步讨论：就0-1背包问题的应用作简单的描述。