算法设计分析第1次.docx

算法设计分析第1次.docx

《算法设计分析第1次.docx》由会员分享，可在线阅读，更多相关《算法设计分析第1次.docx（8页珍藏版）》请在冰点文库上搜索。

算法设计分析第1次

第1次作业

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

1.

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

A.m[0,n]

B.m[1,n-1]

C.m[1,n+1]

D.m[1,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=log100n

C.y=

D.

y=

7.实现归并排序利用的算法是（）。

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]为X1..i和Y1..j的最长公共子序列的长度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（  ）。

A.c[0,0]

B.c[1,1]

C.c[1,m]

D.c[m,n]

12.以下关于贪心算法，不正确的说法是（  ）。

A.用于解决优化问题

B.总是选择在当前看来最好的选择

C.期望通过局部最优达到全局最优

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

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

A. pxr

B.q2

C. pxqxr

D.q3

14.

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

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

A.1次

B.2次

C.3次

D.4次

15.

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

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

B.系统程序和应用程序

C.系统程序和理论程序

D.D系统程序和APPLET应用程序

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分，共20小题，每小题2分）

1.

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

（  ）

2.

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

（ ）

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

（）

4.

要想在电脑上扩大所处理问题的规模,有效的途径是提高算法的计算复杂度。

（）

5.

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

6.

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

7.

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

（）

8.

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

（）

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

10.

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

11.

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

（）

12.

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

（）

13.

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

（ ）

14.

T（n）是某算法的时间复杂性函数，f（n）是一简单函数，存在正整数n0和c，n〉n0，有T（n）

（）

15.

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

（  ）

16.

能否利用分治法完全取决于问题是否具有如下特征：

利用该问题分解出的子问题的解可以合并为该问题的解。

（）

17.

贪心算法所做的选择都是目前最佳的（）。

18.

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

（）

19.

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

（）

20.

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

（  ）

答案：

一、单项选择题（60分，共20题，每小题3分）

1.D2.A3.B4.A5.D6.C7.A8.C9.C10.C11.D12.D13.C14.C15.A16.B17.C18.C19.A20.A

二、判断题（40分，共20题，每小题2分）

1.√2.√3.√4.×5.√6.×7.√8.√9.×10.×11.×12.√13.×14.√15.√16.√17.√18.√19.√20.×