第 7章软件技术基础
本章根据教育部考试中心颁发的《全国计算机等级考试二级公共基础知识考试大纲》编写，主要内容包括算法与数据结构、软件工程基础和数据库设计基础。
7.1算法
7.1.1算法的基本概念
算法是对特定问题求解步骤的具体描述，它是指令的有限序列，其中每一条指令表示一个或多个基本操作。
对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间得到正确地结果，则称这个问题是算法可解的。虽然计算机程序可以作为算法的一种描述形式，但算法不等于程序，这是因为编写程序要受计算机系统运行环境的限制，通常需要考虑许多与方法和分析无关的细节，程序的编制应在算法设计之后。
1． 算法的基本特征
利用计算机算法为计算机解题的过程实际上是在实施某种算法。通常算法具有以下四个重要特征：
（1） 有穷性。算法有穷性是指算法总是在执行有穷步之后结束，且每一步都在有
限时间内完成。
（2） 确定性。算法的确定性是指算法中的每一步都必须有明确的含义，不允许有
二义性或多义性。并且在任何条件下对相同的输入只能得到相同的输出。
（3） 可行性。一个算法是可行的是指算法的每一步都可以通过已经实现的基本运
算执行有限次来实现。
（4） 输入和输出一个算法可以有零个或多个输入，以描述算法对象的初始情况；
同时算法必须有一个或多个输出，以反映对输入数据的处理结果。没有输出的算法是毫无意义的算法。
第1页共35页
2． 算法的表示
算法的描述应直观、清晰、易读和便于修改维护。描述算法的方法包括自然语言、流程图、程序设计语言、形式化方法等。不同的表示方法有不同的特点和作用。
（1） 自然语言
自然语言方式就是人们日常使用的语言。例如，在求一元二次方程的根时，就可以使用这种表示方式：\一元二次方程的根的计算公式是，在a不等于0的情况下，分子是负b加减b的平方减去4ac的平方根，分母是2a。\
用自然语言表示算法的优点是简单、方便，适合描述简单的算法或算法的高层思想。但是，该方式的主要问题是冗长、语义容易模糊，很难准确地描述复杂的、技术性强的算法。一般不用自然语言表示算法。
（2） 流程图
流程图是一种用于表示算法或过程的图形。在流程图中，使用各种符号表示算法或过程的每一个步骤，使用箭头符号将这些步骤按照顺序连接起来。使用流程图表示算法可以避免自然语言的模糊缺陷，且依然独立于任何一种特殊的程序设计语言。流程图的使用人员包括分析人员、设计人员、管理人员、工程师、编程人员等。
流程图有多种类型，下面主要介绍一般流程图与NS图的用法。
在一般流程图中，主要的图形元素包括开始/结束标志、箭线、处理框、输入/输出框、条件判断框等。
开始/结束标志一般使用圆形、椭圆形或圆角矩形表示，开始和结束的符号是对应的，且通常包含\开始\、\结束\等字样，开始和结束符号用于明确表示流程图的开始和结束。箭线的符号是带有箭头的线段，表示算法控制语句的流向。一般地，箭线源自流程图中的某个图形，在另一个图形处终止，从而描述算法的执行过程。直角矩形表示算法的处理步骤，称为处理框。平行四边形来表示输入/输出框，也就是表示算法的输入、输出操作。菱形表示条件判断框，用于执行算法中的条件判断，控制算法的执行过程。在条件判断框中，往往有一个输入箭线和两个输出箭线。两个输出箭线分别表示条件成立时和
第2页共35页
不成立时的执行顺序。输出箭线上常标注Yes和No、或Y和N、或True和False、或T和F、或\真\和\假\等字样。如图所示。
NS图是Nassi-Shneiderman图的简称，有时也称为N-S图、盒图等，是1972年Isaac
Nassi和Ben Shneiderman提出的结构化表示程序的图形。NS图遵循自顶向下的原则，将问题对象逐步分解为一个个小问题、再继续分解，直到可以使用简单的语句或控制流程图表示为止。
在如图所示的NS图基本表示形式中，图4-3(a)表示了顺序结构；图4-3(b)表示了条件选择结构，并示意了简单条件选择结构和多条件选择结构的特点；图4-3 (c)表示了循环结构的特点，前一个图表示先判断循环条件后执行循环体，后一个图表示先执行循环体后判断循环条件的循环结构。
（3） 程序设计语言
程序设计语言表示方式是指采用程序设计语言、类程序设计语言(也称为类语言、伪代码等)等形式表示算法。
第3页共35页
用程序设计语言表示的算法实际上就是计算机将要执行的程序。这是计算机领域中算法最完整、最准确、最终的表示方式，也是最复杂的表示方式。程序设计语言表示的算法虽然最精细，但是却难以进行一般的阅读和交流。
由于算法在研究和沟通过程中，需要进行不断地修改和完善，并向多个相关人员和组织提交并得到理解。程序设计语言语法的精细特点在算法设计阶段有可能成为影响算法不断完善和优化的障碍。因此，人们更倾向于采用类程序设计语言来描述和表示算法。类程序设计语言是指对程序设计语言的精简的、非正式的描述，目的是便于人们的阅读和理解，而不是用于计算机的执行。许多流行的程序设计语言，例如C++、Visual Basic、Java、Pascal、C#等，都有自己的类语言。类语言往往省略了程序设计语言的许多细节，目的是准确地表示出算法的思想和过程。 （4） 形式化方法
形式化方法是一种描述计算机软件和硬件系统思想的数学方法。形式化方法主要用于规格说明、设计开发、系统验证等。使用形式化方法的主要好处是可以准确地描述系统或算法的思想，可以满足工程原理验证、执行性能估算、系统可靠性验证等作用。但是，在程序设计领域采用形式化方法的成本比较高，因此该方法仅适用于要求严格的软件项目中。例如，Petri网、ASM(abstract state machine，抽象状态机)等都是典型的形式化方法。
3. 算法的基本结构
在结构化编程中，程序的控制结构仅由顺序、选择和循环结构或三种结构的复合组成；每个节点都由单个入口与单个出口，从入口到出口都存在一条经过该结点的路径。
第4页共35页
