1、一、单项选择题（共30题、共90分）在流网络中，对于网络中的节点，下面说法正确的选项是（）.在流网络中,对于任何节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是不相等的。在流网络中，对于汇节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。Edmonds-Karp算法中寻找增广路径的方法是（）。深度优先算法Dijkstra算法广度优先算法Prim算法以下关于贪心算法，不正确的说法是（）。用于解决
2、优化问题所需求解的问题可以不满足最优子结构性质总是选择在当前看来最好的选择算法以优先队列为空为结束条件C、从Q中取出一个顶点的实质是在应用MST性质选择连接A与V-A的最小权边算法执行结束后，生成树有n-1个顶点在使用伪代码进行算法描述时，不可以实现循环的是（）oA、whileB、gotoC、forD、if在最优二叉搜索树问题中，我们的优化目标是（）。只经过最少次数的比拟就可以找到概率最大的元素元素搜索代价的数学期望为最小经过最屡次数的比拟就可以找到概率最小的元素找到每个元素所需要的平均比拟次数为最小30.一个长度为n英寸的钢管的最优切割问题，总共有（）个不同的子问题。A、n+1lognn2n
5、=rn-3+3rn=rn-3在最长公共子序列问题中，如果定义ci,j为Xl.Xi和Yl.Yj的最长公共子序列的长度,那么长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（）。c0,0cm,ncl,mcl,l一个长度为n英寸的钢管的最优切割问题，总共有（）个不同的子问题。n+1lognnlognn2关于背包问题的下述形式化公式描述：下述说法不正确的选项是（）oi表示物品的重量求解目标是最大化装入背包内的物品的总价值xi=0表示编号为i的物品不被选择C表示背包容量应用分治法的两个前提是（）。问题的可分性和解的可归并性问题的可分性和解的复杂性问题的复杂性和解的可归并性问
6、题的可分性和解的存在性算法分析中，记号O表示（）A、渐进上界B、非紧下界C、非紧下界D、非紧上界由边界条件出发,通过递推式求f（n）的值，从边界到求解的全过程十分清楚的是（）贪心概率c、递归D、递推二分搜索算法是基于（）设计的算法。分治法穷尽法贪心法动态规划法以下关于Huffmann树的描述，哪一项为哪一项错误的（）。Huffman树是满树在树的同一层，字符的出现顺序会影响平均编码长度的数学期望最低频度的两个字符处于树的最底层，且互为兄弟字符均在叶子结点上Java的类一般有4个局部组成：请选出不属于的一个（）类名组C、方法D、数据成员16.活动选择问题就是在所给的活动集合中，选出（）的相容活
11、的问题适用于递归求解。（）正确错误备忘录方法可以看作是动态规划算法的变形。（）正确错误分治策略是将一个规模为n的问题分成k个规模较小而结构与原问题相似的子问题。（）正确错误Huffmann编码树所对应的编码并不一定是前缀码。（）正确错误在活动选择问题中，如果活动A晚于活动B开始，那么两个活动相容。（）正确错误0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解。()正确错误归并排序是指将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，那么继续分治，直到一个元素。()正确错误一、填空题(共10题、共30分)归并排
12、序算法是用策略实现对n个元素进行排序的算法。在线答题扫码传如作答中有图片或公式，请使用“扫码传”一个递归算法必须包括。在线答题扫码传如作答中有图片或公式，请使用“扫码传”快速排序算法是基于的一种排序算法。在线答题扫码传如作答中有图片或公式，请使用“扫码传”伪代码是一种语言。在线答题扫码传如作答中有图片或公式，请使用“扫码传”Huffmann算法是一种。在线答题扫码传如作答中有图片或公式，请使用“扫码传”找零钱问题中，我们应用的贪心规那么是O在线答题扫码传如作答中有图片或公式，请使用“扫码传”一个30行20列的矩阵可与一个行75列的矩阵相乘。在线答题扫码传如作答中有图片或公式，请使用“
13、扫码传”从分治法的一般设计模式可以看出，用它设计出的程序一般是一个过程。在线答题扫码传如作答中有图片或公式，请使用“扫码传”算法的五个重要特征是、。在线答题扫码传如作答中有图片或公式，请使用“扫码传”分治法在每一层递归上有三个步骤：分解、解决、合并，其中解决是指O在线答题扫码传如作答中有图片或公式，请使用“扫码传”二、简答题（共6题、共30分）算法的正确性是指什么？在线答题扫码传如作答中有图片或公式，请使用“扫码传”b）,写出求它们的最大公约数的算法或程序。在线答题扫码传如作答中有图片或公式，请使用“扫码传”对于aeklu五个字符,及其频度数据：=0.32,=0.25,=0.20,=
14、0.18,=0.05o请用Huffmann算法构造其Huffmann树。在线答题扫码传如作答中有图片或公式，请使用“扫码传”设是一个流网络，f为G的流，（S,T）为G的一个割，证明|f|=f（S,T）。在线答题扫码传如作答中有图片或公式，请使用“扫码传”一个人把一对兔子用围墙围住。如果最初的一对兔子（一雌一雄）是新生的，并且所有的兔子在出生后的第一个月都不能繁殖，但是在之后的每个月末都能生出一对兔子（一雌一雄），那么一年后围墙里将会有多少对兔子？在线答题扫码传如作答中有图片或公式，请使用“扫码传”在三数取中划分法中，第k小的元素要成为中心数，必须与一个比它更小的元素以及一个比它大的元
16、)二分检索算法不适合于检索数据不属于数组的情况二分检索算法适合于无序的数列的检索二分检索算法的效率和二叉树的深度有关9.阶乘函数用递归定义Publicstaticintfactorial(intn)if(n=O)return1;return();n*factorial(n)n*factorial(n+l)n*factorial(n-l)n*factorial(n-2)10.以下算法中通常以自底向上的方式求解最优解的是（）o备忘录法回溯法动态规划法贪心法一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比（）o动态规划效果好哪个效果好备忘录方