川农大算法分析期末复习

《川农大算法分析期末复习》由会员分享，可在线阅读，更多相关《川农大算法分析期末复习（39页珍藏版）》请在装配图网上搜索。

1、-算法分析与设计复习题判断题1选择题：2判断题1. 算法就是一组有穷的规那么。答案：正确2. 概率算法中蒙特卡罗算法得到的解必是正确的。答案：错误3. 程序和算法一样，都是某种程序设计语言的具体实现。答案：错误4. 合并排序算法是渐近最优算法。答案：正确5. 递归定义必须是有确切含义是指必须一步比一步简单，最后是有终结的，决不能无限循环下去。答案：正确6. 二分搜索方法在最坏的情况下用O(log n)时间完成搜索任务。答案：正确7. 能否利用分治法完全取决于问题是否具有如下特征：利用该问题分解出的子问题的解可以合并为该问题的解。答案：正确8. 分治法的根本思想是将一个规模较大的问题分解成假设干

2、个规模较小的子问题，这些子问题之间并不一定相互独立。答案：错误9. 递归算法的效率往往很低，费时和费存空间。答案：正确10. 当一个问题具有最优子构造性质时只能用动态规划方法求解。答案：错误11. 如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，那么称它为多阶段决策问题。答案：正确12. 反复应用分治手段，不能使子问题与原问题类型一致而其规模却不断缩小。答案：错误13. 裴波那契数列的定义：f(n)=f(n-1)+f(n-2),f(0)=1,f(1)=2，其数据的定义形式不是按递归定义。答案：错误14. 0-1背包问题与背包问题这两类问题都可以用贪心算法求解。答案：错误15.

3、 证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子构造性质。答案：错误16. 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。答案：正确17. 概率算法允许在执行过程中随机地选择下一个计算步骤。答案：正确18. 二分搜索法的二分查找只适用于顺序存储构造。答案：正确19. 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。答案：正确20. 用回溯法解题一个显著特征是在搜索过程中动态产生问题的解空间。答案：错误21. 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进展分析。答案：正

4、确22. 多阶段决策问题中，每一个阶段可能有假设干个决策可供选择答案：正确23. 拉斯维加斯算法不会得到不正确的解，但有时找不到解。答案：正确24. 在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。答案：正确25. 要想在电脑上扩大所处理问题的规模，有效的途径是提高算法的计算复杂度。答案：错误26. 程序必须满足算法具有数据输出的性质。答案：正确27. 反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小答案：正确28. 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量答案：正确29. 最优子构造性质特征反映了递归思想的应用答案：

5、正确30. 递归边界本身并不使用递归的定义答案：正确31. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。答案：正确32. 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个最优解。答案：正确33. 好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。答案：正确34. 一个递归定义必须是有确切含义的，必须一步比一步简单，最后是有终结的，不能无限循环下去。答案：正确35. 最优子构造性质是应用分治法的前提。答案：正确36.

6、 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。答案：正确37. 有些数据构造如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。答案：正确38. 概率算法的一个根本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全一样的效果。答案：错误39. 问题可以分解为假设干个规模较小的一样问题，即称该问题具有最优子构造性质。答案：错误40. 递推是从边界条件出发，通过递推式到达边界条件。答案：正确41.所有的递归函数都能找到对应的非递归定义。答案：正确42.定义递归函数时可以没有初始值。答案：错误43.动态规划算法的根本要素是最优子构造。答案：正确44.最优子构造

7、性质是指原问题的最优解包含其子问题的最优解。答案：正确45.动态规划算法求解问题时，分解出来的子问题相互独立。答案：错误46.满足贪心选择性质必满足最优子构造性质。答案：错误47.回溯法中限界函数的目的是剪去得不到最优解的子树。答案：正确48. 分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是一样的。答案：错误49. 任何递归算法都有递归出口。答案：正确50. 递归算法的执行效率比功能一样的非递归算法的执行效率高。答案：错误51. 递归算法不能转换成对应的非递归算法。答案：错误52. 数据元素是数据的最小单位答案：错误53. 数据对象就是一组数据元素的集合

8、答案：错误54. 任何数据构造都具备三个根本运算：插入、删除和查找。答案：错误55. 数据对象是由有限个类型一样的数据元素构成的。答案：正确56. 数据的逻辑构造与各数据元素在计算机中如何存储有关。答案：错误57. 如果数据元素值发生改变，那么数据的逻辑构造也随之改变。答案：错误58. 逻辑构造一样的数据，可以采用多种不同的存储方法。答案：正确59. 逻辑构造不一样的数据，必须采用不同的存储方法来存储。答案：错误60.数据的逻辑构造是指数据元素的各数据项之间的逻辑关系。答案：错误61.顺序存储方式只能用于存储线性构造。答案：错误62. 算法可以用不同的语言来描述，如果用C语言或Pascal语言

9、等高级语言来描述，那么算法就等同于程序。答案：错误63.数据的逻辑构造是指各数据元素之间的逻辑关系。答案：正确64.数据构造、数据元素、数据项在计算机中的映像或表示分别称为存储构造、节点和数据域。答案：正确65.数据的物理构造是指数据在计算机的实际存储形式。答案：正确66.分配给单链表的存与地址必须是连续的。答案：错误67.从长度为n的顺序表中删除任何一个元素，时间复杂度都是O(n)。答案：错误68. 向顺序表中插入一个元素，平均要移动大约一半的元素。答案：正确69.但凡为空的单链表都是不含任何节点的。答案：错误70. 如果单链表带有头节点，那么插入操作永远不会改变头节点指针的值。答案：正确7

10、1. 在循环单链表中，任何一个节点的指针域都不可能为空。答案：正确72. 顺序存储方式的特点是存储密度大且插入、删除运算效率高。答案：错误73. 线性表的顺序存储构造优于链式存储构造。答案：错误74. 顺序存储构造属于静态构造而链式存储构造属于动态构造。答案：正确75. 由于顺序存储构造要求连续的存储区域，所以在存储管理上不够灵活。答案：正确76. 对于单链表来说，只有从头节点开场才能扫描表中全部节点。答案：正确77. 对于循环单链表来说，从表中任一节点出发都能扫描表中全部节点。答案：正确78. 双链表的特点是很容易找任一节点的前趋和后继。答案：正确79. 线性表有两种存储构造：一是顺序表，二

11、是链表。答案：正确80. 如果有多个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动改变。在此情况下，应选用链式存储构造。答案：正确81.假设线性表的总数根本稳定且很少进展插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应该选用顺序存储构造。答案：正确82.对于单链表和双链表，均能从当前节点出发访问到任一节点。答案：错误83. 循环单链表和循环双链表从尾指针出发可以访问到链表中的任意节点。答案：正确84.假设频繁地对一个线性表进展插入和删除操作，该线性表宜采用链式存储构造。答案：正确85.栈底元素是不能删除的元素。答案：错误86.顺序栈中元素值的大小是

12、有序的。答案：错误87.栈顶元素和栈底元素有可能是同一个元素。答案：正确88. 假设用s1m表示顺序栈的存储空间，那么对栈的进栈、出栈操作最多只能进展m次。答案：错误89. 栈是一种对进栈、出栈操作总次数作了限制的线性表。答案：错误90. 空栈没有栈顶指针答案：错误91. 环形队列中有多少元素，可以根据队首指针和队尾指针的值来计算。答案：正确92. 无论是顺序队列，还是链式队列，插入、删除运算的时间复杂度都是O(1)。答案：正确93. 栈和队列都是插入和删除操作受限的线性表。答案：正确94. 栈和队列的存储方式既可以是顺序方式，也可以是链式方式答案：正确95. 环形队列也存在空间溢出的问题答案

13、：正确96.消除递归不一定需要使用栈。答案：正确97. 二分搜索算法是利用贪心法实现的算法。答案：错误98. 动态规划算法通常是以自底向上的方式求解最优解。答案：正确99. 贪心法不能解决0/1背包问题。答案：正确100. 深度优先不是分支限界法的搜索方式。答案：正确101. 二分搜索算法是利用分治策略实现的算法。答案：正确102. 背包问题不能使用贪心法解决。答案：错误103. 单源最短路径问题不能使用贪心法解决。答案：错误104. 时间复杂度低是衡量一个算法好坏的标准。答案：正确105. 归并排序不可以使用分治法求解。答案：错误106. 拉斯维加斯算法有时找不到问题的解。答案：正确107.

14、 舍伍德算法有时候找不到问题的解。答案：错误108. NP问题都是不可能解决的问题答案：错误109. P类问题包含在NP类问题中。答案：正确110. NP类问题包含在P类问题中。答案：错误111. NP完全问题是P类问题的子集答案：错误112. 蒙特卡罗算法是概率算法的一种答案：正确113. 蒙特卡罗算法是贪心算法的一种答案：错误114. 蒙特卡罗算法是回溯算法的一种答案：错误115. 动态规划算法不是随机化算法答案：正确116. 最优子构造性质是贪心算法与动态规划算法的共同点答案：正确117. 矩阵连乘问题的算法可由动态规划算法来设计实现答案：正确118. Strassen 矩阵乘法是利用分

15、治策略实现的算法答案：正确119. Strassen 矩阵乘法是利用贪心法实现的算法答案：错误120. 贪心选择性质是贪心算法的根本要素答案：正确121. 以深度优先方式系统搜索问题解的算法称为回溯算法答案：正确122. 算法分析的两个主要方面是时间复杂度和空间复杂度分析答案：正确123. 实现最大子段和利用的算法是动态规划法答案：正确124. 实现最大子段和利用的算法是贪心法答案：错误125. 实现最大子段和利用的算法是回溯法答案：错误126. 广度优先是分支限界算法的一种搜索方式答案：正确127. 广度优先是回溯算法的一种搜索方式答案：错误128. 广度优先是贪心算法的一种搜索方式答案：错

16、误129. 舍伍德算法是概率算法的一种答案：正确130. 舍伍德算法是贪心算法的一种。答案：错误131. 舍伍德算法是回溯算法的一种。答案：错误132. 实现最长公共子序列利用的算法是动态规划法。答案：正确133. 计算机算法指的是解决问题的方法和过程。答案：正确134. 根据排序元素所在位置的不同，排序分排序和外排序。答案：正确135. 根据排序元素所在位置的不同，排序分首排序和尾排序。答案：错误136. 算法必须具备输入、输出和有穷性、确定性和可行性等5个特性。答案：正确137. 算法必须具备输入、输出和易读性、稳定性和平安性等 5个特性。答案：错误138. 与分治法不同的是，适合于用动态

17、规划求解的问题经分解得到的子问题往往不是相互独立的答案：正确139. 与分治法不同的是，适合于用动态规划求解的问题往往是相互独立的答案：错误140. 二分搜索算法的根本思想是将 n 个元素分成个数大致一样的两半，取 an/2与 x 进展比拟：如果xan/2，那么只要在数组 a 的左半部继续搜索 x答案：错误142.算法必须具备输入、输出和可执行性、可移植性和可扩大性等5个特性。答案：错误143. 适用动态规划的问题必须满足最优化原理和无后效性。答案：正确144. 适用动态规划的问题必须满足最优化原理和后效性。答案：错误145. 二分查找只适用于顺序存储构造。答案：正确146. 二分查找只适用于

18、链式存储构造。答案：错误147. 应用分治法的两个前提是问题的可分性和解的可归并性。答案：正确148. 应用分治法的两个前提是问题的可分性和解的复杂性。答案：错误149. 对于n个元素的排序问题。n2时只要作1次比拟即可排好序。答案：正确150. 对于n个元素的排序问题。n2时要作2次比拟即可排好序。答案：错误151. 分治法所能解决的问题应具有的关键特征是利用该问题分解出的子问题的解可以合并为该问题的解。答案：正确152. 分治法所能解决的问题应具有的关键特征是该问题的规模缩小到一定的程度就可以容易地解决。答案：错误153. 直接或间接的调用自身的算法称为递归算法。答案：正确154. 直接或

19、间接的调用自身的算法称为动态规划算法。答案：错误155.当上下限表示相等时我们使用表示法来描述算法代价。答案：正确156. 当上下限表示相等时我们使用大O表示法来描述算法代价。答案：错误157. 递归通常用栈来实现。答案：正确158. 递归通常用队列来实现。答案：错误159. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题的问题规模不同，问题性质一样。答案：正确160. 0/1背包问题不能用贪心算法求解。答案：正确161. 可以由多项式时间算法求解的问题是易处理的。答案：正确162. 可以由多项式时间

20、算法求解的问题是难处理的。答案：错误163. 需要超过多项式时间算法求解的问题是不能处理的。答案：错误164. 递归通常用数组来实现。答案：错误165. 哈密尔顿回路问题是典型的NP完全问题。答案：正确166. 排序问题是典型的NP完全问题。答案：错误167. 算法分析需要对算法需要多少计算时间和存储空间作定量分析。答案：正确168. 用数量级形式表示算法的执行时间称为算法的时间复杂度。答案：正确169. 用数量级形式表示算法的执行时间称为算法的空间复杂度。答案：错误170. 最坏情况下，顺序查找的时间复杂度为O(n)。答案：正确171. 最坏情况下，折半查找的时间复杂度为O(log2n)。答

21、案：正确172. 合并排序的根本运算是把两个或多个有序序列合并成一个有序序列答案：正确173. 最优子构造是动态规划算法的根本要素之一。答案：正确174. 快速排序算法是基于分治策略的一种排序算法。答案：正确175. 快速排序算法是基于回溯的一种排序算法。答案：错误176. 快速排序算法是基于贪心法的一种排序算法。答案：错误177. 贪心法通常以自顶向下的方式求解最优解。答案：正确178. 分治法通常以自顶向下的方式求解最优解。答案：错误179. 回溯法通常以自顶向下的方式求解最优解。答案：错误180. 不断回头寻找目标的方法称为回溯法。答案：正确181. 不断回头寻找目标的方法称为概率算法。

22、答案：错误182. 不断回头寻找目标的方法称为贪心法。答案：错误183. 拉斯维加斯算法找到的解一定是正确的。答案：正确184. 拉斯维加斯算法找到的解正确与否不确定。答案：错误185. 记号在算法复杂性的表示法中表示紧致界。答案：正确186. 记号在算法复杂性的表示法中表示上界。答案：错误187. 记号在算法复杂性的表示法中表示下界。答案：错误188. 一个算法是对特定问题求解的一种描述，它是指令的有限序列。答案：正确189. 一个递归算法必须包括终止条件和递归局部。答案：正确190. 栈和队列的共同点是只允许在端点处插入和删除元素。答案：正确191. 排序趟数与原始序列有关的排序方法是冒泡

23、排序法。答案：正确192. 栈和队列的共同点都是先进先出。答案：错误193.栈和队列的共同点都是先进后出。答案：错误194. 排序趟数与原始序列有关的排序方法是选择排序法。答案：错误195. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是最坏情况下的时间复杂度。答案：正确196. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是最好情况下的时间复杂度。答案：错误197. 假设一个算法的时间复杂度用T(n)表示，其中n的含义是问题规模。答案：正确198. 合并排序法的根本思想是：将待排序元素分成大小大致一样的2个子集合，分别对每个子集合进展排序，最终将排好序的子集合合并

24、成为所要求的排好序的集合。答案：正确选择题：1. 二分搜索算法是利用 A 实现的算法。选项A. 分治策略选项B. 动态规划法选项C. 贪心法选项D. 回溯法答案：2. 回溯法解旅行售货员问题时的解空间树是 B 。选项A. 子集树选项B. 排列树选项C. 深度优先生成树选项D. 广度优先生成树答案：3. 以下算法常以自底向上的方式求解最优解的是 B 。选项A. 备忘录法选项B. 动态规划法选项C. 贪心法选项D. 回溯法答案：4. 下面不是分支界限法搜索方式的是 D 。选项A. 广度优先选项B. 最小消耗优先选项C. 最大效益优先选项D. 深度优先答案：5采用贪心算法的最优装载问题的主要计算量在

25、于将集装箱依其重量从小到大排序，故算法的时间复杂度 B 。A、OB、OC、OD、O6分支限界法求解最大团问题时，活结点表的组织形式是 B 。A、最小堆B、最大堆C、栈D、数组7、下面问题 B 不能使用贪心法解决。A 单源最短路径问题B N皇后问题C 最小花费生成树问题D 背包问题答案：8.以下算法中不能解决0/1 背包问题的是 A 。A 贪心法B 动态规划C 回溯法D 分支限界法答案：9.背包问题的贪心算法所需的计算时间为 B 。A、On B、OnlognC、OD、On答案：10二分搜索算法是利用 A 实现的算法。A. 分治策略B、动态规划法C、贪心法D、回溯法答案：11以下不是动态规划算法根

26、本步骤的是 B 。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解答案：12最大效益优先是 A 的一种搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法答案：13、在以下算法中有时找不到问题解的是 B 。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法答案：14以下算法常以自底向上的方式求解最优解的是 B 。A、备忘录法B、动态规划法C、贪心法D、回溯法答案：14以下算法常以自底向上的方式求解最优解的是 B 。A、备忘录法B、动态规划法C、贪心法D、回溯法答案：15、衡量一个算法好坏的标准是 C 。A 运行速度快B 占用空间少C 时间复杂度低D 代码短答案

27、：16、以下不可以使用分治法求解的是 D 。A、棋盘覆盖问题B、选择问题C、归并排序D、 0/1背包问题答案：17. 实现循环赛日程表利用的算法是 A A、分治策略B、动态规划法C、贪心法D、回溯法答案：18、以下随机算法中运行时有时候成功有时候失败的是 C A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法答案：19下面不是分支界限法搜索方式的是 D 。A、广度优先B、最小消耗优先C、最大效益优先D、深度优先答案：20以下算法常以深度优先方式系统搜索问题解的是 D 。A、备忘录法B、动态规划法C、贪心法D、回溯法答案：21.备忘录方法是那种算法的变形。 B 。A、分治法B、动态

28、规划法C、贪心法D、回溯法答案：22哈弗曼编码的贪心算法所需的计算时间为 B 。A、OnB、OnlognC、OD、On答案：23最长公共子序列算法利用的算法是 B A、分支界限法B、动态规划法C、贪心法D、回溯法答案：24实现棋盘覆盖算法利用的算法是 A 。A、分治法B、动态规划法C、贪心法D、回溯法答案：25.下面是贪心算法的根本要素的是 C 。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解26.回溯法的效率不依赖于以下哪些因素 D 。A. 满足显约束的值的个数C. 计算限界函数的时间B. 计算约束函数的时间D. 确定解空间的时间27.下面哪种函数是回溯法中为防止无效搜索采取的策

29、略 B 。A递归函数B. 剪枝函数C随机数函数D搜索函数28、下面关于 NP 问题说确的是 B 。ANP问题都是不可能解决的问题BP类问题包含在NP类问题中CNP 完全问题是P类问题的子集DNP类问题包含在P类问题中29、蒙特卡罗算法是 B 的一种。A. 分支界限算法B. 概率算法C. 贪心算法D. 回溯算法答案：30.以下哪一种算法不是随机化算法 C 。A. 蒙特卡罗算法B. 拉斯维加斯算法C. 动态规划算法D.舍伍德算法答案：31. D 是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子构造性质答案：32. 矩阵连乘问题的算法可由 B 设计实现。A、分

30、支界限算法B、动态规划算法C、贪心算法D、回溯算法答案：33、Strassen 矩阵乘法是利用 A 实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法答案：34、使用分治法求解不需要满足的条件是 A 。A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用一样的方法求解答案：35、回溯法搜索状态空间树是按照 C的顺序。A 中序遍历B 广度优先遍历C 深度优先遍历D 层次优先遍历答案：36、实现合并排序利用的算法是 A A、分治策略B、动态规划法C、贪心法D、回溯法答案：37、以下是动态规划算法根本要素的是 D A、定义最优解B、构造最优解C、算出最优解D

31、、子空间重叠性质答案：38采用广度优先策略搜索的算法是 A A、分支界限法B、动态规划法C、贪心法D、回溯法答案：39、在以下算法中得到的解未必正确的选项是 A A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法答案：40实现大整数的乘法是利用的算法 C A、贪心法B、动态规划法C、分治策略D、回溯法答案：410-1 背包问题的回溯算法所需的计算时间为 A A、OnB、OnlognC、OD、On答案：42贪心算法与动态规划算法的主要区别是 B A、最优子构造B、贪心选择性质C、构造最优解D、定义最优解答案：43. 实现最大子段和利用的算法是 B 。A、分治策略B、动态规划法C、贪

32、心法D、回溯法答案：44.优先队列式分支限界法选取扩展结点的原那么是 C A、先进先出B、后进先出C、结点的优先级D、随机答案：45、广度优先是 A 的一种搜索方式。A、分支界限算法B、动态规划法C、贪心算法D、回溯算法答案：46、舍伍德算法是 B 的一种A、分支界限算法B、概率算法C、贪心算法D、回溯算法答案：47、在以下算法中有时找不到问题解的是 B A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法答案：48 以下哪一种算法是随机化算法 D 。A. 贪心算法B. 回溯法C. 动态规划算法D. 舍伍德算法答案：49. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的

33、B 。A、重叠子问题B、最优子构造性质C、贪心选择性质D、定义最优解答案：52. 以深度优先方式系统搜索问题解的算法称为 D 。A、分支界限算法B、概率算法C、贪心算法D、回溯算法答案：53. 实现最长公共子序列利用的算法是 B 。A、分治策略B、动态规划法C、贪心法D、回溯法54. 算法分析的两个主要方面是 A 。A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂度和程序复杂度55. 计算机算法指的是 C 。A. 计算方法B. 排序方法C. 解决问题的方法和过程D. 调度方法56. 多阶段决策问题就是要在可以选择的那些策略中间选取一个 A 策略使在预定的标准下

34、到达最好的效果。A. 最优B. 最差C. 平衡D. 任意57. 根据排序元素所在位置的不同，排序分 A 。A. 排序和外排序B. 首排序和尾排序C. 顺序排序和逆序排序D. 堆排序和栈排序58. 算法必须具备输入、输出和 B 等 5 个特性。A. 可执行性、可移植性和可扩大性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和平安性59. 与分治法不同的是，适合于用动态规划求解的问题 A 。A. 经分解得到子问题往往不是互相独立的B. 经分解得到子问题往往是互相独立的C.经分解得到子问题往往是互相穿插的D. 经分解得到子问题往往是任意的60. 二分搜索算法的根本思想是

35、将 n 个元素分成个数大致一样的两半，取 an/2与 x 进展比拟：如果 A ，那么只要在数组 a 的左半部继续搜索 x。A. xan/2B. x=an/2C. xan/2D. x=an/261. 活动安排问题就是在所给的活动集合中，选出 C 的相容活子集。A. 最小B. 任意C. 最大D. 一个62. 在对问题的解空间树进展搜索的方法中一个活结点最多有一次时机成为活结点的是 B 。A. 回溯法B. 分支限界法C. 回溯法和分支限界法D. 回溯法求解子集树问题63. 适用动态规划的问题必须满足 D 。A. 最优化原理B. 无前效性C. 最优化原理和后效性D. 最优化原理和无后效性64. 算法的

36、每种运算必须要有确切的定义不能有二义性，以下符合算法确定性运算的是 B 。A. 5/0 B.将6或7与x相加C.未赋值变量参与运算D. f(n)=f(n-1)+2，F(1)=10，n为自然数65. 直接或间接的调用自身的算法称为 B 。A. 贪心算法B. 递归算法C. 迭代算法D. 动态规划算法66. 二分查找只适用 B 存储构造。A. 堆B. 顺序C. 任意顺序D. 栈67. 应用分治法的两个前提是 A 。A. 问题的可分性和解的可归并性B. 问题的可分性和解的存在性C. 问题的复杂性和解的可归并性D. 问题的可分性和解的复杂性68. 优先队列的分支限界法将活结点表组织成一个优先队列，并按优

37、先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的上下与p值大小相关，根据问题的不同情况，采用 C 来描述优先队列。A. 先进先出队列B. 后进先出的栈C. 最大堆或最小堆D. 随机序列69. 阶乘函数用递归定义 Public static int factorialint n ifn=0return 1；return B ：A. n*factorial(n)B. n*factorial(n-1)C. n*factorial(n-2)D. n*factorial(n+1)70. B 能够求得问题的解但却

38、无法有效地判定解的正确性。A. 数值概率算法B. 蒙特卡罗算法C. 拉斯维加斯算法D. 舍伍得算法71. 对于n个元素的排序问题。n2时只要作 C 次比拟即可排好序。A. 3B. 2C. 1D. 472. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比： B 。A. 效果一样B. 动态规划效果好C. 备忘录方法效果好D. 无法判断哪个效果好73. 分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者 B 。A. 求解目标不同搜索方式一样B. 求解目标不同搜索方式也不同C. 求解目标一样搜索方式不同D. 求解目标一样搜索方式也一样74. 递归算法不能适用

39、以下场合 D 。A. 数据的定义形式按递归定义B. 数据之间的关系即数据构造按递归定义C. 问题解法按递归算法实现D. 概率问题75. 假设当子问题之间包含公共的子子问题时，那么分治法要做许多不必要的工作，重复地解公共的子问题，此时一般用 A 法较好。A. 动态规划B. 分治C. 贪心D. 概率76. 分治法所能解决的问题应具有的关键特征是 C 。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为假设干个规模较小的一样问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的77. 对于货箱装船问题根据贪心策略首先选择 A 的货

40、箱然后选 A 的货箱如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。A. 最轻次轻B. 最重次重C. 最轻次重D.最重次轻78. 用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树，place中的if判断条件应为 A 。A. (Math.abs(k-j)=Math.abs(xj-xk)|xj=xk)B. (Math.abs(k-j)=Math.abs(xj-xk)C. (xj-xk)D. 以上都不正确79. 分支限界法的搜索策略是：在扩展结点处，先生成其 D 儿子结点分支，然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下

41、一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值限界，并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。A. 一个B. 二个C. 任意多个D. 所有的80. 能够用动态规划解决的问题还有一个显著特征 D 这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。A. 子问题的可求解性B. 子问题的独立性C. 子问题的可合并性D. 子问题的重叠性81. 在任何一个的棋盘覆盖中，用到的L型骨牌个数恰为 A 。A. B. C. D. 82. 以Bito

42、nic旅行路线问题为例，动态规划的时间复杂度为 C 。A. O(n)B. O(n!)C. O(n2)D. O(n3)83. 一个算法应该包含如下几条性质除了 A 。A二义性B有限性C正确性D 可终止性84. 解决一个问题通常有多种方法。假设说一个算法有效是指 D 。A. 这个算法能在一定的时间和空间资源限制将问题解决B这个算法能在人的反响时间将问题解决C这个算法比其他算法都更快地将问题解决D A和C 85. 当输入规模为n时算法增长率最小的是 B 。ABCD86渐进算法分析是指 B 。A. 算法在最正确情况、最差情况和平均情况下的代价B. 当规模逐步往极限方向增大时对算法资源开销增长率上的简化

43、分析C. 数据构造所占用的空间D. 在最小输入规模下算法的资源代价87当上下限表达式相等时我们使用以下哪种表示法来描述算法代价 C A大O表示法B大表示法C表示法D 小o表示法88. 采用顺序搜索法从一个长度为N的随机分布数组中搜寻值为K的元素，以下对顺序搜索法分析正确的选项是 B 。A最正确情况、最差情况和平均情况下顺序搜索法的渐进代价都一样B最正确情况的渐进代价要好于最差情况和平均情况的渐进代价C最正确情况和平均情况的渐进代价要好于最差情况的渐进代价D最正确情况的渐进代价要好于平均情况的渐进代价而平均情况的渐进代价要好于最差情况的渐进代价89递归通常用 C 来实现。A. 有序的线性表B.

44、队列C. 栈D. 数组90. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 C 。A问题规模一样，问题性质一样B问题规模一样，问题性质不同C问题规模不同，问题性质一样D问题规模不同，问题性质不同91在寻找n个元素中第k小元素问题中如快速排序算法思想运用分治算法对n个元素进展划分如何选择划分基准下面 D 答案解释最合理。A随机选择一个元素作为划分基准B取子序列的第一个元素作为划分基准C用中位数的中位数方法寻找划分基准D以上皆可行。但不同方法算法复杂度上界可能不同92. 对于01背包问题和背包问题的解法

45、下面 C 答案解释正确。A01背包问题和背包问题都可用贪心算法求解B01背包问题可用贪心算法求解但背包问题那么不能用贪心算法求解C01背包问题不能用贪心算法求解但可以使用动态规划或搜索算法求解而背包问题那么可以用贪心算法求解D因为01背包问题不具有最优子构造性质所以不能用贪心算法求解93关于回溯搜索法的介绍下面 D 是不正确描述。A回溯法有通用解题法之称它可以系统地搜索一个问题的所有解或任意解B回溯法是一种既带系统性又带有跳跃性的搜索算法C回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解如果肯定不包含那么跳过对该结点为根的子树的搜索逐层向祖先结点回溯D回溯算法需要借助队列这种构

46、造来保存从根结点到当前扩展结点的路径94. 关于回溯算法和分支限界法以下 A 是不正确描述。A回溯法中每个活结点只有一次时机成为扩展结点B分支限界法中活结点一旦成为扩展结点就一次性产生其所有儿子结点在这些儿子结点中那些导致不可行解或导致非最优解的儿子结点被舍弃其余儿子参加活结点表中C回溯法采用深度优先的结点生成策略D分支限界法采用广度优先或最小消耗优先最大效益优先的结点生成策略95. 优先队列通常用以下 B 数据构造来实现。A栈B堆C队列D二叉查找树96. 在分支限界算法中根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下 D 描述最为准确。A采用FIFO队列的队列式分支限界法B

47、采用最小值堆的优先队列式分支限界法C采用最大值堆的优先队列式分支限界法D以上都常用针对具体问题可以选择采用其中某种更为适宜的方式97. 对布线问题以下 C 是不正确描述。A布线问题的解空间是一个图B可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定C采用广度优先的标号法找到从起点到终点的布线方案这个方案如果存在的话不一定是最短的D采用先入先出的队列作为活结点表以，终点b为扩展结点或活结点队列为空作为算法完毕条件98. 下述表达不正确的选项是 D 。A. 的渐进表达式上界函数是B的渐进表达式下界函数是C的渐进表达式上界函数是D的渐进表达式下界函数是99当输入规模为

48、n时，算法增长率最大的是 A 。ABCD100. T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是 C 。AT(n)=T(n-1)+1，T(1)=1BT(n)=2n2C. T(n)=T(n/2)+1，T(1)=1D. T(n)=3nlog2n101. 有9个村庄，其坐标位置如下表所示：i123456789x(i)123456789y(i)123456789现在要盖一所邮局为这9个村庄效劳，请问邮局应该盖在 C 才能使邮局到9个村庄的距离和最短。A. 4.5，0B. 4.5，4.5C. 5，5D. 5，0102. n个人拎着水桶在一个水龙头前面排队打水水桶有大有小水桶必须打满水水流恒

49、定。如下 A 说法不正确A让水桶大的人先打水可以使得每个人排队时间之和最小B让水桶小的人先打水可以使得每个人排队时间之和最小C让水桶小的人先打水在某个确定的时间t可以让尽可能多的人打上水D假设要在尽可能短的时间n个人都打完水按照什么顺序其实都一样103. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 B 。104以下关于判定问题难易处理的表达中正确的选项是 C A.可以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的105. 回溯法在解空间树T上的搜索

50、方式是 A A. 深度优先B. 广度优先C. 最小消耗优先D. 活结点优先106. 设f(N)，g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，那么称函数f(N)当N充分大时有上界g(N)，记作f(N)=O(g(N),即f(N)的阶 Ag(N)的阶。A. 不高于B. 不低于C. 等价于D. 逼近107. 以下 C 不能在线性时间完成排序A.计数排序B.基数排序C.堆排序D.桶排序108. 以下 A 不一定得到问题的最优解A.贪心算法B.回溯算法C.分支限界法D.动态规划法109.以下不属于一个好的算法应具有的特性的是 C 。A. 正确性B.

51、 简明性C. 无限性D. 最优性110. 算法分析是 C 。A. 将算法用某种程序设计语言恰当地表示出来B在抽象数据集合上执行程序，以确定是否会产生错误的结果C. 对算法需要多少计算时间和存储空间作定量分析D. 证明算法对所有可能的合法输入都能算出正确的答案111. 学校要举行运动会，请你设计一个能够对运发动分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是 C 。A. 分析问题，编写程序，设计算法，调试程序B. 设计算法，编写程序，提出问题，调试程序C. 提出问题，设计算法，编写程序，调试程序D. 设计算法，提出问题，编写程序，调试程序112. 考虑背包问题：n=6，M=10，V1

52、:6=15，59，21，30，60，5，W1:6=1，5，2，3，6，1。该问题的最大效益值为 C 。A. 101B. 110C. 115D.120113. 考虑背包问题：n=6，M=10，V1:6=15，59，21，30，60，5，W1:6=1，5，2，3，6，1。假设把它看作是0/1背包问题，那么该问题的最大效益值为 B 。A. 101B. 110C. 115D.120114. 找最小生成树的算法Kruskal的时间复杂度为 D 。A. O(n2)B. O(mlogn)C. O(nlogm)D. O(mlogm)115. 算法与程序的区别在于算法具有 C 。A. 能行性B. 确定性C. 有

53、穷性D. 输入和输出116. 设A1.60=11,12,70。算法折半查找在A上搜索x=33、7、70、77时执行的元素比拟次数分别为a、b、c、d, 那么 C 。A. abcb=c=dC. ab=c=dD. ac0) hanoi( n-1, a, c, b); move(a, b);hanoi( n-1, c, b, a);上述算法的时间复杂度为 A 。A. O(2n)B. O(nlogn)C. D. 119. 当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差异时，可以使用 B 来消除或减少问题的好坏实例间的这种差异。A. 数值概率算法B. 舍伍德算法C. 拉斯维

54、加斯算法D. 蒙特卡罗算法120. 当输入规模为n时，算法增长率最快的是( C )。A. 12nB.C. 2n2D. 121. 关于0-1背包问题，以下描述正确的选项是 D 。A. 可以使用贪心算法找到最优解B. 能找到多项式时间的有效算法C. 使用教材介绍的动态规划方法可求解任意0-1背包问题D. 对于同一背包与一样的物品，做背包问题取得的总价值一定大于等于做0-1背包问题。122. 设有n项独立的作业1,2, n,由m台一样的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调

55、度方案，使所给的n个作业在尽可能短的时间由m台机器处理完nm。对于多级调度问题，使用哪种贪心策略比拟适宜 B 。A. 作业从小到大依次分配给空闲的机器B. 作业从大到小依次分配给空闲的机器C. 每个机器分配一样的作业数D. 使用以上几种贪心策略都能找到最优解，所以都适宜123. 使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比拟的次数为 A 。A. 10B. 11C. 500D. 1000124. 用数量级形式表示算法的执行时间称为算法的 A 。A. 时间复杂度B. 空间复杂度C. 处理器复杂度D. 通信复杂度125. 下面哪个问题不是典型的NP完全问题

56、D 。A. m-着色问题B. 旅行商问题C. 哈密尔顿回路问题D. 排序问题126. 顺序查找的时间复杂度为 A 。A. O(n)B. O(logn)C. O(n2)D.O(nlogn)127. 折半查找的时间复杂度为 B 。A. O(n)B. O(logn)C. O(n2)D.O(nlogn)128. 算法的复杂性有时间复杂性和 C 复杂性之分。A. 处理器复杂性B. 通信复杂性C. 空间复杂性D. 存储复杂性129. 算法的复杂性有空间复杂性和 C 复杂性之分。A. 处理器复杂性B. 通信复杂性C. 时间复杂性D. 存储复杂性130. 算法是由假设干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。其中算法的确定性是指组成算法的每条 B 是清晰的，无歧义的。A. 程序B. 指令C. 语句D. 语句块131. ( C ) 的根本运算是把两个或多个有序序列合并成一个有序序列。