算法设计与分析试卷

算法设计与分析试卷Tag内容描述：<p>1、1 装订线 华南农业大学期末考试试卷（A卷） 2010学年第一学期 考试科目： 算法分析与设计 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 题号 一 二 三 四 总分 得分 评阅人 注意：所有答案请写在答卷上，写在试卷上不得分。 一、选择题（本大题共 10 小题，每小题 2 分，共 20 分） 1、以下有关NP完全性理论的相关描述，正确的是（ ）。 （A）P问题都是NP问题 （B）NP问题指的是不能够在多项式时间内求解的问题 （C）P = NP （D）0-1背包问题属于P问题 2、void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1,。</p><p>2、1 计算机算法设计与分析复习题计算机算法设计与分析复习题 一一、填空填空题题 1、 一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上， 因此算法的复杂性有 时间 复杂性和空间复杂性之分。 2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题 时，这些子问题的规模都大致 相同 。 3、使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最佳情况下， 搜索的时间复杂性为 O （1） ， 在最坏情况下， 搜索的时间复杂性为 O （ logn ） 。 4、已知一个分治算法耗费的计算时间 T(n)，T(n)满足。</p><p>3、1） 用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2） 算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3） 算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的。</p><p>4、诚信保证本人知晓我校考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号： 成绩西北工业大学考试试题（卷）20132014 学年第 二 学期开课学院 计算机学院 课程 算法设计与分析 学时 32 考试日期 2014.6.30 考试时间2小时 考试形式 闭卷 考生班级学号姓名一、简答题（每小题8分，共40分）1.写出回溯算法的一般模式。2.分治算法的基本思想是什么？3.什么是最优子结构性质？4.请简述广度优先搜索算法的基本思想。5简述分治法与动态规划算法的区别于共同点？二、算法设计（ 每题10分 共30分）1. 用贪心算法解决。</p><p>5、算法设计与分析试卷填空题（20分，每空2分）1.算法的性质包括输入、输出、有限性。2.动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。3.设计动态规划算法的4个步骤：4.找出，并刻画其结构特征。5.根据计算最优值得到的信息，。6.流水作业调度问题的johnson算法：令N1=,N2=i|ai=bj;将N1中作业依ai的。7.对于流水作业高度问题，必存在一个最优调度，使得作业（i）和（i+1）满足Johnson不等式。8.最优二叉搜索树即是的二叉搜索树。9.下面程序段的所需要的计算时间为（ ）。int MaxSum(int n, int *a。</p><p>6、2006级计算机专业20062007学年第二学期算法设计与分析期末试题 (A卷)一、 填空题(10题2分=20分)1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括（ ）和（ ）。2、对于函数，如果存在，使得当时有，就说是当时的（ ）。3、多项式的上界为（ ）。4、直接或间接地调用自身的算法称为（ ），用函数自身给出定义的函数称为（ ）。5、（ ）与（ ）是递归函数的两个要素。6、（ ）是问题能用动态规划算法求解的前提。7、贪心算法的两个基本要素是（ ）和（ ）。8、回溯法的含义是（ ）。9、回溯法中的解空间树结构通常有两种，分别。</p><p>7、算法设计与分析1、(1) 证明：O(f)+O(g)=O(f+g)（7分）(2) 求下列函数的渐近表达式：（6分） 3n2+10n; 21+1/n;2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n)或f(n)=(g(n)或f(n)=(g(n)，并简述理由。（15分）(1)(2)(3)3、试用分治法对数组An实现快速排序。（13分）4、试用动态规划算法实现最长公共子序列问题。（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。（12分）6、试用动态规划算法实现下列问题：设A和B是。</p><p>8、算法设计与分析复习题1一个算法应有哪些主要特征？另附资料2分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？另附资料3试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。另附资料4编写一个递归算法求解Hanoi 塔问题。Void Hanoi(int n,int first,int second,int third) If(n=1)Move(first,third);Else Hanoi(n-1,first,third,second);Move(first,third);Hanoi(n-1,second,first,second);5求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。6求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。7求解方程T(n)=aT(n。</p>