算法设计分析第次样本

第1次作业

一、单项选择题（本大题共60分，.2.小题，每小..分）

1.

设m[i,j]为计算矩阵链Ai…j所需的乘法运算次数的最小值，则矩阵链

A1…n所需的乘法运算次数的最小值为（）。

A.m[0,n]

B.m[l,n-l]

C.m[l,n+1]

D.m[l,n]

2.二分搜索算法是基于.）设计的算法。

A.分治法

B.动态规划法

C.贪心法

D.穷尽法

3.直接或间接的调用自身的算法称为.）。

A.贪心算法

B.递归算法

C.迭代算法

D.动态规划算法

4.算法分析的两个重要方面是.）。

A.空间复杂度和时间复杂度

B.对的性和简朴性

C.可读性和文档性

5.下述关于最优子结构的说法，不对的的是（.）。

A.原问题的最优解包含子问题的最优解

B.原问题的最优解建立在子问题的最优解基础之上

C.原问题的最优解依赖于子问题的最优解

D.原问题的最优解通过子问题的非最优解合并而得

6.当n越来越大时，下列函数中，增长速度最快的应当是（）

A.y=100n

B.y=loglOOn

C.y二

D.

7.实现归并排序运用的算法是（）o

A.

分治策略

B.动态规划法

C.贪心法

D.回溯法

8.算法的时间复杂度是指（）

A.执行算法程序所需要的时间

B.算法程序的长度

C.算法执行过程中所需要的基本运算次数

D.算法程序中的指令条数

9.在活动安排问题中，下述哪项描述中的活动A,B是相容.（.）？

A.活动A于活动B开始前开始

B.活动A于活动B结束前开始

C.活动A于活动B开始前结束

D.活动A于活动B开始后开始

10.衡量一个算法好坏的标准是.）。

A.运营速度快

B.占用空间少

C.时间复杂度低

D.代码短

11.

在最长公共子序列问题中，假如定义c[i,j]为Xl..i和Yl..j的最长公共

子序列的长度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的

长度为（)o

A.c[0,0]

1]

C.c[l,m]

D.c[m,n]

12.以下关于贪心算法，不对的的说法.（.）o

A.用于解决优化问题

&总是选择在当前看来最佳的选择

C.盼望通过局部最优达成全局最优

D.所需求解的问题可以不满足最优子结构性质

13.一个p行q列的矩形同一个q行r列的矩形相乘，总共要作多少次乘法运

算？（.）

A...r

B.q2

C.......r

D.q3

14.

在最优二又搜索树问题中，考虑如下的BST:

假如要搜索k3，总共要通过多少次比较（）。

A.1次

B.2次

C.3次

D.4次

15.

JAVA程序重要有以下两种类型（）

A.应用程序和APPLE.应用程序和理论程序

B.系统程序和应用程序

C.系统程序和理论程序

D.D系统程序和APPLE?应用程序

16.

如图所示的Huffmann树,

字符s的编码是（）。

A.1010

B.1110

C.1111

D.010

17.合用动态规划解决的问题必须满足最优子结构.（.）性质。

A.无后效性

B.无前效性

C.重叠子问题

D递归

18.对于n个元素的排序问题.n=2时，只要作（.）次比较即可排好序

A.3

B.2

C.1

D.4

19.二分搜索算法的基本思想是将n个元素提成个数大体相同的两半，取a[n/2]

与x进行比较：假如.），则只要在数组a的左半部继续搜索X。

A.

x<a[n/2]

B.x=a[n/2]

C.x>a[n/2]

D.x>=a[n/2]

20.

备忘录方法的递归方式是（）

A.

自顶向下

B.

自右向左

C.

忽上忽下

D.

自底向上

二、判断题（本大题共40分，.2.小题，每小..分）

1.

应用Huffmann编码的目的是用更少的比特流表达更多的信息。（)

2.

两个序列的最长公共子序列可以帮助评价两个序列的相似度。（）

3.算法就是一组有穷的规则。.）

4.

要想在电脑上扩大所解决问题的规模，有效的途径是提高算法的计算复杂度，（）

5.

归并排序算法是渐近最优算法？（）

6.

快速排序算法是基于贪心策略的一个算法（）。

7.

二分搜索方法在最坏的情况下用O（logn）时间完毕搜索任务。（）

8.

快速排序法是基于分治策略的。（）

9.基于三数取中划分的快速排序算法其最坏时间复杂度比基本的快速排序算法

要好.）

10.

递归算法解题通常显得很简洁,并且运营效率较高？（）

11.

最坏情况下的时间复杂度和平均时间复杂度同样。（）

12.

计算机只能运营在有穷步内终止的算法。O

13.

在活动选择问题中，假如活动A晚于活动B开始，则两个活动相容。（）

14.

T(n)是某算法的时间复杂性函数，f(n)是一简朴函数，存在正整数nO和c,

n)nO,有T(n)〈cf(n),这种关系记作T(n)=O(f：n))。()

15.

动态规划的一个重要思想是要记住己经计算过的子问题的解。()

16.

能否运用分治法完全取决于问题是否具有如下特性：运用该问题分解出的子问

题的解可以合并为该问题的解。()

17.

贪心算法所做的选择都是目前最佳的()o

18.

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。()

19.

矩阵连乘积计算顺序问题的最优解包含着其子问题的最优解。（）

20.

对钢管切割问题反复应用“总是切单位价值最高的允许长度”的贪心规则可以

获得最优解。（）

答案：

一、单项选择题（60分，.2.题，短小..分）

1..2..3..4..5..6..7..8..9..10..