川农大算法分析期末复习

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

1、算法分析与设计 复习题判断题1选择题：15判断题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. 最优子结构性质是应用分治法的前提。答案：

6、正确36. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。答案：正确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语言或Pas

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

10、。答案：正确71. 在循环单链表中，任何一个节点的指针域都不可能为空。答案：正确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. 拉斯维加斯算法有时找不到问题的解。答案：正确1

14、07. 舍伍德算法有时候找不到问题的解。答案：错误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(log

21、2n)。答案：正确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. 最大效益优先 选

25、项D. 深度优先 答案：5采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度（ B ）。 A、O（） B、O（） C、O（） D、O（） 6分支限界法求解最大团问题时，活结点表的组织形式是（ B ）。A、最小堆 B、最大堆 C、栈 D、数组 7、下面问题（ B ）不能使用贪心法解决。 A 单源最短路径问题 B N皇后问题C 最小花费生成树问题 D 背包问题 答案：8.下列算法中不能解决0/1 背包问题的是（ A ）。 A 贪心法 B 动态规划 C 回溯法 D 分支限界法 答案：9.背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n ） B、O（n

26、logn） C、O（ ） D、O（n） 答案：10二分搜索算法是利用（ A ）实现的算法。A. 分治策略 B、动态规划法 C、贪心法 D、回溯法答案：11下列不是动态规划算法基本步骤的是（ B ）。A、找出最优解的性质 B、构造最优解 C、算出最优解D、定义最优解答案：12最大效益优先是（ A ）的一种搜索方式。A、分支界限法B、动态规划法C、贪心法D、回溯法答案：13、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法B、拉斯维加斯算法 C、舍伍德算法D、数值概率算法答案：14下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、

27、回溯法 答案：14下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 答案：15、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 答案：16、以下不可以使用分治法求解的是（ D ） 。 A、 棋盘覆盖问题 B、 选择问题 C、 归并排序 D、 0/1背包问题答案：17. 实现循环赛日程表利用的算法是（ A ）A、分治策略 B、动态规划法 C、贪心法 D、回溯法答案：18、下列随机算法中运行时有时候成功有时候失败的是（ C ） A 数值概率算法 B 舍伍德算法C 拉斯维加斯算法 D 蒙

28、特卡罗算法 答案：19下面不是分支界限法搜索方式的是（ D ）。A、广度优先B、最小耗费优先C、最大效益优先D、深度优先答案：20下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。A、备忘录法 B、动态规划法 C、贪心法D、回溯法答案：21.备忘录方法是那种算法的变形。（ B ）。A、分治法B、动态规划法 C、贪心法D、回溯法 答案：22哈弗曼编码的贪心算法所需的计算时间为（ B ）。A、O（n）B、O（nlogn） C、O（）D、O（n）答案：23最长公共子序列算法利用的算法是（ B ）A、分支界限法B、动态规划法 C、贪心法 D、回溯法 答案：24实现棋盘覆盖算法利用的算法是（ A

29、 ）。A、分治法 B、动态规划法C、贪心法D、回溯法答案：25.下面是贪心算法的基本要素的是（ C ）。A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 26.回溯法的效率不依赖于下列哪些因素（ D ）。A. 满足显约束的值的个数 C. 计算限界函数的时间 B. 计算约束函数的时间 D. 确定解空间的时间27.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）。A递归函数 B. 剪枝函数 C随机数函数D搜索函数28、下面关于 NP 问题说法正确的是（ B ）。 ANP 问题都是不可能解决的问题 BP类问题包含在NP类问题中CNP 完全问题是P类问题的子集DNP类问题包含在

30、P类问题中29、蒙特卡罗算法是（ B ）的一种。A. 分支界限算法B. 概率算法C. 贪心算法 D. 回溯算法 答案： 30.下列哪一种算法不是随机化算法（ C ）。 A. 蒙特卡罗算法 B. 拉斯维加斯算法C. 动态规划算法 D.舍伍德算法 答案：31. （ D ）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解 C、贪心选择性质D、最优子结构性质答案：32. 矩阵连乘问题的算法可由（ B ）设计实现。A、分支界限算法 B、动态规划算法 C、贪心算法D、回溯算法答案：33、Strassen 矩阵乘法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯

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

32、答案：39、在下列算法中得到的解未必正确的是（ A ）A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 答案：40实现大整数的乘法是利用的算法（ C ） A、贪心法 B、动态规划法 C、分治策略 D、回溯法 答案：410-1 背包问题的回溯算法所需的计算时间为（ A ） A、O（n） B、O（nlogn）C、O（） D、O（n）答案：42贪心算法与动态规划算法的主要区别是（ B ） A、最优子结构 B、贪心选择性质 C、构造最优解D、定义最优解 答案：43. 实现最大子段和利用的算法是（ B ）。A、分治策略 B、动态规划法 C、贪心法 D、回溯法 答案：44.优先队列式

33、分支限界法选取扩展结点的原则是（ 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. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（

34、 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. 多阶段决策问题就是要在可以选择的那些策

35、略中间选取一个（ A ）策略使在预定的标准下达到最好的效果。A. 最优B. 最差C. 平衡D. 任意57. 根据排序元素所在位置的不同，排序分（ A ）。A. 内排序和外排序B. 首排序和尾排序C. 顺序排序和逆序排序D. 堆排序和栈排序58. 算法必须具备输入、输出和（ B ）等 5 个特性。A. 可执行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性59. 与分治法不同的是，适合于用动态规划求解的问题（ A ）。A. 经分解得到子问题往往不是互相独立的B. 经分解得到子问题往往是互相独立的C. 经分解得到子问题往往是互相交叉的D.

36、经分解得到子问题往往是任意的60. 二分搜索算法的基本思想是将 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.

37、 无前效性C. 最优化原理和后效性D. 最优化原理和无后效性64. 算法的每种运算必须要有确切的定义不能有二义性，以下符合算法确定性运算的是（ 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.

38、 问题的可分性和解的复杂性68. 优先队列的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的高低与p值大小相关，根据问题的不同情况，采用（ C ）来描述优先队列。A. 先进先出队列B. 后进先出的栈C. 最大堆或最小堆D. 随机序列69. 阶乘函数用递归定义 Public static int factorial（int n） if（n=0）return 1；return（ B ）： A. n*factorial(n)B. n*factorial(n-1)

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

40、索方式相同B. 求解目标不同搜索方式也不同C. 求解目标相同搜索方式不同D. 求解目标相同搜索方式也相同74. 递归算法不能适用以下场合（ D ）。A. 数据的定义形式按递归定义B. 数据之间的关系即数据结构按递归定义C. 问题解法按递归算法实现D. 概率问题75. 若当子问题之间包含公共的子子问题时，则分治法要做许多不必要的工作，重复地解公共的子问题，此时一般用（ A ）法较好。A. 动态规划B. 分治C. 贪心D. 概率76. 分治法所能解决的问题应具有的关键特征是（ C ）。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个规模较小的相同问题C. 利用该问题分

41、解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的77. 对于货箱装船问题根据贪心策略首先选择（ A ）的货箱然后选 （ 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-

42、xk)D. 以上都不正确79. 分支限界法的搜索策略是：在扩展结点处，先生成其（ D ）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。A. 一个B. 二个C. 任意多个D. 所有的80. 能够用动态规划解决的问题还有一个显著特征（ D ）这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。A. 子问题的

43、可求解性B. 子问题的独立性C. 子问题的可合并性D. 子问题的重叠性81. 在任何一个的棋盘覆盖中，用到的L型骨牌个数恰为（ A ）。A. B. C. D. 82. 以Bitonic旅行路线问题为例，动态规划的时间复杂度为（ C ）。A. O(n)B. O(n!)C. O(n2)D. O(n3)83. 一个算法应该包含如下几条性质除了（ A ）。 A二义性 B有限性 C正确性 D 可终止性 84. 解决一个问题通常有多种方法。若说一个算法“有效”是指（ D ）。 A. 这个算法能在一定的时间和空间资源限制内将问题解决 B这个算法能在人的反应时间内将问题解决 C这个算法比其他已知算法都更快地将

44、问题解决 D A和C 85. 当输入规模为n时算法增长率最小的是（ B ） 。 ABCD86渐进算法分析是指（ B ） 。 A. 算法在最佳情况、最差情况和平均情况下的代价 B. 当规模逐步往极限方向增大时对算法资源开销“增长率”上的简化分析 C. 数据结构所占用的空间 D. 在最小输入规模下算法的资源代价 87当上下限表达式相等时我们使用下列哪种表示法来描述算法代价?（ C ）A大O表示法 B大表示法 C表示法 D 小o表示法 88. 采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素，以下对顺序搜索法分析正确的是（ B ）。A最佳情况、最差情况和平均情况下顺序搜索法的渐进代价

45、都相同 B最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 C最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 D最佳情况的渐进代价要好于平均情况的渐进代价而平均情况的渐进代价要好于最差情况的渐进代价 89递归通常用（ C ）来实现。 A. 有序的线性表 B. 队列 C. 栈 D. 数组90. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ C ）。A问题规模相同，问题性质相同 B问题规模相同，问题性质不同 C问题规模不同，问题性质相同 D问题规模不同，问题性质不同 91在寻找n个元素中第k

46、小元素问题中如快速排序算法思想运用分治算法对n个元素进行划分如何选择划分基准下面（ D ）答案解释最合理。 A随机选择一个元素作为划分基准 B取子序列的第一个元素作为划分基准 C用中位数的中位数方法寻找划分基准D以上皆可行。但不同方法算法复杂度上界可能不同 92. 对于01背包问题和背包问题的解法下面（ C ）答案解释正确。 A01背包问题和背包问题都可用贪心算法求解 B01背包问题可用贪心算法求解但背包问题则不能用贪心算法求解 C01背包问题不能用贪心算法求解但可以使用动态规划或搜索算法求解而背包问题则可以用贪心算法求解 D因为01背包问题不具有最优子结构性质所以不能用贪心算法求解 93关于

47、回溯搜索法的介绍下面（ D ）是不正确描述。 A回溯法有“通用解题法”之称它可以系统地搜索一个问题的所有解或任意解 B回溯法是一种既带系统性又带有跳跃性的搜索算法 C回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解如果肯定不包含则跳过对该结点为根的子树的搜索逐层向祖先结点回溯 D回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 94. 关于回溯算法和分支限界法以下（ A ）是不正确描述。 A回溯法中每个活结点只有一次机会成为扩展结点 B分支限界法中活结点一旦成为扩展结点就一次性产生其所有儿子结点在这些儿子结点中那些导致不可行解或导致非最优解的儿子结点被舍弃其余儿子

48、加入活结点表中 C回溯法采用深度优先的结点生成策略 D分支限界法采用广度优先或最小耗费优先最大效益优先的结点生成策略 95. 优先队列通常用以下（ B ）数据结构来实现。 A栈 B堆 C队列 D二叉查找树96. 在分支限界算法中根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下（ D ）描述最为准确。 A采用FIFO队列的队列式分支限界法 B采用最小值堆的优先队列式分支限界法 C采用最大值堆的优先队列式分支限界法 D以上都常用针对具体问题可以选择采用其中某种更为合适的方式 97. 对布线问题以下（ C ）是不正确描述。 A布线问题的解空间是一个图 B可以对方格阵列四周设置围墙，即

49、增设标记的附加方格的预处理，使得算法简化对边界的判定 C采用广度优先的标号法找到从起点到终点的布线方案这个方案如果存在的话不一定是最短的 D采用先入先出的队列作为活结点表以，终点b为扩展结点或活结点队列为空作为算法结束条件98. 下述表达不正确的是（ D ）。A. 的渐进表达式上界函数是B的渐进表达式下界函数是C的渐进表达式上界函数是D的渐进表达式下界函数是99当输入规模为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(

50、1)=1D. T(n)=3nlog2n101. 有9个村庄，其坐标位置如下表所示：i123456789x(i)123456789y(i)123456789现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在（ C ）才能使邮局到9个村庄的距离和最短。A. （4.5，0）B. （4.5，4.5）C. （5，5）D. （5，0）102. n个人拎着水桶在一个水龙头前面排队打水水桶有大有小水桶必须打满水水流恒定。如下（ A ） 说法不正确A让水桶大的人先打水可以使得每个人排队时间之和最小 B让水桶小的人先打水可以使得每个人排队时间之和最小 C让水桶小的人先打水在某个确定的时间t内可以让尽可能多的人打上

51、水 D若要在尽可能短的时间内n个人都打完水按照什么顺序其实都一样103. 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为（ B ）。A.B.C.D.104以下关于判定问题难易处理的叙述中正确的是（ C ）A.可以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的105. 回溯法在解空间树T上的搜索方式是（ A ）A. 深度优先B. 广度优先C. 最小耗费优先D. 活结点优先106. 设f(N)，g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数N

52、0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时有上界g(N)，记作f(N)=O(g(N),即f(N)的阶（ A ）g(N)的阶。A. 不高于B. 不低于C. 等价于D. 逼近107. 以下（ C ）不能在线性时间完成排序A.计数排序B.基数排序C.堆排序D.桶排序108. 以下（ A ）不一定得到问题的最优解A.贪心算法B.回溯算法C.分支限界法D.动态规划法109.下列不属于一个好的算法应具有的特性的是（ C ）。A. 正确性B. 简明性C. 无限性D. 最优性110. 算法分析是（ C ）。A. 将算法用某种程序设计语言恰当地表示出来B在抽象数据集合上执行程序，以确定

53、是否会产生错误的结果C. 对算法需要多少计算时间和存储空间作定量分析D. 证明算法对所有可能的合法输入都能算出正确的答案111. 学校要举行运动会，请你设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是（ C ）。A. 分析问题，编写程序，设计算法，调试程序B. 设计算法，编写程序，提出问题，调试程序C. 提出问题，设计算法，编写程序，调试程序D. 设计算法，提出问题，编写程序，调试程序112. 考虑背包问题：n=6，M=10，V（1:6）=（15，59，21，30，60，5），W（1:6）=（1，5，2，3，6，1）。该问题的最大效益值为（ C ）。A. 101

54、B. 110C. 115D.120113. 考虑背包问题：n=6，M=10，V（1:6）=（15，59，21，30，60，5），W（1: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. 有穷性D. 输入和输出116. 设A1.60=11,12,70。算法折半查找在A上搜索x=3

55、3、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. 拉斯维加斯算法D. 蒙特卡罗算法120. 当输入规模为n时，算法增长率最快的是( C )。A. 12nB.C. 2n2D. 121. 关于0-1背包问题，以下描述正确的是（ D ）。A. 可以使用贪心算法找到最优解B. 能找到多项式时间的有效算法C. 使用教材介绍的动态规划方法可求解任意0-1背包问题D. 对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0-1背包问题。12