算法设计与分析模拟试卷

《算法设计与分析模拟试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析模拟试卷一、选择题（10个）1：设有四个矩阵A、B、C、D连乘，它们的维数分别是：A(50×10)、B(10×40)、C(40×30)、D(30×5)，下面加括号表示的不同计算次序，其中计算量最大的是（）。A）A（（BC）D）B）A（B（CD））C）（AB）（CD）D）（（AB）C）D2：给定2个序列A=”xyzyxzxz”和B=”xzyxxyzx”，下列不是A和B的公共子序列的是（）。A）xxxB）xzyzC）xzyxxzD）xzyxxzx3：棋盘覆盖问题中，任何一个2k*2k的棋盘覆盖中，用到的L型骨牌个数为（）。A）4kB）(4k-1)/3C）(4k-

2、1)/4D）4k/34：分支限界法在搜索解空间时，经常使用（）来组织解空间。A）数组B）链表C）图形结构D）树形结构二、判断题（10个）1：分支限界法使用广度优先或最小耗费优先方法搜索构造的解空间。（）2：分支限界法求解0-1背包问题，其解空间是一棵排列树。（）三、综合题（5-6个）1：给定3种物品和一背包，背包的容量为C=50，物品的重量w=[10,20,30]，其价值为v=[60,100,120]。（1）求解背包问题，选用算法？最大价值？（2）求解0-1背包问题，选用算法？最大价值？2：设有三个矩阵A1、A2、A3，它们的维数分别是：A1（10×100）、A2（100

3、×5）、A3（5×50）。确定共有几种不同的计算次序，比较哪种情形计算量是最小的。3：活动安排问题：要在所给的活动集合内选出最大的相容活动子集合。下表给出8个活动的起始时间，选用相应算法解决此问题。i12345678S[i]523671810f[i]861091131716四、算法设计及应用题（3-4个）1：假设有四个矩阵连乘：A1A2A3A4，其中矩阵A1（2×10）（2行10列矩阵），矩阵A2（10×1），矩阵A2（1×5），矩阵A4（5×4），通过加括号的方式确定计算此矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。第３页共3页算法设计与分析模拟

4、试卷要求：（1）确定解决问题选择的算法；（2）写出解决上述问题的实现算法（最小计算量、计算次序）；（3）写出通过此算法解决上述问题的过程及结果。2：假设有两个序列A=“xyxzyxyzzy”、B=“xzyzxyzxyzxy”，要求求出序列A、B的最长公共子序列的长度。要求：（1）确定解决问题选择的算法；（2）写出解决上述问题的实现算法lcsLength；（3）写出通过此算法解决上述问题的过程及结果。答题纸专业班级：___________考生姓名：____________学号：___________　　　　　　一：选择题答案12345678910二、判断题答案1234567

5、8910三、将所有综合题及算法设计及应用题答案顺次写在下面及答题纸上。（注：请注清楚大小题号，不做请留空白。）第３页共3页算法设计与分析模拟试卷第３页共3页