《网络教育学院专升本课程算法设计分析》由会员分享，可在线阅读，更多相关《网络教育学院专升本课程算法设计分析（41页珍藏版）》请在金锄头文库上搜索。
1、1、算法分析中，记号 O 表示（ ） A、渐进上界 B、非紧上界 C、非紧下界 D、非紧下界参考答案A2、 在找零钱问题中，收银员算法中所应用的贪心规则的最恰当描述是 （ ）。 A、总是选择面值最高的硬币 B、总是选择不超过剩余应找钱数的最大面值的硬币 C、总是选择面值是10，5的倍数的硬币 d、总是选择面值最小的硬币参考答案B3、由边界条件出发,通过递推式求f（n）的值，从边界到求解的全过程十分清楚的是（） A、贪心 B、递推 C、递归D、概率参考答案B4、考虑最长公共子序列问题的下述递归表达式，如果全部子问题组织在一个ci,j的二维表格中，则ci,j不依赖于下述哪个子问题：（）。 B、同一
2、列的上一行 C、上一行的上一列 d、同一行的下一列|参考答案 D5、 算法的时间复杂度是指（） A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 、算法程序中的指令条数参考答案C6、活动选择问题就是在所给的活动集合中，选出（）的相容活动子集。 A、当前可选活动中结束时间最早的活动 B、当前可选活动中开始时间最早的活动 C、当前可选活动中冲突数量最少的活动 d、当前可选活动中持续时间最长的活动参考答案A7、一个长度为n英寸的钢管的最优切割问题，总共有（）个不同的子问题。 A、n+1 B、n2 C、nlogn D、 logn参考答案A8、最优二叉搜索树的时间
3、复杂度为（ ） 。 A、O(n) B、O(n!) C、O(n2) 卩、O(nlogn),参考答案D9、算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是( ) A、5/0 B、将6或7与x相加 C、未赋值变量参与运算 D、f(n)=f(n-l)+2.f(l)=10.n 为自然数参考答案D10、对于三个物体的背包问题，问题相关的数据为n=3, M=20,P=(25,24,15),W(l 8, 15,10)。下面给岀的四个可 行解中，最好的是() A、(1/2，1/3，1/4) B、(1，2/15，0) C、(0，2/3，1) D、(0, 1, 1/2)参考答案D11、递归
4、函数f(n)=f(n-1)+n(n 1)的递归出口是()。 A、f(0)=0 B、f(1)=1 C、f(0)=1 ”、f(n)=n参考答案 B12、下面关于快速排序的说法，正确的是() A、快速排序的速度和数据无关，是一个固定的值 B、快速排序的速度在分解的均匀的时候效果最好，速度最快 C、快速排序主要的时间花在合并上面 D、快速排序在分解均匀的适合速度最慢参考答案B13、下面关于货郎担问题的描述，正确的是()A、货郎担问题是求取具有最大成本的周游路线问题 B、货郎担问题适合使用贪心算法求问题的最优解 C、货郎担问题存在多项式时间算法 D、货郎担问题可以通过动态规划算法实现，参考答案 D14、
5、实现快速排序算法如下：QuickSor t (A, p, r)IF p B、对于所有“二f(XY)=f(Yj X)9 C、对于所有【，匸 D、参考答案B对于所有-:928、大型程序设计一般用（ ）数据类型来描述算法。 A、逻辑 B、抽象 C、简明 d、复杂参考答案B29、与分治法不同的是，适合于用动态规划求解的问题（ ）。 B、经分解得到子问题往往是互相独立的c、经分解得到子问题往往是互相交叉的D、经分解得到子问题往往是任意的参考答案A30、算法 simpleMaxMin(Al.r)如下, Max=Min=Al;for i=l+1 to r doif AiMax MaxAi;else if A
6、iMin MinAi; return Max,Min其时间复杂度是( )。 A、2n B、2(n-1) c、3n D、3(n-l)参考答案B31、快速排序法的基本思想是对输入的数组按以下三个步骤进行排序（）。 A、分解，合并，递归求解 B、合并，递归求解，分解 C、递归求解，分解，合并 d、分解，递归求解,合并 参考答案D32、合并排序法的基本思想是：将待排序元素分成大小大致相同的（）个子集合，分别对每个子集合进行排 序，最终将排好序的子集合合并成为所要求的排好序的集合。 B、3 C、2 D、5参考答案 C33、在最优二叉搜索树问题中，我们的优化目标是( )。 A、只经过最少次数的比较就可以找
7、到概率最大的元素 B、经过最多次数的比较就可以找到概率最小的元素 C、找到每个元素所需要的平均比较次数为最小 d、元素搜索代价的数学期望为最小参考答案D34、下面是贪心算法的基本要素的是( )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 |参考答案C35、分治法所能解决的问题应具有的关键特征是( )。 A、该问题的规模缩小到一定的程度就可以容易地解决 B、该问题可以分解为若干个规模较小的相同问题 C、利用该问题分解出的子问题的解可以合并为该问题的解 d、该问题所分解出的各个子问题是相互独立的参考答案 C36、T(n)=2n3+10mlog(n)+30n 的渐近时间复杂度
8、为()。 A、O(n2log(n) B、O(n4) C、0(n3)参考答案C37、在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的最大收益，且已知rn所代 表的最优解里，第一刀切下了3英寸，则下述公式正确的是( ) 。B、rn = rn - 3C、rn = rn-3 + 3D、rn = r3 + p3参考答案38、）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质|参考答案D39、 下列关于选择排序和冒泡排序的稳定性的说法，正确的是（ ）。 A、选择排序是稳定的，冒泡排序是稳定的。 B、选择排序是不稳定的，冒泡排序
9、是不稳定的 C、选择排序是稳定的，冒泡排序是不稳定的。 D、选择排序是稳定的，冒泡排序是不稳定的。参考答案B40、Edmonds-Karp算法中寻找增广路径的方法是（）。 A、深度优先算法 B、广度优先算法 C、Prim 算法 D、Dijkstra 算法参考答案 B使用分治法求解不需要满足的条件是（ ） 。A、子问题必须是一样的 B、子问题不能够重复 C、子问题的解可以合并 、原问题和子问题使用相同的方法解参考答案 A42、在流网络中，对于源节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 A、在流网络中，对于任何节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 B、在流网络中，对于汇节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。
