当前位置:首页 >> IT/计算机 >>

算法分析与设计试题

一、 选择题(20 分) 1.最长公共子序列算法利用的算法是( A、分支界限法 B、动态规划法 B ) 。 D、回溯法

C、贪心法 A C、贪心法 C ) 。 ) 。

2.实现棋盘覆盖算法利用的算法是( A、分治法 B、动态规划法

D、回溯法

3.下面是贪心算法的基本要素的是( A、重叠子问题 B、构造最优解

C、贪心选择性质 D )

D、定义最优解

4.回溯法的效率不依赖于下列哪些因素( A.满足显约束的值的个数 C. 计算限界函数的时间

B. 计算约束函数的时间 D. 确定解空间的时间 B ) D.搜索函数 ) 。 C、贪心法 B ) 。 C、构造最优解 D、定义最 D、回溯法

5.下面哪种函数是回溯法中为避免无效搜索采取的策略( A.递归函数 B.剪枝函数 C。随机数函数 A

6.采用最大效益优先搜索方式的算法是( A、分支界限法 B、动态规划法

7.贪心算法与动态规划算法的主要区别是( A、最优子结构 优解 8. 实现最大子段和利用的算法是( A、分治策略 B、动态规划法 B B、贪心选择性质

) 。 C、贪心法 C ) 。 D、随机 ) 。 D、回溯法

9.优先队列式分支限界法选取扩展结点的原则是( A、先进先出 B、后进先出

C、结点的优先级
A

10.下列算法中通常以广度优先方式系统搜索问题解的是( A、分支限界法 B、动态规划法 C、贪心法

D、回溯法

二、填空题(22 分 每空 2 分) 1.算法是由若干条指令组成的有穷序列,且要满足输入、 确定性和 有限性 四条性质。 分治法 来设计的。 分支限界法 。 输出 、

2、大整数乘积算法是用

3、以广度优先或以最小耗费方式搜索问题解的算法称为 4、舍伍德算法总能求得问题的 5、 贪心选择性质 一个解 。

是贪心算法可行的第一个基本要素,也是贪心算法与动态

规划算法的主要区别。 6.快速排序 template<class Type> void QuickSort (Type a[], int p, int r) { if (p<r) { int q=Partition(a,p,r); QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 } } 7. 哈密顿环问题的算法可由 8.贪心算法 不一定 回溯法 设计实现。

产生最优解。 。

9.算法中通常以深度优先方式系统搜索问题解的是 回溯法

三、 算法设计与分析(25 分) 1.用欧几里德迭代算法求两个数的最小公倍数(10 分) #include<iostream> using namespace std; int Gcd(int m,int n)

{ if(m==0) return n; if(n==0) return m; int t=m>n?n:m; while(m%t||n%t) t--; return t; } int main() { int a,b; cout<<"Input a & b (0<=a<b) :"; cin>>a>>b; int m=a*b/Gcd(a,b); cout<<"The Least Common Multiple is:"<<m<<endl; return 0; 2、试用动态规划算法实现最大子矩阵和问题:求 m ? n 矩阵 A 的一个子矩阵,使 其各元素之各为最大。 (15 分)
解:解答如下: int MaxSum2(int m,int n,int **a) { int sum=0; int *b=new int[n+1]; for(int i=1;i<=m;i++){ for(int k=1;k<=n;k++) b[k]=0; ……………………………..(5 分) for(int j=i;j<=m;j++){ for(int k=1;k<=n;k++) b[k]+=a[j][k]; int max=MaxSum(n,b); if(max>sum) sum=max; } } return sum; ……………………………..(10 分) } int MaxSum(int n,int *a) { int sum=0,b=0; for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; }

Return sum; ……………………………..(15 分) } 四、简答题(33 分)

1、假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均可以被分割,且背包容 量 M=150,如果使用贪心方法求解此背包问题,使收益最大,请写出求解过程请写出求解 过程。 (10 分) 物品 重量 价值 A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30

解: 使用单位价值从大到小: FBGDECA, 得到贪心解为: FBGD 全部放入, E 放入 87.5%, 而 得到价值为 190.625。 2. 写出分治算法 MaxMin 算法对下列实例中找最大数和最小数的过程。 (10 分) 数组 A=(48,12,61,3,5,19,32,7) 解:1、 2、48,12 48,12,61,3, 61,3 5,19 5,19,32,7 32,7 表中元素多于二, 对半分割 表中元素多于二, 对半分割

3、 48~61, 12~3 为最小 4、 61~32 5、 61 3 3~5

19~32,5~7

求前半部分的最大最小和后半部分的最大最小,两个半部分的大者为最大,小者 两个半部分的大者为最大,小者为最小

寻找结束

3. 写出多段图最短路经动态规划算法求解下列实例的过程,并求出最优值。 (13 分)

2 4 3 1 5 2 4 各边的代价如下: C(1,2)=3, C(1,3)=5 ,C(1,4)=2 3 4 2 1 8

5 4 6 5 6 7 8

C(2,6)=8 ,C(2,7)=4 ,C(3,5)=5 ,C(3,6)=4, C(4,5)=2,C(4,6)=1 C(5,8)=4, C(6,8)=5 ,C(7,8)=6 解 :Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 , Cost(3,6)= C(6,8)+0=5, Cost(3,5)= C(5,8)+0=4 Cost(2,4)= = Cost(2,3)= = Cost(2,2)= = min{C(4,6)+ Cost(3,6), C(4,5)+ Cost(3,5)} min{1+ 5, 2+4}=6 min{C(3,6)+ Cost(3,6) } min{4+5}=9 min{C(2,6)+ Cost(3,6), C(2,7)+ Cost(3,7)} min{8+5, 4+6}=10

Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)} = min{3+10, 5+9,2+6}= 8 按上所述,Cost(1,1)为所求最优值。


相关文章:
算法设计与分析试卷及答案.doc
算法设计与分析试卷及答案 - 湖南科技学院二○ 信息与计算科学专业 考试类型:开卷 题号得分 阅卷人 复查人 一二三 年 学期期末考试 年级《算法设计与分析》 ...
算法分析与设计试题.doc
算法分析与设计试题 - 一、 选择题(20 分) 1.最长公共子序列算法利用的算
算法设计与分析考试题及答案.doc
算法设计与分析试题及答案 - 一、填空题(20 分) 填空题 1.一个算法就是
《算法设计与分析》历年期末试题整理(含答案).pdf
算法设计与分析》历年期末试题整理(含答案) - 《算法设计与分析》历年期末试题整理(含答案) (1)用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、...
算法分析与设计习题集整理_图文.doc
算法分析与设计习题集整理 - 算法分析与设计习题集整理 第一章算法引论 一、填空
算法设计与分析试卷(A)及答案.doc
算法设计与分析试卷(A)及答案 - --- 密 ---...
《算法设计与分析》考试题目及答案...doc
算法设计与分析 pdf,算法分析与设计 ppt,简便算法题目大全及答案,c语言算法题目及答案,算法设计分析试题,算法分析与设计答案,算法设计及分析,算法设计与分析陈慧南...
《算法设计与分析》考试题目及答案.doc
算法设计与分析》考试题目及答案 - 《算法分析与设计》期末复习题 一、 选择题
《算法分析与设计》期末考试复习题纲(完整版)_图文.doc
算法分析与设计》期末考试复习题纲(完整版)_工学_高等教育_教育专区。信息与计算科学专业的《算法与设计》考试题目复习提纲 《算法分析与设计》期末复习题 一、...
算法分析与设计 重点知识及试题.doc
算法分析与设计 重点知识及试题 - 递归: 直接或间接的调用自身算法称为递归算法
《算法分析与设计》期末考试复习试题_学生版.doc
算法分析与设计》期末考试复习试题_学生版 - ., .. .. 《算法分析与设计》期末复习题 一、 选择题 1.应用 Johnson 法则的流水作业调度采用的算法是(D) A...
《算法分析与设计》期末考试复习题-学生版.doc
算法分析与设计》期末考试复习题-学生版 - 《算法分析与设计》期末复习题 一、
算法分析与设计复习题及参考答案.doc
算法分析与设计复习题及参考答案 - 网络教育课程考试复习题及参考答案 算法分析与
计算机算法设计与分析期末试题4套(含答案).doc
计算机算法设计与分析期末试题4套(含答案) - (1)用计算机求解问题的步骤: )用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法...
《算法分析与设计试卷2016-2017》.doc
算法分析与设计试卷2016-2017》_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载 | 举报文档 《算法分析与设计试卷2016-2017》_数学_高中教育_教育专区。...
算法设计与分析期末试卷A卷.doc
算法设计与分析期末试卷A卷 - A卷 一、选择题 1.二分搜索算法是利用(A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 )。 D、广度优先...
算法设计与分析试卷及答案..doc
算法设计分析试卷及答案._数学_自然科学_专业资料。算法设计分析试卷及答案.,信息系统分析与设计课程设计,系统工程 分析,信息系统分析与设计试卷及答案,算法设计...
算法设计与分析期末试题终极版.doc
算法设计与分析期末试题终极版 - 1 、用计算机求解问题的步 骤: 1、问题分析 2、数学模型建 立 3、算法设计与选择 4、算 法指标 5、算法分析 6、算法 实现...
算法设计与分析期末考试卷及答案a.doc
算法设计与分析期末考试卷及答案a - 一.填空题(每空 2 分,共 30 分) 1.算法的时间复杂性指算法中的执行次数。 2.在忽略常数因子的情况下, O、 ? 和 ?...
算法分析与设计复习题及参考答案.doc
算法分析与设计复习题及参考答案_数学_初中教育_教育专区。算法分析与设计复习题及参考答案,工程力学复习题及参考答案,《商法》期末复习题及参考答案,护理学导论复习...