《算法分析与设计》(李春葆版)课后选择题答案与解析

《算法及其分析》课后选择题答案及详解第1

章——概论1.下列于算法的说法中确的有（

Ⅰ.求解某一类题的算法是唯一

Ⅱ.算法必须在限步操作之后停

Ⅲ.算法的每一操作必须是明确，不能有歧义或义模糊

Ⅳ.算法执行后定产生确定的结

A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)=

T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。答案为C。2.答：选项A的时间复杂度为O(n)。选项B的时间复杂度为O(n)。选项C的时间复杂度为O(log2n)。选项D的时间复杂度为O(nlog2n)。答案为C。第3

章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。

A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同

2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。但不同方法，算法复杂度上界可能不同

3.对于下列二分查找算法，以下正确的是（）。

A.

int

x)

{intlow=0,high=n-1;

while(low<=high)

{intmid=(low+high)/2;

if(x==a[mid])returnmid;

if(x>a[mid])low=mid;

elsehigh=mid;}return

–1;}B.

int

x)

{ intlow=0,high=n-1;

while(low+1!=high)

{intmid=(low+high)/2;

if(x>=a[mid])low=mid;

elsehigh=mid;

}

if(x==a[low])returnlow;

elsereturn

–1;

}

C.

intintx)

{ intlow=0,high=n-1;

while(low<high-1)

{intmid=(low+high)/2;if(x<a[mid])

high=mid;

elselow=mid;

}

if(x==a[low])returnlow;

elsereturn

–1;

}

D.int

x)

{if(n>0&&x>=a[0])

{intlow=

high=n-1;

while(low<high){intmid=(low+high+1)/2;

if(x<a[mid])

high=mid-1;

elselow=mid;

}

if(x==a[low])returnlow;

}

return

–1;

}答案解析：1.答：C。2.答：D。3.答：以a[]={1，2，3，4，5}为例说明。选项A中在查找5时出现死循环。选项B中在查找5时返回-1。选项C中在查找5时返回-1。选项D正确。第5

章─回溯法1.回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

A.广度优先B.活结点优先C.扩展结点优先D.深度优先2.关于回溯法以下叙述中不正确的是（）。A.回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解B.回溯法是一种既带系统性又带有跳跃性的搜索算法C.回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

D.回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯3.回溯法的效率不依赖于下列哪些因素（）。A.确定解空间的时间C.计算约束函数的时间B.满足显约束的值的个数D.计算限界函数的时间4.下面（）函数是回溯法中为避免无效搜索采取的策略。A.递归函数B.剪枝函数C.随机数函数D.搜索函数答案解析：1.答：D。2.答：回溯算法是采用深度优先遍历的，需要借助系统栈结构来保存从根结点到当前扩展结点的路径。答案为C。3.答：回溯法解空间是虚拟的，不必确定整个解空间。答案为A。4.答：B。第6

章─分枝限界法1.分枝限界法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。A.广度优先B.活结点优先C.扩展结点优先D.深度优先2.常见的两种分枝限界法为（）。A.广度优先分枝限界法与深度优先分枝限界法

B.队列式（FIFO）分枝限界法与堆栈式分枝限界法C.排列树法与子集树法D.队列式（FIFO）分枝限界法与优先队列式分枝限界法

3.分枝限界法求解0/1背包问题时，活结点表的组织形式是（）。A.小根堆B.大根堆C.栈4.采用最大效益优先搜索方式的算法是（）。A.分支界限法B.动态规划法C.贪心法D.回溯法

5.优先队列式分枝限界法选取扩展结点的原则是（）。A.先进先出B.后进先出C.结点的优先级D.随机答案解析：1.答：A。2.答：D。3.答：B。4.答：A。5.答：C。第7

章─贪心法1.下面是贪心算法的基本要素的是（）。

A.重叠子问题B.构造最优解C.贪心选择性质D.定义最优解2.下面问题（）不能使用贪心法解决。

A.单源最短路径问题B.n皇后问题C.最小花费生成树问题D.背包问题3.采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）。A.O(n)B.O(n)C.O(n)D.O(nlog2n)

4.关于0/1背包问题以下描述正确的是（）。A.可以使用贪心算法找到最优解B.能找到多项式时间的有效算法C.使用教材介绍的动态规划方法可求解任意0－1

背包问题D.对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0/1背包问题5.一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码A.107B.108C.214D.215答案解析：1.答：C。2.答：n皇后问题的解不满足贪心选择性质。答案为B。3.答：D。4.答：由于背包问题可以取物品的一部分，所以总价值一定大于等于做0/1背包问题。答案为D。5.答：这里n=215，哈夫曼树中n1=0，而n0=n2+1，n=n0+n1+n2=2n0-1，n0=(n+1)/2=108。答案为B。第8

章─动态规划1.下列算法中通常以自底向上的方式求解最优解的是（）。

备忘录法B.动态规划法C.贪心法D.回溯法2.备忘录方法是（）算法的变形。A.分治法B.回溯法C.贪心法D.动态规划法3.下列是动态规划算法基本要素的是（）。A.定义最优解B.构造最优解C.算出最优解D.子问题重叠性质4.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）A.贪心选择性质B.重叠子问题C.最优子结构性质D.定义最优解答案解析：1.答：B。2.答：D。3.答：D。4.答：C。第9

章─图算法设计1..以下不属于贪心算法的是（）。A.Prim

算法B.Kruskal

算法C.Dijkstra算法D.深度优先遍历2.一个有n个顶点的连通图的生成树是原图的最小连通子图，且包含原图中所有n个顶点，并且有保持图联通的最少的边。最大生成树就是权和最大生成树，现在给出一个无向带权图的邻接矩阵为{{0，4，5，0，3}，{4，0，4，2，3}，{5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}}，其中权为0

表示没有边。一个图为求这个图的最大生成树的权和是（）。A.11B.12C.13D.14E.15答案解析：1.答：D。2.答：采用类似Kurskal

算法来求最大生成树，第1

步取最大边（0，2），第2步取边（0，1），第3步取边（0，4），第4步取最大边（1，3），得到的权和为14。答案为D。第11章─计算复杂性理论1.旅行商问题是NP问题吗？A.否B.是

C.至今尚无定论

2.下面有关P问题，NP问题和NPC问题，说法错误的是（）。

A.如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题B.NP问题是指可以在多项式的时间里验证一个解的问题C.所有的P类问题都是NP问题D.NPC问题不一定是个NP问题，只要保证所有的NP问题都可以约化到它即可答案解析：1.答：B。2.答：D。第12章─概率算法和近似算法1.蒙特卡罗算法是（）的一种。A.分枝限界算法B.贪心算法C.概率算法D.回溯算法2.在下列算法中有时找不到问题解的是（）。A.蒙特卡罗算法B.拉斯维加斯算法C.舍伍德算法D.数值概率算法3.在下列算法中得到的解未必正确的是（）。A.蒙特卡罗算法B.拉斯维加斯算法C.舍伍德算法D.数值概率算法4.总能求得非数值问题的一个解，且所求得的解总是正确的是（）。A.蒙特卡罗算法B.拉斯维加斯算法C.数值概率算法D.舍伍德算法5.目前可以采用（）在多项式级时间内求出旅行商问题的一个近似最优解。A.回溯法B.蛮力法C.近似算法D.都不可能

6.下列叙述错误的是（）。A.概率算法的期望执行时间是指反复解同一个输入实例所花的平均执行时间

B.概率算法的平均期望时间是指所有输入实例上的平均期望执行时间C.概率算法的最坏期望事件是指最坏输入实例上的期望执行时间D.概率算法的期望执行时间是指所有输入实例上的所花的平均执行时间7.下列叙述错误的是（）。

A.数值概率算法一般是求数值计算问题的近似解B.MonteCarlo总能求得问题的一个解，但该解未必正确C.LasVegas