下载文档原格式
《计算机软件技术基础》第一章算法1.1算法的基本概念算法：指解题方案的准确而完整的描述算法的基本特征：能行性（算法中的每一个步骤必须能够实现；算法执行的结果要能够达到预期的目的）确定性（算法中的每一个步骤都必须是有明确定义的，不能摸棱两可，也不能有多义性）有穷性（算法必须能在执行有限个步骤之后终止）拥有足够的情报（算法执行的结果总是与输入的初始数据有关。
不同输入对应不同输出）算法：是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数下终止。
算法的基本要素：1.算法中对数据的运算和操作（算术运算、逻辑运算、关系运算、数据传输【赋值、输入、输出】）2.算法的控制结构（算法中各操作之间的执行顺序）1.2算法描述语言C语言描述和简单的算法描述语言（1）符号与表达式：符号主要用以表述变量名、数组名等（2）赋值语句（3）控制转移语句：无条件转移语句形式：GOTO 标号条件转移语句形式IF C THEN SIF C THEN S1ELSE S2（4）循环语句WHILE语句：WHILE C DO SFOR语句：FOR i=init TO limit BY step DO S（5）其他语句EXIT语句：退出某个循环，使控制转到包含EXIT语句的最内层的WHILE或FOR循环后面的一个语句去执行RETURN语句：结束算法的执行（允许使用用引号括起来的注释信息）READ(INPUT)和WRITE(PRINT/OUTPUT)语句：用于输入输出（6）算法中的注释总是用一对方括号【】括起来；复合语句用一对花括号{}括起来1.3算法设计基本方法1.列举法【例1.1】基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的（通常解决“是否存在”“有多少种可能”类型问题）特点：算法比较简单，但列举情况较多时，工作量将很大寻找路径、查找、搜索等问题采用列举法有效2.归纳法基本思想：通过列举少量的特殊情况，经过分析，最后找出一般的关系3.递推法（数学例题）指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（本质属于归纳法）4.递归基本思想：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些简单的问题后，再沿着原来分解的逆过程逐步进行综合【例1.3】自己调用自己的过程称为递归调用过程递归分为直接递归：一个算法P显式地调用自己间接递归：算法P调用另一个算法Q，而算法Q又调用算法P5.减半递推技术（分治法）减半：将问题的规模减半，而问题的性质不变递推：重复“减半”的过程【例1.4】6.回溯法通过对问题的分析，找出一个解决问题的线索；然后沿着这个线索逐步试探。
流程图-n s图-p a d图-p d l-h i p o流程图、N-S图、PAD图、判定表、PDL、HIPO图程序流程图程序流程图独立于任何一种程序设计语言，比较直观、清晰，易于学习掌握。
但流程图也存在一些严重的缺点。
例如流程图所使用的符号不够规范，常常使用一些习惯性用法。
特别是表示程序控制流程的箭头可以不受任何约束，随意转移控制。
这些现象显然是与软件工程化的要求相背离的。
为了消除这些缺点，应对流程图所使用的符号做出严格的定义，不允许人们随心所欲地画出各种不规范的流程图。
例如，为使用流程图描述结构化程序，必须限制流程图只能使用图3.25所给出的五种基本控制结构。
图4.3 流程图的基本控制结构任何复杂的程序流程图都应由这五种基本控制结构组合或嵌套而成。
作为上述五种控制结构相互组合和嵌套的实例，图示给出一个程序的流程图。
图中增加了一些虚线构成的框，目的是便于理解控制结构的嵌套关系。
显然，这个流程图所描述的程序是结构化的。
图4.4流程图的基本控制结构N-S图Nassi和Shneiderman 提出了一种符合结构化程序设计原则的图形描述工具，叫做盒图，也叫做N-S图。
为表示五种基本控制结构，在N-S图中规定了五种图形构件。
参看图4.5。
为说明N-S图的使用，仍用图4.4给出的实例，将它用如图4.6所示的N-S图表示。
如前所述，任何一个N-S图，都是前面介绍的五种基本控制结构相互组合与嵌套的结果。
当问题很复杂时，N-S图可能很大。
图4.5 N-S图的五种基本控制结构图4.6 N-S图的实例PADPAD是Problem Analysis Diagram的缩写，它是日本日立公司提出，由程序流程图演化来的，用结构化程序设计思想表现程序逻辑结构的图形工具。
现在已为ISO认可。
PAD也设置了五种基本控制结构的图式，并允许递归使用。
图4.7 PAD的基本控制结构做为PAD应用的实例，图4.8给出了图4.4程序的PAD表示。
流程图、N-S图、PAD图、判定表、PDL、HIPO图程序流程图程序流程图独立于任何一种程序设计语言，比较直观、清晰，易于学习掌握。
但流程图也存在一些严重的缺点。
例如流程图所使用的符号不够规范，常常使用一些习惯性用法。
特别是表示程序控制流程的箭头可以不受任何约束，随意转移控制。
这些现象显然是与软件工程化的要求相背离的。
为了消除这些缺点，应对流程图所使用的符号做出严格的定义，不允许人们随心所欲地画出各种不规范的流程图。
例如，为使用流程图描述结构化程序，必须限制流程图只能使用图3.25所给出的五种基本控制结构。
图4.3 流程图的基本控制结构任何复杂的程序流程图都应由这五种基本控制结构组合或嵌套而成。
作为上述五种控制结构相互组合和嵌套的实例，图示给出一个程序的流程图。
图中增加了一些虚线构成的框，目的是便于理解控制结构的嵌套关系。
显然，这个流程图所描述的程序是结构化的。
图4.4流程图的基本控制结构N-S图Nassi和Shneiderman 提出了一种符合结构化程序设计原则的图形描述工具，叫做盒图，也叫做N-S图。
为表示五种基本控制结构，在N-S图中规定了五种图形构件。
参看图4.5。
为说明N-S图的使用，仍用图4.4给出的实例，将它用如图4.6所示的N-S图表示。
如前所述，任何一个N-S图，都是前面介绍的五种基本控制结构相互组合与嵌套的结果。
当问题很复杂时，N-S图可能很大。
图4.5 N-S图的五种基本控制结构图4.6 N-S图的实例PADPAD是Problem Analysis Diagram的缩写，它是日本日立公司提出，由程序流程图演化来的，用结构化程序设计思想表现程序逻辑结构的图形工具。
现在已为ISO认可。
PAD也设置了五种基本控制结构的图式，并允许递归使用。
图4.7 PAD的基本控制结构做为PAD应用的实例，图4.8给出了图4.4程序的PAD表示。
PAD所描述程序的层次关系表现在纵线上。
每条纵线表示了一个层次。
一，第一章1．软件工程→1968年的NATO会议上提出解决“软件危机”2．倡导工程原理，原则，方法进行软件开发，以期解决“软危”3．软件工程：用计算机科学理论和技术和工程管理原则方法，按预算，进度满足用户要求的软件产品工程。
4．软工两时间：1. 60-80年代，系统规模，复杂性，关键领域应用，提出了waterfall, C, Pascal, Ada; Jackson方法，结构化方法。
2. 80年代后大量软件的实践，过程支持，软件生产技术，复用技术，生产管理。
《软件和存周期过程》，C++, Eiffel, Smalltalk5．软件=程序+文档，是逻辑实体，“无形”6．程序=处理对象+处理规则7．文档=理解程序所需的阐述性资料8．软件开发的本质：不同抽象层术语+处理逻辑之间的“映射”9．建模的方法：结构化方法，面向对象方法，诸多面向数据结构方法10．模型:待建系统的任意抽象，包括基本能力，特性，或其他方面；抽象上对物理系统的描述，系统边界，关系的主义描述。
11．软件系统模型：1，概念模型（用户）2，软件模型（开发者）a)需求→概念模型b)设计→软件模型c)实现→软件模型d)部署→软件模型12．软件开发有技术和管理上的问题二，第二章1．正确定义问题，是解决问题的基础2．需求是“要予构造”的陈述，描述了软件“能力”“性能参数”“其他性质”3．需求的性质：a)必要b)无歧义c)可测/测量d)可跟踪4．验证需求是不是歧义→需求复审5．需求分类：功能/非功能（性能，外部接口，设计约束，质量属性），6．需求发现：自悟，交谈，观察，小组会，提炼a)自悟要求高，要有想象力/需求不正确b)交谈依赖“正确提问”“揭示本意”/不能认识到合理需求→复审c)观察要有洞察力/客户抵触，客户认为熟悉了业务d)小组会人力资源，良好的需求发现能力，达成共识/客观条件限制，互相矛盾的需求e)提炼要有想像力和需求标识力熟悉技术和法规/无法验证需求是否正确7．需求规约是陈述的正式文档，表达概念模型a)重要性和稳定性程度b)可修改c)完整d)一致8． 需求规约表达：非形式化（规模小，不复杂，小型软件），半形式和形式化（主要为了验证程序正确）9． 需求规约作用：a) 技术合同，产品功能和环境体现b) 管理控制点c) 正式，受控的起点d) 初始测试计划，用户系统操作描述10． 需求规约不是一个设计文档，用于设计的文档，也不是进度和规划文档三，第三章1．软件需求中三挑战：1． 问题空间理解2． 人与人之间通信3． 需求的变化性2．20世纪70年代提出结构化方法3．基本术语1． 数据流程2． 加工3． 数据存储4． 数据源和数据潭4.数据流图DFD P375.按功能分解的设计思想：自顶向下，逐步求精6．数据字典：[=]定义为；[|]或者；[+]顺序；[{}]重复；[m.n]子界7．数据结构3种条目：数据流条目；数据存储条目；数据项条目8．结构化语言是形式化语言和自然语言之间的语言9．判定表；判定树P4311． 图元数7正负212． 15%的错误源自错误的需求13． 总体设计：模块和模块调用14． 总体设计：模块结构图/层次图/HIPO 图P4515． “高内聚，低耦合”16．数据流图分为：变换型和事务型17．模块化，软件分为简单的高内聚低耦合的模块（两部分：接口和模块体）18．耦合：依赖程度的度量。
一、判断题1、The results of decomposition form composite parts called modules or components.（T）2、Cohesion refers to the internal “glue” with which a component is constructed.（T）3、We say that two components are loosely coupled when there is a great deal of dependence between them.（F）4、Design is the creative process of transforming the problem intoa solution.（T）二、解释概念1、 what is design?Design is the creative process to transform the problem into a solution. 设计是将问题转化成解决方案的创造性的活动Design is the description of a solution. 是对解决方案的描述。
2、What is Coupling? States Coupling levels from low to high.Coupling耦合性是指模块间联系，即程序结构中不同模块之间互连程度。
耦合等级从低到高：Uncoupled 非直接耦合：通过上级模块进行联系，无直接关联。
Data coupling 数据耦合：参数传递的是一般类型的数据。
Stamp coupling 标记耦合：参数传递的是诸如结构类型的数据。
Control coupling 控制耦合：模块间传递的是诸如标记量的控制信息。
Common coupling 公共耦合：全局结构类型的数据。
Content coupling 内容耦合：病态连接，一个模块可以直接操作另一个模块的数据（如go to 语句的使用）。
软件工程课后习题答案——殷锋主编注：有些可能错误，读者自己注意第一章一、填空题：1、软件是计算机系统中与硬件彼此依存的另一部份，是包括程序、数据、及相关文档的的完整集合2、软件工程包括三要素：方式、工具和进程。
3、软件开发的大体方式包括结构化方式和面向对象方式二、选择题：C 2、B 3、C1软件的特点：（1）逻辑实体（2）与硬件生产方式不同（3）与硬件的保护不同（4）复杂的5 本钱相当昂贵2软件危机的产生及其表现：1开发进度难以预测2本钱难以控3功能不能能知足用户的需求4质量难以保证5难以保护6缺少适当的文本资料3比较结构化方式和面向对象方式：结构化方式：自顶向下，慢慢分解模块易于控制和处置模块相对独立、接口简单、利用保护超级方便面向对象方式：提高软件系统的稳定性可修改和可重用性产生的具有特点：客观世界任何事物对象都是对象每各类概念一种方式若干对象组成参次结构系统对象通过传递消息彼此联系第二章一、填空题：1、软件生存周期的各个进程可以分成三类，及主要生存周期进程、支持生存周期进程和组织的生存周期进程。
2、软件生存周期包括计划、需求分析、设计、程序编码、软件测试和运行保护6个阶段。
3、软件进程改良（SPI）帮忙软件企业对其软件进程的改变进行计划，制定和实施。
二、填空题1、A2、B三、判断题1、√2、X4什么是软件进程？软件生存周期进程或软件进程组，是指软件生存周期中的一系类相关进程。
5软件的生存周期：计划需求分析设计程序编码软件测试运行保护6可行性研究的任务是什么？进行一次大大紧缩简化的系统分析和设计的进程，在高参差上以抽象的方式进行系统分析和设计。
任务：以最小的代缴在最短的时间内肯定问题可否解决，也就是判定原定的目标和规模可否实现第三章三、填空题：1、可行性研究的目的是用最小的代价，在尽可能短的时间内，肯定问题是不是能够解决2、可行性研究在进行简要需求分析和设计时，要在高层次上以较抽象的方式进行3、需求分析阶段产生的最重要的文档是软件需求规格说明书。
信息系统管理工程师模拟题及答案解析第四套试题一[说明]信息系统设计主要包括概要设计和详细设计。
详细设计的主要任务是对每个模块完成的功能进行具体描述，并将功能描述转变为精确的、结构化的过程描述。
详细设计一般包括代码设计、数据库设计、输入/输出设计、处理过程设计和用户界面设计等。
其中，数据库设计分为4个主要阶段，在对应用对象的功能、性能和限制等要求进行分析后，进入对应用对象进行抽象和概括阶段，完成企业信息模型；处理过程设计是用一种合适的表达方法来描述每个模块的执行过程，并可由此表示方法直接导出用编程语言表示的程序。
1、[问题1]请指出数据库设计过程主要包括哪4个阶段？2、[问题2]概念结构设计最常用的方法是什么？请简要说明其设计过程主要包括哪些步骤？3、[问题3]请指出处理过程设计常用的描述方式是哪3种，常用的图形表示方法是哪2种图？试题二[说明]企业信息化是企业以业务流程的优化和重构为基础，利用计算机技术、网络技术和数据库技术，集成化管理企业生产经营活动中的各种信息，实现企业内外部信息的共享和有效利用，以提高企业的经济效益和市场竞争力的一项建设工作，它涉及企业管理理念的创新，管理流程的优化，管理团队的重组和管理手段的创新。
企业信息化涉及面广，就制造型企业而言，企业信息化包括生产过程控制的信息化、企业管理的信息化、企业供应链管理的信息化等内容。
企业信息化建设要应用计算机辅助设计（CAD.、计算机辅助制造（CAM）、复杂工程结构设计（CAE.、辅助工艺设计（CAPP）、集散型控制系统（DCS）、计算机集成制造系统（CIMS）、计算机集成生产系统（CIPS）、事务处理系统（TPS）、管理信息系统（MIS）、决策支持系统（DSS）、智能决策支持系统（IDSS）、企业资源计划（ERP）、产品数据管理（PDM）、安全防范系统（PPS）、办公自动化（OA.等软件工具以及企业网站建设等。
而事实上，企业信息化建设的主要工作之一就是选择各种适宜的软件以应用于企业的各项工作，从而提高企业各项工作的现代化管理水平。
流程图、N-S图、PAD图、判定表、PDL、HIPO图程序流程图程序流程图独立于任何一种程序设计语言，比较直观、清晰，易于学习掌握。
但流程图也存在一些严重的缺点。
例如流程图所使用的符号不够规范，常常使用一些习惯性用法。
特别是表示程序控制流程的箭头可以不受任何约束，随意转移控制。
这些现象显然是与软件工程化的要求相背离的。
为了消除这些缺点，应对流程图所使用的符号做出严格的定义，不允许人们随心所欲地画出各种不规范的流程图。
例如，为使用流程图描述结构化程序，必须限制流程图只能使用图3.25所给出的五种基本控制结构。
图4.3 流程图的基本控制结构任何复杂的程序流程图都应由这五种基本控制结构组合或嵌套而成。
作为上述五种控制结构相互组合和嵌套的实例，图示给出一个程序的流程图。
图中增加了一些虚线构成的框，目的是便于理解控制结构的嵌套关系。
显然，这个流程图所描述的程序是结构化的。
图4.4流程图的基本控制结构N-S图Nassi和Shneiderman 提出了一种符合结构化程序设计原则的图形描述工具，叫做盒图，也叫做N-S图。
为表示五种基本控制结构，在N-S图中规定了五种图形构件。
参看图4.5。
为说明N-S图的使用，仍用图4.4给出的实例，将它用如图4.6所示的N-S图表示。
如前所述，任何一个N-S图，都是前面介绍的五种基本控制结构相互组合与嵌套的结果。
当问题很复杂时，N-S图可能很大。
图4.5 N-S图的五种基本控制结构图4.6 N-S图的实例PADPAD是Problem Analysis Diagram的缩写，它是日本日立公司提出，由程序流程图演化来的，用结构化程序设计思想表现程序逻辑结构的图形工具。
现在已为ISO认可。
PAD也设置了五种基本控制结构的图式，并允许递归使用。
图4.7 PAD的基本控制结构做为PAD应用的实例，图4.8给出了图4.4程序的PAD表示。
PAD所描述程序的层次关系表现在纵线上。
每条纵线表示了一个层次。
把PAD图从左到右展开。
随着程序层次的增加，PAD逐渐向右展开。
PAD的执行顺序从最左主干线的上端的结点开始，自上而下依次执行。
每遇到判断或循环，就自左而右进入下一层，从表示下一层的纵线上端开始执行，直到该纵线下端，再返回上一层的纵线的转入处。
如此继续，直到执行到主干线的下端为止。
图4.8 PAD实例判定表当算法中包含多重嵌套的条件选择时，用程序流程图、N-S图或PAD都不易清楚地描述。
然而，判定表却能清晰地表达复杂的条件组合与应做动作之间的对应关系。
仍然使用图4.4的例子。
为了能适应判定表条件取值只能是"T"和"F"的情形，对原图稍微做了些改动，把多分支判断改为两分支判断，但整个图逻辑没有改变。
见图4.9。
与图3.31表示的流程图对应的判定表如图3.32所示。
在表的右上半部分中列出所有条件，"Ｔ"表示该条件取值为真，"Ｆ"表示该条件取值为假，空白表示这个条件无论取何值对动作的选择不产生影响。
在判定表右下半部分中列出所有的处理，画"Ｙ"表示要做这个动作，空白表示不做这个动作。
判定表右半部的每一列实质上是一条规则，规定了与特定条件取值组合相对应的动作。
图4.9 不包含多分支结构的流程图实例PDL(Program Design Language)PDL是一种用于描述功能模块的算法设计和加工细节的语言。
称为设计程序用语言。
它是一种伪码。
一般地，伪码的语法规则分为"外语法"和"内语法"。
外语法应当符合一般程序设计语言常用语句的语法规则；而内语法可以用英语中一些简单的句子、短语和通用的数学符号，来描述程序应执行的功能。
使用PDL语言，可以做到逐步求精：从比较概括和抽象的PDL程序起，逐步写出更详细的更精确的描述。
PDL就是这样一种伪码。
它具有严格的关键字外语法，用于定义控制结构和数据结构，同时它的表示实际操作和条件的内语法又是灵活自由的，可使用自然语言的词汇。
下面举一个例子，来看PDL的使用。
从上例可以看到，PDL 语言具有正文格式，很像一个高级语言。
人们可以很方便地使用计算机完成PDL的书写和编辑工作。
PROCEDURE spellcheck IS 查找错拼的单词BEGINsplit document into single words 把整个文档分离成单词lood up words in dictionary 在字典中查这些单词display words which are not in dictionary 显示字典中查不到的单词create a new dictionary 造一新字典END spellcheckPDL作为一种用于描述程序逻辑设计的语言，具有以下特点：·有固定的关键字外语法，提供全部结构化控制结构、数据说明和模块特征。
属于外语法的关键字是有限的词汇集，它们能对PDL正文进行结构分割，使之变得易于理解。
为了区别关键字，规定关键字一律大写，其它单词一律小写。
·内语法使用自然语言来描述处理特性。
内语法比较灵活，只要写清楚就可以，不必考虑语法错，以利于人们可把主要精力放在描述算法的逻辑上。
·有数据说明机制，包括简单的（如标量和数组）与复杂的（如链表和层次结构）的数据结构。
·有子程序定义与调用机制，用以表达各种方式的接口说明。
HIPO图(Hierarchy plus Input Process Output)HIPO最初只用做文档编写的格式要求，随后发展成比较有名的软件设计手段。
HIPO图采用功能框图和PDL 来描述程序逻辑，它由两部分组成：可视目录表和IPO图。
可视目录表给出程序的层次关系，IPO图则为程序各部分提供具体的工作细节。
1、可视目录表可视目录表由体系框图、图例、描述说明三部分组成。
(1)体系框图又称层次图（H图），是可视目录表的主体，用它表明各个功能的隶属关系。
它是自顶向下逐层分解得到的，是一个树形结构。
它的顶层是整个系统的名称和系统的概括功能说明；第二层把系统的功能展开，分成了几个框；第二层功能进一步分解，就得到了第三层、第四层，…，直到最后一层。
每个框内都应有一个名字，用以标识它的功能。
还应有一个编号，以记录它所在的层次及在该层次的位置。
(2)图例每一套HIPO图都应当有一个图例，即图形符号说明。
附上图例，不管人们在什么时侯阅读它都能对其符号的意义一目了然。
(3)描述说明它是对层次图中每一框的补充说明，在必须说明时才用，所以它是可选的。
描述说明可以使用自然语言。
例如，应用HIPO法对盘存/销售系统进行分析。
得到如图4.10所示的工作流程图。
分析此工作流程图，可得如图3.34所示的可视目录表。
图4.11(a)是系统的层次图，图4.11(b)是后面IPO 图的图例，图4.11(c)是描述说明。
图4.10 盘存/销售系统工作流程图图4.11 盘存/销售系统的可视目录表2、IPO图IPO图为层次图中每一功能框详细地指明输入、处理及输出。
通常，IPO图有固定的格式，图中处理操作部分总是列在中间，输入和输出部分分别在其左边和右边。
由于某些细节很难在一张IPO图中表达清楚，常常把IPO图又分为两部分，简单概括的称为概要IPO图，细致具体一些的称为详细IPO图。
概要IPO图用于表达对一个系统，或对其中某一个子系统功能的概略表达，指明在完成某一功能框规定的功能时需要哪些输入，哪些操作和哪些输出。
图4.12是表示销售/盘存系统第二层的对应于H图上的1.1.0框的概要IPO图。
图4.12 对应H图上1.1.0框的概要IPO图在概要IPO图中，没有指明输入―处理―输出三者之间的关系，用它来进行下一步的设计是不可能的。
故需要使用详细IPO 图以指明输入―处理―输出三者之间的关系，其图形与概要IPO图一样，但输入、输出最好用具体的介质和设备类型的图形表示。
图4.13是销售/盘存系统中对应于1.1.2框的一张详细IPO图。
图4.13 对应于H图1.1.2框的详细IPO图3、利用HIPO进行迭代式细化设计在软件设计时，解决设计问题通常需要经历一个认识逐步发展的过程，并且对一些问题还要经过反复的考虑才可能达到比较满意的设计效果。
我们称此为迭代式细化设计。
HIPO能很好地适应这一要求。
图 4.14是利用HIPO进行迭代式细化设计的示意图。
从图中可看到，把可视目录表和IPO图结合起来，反复交替地使用它们，可使得设计工作逐步深化，最终取得完满的设计结果。
其实这正是自顶向下，逐步求精的结构化程序设计思想。
HIPO有自己的特点。
首先，这一图形表达方法容易看懂。
其次，HIPO的适用范围很广，绝不限于详细设计。
事实上，画可视目录表就是与概要设计密切相关的工作。
如果利用它仅仅表达软件要达到的功能，则是需求分析中描述需求的很好的工具。
因为HIPO是在开发过程中的表达工具，所以它又是开发文档的编制工具。
开发完成后，HIPO图就是很好的文档，而不必在设计完成以后，专门补写文档。
图4.14 利用HIPO进行迭代式细化设计。
