《算法与数据分析》考前练兵

奥鹏作业答案

《算法与数据分析》考前练兵
1.[单选题] 二分搜索算法是利用（          ）实现的算法
更多学习资料www.openhelp100.com
    A.分治策略
    B.动态规划法
    C.贪心法
    D.回溯法
    答:——A——
2.[单选题] 最大效益优先是（          ）的一搜索方式。
    A.分支界限法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:——A——
3.[单选题] 下列不是动态规划算法基本步骤的是（          ）。
    A.找出最优解的性质
    B.构造最优解
    C.算出最优解
    D.定义最优解
    答:——A——
4.[单选题] 在下列算法中有时找不到问题解的是（          ）。
    A.蒙特卡罗算法
    B.拉斯维加斯算法
    C.舍伍德算法
    D.数值概率算法
    答:————
5.[单选题] 回溯法解旅行售货员问题时的解空间树是（          ）。
    A.子集树
    B.排列树   
    C.深度优先生成树
    D.广度优先生成树
    答:————
6.[单选题] 下列算法中通常以自底向上的方式求解最优解的是（          ）。
    A.备忘录法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
7.[单选题] 衡量一个算法好坏的标准是（          ）。
    A.运行速度快
    B.占用空间少
    C.时间复杂度低
    D.代码短
    答:————
8.[单选题] 实现循环赛日程表利用的算法是（          ）。
    A.分治策略
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
9.[单选题] 以下不可以使用分治法求解的是（          ）。
    A.棋盘覆盖问题
    B.选择问题
    C.归并排序
    D.0/1背包问题
    答:————
10.[单选题] 下列随机算法中运行时有时候成功有时候失败的是（          ）。
    A.数值概率算法
    B.舍伍德算法
    C.拉斯维加斯算法
    D.蒙特卡罗算法
    答:————
11.[单选题] 下面关于NP问题说法正确的是（          ）。
    A.NP问题都是不可能解决的问题
    B.P类问题包含在NP类问题中
    C.NP完全问题是P类问题的子集
    D.NP类问题包含在P类问题中
    答:————
12.[单选题] 下列哪一种算法不是随机化算法（          ）。
    A.蒙特卡罗算法
    B.拉斯维加斯算法
    C.动态规划算法
    D.舍伍德算法
    答:————
13.[单选题] 蒙特卡罗算法是（          ）的一种。
    A.分支界限算法
    B.概率算法
    C.贪心算法
    D.回溯算法
    答:————
14.[单选题] 分支限界法解旅行售货员问题时，活结点表的组织形式是（          ）。
    A.最小堆
    B.最大堆
    C.栈
    D.数组
    答:————
15.[单选题] （          ）是贪心算法与动态规划算法的共同点。
    A.重叠子问题
    B.构造最优解
    C.贪心选择性质
    D.最优子结构性质
    答:————
16.[单选题] 矩阵连乘问题的算法可由（          ）设计实现。
    A.分支界限算法
    B.动态规划算法
    C.贪心算法
    D.回溯算法
    答:————
17.[单选题] Strassen矩阵乘法是利用（          ）实现的算法。
    A.分治策略
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
18.[单选题] 使用分治法求解不需要满足的条件是（          ）。
    A.子问题必须是一样的
    B.子问题不能够重复
    C.子问题的解可以合并
    D.原问题和子问题使用相同的方法解
    答:————
19.[单选题] 下面问题（          ）不能使用贪心法解决。
    A.单源最短路径问题
    B.N皇后问题
    C.最小生成树问题
    D.背包问题
    答:————
20.[单选题] 设计动态规划算法的主要步骤不包括（          ）。
    A.找出最优解的性质
    B.递归地定义最优值
    C.以自顶向下的方式计算出最优值
    D.根据计算最优值时得到的信息，构造最优解
    答:————
21.[单选题] 下列算法中通常以深度优先方式系统搜索问题解的是（          ）。
    A.备忘录法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
22.[单选题] 下面不是分支界限法搜索方式的是（          ）。
    A.广度优先
    B.最小耗费优先
    C.最大效益优先
    D.深度优先
    答:————
23.[单选题] 哈夫曼编码的贪心算法所需的计算时间为（          ）。
    A.O（n2n）
    B.O（nlogn）
    C.O（2n）
    D.O（n）
    答:————
24.[单选题] 备忘录方法是那种算法的变形（          ）。
    A.分治法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
25.[单选题] 分支限界法解最大团问题时，活结点表的组织形式是（          ）。
    A.最小堆
    B.最大堆
    C.栈
    D.数组
    答:————
26.[单选题] 最长公共子序列算法利用的算法是
    A.分支界限法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
27.[单选题] 实现棋盘覆盖算法利用的算法是（          ）。
    A.分治法
    B.动态规划法
    C.贪心法
    D.回溯法
    答:————
28.[单选题] 回溯法的效率不依赖于下列哪些因素（          ）。
    A.满足显约束的值的个数
    B.计算约束函数的时间
    C.计算限界函数的时间
    D.确定解空间的时间
    答:————
29.[单选题] 下面是贪心算法的基本要素的是（          ）。
    A.重叠子问题
    B.构造最优解
    C.贪心选择性质
    D.定义最优解
    答:————
30.[单选题] 下面哪种函数是回溯法中为避免无效搜索采取的策略（          ）。
    A.递归函数
    B.剪枝函数
    C.随机数函数
    D.搜索函数
    答:————
31.[判断题] 利用概率的性质计算近似值的随机算法是数值概率算法，运行时以一定的概率得到正确解的随机算法是蒙特卡罗算法。
    A.对
    B.错
    答:————
32.[判断题] 算法的复杂性没有时间复杂性和空间复杂性之分。
    A.对
    B.错
    答:————
33.[判断题] 程序是算法用某种程序设计语言的具体实现。
    A.对
    B.错
    答:————
34.[判断题] 拉斯维加斯算法找到的解不一定是正确解。
    A.对
    B.错
    答:————
35.[判断题] 矩阵连乘问题的算法可由动态规划设计实现。
    A.对
    B.错
    答:————
36.[判断题] 算法的“确定性”指的是组成算法的每条指令是清晰的，有歧义的。
    A.对
    B.错
    答:————
37.[判断题] 计算一个算法时间复杂度通常无法计算循环次数基本操作的频率或计算步。
    A.对
    B.错
    答:————
38.[判断题] 使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。
    A.对
    B.错
    答:————
39.[判断题] 解决0/1背包问题可以使用动态规划回溯法和分支限界法，其中需要排序的是动态规划，不需要排序的是回溯法，分支限界法。
    A.对
    B.错
    答:————
40.[判断题] 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
    A.对
    B.错
    答:————
41.[判断题] 从分治法的一般设计模式可以看出，用它设计出的程序一般不是递归算法。
    A.对
    B.错
    答:————
42.[判断题] 算法是指解决问题的一种方法或一个过程。
    A.对
    B.错
    答:————
43.[判断题] 数值概率算法常用于数值问题的求解。
    A.对
    B.错
    答:————
44.[判断题] 以深度优先方式系统搜索问题解的算法称为动态规划法。
    A.对
    B.错
    答:————
45.[判断题] 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
    A.对
    B.错
    答:————
46.[问答题] 请编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
    答:————
47.[问答题] 请给出背包问题的程序解析。
    答:————
48.[问答题] 一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？
    答:————
49.[问答题] 采用递归方法找一个解与找全部解稍有不同，在找一个解的算法中，递归算法要对当前候选解最终是否能成为解要有回答。当它成为最终解时，递归函数就不再递归试探，立即返回；若不能成为解，就得继续试探。设函数queen_one()返回1表示找到解，返回0表示当前候选解不能成为解。
    答:————
50.[问答题] 假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮箱问题要求对于给定的n和m，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。 例如当n=5，m=4时，面值为1，3，11，15，32的5种邮票可以贴出邮资的最大连续区间是1到70。
    答:————
51.[问答题] 装载问题最优解
    答:————
52.[问答题] 请简述算法具有哪些属性？
    答:————
53.[问答题] 请简述算法的定义？
    答:————
54.[问答题] 请简述计算机求解问题的步骤？
    答:————
55.[问答题] 解析背包问题
    答:————
56.[问答题] 试阐述贪婪法
    答:————
57.[问答题] 动态规划的基本思想
    答:————
58.[问答题] 分治法的基本思想
    答:————
59.[问答题] 分治法的基本步骤
    答:————

更多学习资料www.openhelp100.com