历年算法试题(上午)

优秀学习资料欢迎下载优秀学习资料欢迎下载优秀学习资料欢迎下载10下●某一维数组中依次存放了数据元素15,23,38,47,55,62,88,95,102,123，采用折半（二分）法查找元素95时，依次与（60）进行了比较。（60）A.62,88,95B.62,95C.55,88,95D.55,95DAC10上DCBC09下ADA09年上午●现有16枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较（63）次才能够找出该假币。（63）A.3B.4C.5D.6B●以下的算法设计方法中，（64）以获取问题最优解为目标。（64）A.回溯方法B.分治法C.动态规划D.递推C●归并排序采用的算法设计方法属于（65）。（65）A.归纳法B.分治法C.贪心法D.回溯方法B08年下●程序设计语言一般都提供多种循环语句，例如实现先判断循环条件再执行循环体的while语句和先执行循环体再判断循环条件的do-while语句。关于这两种循环语句，在不改变循环体的条件下，（21）是正确的。（21）A.while语句的功能可由do-while语句实现B.do-while语句的功能可由while语句实现C.若已知循环体的次数，则只能使用while语句D.循环条件相同时，do-while语句的执行效率更高B●某一维数组中依次存放了数据元素12,23,30,38,41,52,54,76,85，在用折半（二分）查找方法（向上取整）查找元素54时，所经历“比较”运算的数据元素依次为（62）（62）A.41,52,54B.41,76,54C.41,76,52,54D.41,30,76,54BDCD08年上●一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有（62）特性。（62）A.有穷性B.可行性C.确定性D.健壮性BCBC07年下●关于算法与数据结构的关系，（64）是正确的。（64）A.算法的实现依赖于数据结构的设计B.算法的效率与数据结构无关C.数据结构越复杂，算法的效率越高D.数据结构越简单，算法的效率越高A●若一个问题既可以用迭代方式也可以用递归方式求解，则（65）方法具有更高的时空效率。（65）A.迭代 B.递归 C.先递归后迭代 D.先迭代后递归A07年上●程序设计语言中（50）。

（50）A.while循环语句的执行效率比do-while循环语句的执行效率高

B.while循环语句的循环体执行次数比循环条件的判断次数多1，而do-while语句的循环体执行次数比循环条件的判断次数少1

C.while语句的循环体执行次数比循环条件的判断次数少1，而do-while语句的循环体执行次数比循环条件的判断次数多1

D.while语句的循环体执行次数比循环条件的判断次数少1，而do-while语句的循环体执行次数等于循环条件的判断次数D●设商店有10元、5元、2元和1元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零29元：先选2张10元币，然后选择1张5元币，再选择两张2元币。以上的找零钱方法采用了（62）策略。

（62）A.分治B.贪心C.动态规划D.回溯B●对n个元素的数组进行（63），其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。

（63）A.希尔排序B.快速排序C.堆排序D.选择排序C06年下●（58）算法策略与递归技术的联系最弱。

（58）A．动态规划B．贪心C．回溯D．分治B●对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用（59），使用分治(DivideandConquer)策略的是（60）算法。

（59）A．希尔排序B．直接插入排序C．快速排序D．堆排序

（60）A．冒泡排序B．插入排序C．快速排序D．堆排序DC06上●设某算法的计算时间可用递推关系式T（n）＝2T（n／2）＋n表示，则该算法的时间复杂度为（59）。

（59）A．O（lgn）B．O（nlgn）C．O（n）D．O（n2）

B●（60）在其最好情况下的算法时间复杂度为O(n)。

（60）A．插入排序B．归并排序C．快速排序D．堆排序A05下●设求解某问题的递归算法如下：求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为____(53)____；设算法Move的计算时间为k，当n=4时，算法F的计算时间为___(54)___。

供选择的答案：

（53）A.T(n)=T(n-1)+1B.T(n)=2T(n-1)

C.T(n)=2T(n-1)+1D.T(n)=2T(n+1)+1

（54)A.14kB.15kC.16kD.17kCB●利用贪心法求解0/1背包问题时，___(55)___能够确保获得最优解。用动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为Wj和pj(j=1~n)。则依次求解f0(X)、f1(X)、...、fn(X)的过程中使用的递推关系式为___(56)___。

供选择的答案：

(55)A.优先选取重量最小的物品B.优先选取效益最大的物品

C.优先选取单位重量效益最大的物品D.没有任何准则

(56)A.fi(X)=min{fi-1(X),fi-1(X)+pi}

B.fi(X)=max{fi-1(X),fi-1(X-Wi)+pi}

C.fi(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi}

D.fi(X)=max{fi-1(X-Wi),fi-1(X)+pi}DB05上●在最好和最坏的情况下的时间复杂度均为O(nlogn)且稳定的排序方法是___(51)__。

供选择的答案：

A．基数排序B．快速排序C．堆排序D．归并排序C●以比较为基础的排序算法在最坏情况下的计算时间下界为__(55)___。

供选择的答案：

A．O(n)B．O(n)C．O(log2n)D．O(nlog2n)D●利用动态规划方法求解每对结点之间的最短路径问题(allpairsshortestpathproblem)时，设有向图G=<V，E>共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用Dk(i，j)即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度（Dk(i，j)即为图G中结点i到j的最短路径长度），则求解该问题的递推关系式为___(56)___。

供选择的答案：

A.Dk(i，j)=Dk-1(i，j)+C(i，j)

B.Dk(i，j)=min{Dk-1(i，j)，Dk-1(i，j)+C(i，j)}

C.Dk(i，j)=Dk-1(i，k)+Dk-1(k，j)

D.Dk(i，j)=min{Dk-1(i，j)，Dk-1(i，k)+Dk-1(k，j)}D04下●采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是__(52)__

（52）A.当前所出的决策不会影响后面的决策

B.原问题的最优解包含其子问题的最优解

C.问题可以找到最优解，但利用贪心法不能找到最优解

D.每次决策必须是当前看来最优决策才可以找到最优解B●下面函数中渐进时间最小的是__(53)__

(53)A.T1(n)=n+nlognB.T2(n)=2n+nLognC.T3(n)=n2-lognD.T4(n)=n+100lognD●下面的程序段违反了算法的__(54)__原则

voidsam()

{

intn=2

while(!odd(n))n+=2;

printf(n);

}

(54)A.有穷性B.确定性C.可行性D.健壮性A●拉斯维加斯（LasVegas）算法是一种常用的__(55)__算法

(55)A.确定性B.近似C.概率D.加密C●在分支-界限算法设计策略中，通常采用__(56)__搜索问题的解空间。

（56）A.深度优先B.广度优先C.自底向上D.拓扑排序B●在下列算法设计方法中，__(57)__在求解为题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决__(58)__问题

（57）A.分治法B.贪心法C.动态规划法D.回溯法

（58）A