B

[解析] 运用数学递推公式，可以推算出数量级O(nlgn)。

A

[解析] 一个算法要求必须总是在执行有穷步之后结束，并月-每一步都可在有穷时间内完成。上述程序段违反了算法的有穷性性质，理论上将导致过程不可终止。

C

[解析] 概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择要省时，因此概率算法可以在很大程度上降低算法的复杂度。
   概率算法通常有两个优点。首先，较之那些我们所知的解决同——问题最好的确定性算法，概率算法所需的运行时间或空间通常小一些；其次，迄今为止所发现的概率算法总是易于理解和实现的。
   概率算法可分为四类，分别是数值概率算法、蒙特卡罗算法(Monte Karlo)、拉斯维加斯算法(Las Vegas)和舍伍德算法(Sherwood)。

B

[解析] 分支-限界算法是在问题的解空间树上搜索问题解的算法，它的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出一个目标函数达到极大或极小的解，即在某种意义下的最优解。
   分支—限界算法以广度优先的方式搜索解空间，其搜索策略是在扩展节点处先生成其所有的儿子节点，然后再从当前节点表中选择下一个扩展节点。

C

[解析] 一个算法具有下列5个重要特性。
   有穷性：一个算法必须总是在执行有穷步之后结束，且每—步都可在有穷时间内完成。
   确定性：算法中的每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。
   可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
   输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
   输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
   综卜所述，算法中的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明了算法的可行性特点。

D

[解析] 迭代法中要求迭代公式与原方程有共同的不同点。其中显然选项D不符合。

D

[解析] 根据二分查找的过程，由于需要栈结构实现递归算法，栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。
   第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n：第二次调用时，无论是在前半区还是在后半区进行查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n/2：第三次调用时，栈中又加入了—条查找记录，所确定的查找区间中的元素最多为n/4。依次类推，当所确定的查找区间中的元素为。时，递归调用该算法的次数为log₂(n+1)次，查找结束。

A

[解析] 贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法(或称贪婪法)一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

B

[解析] 快速排序算法采用的设计方法是分治法。

D

[解析] 从“D_k(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中，我们得到一个提示，在求i,j之间最短路径的时候，会考虑它经过哪些节点能缩短原来的路径。在 D_k(i,j)=min{D_k-1(i,j),D_k-1(i,k)+D_k-1(k,j)}中，D_k(i,j)表示i到j不经过k的路径长度，而 Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度，且min()函数用于找最小值，所以此式正确。

B

[解析] 动态规划策略设计算法的第一步通常是刻画最优解结构。当问题的最优解包含了子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。
   动态规划策略设计算法利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。