04(15分)软件技术基础(包含数据结构、软件工程、数据库hqn.docx

《04(15分)软件技术基础(包含数据结构、软件工程、数据库hqn.docx》由会员分享，可在线阅读，更多相关《04(15分)软件技术基础(包含数据结构、软件工程、数据库hqn.docx（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1数数据结构构与算法法1.1 算法 算法：是是指解题题方案的的准确而而完整的的描述。 算法不等等于程序序，也不不等计算算机方法法，程序序的编制制不可能能优于算算法的设设计。 算法的基基本特征征：是一一组严谨谨地定义义运算顺顺序的规规则，每每一个规规则都是是有效的的，是明明确的，此此顺序将将在有限限的次数数下终止止。特征征包括： （1）可可行性； （2）确确定性，算算法中每每一步骤骤都必须须有明确确定义，不不充许有有模棱两两可的解解释，不不允许有有多义性性； （3）有有穷性，算算法必须须能在有有限的时时间内做做完，即即能在执执行有限限个步骤骤后终止止，包括括合理的的执行时时间的含含义； （4

2、）拥拥有足够够的情报报。 算法的基基本要素素：一是是对数据据对象的的运算和和操作；二是算算法的控控制结构构。 指令系统统：一个个计算机机系统能能执行的的所有指指令的集集合。 基本运算算和操作作包括：算术运运算、逻逻辑运算算、关系系运算、数数据传输输。 算法的控控制结构构：顺序序结构、选选择结构构、循环环结构。 算法基本本设计方方法：列列举法、归归纳法、递递推、递递归、减减斗递推推技术、回回溯法。 算法复杂杂度：算算法时间间复杂度度和算法法空间复复杂度。 算法时间间复杂度度是指执执行算法法所需要要的计算算工作量量。 算法空间间复杂度度是指执执行这个个算法所所需要的的内存空空间。 1.2 数据结结

3、构的基基本基本本概念 数据结构构研究的的三个方方面： （1）数数据集合合中各数数据元素素之间所所固有的的逻辑关关系，即即数据的的逻辑结结构； （2）在在对数据据进行处处理时，各各数据元元素在计计算机中中的存储储关系，即即数据的的存储结结构； （3）对对各种数数据结构构进行的的运算。 数据结构构是指相相互有关关联的数数据元素素的集合合。 数据的逻逻辑结构构包含： （1）表表示数据据元素的的信息； （2）表表示各数数据元素素之间的的前后件件关系。 数据的存存储结构构有顺序序、链接接、索引引等。 线性结构构条件： （1）有有且只有有一个根根结点； （2）每每一个结结点最多多有一个个前件，也也最多有有

4、一个后后件。 非线性结结构：不不满足线线性结构构条件的的数据结结构。13 线性表表及其顺顺序存储储结构 线性表由由一组数数据元素素构成，数数据元素素的位置置只取决决于自己己的序号号，元素素之间的的相对位位置是线线性的。 在复杂线线性表中中，由若若干项数数据元素素组成的的数据元元素称为为记录，而而由多个个记录构构成的线线性表又又称为文文件。 非空线性性表的结结构特征征： （1）且且只有一一个根结结点a11，它无无前件； （2）有有且只有有一个终终端结点点an，它它无后件件； （3）除除根结点点与终端端结点外外，其他他所有结结点有且且只有一一个前件件，也有有且只有有一个后后件。结结点个数数n称为为

5、线性表表的长度度，当nn=0时时，称为为空表。 线性表的的顺序存存储结构构具有以以下两个个基本特特点： （1）线线性表中中所有元元素的所所占的存存储空间间是连续续的； （2）线线性表中中各数据据元素在在存储空空间中是是按逻辑辑顺序依依次存放放的。 ai的存存储地址址为：AADR(ai)=ADDR(aa1)+(i-1)kk,，AADR(a1)为第一一个元素素的地址址，k代代表每个个元素占占的字节节数。 顺序表的的运算：插入、删删除。 （详见见14-166页） 14 栈和队队列 栈是限定定在一端端进行插插入与删删除的线线性表，允允许插入入与删除除的一端端称为栈栈顶，不不允许插插入与删删除的另另一端

6、称称为栈底底。 栈按照“先进后后出”（FIILO）或或“后进先先出”（LIIFO）组组织数据据，栈具具有记忆忆作用。用用topp表示栈栈顶位置置，用bbotttom表表示栈底底。 栈的基本本运算：（1）插插入元素素称为入入栈运算算；（22）删除除元素称称为退栈栈运算；（3）读读栈顶元元素是将将栈顶元元素赋给给一个指指定的变变量，此此时指针针无变化化。 队列是指指允许在在一端（队队尾）进进入插入入，而在在另一端端（队头头）进行行删除的的线性表表。Reear指指针指向向队尾，ffronnt指针针指向队队头。 队列是“先进行行出”（FIIFO）或或“后进后后出”（LIILO）的的线性表表。 队列运算

7、算包括（11）入队队运算：从队尾尾插入一一个元素素；（22）退队队运算：从队头头删除一一个元素素。 循环队列列：s=0表示示队列空空，s=1且ffronnt=rrearr表示队队列满 15 线性链链表 数据结构构中的每每一个结结点对应应于一个个存储单单元，这这种存储储单元称称为存储储结点，简简称结点点。 结点由两两部分组组成：（11）用于于存储数数据元素素值，称称为数据据域；（22）用于于存放指指针，称称为指针针域，用用于指向向前一个个或后一一个结点点。 在链式存存储结构构中，存存储数据据结构的的存储空空间可以以不连续续，各数数据结点点的存储储顺序与与数据元元素之间间的逻辑辑关系可可以不一一致

8、，而而数据元元素之间间的逻辑辑关系是是由指针针域来确确定的。 链式存储储方式即即可用于于表示线线性结构构，也可可用于表表示非线线性结构构。 线性链表表，HEEAD称称为头指指针，HHEADD=NUULL（或或0）称称为空表表，如果果是两指指针：左左指针（LLlinnk）指指向前件件结点，右右指针（RRlinnk）指指向后件件结点。 线性链表表的基本本运算：查找、插插入、删删除。 16 树与二二叉树 树是一种种简单的的非线性性结构，所所有元素素之间具具有明显显的层次次特性。 在树结构构中，每每一个结结点只有有一个前前件，称称为父结结点，没没有前件件的结点点只有一一个，称称为树的的根结点点，简称称

9、树的根根。每一一个结点点可以有有多个后后件，称称为该结结点的子子结点。没没有后件件的结点点称为叶叶子结点点。 在树结构构中，一一个结点点所拥有有的后件件的个数数称为该该结点的的度，所所有结点点中最大大的度称称为树的的度。树树的最大大层次称称为树的的深度。 二叉树的的特点：（1）非非空二叉叉树只有有一个根根结点；（2）每每一个结结点最多多有两棵棵子树，且且分别称称为该结结点的左左子树与与右子树树。 二叉树的的基本性性质： （1）在在二叉树树的第kk层上，最最多有22k-11(k1)个个结点； （2）深深度为mm的二叉叉树最多多有2m-1个个结点； （3）度度为0的的结点（即即叶子结结点）总总是比

10、度度为2的的结点多多一个； （4）具具有n个个结点的的二叉树树，其深深度至少少为llog22n+1,其其中llog22n表表示取llog22n的整整数部分分； （5）具具有n个个结点的的完全二二叉树的的深度为为loog2nn+11； （6）设设完全二二叉树共共有n个个结点。如如果从根根结点开开始，按按层序（每每一层从从左到右右）用自自然数11，2，.n给结点进行编号（k=1,2.n），有以下结论： 若k=1，则则该结点点为根结结点，它它没有父父结点；若k1，则则该结点点的父结结点编号号为INNT(kk/2)； 若2kkn，则则编号为为k的结结点的左左子结点点编号为为2k；否则该该结点无无左子结

11、结点（也也无右子子结点）； 若2kk+1n，则则编号为为k的结结点的右右子结点点编号为为2k+1；否否则该结结点无右右子结点点。 满二叉树树是指除除最后一一层外，每每一层上上的所有有结点有有两个子子结点，则则k层上上有2kk-1个个结点深深度为mm的满二二叉树有有2m-11个结点点。 完全二叉叉树是指指除最后后一层外外，每一一层上的的结点数数均达到到最大值值，在最最后一层层上只缺缺少右边边的若干干结点。 二叉树存存储结构构采用链链式存储储结构，对对于满二二叉树与与完全二二叉树可可以按层层序进行行顺序存存储。 二叉树的的遍历： （1）前前序遍历历（DLLR），首首先访问问根结点点，然后后遍历左左

12、子树，最最后遍历历右子树树； （2）中中序遍历历（LDDR），首首先遍历历左子树树，然后后访问根根结点，最最后遍历历右子树树； （3）后后序遍历历（LRRD）首首先遍历历左子树树，然后后访问遍遍历右子子树，最最后访问问根结点点。 17 查找技技术 顺序查找找的使用用情况： （1）线线性表为为无序表表； （2）表表采用链链式存储储结构。 二分法查查找只适适用于顺顺序存储储的有序序表，对对于长度度为n的的有序线线性表，最最坏情况况只需比比较loog2nn次。 18 排序技技术 排序是指指将一个个无序序序列整理理成按值值非递减减顺序排排列的有有序序列列。 交换类排排序法：（1）冒冒泡排序序法，需需要

13、比较较的次数数为n(n-11)/22； （22）快速速排序法法。 插入类排排序法：（1）简简单插入入排序法法，最坏坏情况需需要n(n-11)/22次比较较；（22）希尔尔排序法法，最坏坏情况需需要O(n1.5)次次比较。 选择类排排序法：（1）简简单选择择排序法法, 最坏情况况需要nn(n-1)/2次比比较；（22）堆排排序法，最最坏情况况需要OO(nllog22n)次次比较.4.2软软件工程程基础 31 软件工工程基本本概念 计算机软软件是包包括程序序、数据据及相关关文档的的完整集集合。 软件的特特点包括括： （1）软软件是一一种逻辑辑实体； （2）软软件的生生产与硬硬件不同同，它没没有明显

14、显的制作作过程； （3）软软件在运运行、使使用期间间不存在在磨损、老老化问题题； （4）软软件的开开发、运运行对计计算机系系统具有有依赖性性，受计计算机系系统的限限制，这这导致了了软件移移植的问问题； （5）软软件复杂杂性高，成成本昂贵贵； （6）软软件开发发涉及诸诸多的社社会因素素。 软件按功功能分为为应用软软件、系系统软件件、支撑撑软件（或或工具软软件）。 软件危机机主要表表现在成成本、质质量、生生产率等等问题。 软件工程程是应用用于计算算机软件件的定义义、开发发和维护护的一整整套方法法、工具具、文档档、实践践标准和和工序。 软件工程程包括33个要素素：方法法、工具具和过程程。 软件工程程

15、过程是是把软件件转化为为输出的的一组彼彼此相关关的资源源和活动动，包含含4种基基本活动动： （1）PP软件件规格说说明； （2）DD软件件开发； （3）CC软件件确认； （4）AA软件件演进。 软件周期期：软件件产品从从提出、实实现、使使用维护护到停止止使用退退役的过过程。 软件生命命周期三三个阶段段:软件件定义、软软件开发发、运行行维护，主主要活动动阶段是是： （1）可可行性研研究与计计划制定定； （2）需需求分析析； （3）软软件设计计； （4）软软件实现现； （5）软软件测试试； （6）运运行和维维护。 软件工程程的目标标和与原原则： 目标：在在给定成成本、进进度的前前提下，开开发出具具

16、有有效效性、可可靠性、可可理解性性、可维维护性、可可重用性性、可适适应性、可可移植性性、可追追踪性和和可互操操作性且且满足用用户需求求的产品品。 基本目标标：付出出较低的的开发成成本；达达到要求求的软件件功能；取得较较好的软软件性能能；开发发软件易易于移植植；需要要较低的的费用；能按时时完成开开发，及及时交付付使用。 基本原则则：抽象象、信息息隐蔽、模模块化、局局部化、确确定性、一一致性、完完备性和和可验证证性。 软件工程程的理论论和技术术性研究究的内容容主要包包括：软软件开发发技术和和软件工工程管理理。 软件开发发技术包包括：软软件开发发方法学学、开发发过程、开开发工具具和软件件工程环环境。

17、 软件工程程管理包包括：软软件管理理学、软软件工程程经济学学、软件件心理学学等内容容。 软件管理理学包括括人员组组织、进进度安排排、质量量保证、配配置管理理、项目目计划等等。 软件工程程原则包包括抽象象、信息息隐蔽、模模块化、局局部化、确确定性、一一致性、完完备性和和可验证证性。 32 结构化化分析方方法 结构化方方法的核核心和基基础是结结构化程程序设计计理论。 需求分析析方法有有（1）结结构化需需求分析析方法； （22）面向向对象的的分析的的方法。 从需求分分析建立立的模型型的特性性来分：静态分分析和动动态分析析。 结构化分分析方法法的实质质：着眼眼于数据据流，自自顶向下下，逐层层分解，建建

18、立系统统的处理理流程，以以数据流流图和数数据字典典为主要要工具,建立系系统的逻逻辑模型型。 结构化分分析的常常用工具具 （1）数数据流图图； （22）数据据字典； （3）判判定树； （44）判定定表。 数据流图图：描述述数据处处理过程程的工具具，是需需求理解解的逻辑辑模型的的图形表表示，它它直接支支持系统统功能建建模。 数据字典典：对所所有与系系统相关关的数据据元素的的一个有有组织的的列表，以以及精确确的、严严格的定定义，使使得用户户和系统统分析员员对于输输入、输输出、存存储成分分和中间间计算结结果有共共同的理理解。 判定树：从问题题定义的的文字描描述中分分清哪些些是判定定的条件件，哪些些是判

19、定定的结论论，根据据描述材材料中的的连接词词找出判判定条件件之间的的从属关关系、并并列关系系、选择择关系，根根据它们们构造判判定树。 判定表：与判定定树相似似，当数数据流图图中的加加工要依依赖于多多个逻辑辑条件的的取值，即即完成该该加工的的一组动动作是由由于某一一组条件件取值的的组合而而引发的的，使用用判定表表描述比比较适宜宜。 数据字典典是结构构化分析析的核心心。 软件需求求规格说说明书的的特点： （1）正正确性； （2）无无岐义性性； （3）完完整性； （4）可可验证性性； （5）一一致性； （6）可可理解性性； （7）可可追踪性性33 结构化化设计方方法 软件设计计的基本本目标是是用比较

20、较抽象概概括的方方式确定定目标系系统如何何完成预预定的任任务，软软件设计计是确定定系统的的物理模模型。 软件设计计是开发发阶段最最重要的的步骤，是是将需求求准确地地转化为为完整的的软件产产品或系系统的唯唯一途径径。 从技术观观点来看看，软件件设计包包括软件件结构设设计、数数据设计计、接口口设计、过过程设计计。 结构设计计：定义义软件系系统各主主要部件件之间的的关系。 数据设计计：将分分析时创创建的模模型转化化为数据据结构的的定义。 接口设计计：描述述软件内内部、软软件和协协作系统统之间以以及软件件与人之之间如何何通信。 过程设计计：把系系统结构构部件转转换成软软件的过过程描述述。 从工程管管理

21、角度度来看：概要设设计和详详细设计计。 软件设计计的一般般过程：软件设设计是一一个迭代代的过程程；先进进行高层层次的结结构设计计；后进进行低层层次的过过程设计计；穿插插进行数数据设计计和接口口设计。 衡量软件件模块独独立性使使用耦合合性和内内聚性两两个定性性的度量量标准。 在程序结结构中各各模块的的内聚性性越强，则则耦合性性越弱。优优秀软件件应高内内聚，低低耦合。 软件概要要设计的的基本任任务是： （1）设设计软件件系统结结构； （22）数据据结构及及数据库库设计； （3）编编写概要要设计文文档； （44）概要要设计文文档评审审。 模块用一一个矩形形表示，箭箭头表示示模块间间的调用用关系。 在

22、结构图图中还可可以用带带注释的的箭头表表示模块块调用过过程中来来回传递递的信息息。还可可用带实实心圆的的箭头表表示传递递的是控控制信息息，空心心圆箭心心表示传传递的是是数据。 结构图的的基本形形式：基基本形式式、顺序序形式、重重复形式式、选择择形式。 结构图有有四种模模块类型型：传入入模块、传传出模块块、变换换模块和和协调模模块。 典型的数数据流类类型有两两种：变变换型和和事务型型。 变换型系系统结构构图由输输入、中中心变换换、输出出三部分分组成。 事务型数数据流的的特点是是：接受受一项事事务，根根据事务务处理的的特点和和性质，选选择分派派一个适适当的处处理单元元，然后后给出结结果。 详细设计

23、计：是为为软件结结构图中中的每一一个模块块确定实实现算法法和局部部数据结结构，用用某种选选定的表表达工具具表示算算法和数数据结构构的细节节。 常见的过过程设计计工具有有：图形形工具（程程序流程程图）、表表格工具具（判定定表）、语语言工具具（PDDL）。 34 软件测测试 软件测试试定义：使用人人工或自自动手段段来运行行或测定定某个系系统的过过程，其其目的在在于检验验它是否否满足规规定的需需求或是是弄清预预期结果果与实际际结果之之间的差差别。 软件测试试的目的的：发现现错误而而执行程程序的过过程。 软件测试试方法：静态测测试和动动态测试试。 静态测试试包括代代码检查查、静态态结构分分析、代代码质

24、量量度量。不不实际运运行软件件，主要要通过人人工进行行。 动态测试试：是基基本计算算机的测测试，主主要包括括白盒测测试方法法和黑盒盒测试方方法。 白盒测试试：在程程序内部部进行，主主要用于于完成软软件内部部操作的的验证。主主要方法法有逻辑辑覆盖、基基本基路路径测试试。 黑盒测试试：主要要诊断功功能不对对或遗漏漏、界面面错误、数数据结构构或外部部数据库库访问错错误、性性能错误误、初始始化和终终止条件件错，用用于软件件确认。主主要方法法有等价价类划分分法、边边界值分分析法、错错误推测测法、因因果图等等。 软件测试试过程一一般按44个步骤骤进行：单元测测试、集集成测试试、验收收测试（确确认测试试）和

25、系系统测试试。 35 程序的的调试 程序调试试的任务务是诊断断和改正正程序中中的错误误，主要要在开发发阶段进进行。 程序调试试的基本本步骤： （1）错错误定位位； （2）修修改设计计和代码码，以排排除错误误； （3）进进行回归归测试，防防止引进进新的错错误。 软件调试试可分表表静态调调试和动动态调试试。静态态调试主主要是指指通过人人的思维维来分析析源程序序代码和和排错，是是主要的的设计手手段，而而动态调调试是辅辅助静态态调试。主主要调试试方法有有： （1）强强行排错错法； （2）回回溯法； （3）原原因排除除法4.3数数据库基基础知识识41 数据库库系统的的基本概概念 数据：实实际上就就是描述

26、述事物的的符号记记录。 数据的特特点：有有一定的的结构，有有型与值值之分，如如整型、实实型、字字符型等等。而数数据的值值给出了了符合定定型的值值，如整整型值115。 数据库：是数据据的集合合，具有有统一的的结构形形式并存存放于统统一的存存储介质质内，是是多种应应用数据据的集成成，并可可被各个个应用程程序共享享。 数据库存存放数据据是按数数据所提提供的数数据模式式存放的的，具有有集成与与共享的的特点。 数据库管管理系统统：一种种系统软软件，负负责数据据库中的的数据组组织、数数据操纵纵、数据据维护、控控制及保保护和数数据服务务等，是是数据库库的核心心。 数据库管管理系统统功能： （1）数数据模式式

27、定义：即为数数据库构构建其数数据框架架； （2）数数据存取取的物理理构建：为数据据模式的的物理存存取与构构建提供供有效的的存取方方法与手手段； （3）数数据操纵纵：为用用户使用用数据库库的数据据提供方方便，如如查询、插插入、修修改、删删除等以以及简单单的算术术运算及及统计； （4）数数据的完完整性、安安生性定定义与检检查； （5）数数据库的的并发控控制与故故障恢复复； （6）数数据的服服务：如如拷贝、转转存、重重组、性性能监测测、分析析等。 为完成以以上六个个功能，数数据库管管理系统统提供以以下的数数据语言言： （1）数数据定义义语言：负责数数据的模模式定义义与数据据的物理理存取构构建； （2

28、）数数据操纵纵语言：负责数数据的操操纵，如如查询与与增、删删、改等等； （3）数数据控制制语言：负责数数据完整整性、安安全性的的定义与与检查以以及并发发控制、故故障恢复复等。 数据语言言按其使使用方式式具有两两种结构构形式：交互式式命令(又称自自含型或或自主型型语言)宿主型型语言（一一般可嵌嵌入某些些宿主语语言中）。 数据库管管理员：对数据据库进行行规划、设设计、维维护、监监视等的的专业管管理人员员。 数据库系系统：由由数据库库（数据据）、数数据库管管理系统统（软件件）、数数据库管管理员（人人员）、硬硬件平台台（硬件件）、软软件平台台（软件件）五个个部分构构成的运运行实体体。 数据库应应用系统

29、统：由数数据库系系统、应应用软件件及应用用界面三三者组成成。 文件系统统阶段：提供了了简单的的数据共共享与数数据管理理能力，但但是它无无法提供供完整的的、统一一的、管管理和数数据共享享的能力力。 层次数据据库与网网状数据据库系统统阶段 ：为统统一与共共享数据据提供了了有力支支撑。 关系数据据库系统统阶段 数据库系系统的基基本特点点：数据据的集成成性 、数数据的高高共享性性与低冗冗余性 、数据据独立性性（物理理独立性性与逻辑辑独立性性）、数数据统一一管理与与控制。 数据库系系统的三三级模式式： （1）概概念模式式：数据据库系统统中全局局数据逻逻辑结构构的描述述，全体体用户公公共数据据视图； （2

30、）外外模式：也称子子模式与与用户模模式。是是用户的的数据视视图，也也就是用用户所见见到的数数据模式式； （3）内内模式：又称物物理模式式，它给给出了数数据库物物理存储储结构与与物理存存取方法法。 数据库系系统的两两级映射射： （1）概概念模式式到内模模式的映映射； （2）外外模式到到概念模模式的映映射。 4.2 数据模模型 数据模型型的概念念：是数数据特征征的抽象象，从抽抽象层次次上描述述了系统统的静态态特征、动动态行为为和约束束条件，为为数据库库系统的的信息表表与操作作提供一一个抽象象的框架架。描述述了数据据结构、数数据操作作及数据据约束。 E-R模模型的基基本概念念 （1）实实体：现现实世

31、界界中的事事物； （2）属属性：事事物的特特性； （3）联联系：现现实世界界中事物物间的关关系。实实体集的的关系有有一对一一、一对对多、多多对多的的联系。 E-R模模型三个个基本概概念之间间的联接接关系：实体是是概念世世界中的的基本单单位，属属性有属属性域，每每个实体体可取属属性域内内的值。一一个实体体的所有有属性值值叫元组组。 E-R模模型的图图示法：（1）实实体集表表示法； （22）属性性表法； （33）联系系表示法法。 层次模型型的基本本结构是是树形结结构，具具有以下下特点： （1）每每棵树有有且仅有有一个无无双亲结结点，称称为根； （2）树树中除根根外所有有结点有有且仅有有一个双双亲。

32、 从图论上上看，网网状模型型是一个个不加任任何条件件限制的的无向图图。 关系模型型采用二二维表来来表示，简简称表，由由表框架架及表的的元组组组成。一一个二维维表就是是一个关关系。 在二维表表中凡能能唯一标标识元组组的最小小属性称称为键或或码。从从所有侯侯选健中中选取一一个作为为用户使使用的键键称主键键。表AA中的某某属性是是某表BB的键，则则称该属属性集为为A的外外键或外外码。 关系中的的数据约约束： （1）实实体完整整性约束束：约束束关系的的主键中中属性值值不能为为空值； （2）参参照完全全性约束束：是关关系之间间的基本本约束； （3）用用户定义义的完整整性约束束：它反反映了具具体应用用中数

33、据据的语义义要求。 4.3关关系代数数 关系数据据库系统统的特点点之一是是它建立立在数据据理论的的基础之之上，有有很多数数据理论论可以表表示关系系模型的的数据操操作，其其中最为为著名的的是关系系代数与与关系演演算。 关系模型型的基本本运算： （1）插插入 （22）删除除 (33)修改改 （44）查询询（包括括投影、选选择、笛笛卡尔积积运算） 4.4 数据库库设计与与管理 数据库设设计是数数据应用用的核心心。 数据库设设计的两两种方法法： （1）面面向数据据：以信信息需求求为主，兼兼顾处理理需求； （2）面面向过程程：以处处理需求求为主，兼兼顾信息息需求。 数据库的的生命周周期：需需求分析析阶段

34、、概概念设计计阶段、逻逻辑设计计阶段、物物理设计计阶段、编编码阶段段、测试试阶段、运运行阶段段、进一一步修改改阶段。 需求分析析常用结结构析方方法和面面向对象象的方法法。结构构化分析析（简称称SA）方方法用自自顶向下下、逐层层分解的的方式分分析系统统。用数数据流图图表达数数据和处处理过程程的关系系。对数数据库设设计来讲讲，数据据字典是是进行详详细的数数据收集集和数据据分析所所获得的的主要结结果。 数据字典典是各类类数据描描述的集集合，包包括5个个部分：数据项项、数据据结构、数数据流（可可以是数数据项，也也可以是是数据结结构）、数数据存储储、处理理过程。 数据库概概念设计计的目的的是分析析数据内

35、内在语义义关系。设设计的方方法有两两种 （1）集集中式模模式设计计法（适适用于小小型或并并不复杂杂的单位位或部门门）； （2）视视图集成成设计法法。 设计方法法：E-R模型型与视图图集成。 视图设计计一般有有三种设设计次序序：自顶顶向下、由由底向上上、由内内向外。 视图集成成的几种种冲突：命名冲冲突、概概念冲突突、域冲冲突、约约束冲突突。 关系视图图设计：关系视视图的设设计又称称外模式式设计。 关系视图图的主要要作用： （1）提提供数据据逻辑独独立性； （2）能能适应用用户对数数据的不不同需求求； （3）有有一定数数据保密密功能。 数据库的的物理设设计主要要目标是是对数据据内部物物理结构构作调

36、整整并选择择合理的的存取路路径，以以提高数数据库访访问速度度有效利利用存储储空间。一一般RDDBMSS中留给给用户参参与物理理设计的的内容大大致有索索引设计计、集成成簇设计计和分区区设计。 数据库管管理的内内容： （1）数数据库的的建立； （2）数数据库的的调整； （3）数数据库的的重组； （4）数数据库安安全性与与完整性性控制； （5）数数据库的的故障恢恢复； （6）数数据库监监控。：计算机机2级公公共基础础1200题公共基础础1200题详解解(1) 下面叙叙述正确确的是_。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指

37、算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对（1）答案C考点程序设计基础评析时间复杂度：在运行算法时所耗费的时间为f(n)（即 n的函数）。空间复杂度：实现算法所占用的空间为g(n)（也为n的函数）。A应为有关。(2) 以下数据结构中不属于线性数据结构的是_。A. 队列B. 线性表C. 二叉树D. 栈（2）答案C考点数据结构与算法评析一棵二叉树的一个结点下面可以有2个子结点，故不是线性结构（通俗地理解，看是否能排成条直线）。A是先进先出的线性表；B是宏观概念，包括顺序表、链表、堆栈、队列；D是先进后出的线性表 (3) 在一棵二叉树上第5层的结点数最多是_。A. 8B. 16C.

38、32D. 15（3）答案B考点数据结构与算法评析依次从上到下，可得出：第1层结点数为1；第2层结点数为2*1=2；第3层结点数为2*2=4；第n层结点数为2的n-1次幂，如图所示(4) 下面描述中，符合结构化程序设计风格的是_。A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto语句（4）答案A考点程序设计基础评析B没这规定，模块之间的可以通过多个接口来耦合C结构化程序设计提倡程序的可读性（可理解性），超过程序执行效率的要求D结构化程序设计限制goto语句的使用，因为goto语句的功能可以用三

39、种基本的控制结构来代替，但也不是绝对不能用，只是限制使用（少用）。(5) 下面概念中，不属于面向对象方法的是_。A. 对象B. 继承C. 类D. 过程调用（5）答案D考点软件工程基础评析面向对象=对象+类+继承+通过消息的通信对象：一组属性及其上的操作的封装体类：一组有相同属性和操作的对象的集合继承：一个类为另一个类上的扩充的方式，子类继承父类，主要目的是代码复用消息：对象间通信的手段D是结构化程序设计或过程式（函数式）语言中的，一般的面向对象程序设计语言兼容这种方式，但不是其特征，故最佳选项为D(6) 在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是_。A. 可行性分析B.

40、 需求分析C. 详细设计D. 程序编码 （6）答案B考点软件工程基础评析分析员对用户的要求作出分析，并画出数据流程图，该图通俗易懂，不涉及到如何在计算机上实现，这是需求分析阶段。软件工程中的瀑布模型：问题定义，可行性研究，需求分析，概要设计，详细设计，编码，测试，运行和维护相关链点：层次图和HIPO图是概要设计中的工具图；程序流程图、N-S图、问题分析PAD图、设计程序语言PDL是详细设计中的工具图(7) 在软件开发中，下面任务不属于设计阶段的是_。A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型（7）答案D考点软件工程基础评析A、B为概要设计中的，C为详

41、细设计中的，D为分析阶段中的(8) 数据库系统的核心是_。A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库（8）答案B考点数据库设计基础评析数据库管理系统DBMS是数据库系统的核心，上层与用户打交道，底层与操作系统接口注意点：数据库系统与数据库管理系统的区别前者指的一整套业务系统，包括用户、应用程序、DBMS及操作系统的支持(9) 下列叙述中正确的是_。A. 数据库是一个独立的系统，不需要操作系统的支持B. 数据库设计是指设计数据库管理系统C. 数据库技术的根本目标是要解决数据共享的问题D. 数据库系统中，数据的物理结构必须与逻辑结构一致 （9）答案C考点数据库设计基础评析晕倒，数

42、据库管理系统是人人都可设计的吗？那SYBASE和ORACLE等不都没饭吃了？普通人的数据库设计就是在DBMS的支持下设计几张表格，命几个名而已；D也错了的，数据库具有物理独立性和逻辑独立性，比如QQ是一个完整的数据库系统，我们使用的只是客户端应用程序，其数据库在腾讯的服务器上，物理独立性呢指的是数据库的底层结构改变了，而QQ的客户端不用变，对应地，逻辑独立性是指QQ的客户端改变了，数指据库的结构不用变了，否则，这么多QQ版本，那腾讯的服务器不是乱了套？(10) 下列模式中，能够给出数据库物理存储结构与物理存取方法的是_。A. 内模式B. 外模式C. 概念模式D. 逻辑模式（10）答案A考点数据

43、库设计基础评析通过前些题可知道，数据库的物理结构最底层，即对应内模式，对应的模式映像为内模式/模式（概念模式映像），逻辑独立性则对应于模式/外模式映像(11) 算法的时间复杂度是指_。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数（11）答案C考点数据结构与算法评析算法的复杂度分时间复杂度和空间复杂度。时间复杂度：在运行算法时所耗费的时间为f(n)(即 n的函数)。空间复杂度：实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n)和O(g(n)为该算法的复杂度。简单的例子比如常见的顺序结构时间复杂度为O(1),1层循

44、环里面次数为n，时间复杂度就是O(n),2层循环for i=1 to n,for j=1 to n算法时间复杂度为O(n2)（里面为n的平方），复杂度主要用于算法的效率比较与优化，比如排序，查找(12) 下列叙述中正确的是_。A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构 （12）答案A考点数据结构与算法评析一棵二叉树的一个结点下面可以有2个子结点，故不是线性结构（通俗地理解，看是否能排成条直线）。此题与（2）题类似(13) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。A. 349B. 350C. 255D. 351（13

45、）答案B考点数据结构与算法评析完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。比如图：完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1比如图：此题的其实是一棵满二叉树，我们根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。(14) 结构化程序设计主要强调的是_。A. 程序的规模B. 程序的易读性C. 程序的执行效率D. 程序的可移植性（14）答案B考点程序设计基础评析又是结构化的问题，何谓结构化？简单地比如：VB: If.End IfC: if.