数媒一班算法模拟题
一、判断题（10分）：
1、产生随机数的算法是一类具有不确定性特征的算法。
2、指数时间算法总比多项式时间算法用时长。
3、对于n个整数，快速排序的时间复杂度总为O(nlogn)。
4、动态规划思想的实质是分治思想与解决冗余。
5、分支限界法中，活结点一旦成为扩展节点就一次性产生其所有儿子结点。
二、填空题（30分）：
1、按渐进阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3，
。
2、假设某算法的时间复杂度T(n) = 5*n3，在某台机器上实现并完成该算法的
时间为t秒。现在另外一计算机，其运行速度为第一台的64倍，那么在这台新计算机上用同一算法在t秒内能解决输入规模为的问题。
3、两个n位二进制整数X、Y，若按公式
XY=(A2n
2+B)(C2
n
2+D)=AC2n+(AD+BC)2
n
2+BD
计算时，请写出两数相乘所需的乘法运算总数T(n)的递归表达式（设加法和移位共用O(n)步完成），n=1时，T(n)= ；n>1时，T(n)= 。
以上整数乘法还可以进一步优化，请写出优化后的XY计算公式，
XY= 。
4、贪心算法和动态规划算法都要求问题具有，但能用贪
心算法的问题还需要满足，而能用动态规划算法的问题
还需要满足                      。 5、
运用动态规划思想求解两个长分别为la 、lb 的字符串A 、B 的最长公共子
序列时，定义dp[i][j]为A 串的前i 个和B 串的前j 个字符包含的最长公共子序列长度。则可建立递推关系式：
6、
诺亚方舟的载重量为C ，灾后重建用的设备的重量为w i （i=1,2,…,n ），在
装载体积不受限制的情况下，要求装载尽可能多的设备上船。请给出一个贪心策略解决此问题：                                            。 7、
刚哥要求你对具有下表所示词频的文本进行无损压缩，请你利用哈夫曼编
码技术给出文本压缩率最高的变长编码方案。
8、
在用回溯法解题时常遇到两种类型的解空间树。
当所给问题是从n 个元素的集合S 中出满足某种性质的子集时，解空间树为        ，其共有      个叶结点；
当所给的问题是确定n 个元素满足某种性质的排列时，其解空间树为        ，共有      个叶结点。 9、
在回溯法中，每个结点有    次机会成为扩展结点，每次产生    （个）
子结点；其搜索解空间的方式是          。
dp[i][j] =
i=0或j=0
i,j>0且A i =B j                                i,j>0且A i !=B j
而在分枝限界法中，每个结点有次机会成为扩展结点，每次产生（个）子结点；其搜索解空间的方式是。
这两种方法中能出所有可行解的是，
需要更大存储空间的是。
10、给出如下无向图G=(V，E)，利用回溯法求解无向图G的最大团，解空间树
的第k层表示选择或者不选择编号为k的结点。i表示扩展结点，j表示i的子结点，bestamt表示当前最大团结点个数，g表示当前已经选择的结点的集合，请给出该问题的约束条件。（可用自然语言表述）
1）可行性约束函数
2）上界函数
三、简答题（20分）：
1、简述动态规划与分治法的异同点。
2、简述回溯法与分支限界法的区别（4点）。
四、算法题（40分）：
1、用动态规划解该问题。给定n个矩阵A1,A2,…,An，Ai的维数为pi-1×pi(1
≤i≤n)，要求计算链乘积A1A2…An的最小乘运算次数。
用例：给定4个矩阵，A1、A2、A3、A4其大小分别为4*3，3*1，1*2，2*5。
（1）请写出n个矩阵链乘的状态及状态转移方程。
（2）请用题目所给的用例画表描述你的算法。
2、有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱
i的重量为w i，且
n
∑w i≤c1+c2
i=1
装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，出一种装载方案。请分别用回溯法和分支限界法做此题。
并按用例（n=5，c1=20，c2=20，5个集装箱重量分别为13、3、8、6、5）画出解空间树标明剪枝及搜索顺序。（注：回溯法需要使用可行性约束和上界函数来剪枝；要求使用优先队列式分支限界法，并将上界函数作为活结点的优先级）
3、设有一4*4的棋盘，把4个皇后放在棋盘上，要求满足下列两个条件：1）
任意两个皇后不在同一行上和同一列上；2）任意两个皇后不在同一条对角线上；问有多少种放法？请画出解空间树标明剪枝及搜索顺序。
4、旅行商问题。已知一个由n个城市组成的网络，记为v1,v2,…,v n，d i,j表示从
v i到v j的距离，一般设d i,j≠d j,i，一个推销员从v1开始，访问每个城市一次且仅一次，最后返回v1。求最短的行走路径。
4个城市，城市之间的距离如见右矩阵。
（1）请
（2）请根据用例和你的状态转移方程，模拟计算机求解过程，给出最短的
数学二进制的算法行走路径。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。