搜档网
当前位置:搜档网 › 串匹配问题,算法分析与设计答案

串匹配问题,算法分析与设计答案

串匹配问题,算法分析与设计答案
串匹配问题,算法分析与设计答案

一、实验内容和目的

1、深刻理解并掌握蛮力算法的设计思想;

2、提高应用蛮力算法设计算法的技能;

3、理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努

力后,都可以对算法的第一个版本进行一定程度的改良,改进其时

间性能

BF算法:

基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比

较,若相等,则继续比较两者的后续字符;若不相等,则从主串S

的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹配

的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,

匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。

KMP算法:

1. 在串S和串T中分别设比较的起始下标i和j;

2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较

完毕

2.1 如果S[i]=T[j],则继续比较S和T的下一个字符;否则

2.2 将j向右滑动到next[j]位置,即j=next[j];

2.3 如果j=0,则将i和j分别加1,准备下一趟比较;

2.4 如果T中所有字符均比较完毕,则返回匹配的起始下标;

否则返回0;

BM算法:

BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法

仅把匹配操作的字符比突顺序改为从右向左,但匹配发生失败时,模

式T右移的计算方法却发生了较大的变化。

设计思想:设文本串T,模式串为P。首先将T与P进行左对齐,然

后进行从右向左比较,若是某趟比较不匹配时,BM算法就采用两条

启发式规则,即坏字符规则和好后缀规则,来计算模式串向右移动的距离,直到整个匹配过程的结束。

b=n

Y

N

Y

N

BF 算法

结束

KMP 算法

结束

a-b →a

b=-1

b 加1

结束

BM算法

二、所用仪器、材料(设备名称、型号、规格等)

Windows 7,Microsoft Visual C++ 6.0

三、实验方法、步骤

1、实现BF算法;

2、实现BF算法的改进算法:KMP算法和BM算法;

3、观察并记录运行结果。

四、实验过程原始记录(数据、图表、计算等)

源程序:

#include "stdio.h"

#include "conio.h"

#include

//BF算法

int BF(char s[],char t[])

{

int i;

int a;

int b;

int m,n;

m=strlen(s); //主串长度

n=strlen(t); //子串长度

printf("\n*****BF*****算法\n");

for(i=0;i

{

b=0;

a=i;

while(s[a]==t[b]&&b!=n)

{

a++;

b++;

}

if(b==n)

{

printf("查找成功!!\n\n");

return 0;

}

}

printf("找不到%s\n\n",t);

return 0;

}

//前缀函数值,用于KMP算法

int GETNEXT(char t[],int b)

{

int NEXT[10];

NEXT[0]=-1;

int j,k;

j=0;

k=-1;

while(j

{

if ((k==-1)||(t[j]==t[k]))

{

j++;

k++;

NEXT[j]=k;

}

else k=NEXT[k];

}

b=NEXT[b];

return b;

}

//KMP算法

int KMP(char s[],char t[])

{

int a=0;

int b=0;

int m,n;

m=strlen(s); //主串长度

n=strlen(t); //子串长度

printf("\n*****KMP算法*****\n");

while(a<=m-n)

{

while(s[a]==t[b]&&b!=n)

{

a++;

b++;

}

if(b==n)

{

printf("查找成功!!\n\n");

return 0;

}

b=GETNEXT(t,b);

a=a-b;

if(b==-1) b++;

}

printf("找不到%s\n\n",t);

return 0;

}

//滑动距离函数,用于BM算法

int DIST(char t[],char c)

{

int i=0,x=1;

int n;

n=strlen(t);

while(x&&i!=n-1)

{

if(t[i]==c)

x=0;

else i++;

}

if(i!=n-1)

n=n-1-i;

return n;

}

//BM算法

int BM(char s[],char t[])

{

int a=0;

int b=0;

int i,j;

printf("\n*****BM算法*****\n");

int z=0;

i=strlen(t)-1;

while(i<=strlen(s)-1)

{

j=strlen(t)-1;

while(j>=0&&s[i]==t[j])

{

j--;

i--;

}

if(j<0)

{

printf("查找成功!!\n\n");

return 0;

}

else

i=i+DIST(t,s[i]);

}

printf("找不到%s\n\n",t);

return 0;

}

void main()

{

char s[]={'\0'}; //主串S

int n=10;

char t[]={'\0'}; //模式T

printf("\n----------串匹配问题----------\n");

printf("\n输入主串S\nS=");

scanf("%s",&s);

printf("\n输入子串T\nT=");

scanf("%s",&t);

printf("主串长%d,子串长为%d\n",strlen(s),strlen(t));

BF(s,t); //BF算法

KMP(s,t); //KMP算法

BM(s,t); //BM算法

}

算法设计与分析(作业三)

算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月

实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n },其中A i 与A i+1是可乘的,i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为: (1)单个矩阵是完全加括号的; (2)矩阵连乘积A 是完全加括号的,则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号,即A=(BC)。 例如,矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式:(A 1(A 2(A 3A 4))),(A 1((A 2A 3)A 4)),((A 1A 2)(A 3A 4)),((A 1(A 2A 3))A 4),(((A 1A 2)A 3)A 4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵,B 是一个q ×r 矩阵,则计算其乘积C=AB 的标准算法中,需要进行pqr 次数乘。 (3)为了说明在计算矩阵连乘积时,加括号方式对整个计算量的影响,先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100,100×5,5×50。加括号的方式只有两种:((A 1A 2)A 3),(A 1(A 2A 3)),第一种方式需要的数乘次数为10×100×5+10×5×50=7500,第二种方式需要的数乘次数为100×5×50+10×100×50=75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见,在计算矩阵连乘积时,加括号方式,即计算次序对计算量有很大的影响。于是,自然提出矩阵连乘积的最优计算次序问题,即对于给定的相继n 个矩阵{A 1,A 2,…,A n }(其中矩阵Ai 的维数为p i-1×p i ,i =1,2,…,n ),如何确定计算矩阵连乘积A 1A 2…A n 的计算次序(完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是: 1)计算最优值算法MatrixChain():建立两张表(即程序中的**m 和**s ,利用二维指针存放),一张表存储矩阵相乘的最小运算量,主对角线上的值为0,依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量,其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得,最后一次求得的值即为n 个矩阵相乘的最小运算量;另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback():矩阵结合即是给矩阵加括号,打印出矩阵结合方式,由递归过程Traceback()完成。分三种情况: (1)只有一个矩阵,则只需打印出A1; (2)有两个矩阵,则需打印出(A1A2); (3)对于矩阵数目大于2,则应该调用递归过程Traceback()两次,构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为)(n 3 O 。 四、实验源代码

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题(20分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分,衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD } 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个(最优)解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ,先求解_子问题 ,然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解; 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i };②将N 1中作业按a i 的非减序排序得到N 1’,将N 2中作业按b i 的非增序排序得到N 2’;③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4,在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ,且 (a 1,a 2,a 3,a 4)=(4,5,12,10),(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2’={4,2}; 最优值为:38 4. 使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为: 该问题的最优值为:16 最优解为:(1,1,0) 5. 设S={X 1,X 2,···,X n }是严格递增的有序集,利用二叉树的结点来存储S 中的元素,在表示S 的二叉搜索树中搜索一个元素X ,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i 。(2)在二叉搜索树的叶结点中确定X ∈(X i ,X i+1),其概率为a i 。在表示S 的二叉搜索树T 中,设存储元素X i 的结点深度为C i ;叶结点(X i ,X i+1)的结点深度为d i ,则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]={X i ,X i+1,···,X j }最优值为m[i][j],W[i][j]= a i-1+b i +···+b j +a j ,则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法分析与设计试卷

《算法分析与设计》试卷(A) (时间90分钟满分100分) 一、填空题(30分,每题2分)。 1.最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2.在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3.实现最大子段和利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4..广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5.衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6.Strassen矩阵乘法是利用( A)实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是( A )。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8.用动态规划算法解决最大字段和问题,其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题,最好用( B )算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略( B ) A.递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是( C )。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14.下面是贪心算法的基本要素的是( C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15.回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题(20分,每空1分)。 1.算法由若干条指令组成的又穷序列,且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法,用一个队列来存储结点的表叫活节点表。

系统与设计复习题

《系统分析与设计》复习题 一.选择题: 1.面向对象的特点主要概括为(C )。 A. 可分解性、可组合性、可分类性 B. 继承性、封装性、 多态性 C. 抽象性、继承性、封装性、多态性 D. 封装性、易维护性、 可扩展性、可重用性 2.信息按照( C )可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 3.按照处理的对象,可把组织的信息系统分为(B )和管理 信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 4.在开发一个企业管理信息系统时,首先要进行用户调查,调查 中收集的主要信息包括( D )。 A. 管理目标、人力资源、业务流程和数据流程信息 B. 组织结构、功能体系、业务流程和数据流程信息 C. 企业性质、客户资源、业务流程和数据流程信息 D. 管理目标、功能体系、业务流程和数据流程信息 5.系统流程图也称为业务流程图,它表达的是(B )。 A. 数据在系统各部件间的流动情况 B. 对数据进行加工

处理的控制过程 C. 逻辑数据流图 D. 白盒子形式的组成系统 的每个部件 6.一般子系统的划分是在系统( C )阶段,根据对系统的功 能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 7.信息系统流程图是以新系统的( D )为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流图 8.在关系规范化过程中,一般来讲,满足(C )的关系即可 满足信息处理的要求,就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 9.信息系统开发的结构化方法的一个主要原则是( A )。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则 10.用户开发应用系统的主要手段是( A )。 A. 生命周期法 B. 原型法 C. 第四代语言 D. 面向对象 方法 11.系统规划的主要任务包括( A )。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析试卷A及答案

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

考试课程: 班级: 姓名: 学号: ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------

参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作; 高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高; 高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高; 把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。 2、 ①不能保证最后求得的解是最佳的;即多半是近似解。(少数问题除外) ②策略容易发现(关键:提取清楚问题中的维度), 而且运用简单,被广泛运用。 ③策略多样,结果也多样。 ④算法实现过程中,通常用到辅助算法:排序 3、解:① 因为:;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知: 1-10n n 2 2+是n ;的渐近表达式。 ② 因为:;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知: 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质,并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息,构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为:FBGDECA 。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得:【排序1分】 5x =6x =7x =

信息系统分析与设计考试相关习题及答案

一、选择填空 4. 业务系统规划法(BSP)的核心是() A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构答案: C 5. 下面哪一项企业关键成功因素的特点是错误的:()。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求答案: B 7. 一般子系统的划分是在系统()阶段,根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计答案: A 10. 信息系统流程图是以新系统的()为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图答案: D 14. 信息系统开发的结构化方法的一个主要原则是()。 A. 自顶向下原则 B. 自底向上原则 C. 分步实施原则 D. 重点突破原则答案: A 16. 一般来说,占维护工作比例最高的是()。 A. 纠错性维护 B. 适应性维护 C. 完善性维护 D. 预防性维护答案: C 19. 系统规划的主要任务包括()。 A. 明确组织的信息需求、制定系统总体结构方案 B. 对系统进行经济、技术和使用方面的可行性研究 C. 选择计算机和网络系统的方案 D. 确定软件系统的模块结构答案: A 20. 系统设计阶段的主要成果是()。 A. 用户的决策方针 B. 用户的分析方案 C. 系统设计说明书 D. 系统总体设计方案答案: C 21. 信息系统建设的结构化方法中用户必须参与的原则是用户必须参与()。 A. 系统建设中各阶段工作 B. 系统分析工作 C. 系统设计工作 D. 系统实施工作答案: A 22. 结构化生命周期法的主要缺点之一是()。 A. 系统开发周期长 B. 缺乏标准、规范 C. 用户参与程度低 D. 主要工作集中在实施阶段答案: A 23. MIS规划的主要内容是()。 A. MIS战略规划,组织信息需求分析,系统目标 B. 组织信息需求分析,系统目标,资源分配 C. MIS战略规划,资源分配,系统目标 D. MIS战略规划,组织信息需要分析,资源分配答案: A 28. 生命周期法的特点之一是()。 A. 整个系统的开发工作是非劳动密集型的 B. 系统开发时间短 C. 对用户需求的变更不能做出迅速响应 D. 适合大型复杂系统答案: C 29. 系统测试中应遵循的一条原则是:测试工作应该由以下人员来承担()。 A. 原程序作者 B. 专门的测试人员 C. 系统设计人员 D. 用户答案: B 30. 系统维护中要解决的问题来源于()。 A. 系统分析阶段 B. 系统设计阶段 C. 系统实施阶段 D. 三者都包括答案: D 31. 在原型法中,原型是进行开发的系统的()。 A. 反映用户最基本需求的可以运行的实验模型 B. 某一主要部分的详细设计方案(物理模型)

最新算法分析与设计作业(一)及参考答案讲课讲稿

《算法分析与设计》作业(一) 本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由简答题和论述题组成,共15分。作业总分30分,将作为平时成绩记入课程总成绩。 客观题部分: 一、选择题(每题1分,共15题) 1、递归算法:(C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题,这些子问题:(D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是:(C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的:(A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是:( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是:(B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是:(A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质:(D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是:(A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题:( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是:(A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法:( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到:(C ) A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是:(A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:( A ) A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分: 二、写出下列程序的答案(每题2.5分,共2题) 1、请写出批处理作业调度的回溯算法。 #include #include using namespace std; class Flowing { friend int Flow(int ** ,int ,int []); private: //int Bound(int i); void Backtrack(int t); int **M;// int *x;//当前解

(完整版)算法设计与分析期末考试卷及答案a

一.填空题(每空 2 分,共30分) 1.算法的时间复杂性指算法中的执行次数。 2.在忽略常数因子的情况下,O、和三个符号中,提供了算法运行时间的一个上界。 3.设D n表示大小为n的输入集合,t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率,则算法的平均情况下时间复杂性A(n)= 。 4.分治算法的时间复杂性常常满足如下形式的递归方程: f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中,g(n)表示。 5. 分治算法的基本步骤包括。6.回溯算法的基本思想是。 7.动态规划和分治法在分解子问题方面的不同点是。 8.贪心算法中每次做出的贪心选择都是最优选择。 9.PQ 式的分支限界法中,对于活结点表中的结点,其下界函数值越小,优先级 10.选择排序、插入排序和归并排序算法中,算法是分治算法。 11.随机算法的一个基本特征是对于同一组输入,不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法,只要在步骤3 前加入随机 化步骤,就可得到一个随机化快速排序算法,该随机化步骤的功能是。 算法QUICKSORT 输入:n 个元素的数组A[1..n] 。 输出:按非降序排列的数组 A 中的元素

1. quicksort(1, n) end QUICKSORT _ _ 过程 quicksort(A, low, high) _ _ // 对 A[low..high] 中的元素按非降序排序。 _ 号 学 2. if low

5.《算法设计与分析》试题库

《算法分析与设计》试题库 (一) 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是(D ) A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上,并 D.动态规划算法

3. 动态规划算法的基本要素为(C) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质

D.预排序与递归调用 4. 算法分析中,记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有:(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题,一般具有的重要性质为:(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先

软件系统分析与设计考试题

题目内容: 一、单项选择题:(本大题共20小题,每题1分,共20分) ? 1. 组成UML有三种基本的建筑块是:(?A ),事物和图 A、关系?????????????????? B、类 C、用例?????????????????? D、实体 2、UML体系包括三个部分:UML基本构造块,(?A )和UML公共机制 A、UML规则????????????? B、UML命名 C、UML模型????????????? D、UML约束 3、UML中的事物包括:结构事物,分组事物,注释事物和( D) A、实体事物?????????? ???????? B、边界事物 C、控制事物?????????????????? D、动作事物 4、( A)模型的缺点是缺乏灵活性,特别是无法解决软件需求不明确或不准确的问题 A、瀑布模型?????????????????? B、原型模型 C、增量模型?????????????????? D、螺旋模型 5、下面哪个不是UML中的静态视图(A? ) A.状态图??????????????????? B.用例图 C.对象图??????????????????? D.类图 6、(?A )技术是将一个活动图中的活动状态进行分组,每一组表示一个特定的类、人或部门,他们负责完成组内的活动。 ? A、泳道??????????????????? B、分叉汇合 ? C、分支??????????????????? D、转移 7、下列关于状态图的说法中,正确的是( C ) A. 状态图是UML中对系统的静态方面进行建模的五种图之一。 B. 状态图是活动图的一个特例,状态图中的多数状态是活动状态 C.活动图和状态图是对一个对象的生命周期进行建模,描述对象随时间变化的 行为。 D. 状态图强调对有几个对象参与的活动过程建模,而活动图更强调对单个反应 型对象建模 8、对反应型对象建模一般使用(?A )图 A、状态图??????????????????? B、顺序图 ?C、活动图??????????????????? D、类图

信息系统分析与设计考试题库及答案

一、选择填空 1. 信息按照(C )可以分为战略信息、战术信息和作业信息)可以分为战略信息、战术信息和作业信息。 A. 应用领域 B. 加工顺序 C. 管理的层次 D. 反映形式 2. 按照处理的对象,可把组织的信息系统分为( B ) 和管理信息系统两大类。按照处理的对象,可把组织的信息系统分为) 和管理信息系统两大类。 A. 电子数据处理系统 B. 作业信息系统 C. 决策支持系统 D. 情报处理系统 3. 信息系统对管理职能的支持,归根到底是对( D ) 的支持。 A. 计划 B. 组织 C. 控制 D. 决策 4. 业务系统规划法(BSP)的核心是(C ) A. 明确企业目标 B. 定义(识别)业务过程 C. 进行数据分析 D. 确定信息结构 5. 下面哪一项企业关键成功因素的特点是错误的:( B )。 A. 少量的易于识别的可操作的目标 B. 可确保企业的成功 C. 由企业的所有CSF决定组织的信息需求 6. 下面哪一项不是信息系统局部开发层次的优势:( D )。 A. 相对简单的IT开发 B. 帮助理论的证明 C. 组织变化的阻力最小 D. 优化组织过程 7. 一般子系统的划分是在系统( A )阶段,根据对系统的功能/数据分析的结果提出的。 A. 需求分析 B. 逻辑阶段 C. 总体设计 D. 详细设计 8. 在新产品开发机构重组中,以开发某一新产品为目标,组织集设计、工艺、生产、供应、检验人员为一体的承包组,打破部门的界限,实行团队管理,以及将设计、工艺、生产制造并行交叉的作业管理,这属于( C )。 A. 功能内的BPR B. 组织间的BPR C. 功能间的BPR D. 功能内的BPR 9. 数据存贮设计则根据数据资源分布具体确定了数据存贮的( A )。 A. 逻辑方式 B. 物理方式 10. 信息系统流程图是以新系统的( D )为基础绘制的。 A. E-R图 B. 管理功能图 C. 业务流程图 D. 数据流程图 11. 在关系规范化过程中,一般来讲,满足( C )的关系即可满足信息处理的要求,就可以认为是比较规范的关系。 A. 第一范式 B. 第二范式 C. 第三范式 D. BC范式 12. RUP中的软件生命周期在时间上被分解为四个顺序的阶段,分别是:初始阶段(Inception)、细化阶段(Elaboration)、构造阶段(Construction)和交付阶段(Transition),每个阶段结束于一个主要的里程碑(Major Milestones)。构建阶段结束时是第三个重要的里程碑:( C ) A. 生命周期目标(Lifecycle Objective)里程碑 C. 初始功能(Initial Operational)里程碑 B. 生命周期结构(Lifecycle Architecture)里程碑 D. 产品发布(Product Release)里程碑 13. 从社会经济发展的角度来看,信息化是指( D )。 A. 计算机和网络的应用规模与效益不断增长的过程 B. 社会上进行交换的信息量不断增长的过程 C. 计算机硬件产业、软件产业、信息服务产业不断发展的过程 D. 人们的信息活动的规模不断扩大以致在国民经济中起主导作用的过程

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案 作业一 一、名词解释: 1.递归算法:直接或间接地调用自身的算法称为递归算法。 2.程序:程序是算法用某种程序设计语言的具体实现。 二、简答题: 1.算法需要满足哪些性质?简述之。 答:算法是若干指令的有穷序列,满足性质: (1)输入:有零个或多个外部量作为算法的输入。(2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令清晰、无歧义。 (4)有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答:分析分治法能解决的问题主要具有如下特征: (1)该问题的规模缩小到一定的程度就可以容易地解决; (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出的子问题的解可以合并为该问题的解; (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 答:将递归算法转化为非递归算法的方法主要有: (1)采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归, 只不过人工做了本来由编译器做的事情,优化效果不明显。(2)用递推来实现递归函数。 (3)通过Cooper 变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善,但其适用范围有限。 三、算法编写及算法应用分析题: 1.冒泡排序算法的基本运算如下: for i ←1 to n-1 do for j ←1 to n-i do if a[j]

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1.D 2.B 3.C 4.D 5.D 6.D 7.C 8.D 9.B 10.C 11.D 12.B 13.D 14.C 15.C 16.D 17.D 18.D 19.D 20.C 1.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 2.根据执行算法的计算机指令体系结构,算法可以分为()。 A精确算法与近似算法B串行算法语并行算法 C稳定算法与不稳定算法D32位算法与64位算法 3.具有10个节点的完全二叉树的高度是()。 A6B5C3D 2 4.下列函数关系随着输入量增大增加最快的是()。 Alog2n B n2 C 2n D n! 5.下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6.Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7.4个盘子的汉诺塔,至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8.下列序列不是堆的是()。 A 99,85,98,77,80,60,82,40,22,10,66 B 99,98,85,82,80,77,66,60,40,22,10 C 10,22,40,60,66,77,80,82,85,98,99 D 99,85,40,77,80,60,66,98,82,10,22 9.Strassen矩阵乘法的算法复杂度为()。 AΘ(n3)BΘ(n2.807) CΘ(n2) DΘ(n) 10.集合A的幂集是()。 A.A中所有元素的集合 B. A的子集合 C. A 的所有子集合的集合 D. 空集 11.与算法英文单词algorithm具有相同来源的单词是()。 A logarithm B algiros C arithmos D algebra 12.从排序过程是否完全在内存中显示,排序问题可以分为()。 A稳定排序与不稳定排序B内排序与外排序 C直接排序与间接排序D主排序与辅助排序 13.下列()不是衡量算法的标准。 A时间效率B空间效率 C问题难度D适应能力 14.对于根树,出度为零的节点为()。 A0节点B根节点C叶节点D分支节点 15.对完全二叉树自顶向下,从左向右给节点编号,节点编号为10的父节点编号为()。 A0B2C4D6 16.下列程序段的算法时间的复杂度为()。 for i ←0 to n do for j ←0 to m do

系统分析与设计复习题

《系统分析与设计》复习题 一、复习要点 1.系统是由处于一定环境中的若干相互联系和相互作用的要素组成并为达到整体目的而存在的集 合。 2.信息系统是指利用计算机、网络、数据库等现代信息技术,处理组织中的数据、业务、管理和 决策等问题,并为组织目标服务的综合系统。信息系统开发的步骤是,在系统规划后,循环进行系统分析、系统设计、系统构建与实施、系统评价工作。信息系统的经济效益可分为三大类:一次性收益,非一次性收益和不可定量的收益 3.系统规划阶段的任务是对组织的环境、战略、目标、现行系统的状况进行初步调查,根据组织 目标和发展战略,确定信息系统的发展战略,对建设新系统的需求做出分析和预测,同时考虑建设新系统所受的各种约束,研究建设新系统的必要性和可能性。对于确定的信息系统项目,要明确其目标,并对目标进行权衡和量化。 4.系统分析的主要活动有系统初步调查、系统可行性研究、系统详细调查研究和新系统逻辑方案 的提出,主要任务是尽可能弄清用户对信息的需求,完成新系统的逻辑设计,规定新系统应当做什么。 5.常用的调查研究的方法有问卷调查法、召开调查会、业务实践、专家访谈、电子问卷。如果系 统初步调查结果表明,拟开发项目有必要也有可能进行时,可向主管单位提出系统开发建议书,需要进行可行性研究安排。 6.可行性研究又叫可行性分析,它是所有工程项目在开始阶段必须进行的一项工作。可行性研究 是指项目正式开发之前,先投入一定的精力,通过一套准则,从经济、技术、社会等方面对项目的必要性、可能性、合理性,以及项目所面临的重大风险进行分析和评价,得出项目是否可行的结论。可行性研究的主要成果是可行性研究报告和系统开发任务书。 7.需求分析是强调用户对新开发的信息系统的需要和要求,结合组织的目标、现状、实力和技术 等因素,通过深入细致的分析,确定出合理可行的信息系统需求,并通过规范的形式描述需求的过程。需求分析结束时,应当提出需求分析报告交上级审查。信息系统需求分为功能需求和非功能需求两类。 8.系统设计用来确定系统的结构,即系统的组成以及各组成成分之间的相互关系,详细设计用来 确定模块内部的算法和数据结构,产生描述各模块程序过程的详细设计文档。系统设计是对系统分析的深化和细化,其目的是提出能够指导信息系统实现的设计方案。系统实施以系统分析

《算法分析与设计》期末试题及参考答案

《算法分析与设计》期末试题及参考答案 一、简要回答下列问题: 1.算法重要特性是什么? 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么? 2.分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关? 3. 算法的时间复杂性与问题的规模相关,是问题大小n的函数。 4.算法的渐进时间复杂性的含义? 4.当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同? 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时,不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度: W(n) = max{ T(n,I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和: A(n) =∑P(I)T(n,I) I∈Dn 6.简述二分检索(折半查找)算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i:j] 和x,选取A[(i+j)/2]与x比较, 如果A[(i+j)/2]=x,则返回(i+j)/2,如果A[(i+j)/2]

相关主题