数据结构软件工程数据库2有答案

二级考试基础辅导讲义,数据结构与算法软件工程数据库基础程序设计基础,本节要点,算法,算法：是指解题方案的准确而完整的描述。算法的基本特征：（1）可行性（2）确定性（3）有穷性算法复杂度：主要包括时间复杂度和空间复杂度（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。（2）算法空间复杂度是指执行这个算法所需要的临时工作单元数。,（1）算法的时间复杂度是指（）A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数（2）算法的空间复杂度是指（）。A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数（3）算法的有穷性是指（）A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用,数据结构,数据结构：是指相互有关联的数据元素的集合。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构分类：逻辑结构:数据元素之间的逻辑关系，即人对数据的理解，而进行抽象的模型存储结构(物理结构)数据元素在计算机中的存储方法，即计算机对数据的理解，逻辑结构在计算机语言中的映射。(座位是物理结构，学号是逻辑结构),逻辑结构：线性（线性表、栈、队列）非线性（树、二叉树、图）物理结构顺序链式索引,如何区分线性和非线性？线性一个数据节点只有一个前件和一个后件非线性一个数据节点有多个前件或多个后件,一种逻辑结构可通过多种物理结构来实现（顺序）线性表如：数组方便查找（折半查找）(链式)线性表优点：修改效率高（插入、删除元素）,地址域,数据域,head,单链表,prev,next,head,左指针数据域右指针,双向链表,循环链表,（1）下列叙述中正确的是A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构（2）下列叙述中正确的是A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对（3）下列叙述中正确的是A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间,入栈,Top栈顶,Bottom栈底不动,入栈：5，3，7出栈：7，3，5特点：先进后出（通常用顺序结构存储也可以用链式存储）,入栈出栈都在栈顶。栈底不动,栈：栈是只能在一端进行插入与删除运算的线性表。,（1）下列关于栈的叙述正确的是A）栈按“先进先出”组织数据B)栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据（2）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA（3）下列叙述中正确的是A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D）上述三种说法都不对,front,入队（增）：rear移动出队（删）：front移动,5,3,7,队列：,头指针,尾指针,队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。,rear,front,rear,循环队列元素个数:若rearfront,则为rear-front若rearfront,则为rear+队列容量-front,循环队列：,a,c,b,d,rear,front,5,4,3,2,1,9,7,8,6,rear,front,（1）设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有个元素。（2）设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有个元素。（3）对于循环队列，下列叙述中正确的是（）。A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针可以大于队尾指针，也可以小于队尾指针（4）下列叙述中正确的是A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定,24,15,树：,是一种简单的非线性结构。,所有数据元素之间的关系具有明显的层次特性。,结点的度：一个结点所拥有的后件的个数（下级分叉）树的度：所有结点中最大的度树的深度：树的最大层次,叶子结点,父结点,子结点,二叉树：,1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。3）二叉树的度可以为0、1或2。,二叉树的基本性质：性质1在二叉树的第k层上，最多有2k-1个结点。性质2深度为m的二叉树最多有个2m-1个结点。性质3在任意一棵二叉树中，度为0的结点个数=度为2的结点个数+1,设度为0的节点数a0，度为1的节点数a1，度为2的节点数a2，总节点数n，则：1）已知a0、a1，可求出n（已知a2、a1，也可求出n）2）已知n、a0，可求出a1、a23）已知n、a1，可求出a0、a2,如：二叉树中度为0的结点60个，度为1的结点59个求总结点数,60+59+59=178,满二叉树：共有2n-1个结点（n为深度）,满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,二叉树的遍历,前序遍历：DLR中序遍历：LDR后序遍历：LRD,L在R之前,前序：ABCDEFGH中序：CBDAGFHE后序：CDBGHFEA,（1）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）A）3B）4C）6D）7（2）某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为A)n+1B)n-1C)2nD)n/2（3）在深度为7的满二叉树中，叶子结点的个数为A)32B)31C)64D)63（4）对下列二叉树进行前序遍历的结果是A)DYBEAFCZXB)YDEBFZXCAC)ABDYECFXZD)ABCDEFXYZ,软件工程基础,1,软件=程序+数据+文档,2软件危机,成本、质量、生产率,3,软件工程:将工程化原则运用到软件开发过程,4.软件生命周期,软件定义、软件开发、软件运行维护三个阶段,软件定义阶段：提出问题（做什么）,可行性研究可行性分析报告,需求分析软件需求规格说明书结构化分析方法工具：-数据流图（DFD）：以图形的方式描绘数据在系统中流动和处理的过程。-数据字典（DD)：对数据流图中出现的被命名的图形元素的确切解释。,数据流图,软件开发阶段“怎么做”,1、软件设计,总体设计：抽象、模块化、信息隐蔽和模块独立性详细设计图形工具：程序流程图、N-S(方盒图)、PAD(问题分析图)、HIPO（层次图+输入/处理/输出图）表格工具：判定表语言工具：PDL（伪码）,2、软件编码编程（根据流程图编写程序）,测试步骤：单元测试、集成测试、确认测试、系统测试,软件测试的目的：尽可能地多发现程序中的错误程序的调试程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行，调试程序应该由编制源程序的程序员来完成。程序调试的基本步骤：（1）错误定位；（2）纠正错误；（3）回归测试。注意与软件测试区分:程序调试的任务是诊断和改正程序中的错误。软件测试的目的：尽可能地多发现程序中的错误，不能也不可能证明程序没有错误。,练习题：（1）下面描述中，不属于软件危机表现的是A）软件过程不规范B）软件开发生产率低C）软件质量难以控制D）软件成本不断提高（2）软件生命周期是指A）软件产品从提出、实现、使用维护到停止使用退役的过程B）软件从需求分析、设计、实现到测试完成的过程C）软件的开发过程D）软件的运行维护过程（3）在软件开发中，需求分析阶段产生的主要文档是A）软件集成测试计划B）软件详细设计说明书C)用户手册D）软件需求规格说明书（4）软件测试的目的是A）评估软件可靠性B）发现并改正程序中的错误C）改正程序中的错误D）发现程序中的错误（5）软件(程序)调试的任务是A)诊断和改正程序中的错误B)尽可能多地发现程序中的错误C)发现并改正程序中的所有错误D)确定程序中错误的性质,(6)数据流程图(DFD图)是A)软件概要设计的工具B)软件详细设计的工具C)结构化方法的需求分析工具D)面向对象方法的需求分析工具(7)软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于A)定义阶段B)开发阶段C)维护阶段D)上述三个阶段(8)软件详细设计产生的图如下：该图是（）A）N-S图B）PAD图C）程序流程图D）E-R图,（9）下面叙述中错误的是A）软件测试的目的是发现错误并改正错误B）对被调试的程序进行“错误定位”是程序调试的必要步骤C）程序调试通常也称为DebugD）软件测试应严格执行测试计划，排除测试的随意性（10）在软件开发中，需求分析阶段可以使用的工具是A）N-S图B）DFD图C）PAD图（问题分析图）D）程序流程图（11）软件是指A)程序B)程序和文档C)算法加数据结构D)程序、数据与相关文档的完整集合（12）从工程管理角度，软件设计一般分为两步完成，它们是A)概要设计与详细设计B)数据设计与接口设计C)软件结构设计与数据设计D)过程设计与数据设计（13）下列叙述中正确的是A)软件测试的主要目的是发现程序中的错误B)软件测试的主要目的是确定程序中错误的位置C)为了提高软件测试的效率，最好由程序编制者自己来完成软件测试的工作D)软件测试是证明软件没有错误,数据库基础,数据库系统,应用程序,数据库管理系统,VB,VC+,PowerBuilder,Delphi,ACCESS,SQLSERVER,ORACLE,FOXPRO,SQL命令,数据库引挚,数据库,IE,HTM、ASP,客户机,服务器,SQL命令,数据库,发出请求,响应请求,数据,数据管理技术的三个发展阶段,人工管理阶段文件管理阶段数据库系统阶段,.人工管理阶段,时间：20世纪50年代中期以前硬件：只有卡片、纸带、磁带等存储设备软件：没有操作系统，没有进行数据管理的软件应用：以科学计算为目的特点：程序和数据放在一起数据不能共享特征图,人工管理阶段数据管理示例,例：两个C语言程序，分别求10个数据之和和最大值。程序与数据放在一起，数据没有能够共享,.文件系统阶段,时间：20世纪60年代中期硬件：磁带、磁盘等大容量存储设备软件：有了操作系统应用：不仅用于科学计算，还用于数据管理特点：程序与数据分离数据有一定的独立性实现了以文件为单位的数据共享特征图,数据文件,文件管理系统,数据文件n,应用程序,应用程序,应用程序n,数据文件2,文件系统阶段数据管理示例,上例用文件实现,3.数据库系统阶段,时间：20世纪60年代后期硬件：出现了大容量且价格低廉的磁盘软件：有了数据库管理系统DBMS应用：各个方面特点：数据结构化数据共享性高，冗余小数据独立性高数据由DBMS统一管理控制为用户提供了友好的接口特征图,数据库系统阶段数据管理示例,解决了数据的独立性问题，实现数据的统一管理，达到数据共享的目的,求和：SELECTMax(Num)FROMData求最大值：SELECTAvg(Num)FROMData,学生成绩表（有冗余）,学生基本情况表,数据冗余,学生成绩表,数据库设计阶段,需求分析概念设计概念模型（E-R图）逻辑设计数据模型（层次模型、网状模型、关系模型）物理设计,数据库的三层模式,外模式（子模式、用户模式）模式（概念模式、逻辑模式）内模式（物理模式）,外模式,模式,内模式,物理独立性,逻辑独立性,概念模型,实体联系图（Entity-Relation图）直接从现实世界中抽象出实体类型及实体间的联系用E-R图来描述E-R图的主要成分实体属性联系,E-R图,Course,CourseNo,CourseName,Teacher,StudentCourse,Student,Age,StudentNo,Dept,StudentName,Score,实体联系,数据模型,层次模型网状模型关系模型,层次模型,网状模型,网状模型,网状模型,关系模型,（1）关系一个关系就是一张二维表，每个关系有一个关系名。（2）元组二维表的每一行在关系中称为元组。在VFP中，一个元组对应表中一个记录。（3）属性二维表的每一列在关系中称为属性，每个属性都有一个属性名。每个属性都有属性名，数据类型，长度。（4）域：属性的取值范围称为域。（5）关键字关系中能唯一区分不同元组（记录）的属性或属性组合，称为该关系的一个关键字。单个属性组成的关键字称为单关键字，多个属性组合的关键字称为组合关键字。（关键字的属性值不能取“空值”）当一个数据表有多个关键字时，可从中选出一个作为主关键字（或主键）。,关系模型,Students表,记录,属性名(字段名),属性值(字段值),关键字唯一确定一条记录,关系（二维表）,值域：男，女,关系必须规范化,工资表（不满足关系模型要求）,工资表（满足关系模型要求）,第一范式（1NF）：分量（字段、属性）不可再分,SQL(结构化查询语言)概述,练习题：（1）负责数据库中查询操作的数据库语言是A）数据定义语言B）数据管理语言C）数据操纵语言D）数据控制语言（2）一个教师可讲授多门课程，一门课程可由多个教师讲授。则实体教师和课程间的联系是A）1：1联系B）1：m联系C)m：1联系D)m：n联系（3）层次型、网状型和关系型数据库划分原则是A）记录长度一B）文件的大小C）联系的复杂程度D）数据之间的联系方式（4）数据库管理系统中负责数据模式定义的语言是A)数据定义语言B)数据管理语言C)数据操纵语言D)数据控制语言（5）在学生管理的关系数据库中，存取一个学生信息的数据单位是A)文件B)数据库C)字段D)记录（6）数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的A)需求分析阶段B)逻辑设计阶段C)概念设计阶段D)物理设计阶段,（7）数据库管理系统是（）。A）操作系统的一部分B）在操作系统支持下的系统软件C）一种编译系统D）一种操作系统（8）在E-R图中，用来表示实体联系的图形是（）。A）椭圆形B）矩形C）菱形D）三角形（9）数据库应用系统中的核心问题是A）数据库设计B）数据库系统设计C）数据库维护D）数据库管理员培训（10）数据库(DB)、数据库系统（DBS）和数据库管理系统（DBMS）三者之间的关系是A）DBS包括DB和DBMSB）DBMS包括DB和DBSC）DB包括DBS和DBMSD）DBS就是DB，也就是DBMS,（11）在数据管理技术发展的三个阶段中，数据共享最好的是A）人工管理阶段B）文件系统阶段C）数据库系统阶段D）三个阶段相同（12）在下列关系运算中，不改变关系表中的属性个数但能减少元组个数的是A)并B)交C)投影D)笛卡儿乘积（13）下列叙述中错误的是A)在数据库系统中，数据的物理结构必须与逻辑结构一致B)数据库技术的根本目标是要解决数据的共享问题C)数据库设计是指在已有数据库管理系统的基础上建立数据库D)数据库系统需要操作系统的支持（14）数据库设计的根本目标是要解决A）数据共享问题B）数据安全问题C）大量数据存储问题D）简化数据维护,SQL与关系代数,集合论和关系代数是SQL的理论基础关系代数选择投影连接除法,关系代数集合运算并、交、差,R,RS,RS,S,RS,并和交都不会改变属性的个数,并会增加元组的个数,而交会减少元组的个数,关系代数集合运算笛卡儿积,R,S,RS,笛卡尔积既会增加属性个数,又会增加元组个数,关系代数集合运算除,R,S,R/S,在关系R中寻找属性A和B的值同时满足关系S中属性A和B的所有元组的元组。,关系代数选择、投影,R,选择,投影,投影运算会减少表中属性个数,但不改变元组个数,关系代数自然连接,R,S,R,S,关系代数自然连接,R,S,R,S,关系代数外部连接,R,S,R,S,左连接,R,S,右连接,关系代数外部连接,R,S,R,S,全连接,练习题：（1）有三个关系R、S和T如下：则由关系R和S得到关系T的操作是A)自然连接B)交C)除D)并（2）有三个关系R、S和T如下：则由关系R和S得到关系T的操作是A）自然连接B）交C）投影D）并,（3）有两个关系R和T如下：则由关系R得到关系T的操作是A)选择B)投影C)交D)并（4）有三个关系R，S和T如下：其中关系T由关系R和S通过某种操作得到，该操作为（）。A）选择B）投影C）交D）并,（5）有三个关系R、S和T如下：由关系R和S通过运算得到关系T，则所使用的运算为A）笛卡儿积B）交C）并D）自然连接,（6）有三个关系R，S和T如下：由关系R和S通过运