算法分析与设计A5卷 .doc

1、 南阳理工学院试卷 课程： 算法分析与设计 考核方式：（闭卷） 课程性质：_ 适用对象：题号一二三四五总分复核人满分2020202020100得分一、 单选题：（每题 2 分，共 20 分）（说明：将认为正确答案的字母填写在每小题后而的括号内）评卷人得分1算法具有五种特性分别是输入、输出、( )、有限性、可行性。A鲁棒性； B二义性； C确定性； D兼容性；20-1背包问题：n=6，W=10，v(1:6)=(15,59,21,30,60,5)，w(1:6)=(1,5,2,3,6,1）。该问题的最大价值为（ ）。A101； B110； C115； D120；3使用子集树解决0-1背包问题时算法的

2、时间复杂度为（ ）。AO(m2m)； BO(n2n)； CO(2mn)； DO(2nm)；4以下关于P类问题的描述正确的是（ ）A存在多项式时间确定性算法的问题是P类问题；B存在多项式时间确定性算法的判定问题是P类问题；C存在多项式时间非确定性算法的问题是P类问题；D存在多项式时间非确定性算法的判定问题是P类问题；5一个正整数n是否为素数的判定方法中的描述正确的是（ ）；A如果(n-1)! mod n= 1，则n一定是素数；B如果(n-1)! mod n= - 1，则n一定是素数；C如果对于区间（0，n）之间的任何一个整数a，an-1 mod n=1，则n一定是素数。D如果同余方程在区间（0，

3、n）之间的解只有1和n-1，则n一定是素数。6在n皇后问题中引入随机化算法的方法中正确的是（ ）；A随机选取棋盘上的一个位置，只要和其它皇后不冲突即可；B随机选择不同斜线的位置；C随机选择不同列的位置；D随机选择不同行的位置；7在P不等于NP的前提下，以下关于P、NP和NP完全问题的关系描述错误的是（ ）A所有的P类问题都属于NP类问题；B所有的NP完全问题都属于NP类问题；CP类问题和NP完全问题有交集；DNP完全问题中哪怕一个问题在多项式时间内能够解决，所有的NP类问题都能在多项式时间内解决；8给定随机化算法A和任意小的正常数，算法A找到正确解的概率为p(0p1)，至少运行（ ）次算法A，

4、使得算法得到正确解的概率不小于。A； B； C； D；9约束标准型线性规划问题的单纯形算法步骤，以下描述不正确的是（ ）A找出基本变量和非基本变量；B判断检验数C是否为整数，如果是，算法无界结束；C选入基变量；D选离基变量；10以下问题中，不属于NP完全问题的是（ ）A最短路径的判定问题； B汉诺塔问题；C哈密顿回路问题； D图的m可着色判定问题二、填空题：（每空 2 分，共 20 分）评卷人得分1贪心法的两个基本要素是 和 。2分治法的求解分为 和 两大步骤。3回溯法中讲解了 树，排列树和 树。4分支限界法是以 或 的方式进行搜索问题的解空间树。5随机化算法分为四类，包括 、蒙特卡罗算法、

5、和舍伍德算法。三、简答题：（每题 5 分，共 20 分）评卷人得分1简述算法设计的一般过程。2简述贪心算法的基本思想和解题步骤。3简述动态规划算法的基本要素。4简述回溯法和分支限界法的异同。四、综合应用题：（每题 10 分，共 20 分）评卷人得分1采用快速排序的思想将给定序列T1:9=45，23，65，57，18，2，90，12，84 由小到大排序。(要求：先描述快速排序的思想，然后写出首次分解得到两个子问题的过程、递归的结果、子问题的解合并成原问题的解的过程)2用动态规划法求最优加工顺序问题：有7个工件在第一台机器和第二台机器上的处理时间分别为3，8，10，12，6，9，15， 7，2，6，18，3，10，4。（要求：先按求解步骤分为两个序列，然后对序列排序合并，再写具体的求解过程，指出最优解）五、算法分析题：（每题 10分，共20 分）评卷人得分1.用分支限界法设计解决0-1背包问题：重量w=3，5，2，1，价值v=9，10，7，4，最大容量C=7。（要求：先给出算法求解步骤，然后写出算法执行过程，分析算法的时间复杂性）2.用增广路算法求下面网络最大流（要求：先给出增广路算法步骤，然后写出问题具体执行过程，最后画出最大流图）第7页，共8页 第8页，共8页