《软件开发方法与信息处理技术》课程论文题目.doc

软件开发方法与信息处理技术 课程论文 所 在 系： 信息工程系 专业班级： 学生姓名： 学生学号： 评定成绩： 二0一二年十二月武汉理工大学华夏学院课程论文1. 试论述什么是数据结构,什么是算法及算法评价标准.数据的逻辑结构及存储结构有哪些？试简述线性表、栈、队列、树与二叉树；试简述常用的查找算法及常用的排序算法及其特点.答：1）.数据结构：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率.数据结构往往同高效的检索算法和索引技术有关.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型.2） 算法定义：算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制.也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题.不同的算法可能用不同的时间、空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 3）算法评定标准：1.时间复杂度：算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=(f(n) 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度. 2.空间复杂度：算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多.4） .数据的逻辑结构：包括线性结构,树形结构，图形结构和集合结构四种结构.存储结构（物理结构）：顺序，连接，索引，散列等四种基本类型.5）线性表：线性表是最基本、最简单、也是最常用的一种数据结构.线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构. 线性表是一个线性结构，它是一个含有n0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点.一般地，一个线性表可以表示成一个线性序列：k1,k2,kn，其中k1是开始结点，kn是终端结点.是一个数据元素的有序（次序）集. 栈：栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的逻辑结构：假设一个栈S中的元素为an,an-1,.,a1，则称a1为栈底元素，an为栈顶元 素。栈中的元素按a1 ,a2,.,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的.因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈.树： 树是由一个或多个结点组成的有限集合，其中：必有一个特定的称为根(ROOT)的结点；剩下的结点被分成n=0个互不相交的集合T1、T2、.Tn，而且， 这些集合的每一个又都是树。树T1、T2、.Tn被称作根的子树.树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树.二叉树：二叉树是一类非常重要的树形结构，它可以递归地定义如下：二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树.6）二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些.常用的排序算法：常用的排序算法有插入排序，希尔排序，冒泡排序，快速排序，归并排序，堆排序还有基数排序.排序算法一般考虑的就是两个方面，即时间复杂度和空间复杂度.其中插入排序，冒泡排序是简单排序，排序的平均时间复杂度是O（n2）, 最坏的情况是O(n2)，辅助存储空间是O(1).快速排序的平均时间复杂度是O(nlogn), 最坏的情况是O(n2), 辅助存储空间是O(logn).归并排序的平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(n).堆排序平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(1)基数排序平均时间复杂度是O(d(n+rd), 最坏的情况是O(d(n+rd), 辅助存储空间是O(rd),其中d关键字的个数，rd是关键字的取值的个数。从平均性能上来而言，快速排序最佳，其所需的时间最省，但快排在最坏的情况下的时间性能不如堆排序和归并排序。而后者相比的结果是，在n较大的时候，归并排序需要的时间比堆排序省，但它需要的辅助存储空间比较多。从方法的稳定性来比较，基数排序是稳定的内排序，所有时间复杂度为O（n2）的简单排序都是稳定的。然而，快速排序，归并排序，堆排序等时间性能较好的排序方法都是不稳定的。2什么是数据库Database？什么是数据库管理系统DBMS？数据库系统的基本功能及特点是什么？逻辑数据模型有哪几种，其特点又是什么？试简述E-R模型及关系代数。试简述数据库设计方法与步骤。答：1）.数据库：数据库是依照某种数据模型组织起来并存放二级存储器中的数据集合.这种数据集合具有如下特点：尽可能不重复，以最优方式为某个特定组织的多种应用服务，其数据结构独立于使用它的应用程序，对数据的增、删、改和检索由统一软件进行管理和控制.2） .数据管理系统：是一种操纵和管理数据库的大型软件，用于建立、使用和维护数据库，简称dbms。它对数据库进行统一的管理和控制，以保证数据库的安全性和完整性。用户通过dbms访问数据库中的数据，数据库管理员也通过dbms进行数据库的维护工作。它可使多个应用程序和用户用不同的方法在同时或不同时刻去建立，修改和询问数据库。DBMS提供数据定义语言DDL与数据操作语言DML，供用户定义数据库的模式结构与权限约束，实现对数据的追加、删除等操作.3） .数据库系统的基本功能及特点：1.数据结构化 ，数据之间具有联系，面向整个系统.2.数据的共享性高，冗余度低，易扩充.3.数据独立性高，数据独立性包括数据的物理独立性和逻辑独立性.4.数据由DBMS统一管理和控制，数据库的共享是并发的共享，即多个用户可以同时存取数据库中的数据，甚至可以同时存取数据库中的同一个数据。4）逻辑数据模型： 简称逻辑模型，这是用户从数据库所看到的模型，是具体的DBMS所支持的数据模型，如网状数据模型、层次数据模型等等。此模型既要面向用户，又要面向系统，主要用于数据库管理系统（DBMS）的实现。5）.E-r模型及关系代数：E-R模型的构成成分是实体集、属性和联系集，其表示方法如下：（1）实体集用矩形框表示，矩形框内写上实体名.（2） 实体的属性用椭圆框表示，框内写上属性名，并用无向边与其实体集相连.（3）实体间的联系用菱形框表示，联系以适当的含义命名，名字写在菱形框中，用无向连线将参加联系的实体矩形框分别与菱形框相连，并在连线上标明联系的类型，即11、1N或MN.因此，E-R模型也称为E-R图.6）数据库设计的基本步骤：1.需求分析阶段：准确了解与分析用户需求(包括数据与处理)是整个设计过程的基础，是最困难、最耗费时间的一步 2.概念结构设计阶段是整个数据库设计的关键 通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS的概念模型3.逻辑结构设计阶段将概念结构转换为某个DBMS所支持的数据模型 对其进行优化 4.数据库物理设计阶段 为逻辑数据模型选取一个最适合应用环境的物理结构(包括存储结构和存取方法) 5.数据库实施阶段 运用DBMS提供的数据语言、工具及宿主语言，根据逻辑设计和物理设计的结果 建立数据库，编制与调试应用程序，组织数据入库，并进行试运行 6.数据库运行和维护阶段 数据库应用系统经过试运行后即可投入正式运行。在数据库系统运行过程中必须不断地对其进行评价、调整与修改 设计特点:在设计过程中把数据库的设计和对数据库中数据处理的设计紧密结合起来将这两个方面的需求分析、抽象、设计、实现在各个阶段同时进行，相互参照，相互补充，以完善两方面的设计3.试简述软件危机。答：软件危机主要表现在： 软件开发费用和进度失控。费用超支、进度拖延的情况屡屡发生。有时为了赶进度或压成本不得不采取一些权宜之计，这样又往往严重损害了软件产品的质量.软件的可靠性差。尽管耗费了大量的人力物力，而系统的正确性却越来越难以保证，出错率大大增加，由于软件错误而造成的损失十分惊人.生产出来的软件难以维护。很多程序缺乏相应的文档资料，程序中的错误难以定位，难以改正，有时改正了已有的错误又引入新的错误。随着软件的社会拥有量越来越大，维护占用了大量人力、物力和财力。进入80年代以来，尽管软件工程研究与实践取得了可喜的成就，软件技术水平有了长足的进展，但是软件生产水平依然远远落后于硬件生产水平的发展速度。 用户对“已完成”的系统不满意现象经常发生。一方面，许多用户在软件开发的初期不能准确完整的向开发人员表达他们的需求；另一方面，软件开发人员常常在对用户需求还没有正确全面认识的情况下，就急于编写程序.软件危机不仅没有消失，还有加剧之势。主要表现在：软件成本在计算机系统总成本中所占的比例居高不下，且逐年上升。由于微电子学技术的进步和硬件生产自动化程度不断提高，硬件成本逐年下降，性能和产量迅速提高。然而软件开发需要大量人力，软件成本随着软件规模和数量的剧增而持续上升。从美、日两国的统计数字表明，1985年度软件成本大约占总成本的90%.软件开发生产率提高的速度远远跟不上计算机应用迅速普及深入的需要，软件产品供不应求的状况使得人类不能充分利用现代计算机硬件所能提供的巨大潜力。4.试简述使用软件工程方法学，使用结构化分析、结构化设计方法开发软件的过程、方法、工具及相关知识。答： 软件工程是管理与技术的紧密结合.管理就是通过计划、组织和控制合理地配置和使用各种资源，以达到既定目标的过程.软件工程方法学包括三个要素：方法、工具和过程.其中，方法是完成软件开发的各项任务的技术方法，回答“如何做”的问题；工具是为方法的运用提供自动的或半自动的软件支撑环境；过程是为了获得高质量的软件所需要完成的一系列任务的框架，它规定了完成各项任务的工作步骤。 传统方法学：采用结构化技术来完成软件开发的各项任务，并使用适当的软件工具或软件工程环境来支持结构化技术的运用。这种方法学把软件生命周期的全过程依次划分为若干个阶段，然后顺序地逐步完成每个阶段的任务。采用这种方法学开发软件的时候，从对任务的抽象逻辑分析开始，一个阶段一个阶段地进行开发。前一个阶段任务的完成是开始进行后一个阶段工作的前提和基础，而后一阶段任务的完成通常是使前一阶段提出的解法更进一步具体化，加进了更多的实现细节。每一个阶段的开始和结束都有严格标准，对于任何两个相邻的阶段而言，前一阶段的结束标准就是后一阶段的开始标准。在每一个阶段结束之前都必须进行正式严格的技术审查和管理复审，从