算法设计试题.pdfVIP

一、选择题(15*2分)

1.算法分析是（C）

A.将算法用某种程序设计语言恰当地表示出来

B.在抽象数据集合上执行程序,以确定是否会产生错误的结果

C.对算法需要多少计算时间和存储空间作定量分析

D.证明算法对所有可能的合法输入都能算出正确的答案

2.算法与程序的区别在于算法具有（C）

A.能行性B.确定性C.有穷性D.输入和输出

3.记号的定义正确的是（B）

A.O(g(n))={f(n)|存在正常数c和n0使得当nn有f(n)cg(n)}



0

B.O(g(n))={f(n)|存在正常数c和n0使得当nn有cg(n)f(n)}



0

C.(g(n))={f(n)|对于任何正常数c0，存在正数和n0使得对所有nn



00

有f(n)cg(n)}

D.(g(n))={f(n)|对于任何正常数c0，存在正数和n0使得对所有nn



00

有cg(n)f(n)}

4.衡量一个算法好坏的标准是（C）

A.运行速度快B.占用空间少C.时间复杂度低D.代码短

5.二分有哪些信誉好的足球投注网站算法是利用（A）实现的算法。

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

6.下面问题（B）不能使用贪心法解决。

A.单源最短路径问题B.N皇后问题

C.最小代价生成树问题D.背包问题

7．用贪心法设计算法的关键是（B）。

A.将问题分解为多个子问题来分别处理

B.选好最优量度标准

C.获取各阶段间的递推关系式

D.满足最优性原理

8.找最小生成树的算法Kruskal的时间复杂度为（D）（其中n为无向图的结点

数，m为边数）

A．O(n2)B．O(mlogn)C．O(nlogm)D．O(mlogm)

9.回溯法有哪些信誉好的足球投注网站状态空间树是按照（C）的顺序。

A.中序遍历B.广度优先遍历

C.深度优先遍历D.层次优先遍历

10.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）

A.重叠子问题B.最优子结构性质

C.最优量度标准性质D.定义最优解

11.程序块（A）是回溯法中遍历排列树的算法框架程序。

A.voidbacktrack(intt)

{

if(tn)output(x);

else

for(inti=t;i=n;i++){

swap(x[t],x[i]);

if(legal(t))backtrack(t+1);

swap(x[t],x[i]);

}

}

B.Voidbacktrack(intt)

{

if(tn)output(x);

else

for(inti=0;i=1;i++){

x[t]=i;