2.算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。

A. （1）（3）

B. （1）（2）（3）

C. （1）（3）（4）

D. 全部

A、（1）（3）

B、（1）（2）（3）

C、（1）(3)

D、全部

如果有一个时间复杂性为O(n²)的算法(如起泡排序、选择排序或插人排序等)，在有

200个元素的数组上运行需要耗时3.1ms，试问在下列类似的数组上运行大约需要多长时间?

(1)具有400个元素;

(2)具有40000个元素。

A.效益的大小

B.效率的高低

C.效能的水平

D.成员心理需要的满足程度

下面的7个算法与本章中的二分搜索算法BinarySearch略有不同.如果算法不正确,请说明产生错误的原因.如果算法正确,请给出算法的正确性证明.

(2)

(3)

(4)

(5)

(6)

(7)

问题描述:设T是一棵带权树,树的每条边带一个正权,S是T的项点集,T/S是从树T中将S中顶点删去后得到的森林.如果T/S中所有树的从根到叶的路长都不超过d,则称T/S是一个d森林.

①设计一个算法求T的最小顶点集S,使T/S是d森林(从叶向根移动).

②分析算法的正确性和计算复杂性.

③设T中有n个顶点,则算法的计算时间复杂性应为O(n)

算法设计:对于给定的带权树,计算最小分离集S.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的带权树有n个项点,编号为1,2,...,n.编号为1的顶点是树根.接下来的n行中,第计1行描述与i个项点相关联的边的信息.每行的第1个正整数k表示与该项点相关联的边数.其后2k个数中,每2个数表示1条边.第1个数是与该顶点相关联的另一个顶点的编号,第2个数是边权值.k=0,表示相应的结点是叶结点.文件的最后一行是正整数d,表示森林中所有树的从根到叶的路长都不超过d.

结果输出:将计算的最小分离集s的顶点数输出到文件output.txt.如果无法得到所要求的d森林则输出“NoSolution!",

对任何非零偶数n,总可以找到奇数m和正整数k,使得n=m2^k.为了求出两个n阶矩阵的乘积,可以把一个n阶矩阵分成m×m个子矩阵,每个子矩阵有2^k×2^k个元素.当需要求2^k×2^k的子矩阵的积时,使用Strassen算法.设计一个传统方法与Strassen算法相结合的矩阵相乘算法,对任何偶数n,都可以求出两个n阶矩阵的乘积.并分析算法的计算时间复杂性.

在有向图中的一个欧拉画路(Eulercircuit)是这样的一个环：其上的每一条边被访问一次且仅被访问一次。

(l)试证明一个有向图存在欧拉回路的充要条件是该图必须是强连通的且每一个顶点有相同的人度与出度;

(2)设图中的顶点数为n，试描述有向图的数据结构并编写一个时间复杂性为O(n)的算法，在有向图中查找一条欧拉回路(如果它存在).

二叉搜索树可用来对n个元素进行排序。试编写一个排序算法，首先将n个元素a[1..n]插人到一个空的二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。