还剩24页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
计算机考试公共基础知识重点笔记完整版第1章数据结构与算法
1.1算法的复杂度
1.算法的基本概念运用计算机算法为计算机解题的过程事实上是在实行某种算法1算法的基本特性算法一般具有4个基本特性可行性、拟定性、有穷性、拥有足够的情报2算法的基本运算和操作算法的基本运算和操作涉及算术运算、逻辑运算、关系运算、数据传输3算法的3种基本控制结构算法的3种基本控制结构是顺序结构、选择结构、循环结构4算法基本设计方法算法基本设计方法列举法、归纳法、递推、递归、减半递推技术、回溯法5指令系统所谓指令系统指的是一个计算机系统能执行的所有指令的集合
2.算法复杂度算法复杂度涉及时间复杂度和空间复杂度注意两者的区别,无混淆,见表1-1表1-1算法复杂性名称描述时间复杂度执行算法所需要的计算工作量空间复杂度执行这个算法所需要的内存空间
1.2数据结构
1.
2.1逻辑结构和存储结构
1.数据结构的基本概念1数据结构排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序
2.插入类排序法
①简朴插入排序法,最坏情况需要nn-l/2次比较;
②希尔排序法,最坏情况需要0nL5次比较
3.选择类排序法
①简朴选择排序法,最坏情况需要nn-l/2次比较;
②堆排序法,最坏情况需要Onlog2n次比较相比以上几种除希尔排序法外,堆排序法的时间复杂度最小第2章程序设计基础
2.1程序设计的方法与风格养成良好的程序设计风格,重要考虑下述因素1源程序文档化
①符号名的命名符号名的命名应具有一定的实际含义,以便于对程序功能的理解;
②程序注释在源程序中添加对的的注释可帮助人们理解程序程序注释可分为序言性注释和功能性注释语句结构清楚第
一、效率第二;
③视觉组织通过在程序中添加一些空格、空行和缩进等,使人们在视觉上对程序的结构一目了然2数据说明的方法为使程序中的数据说明易于理解和维护,可采用下列数据说明的风格,见表2-1表2-1数据说明风格数据说明风格具体说明顺序应规范化使数据说明顺序固定,使数据的属性容易查找,也有助于测试、排错和维护变量安排有序化当多个变量出现在同一个说明语句中时,变量名应按字母顺序排序,以便于查找使用注释在定义一个复杂的数据结构时,应通过注解来说明该数据结构的特点3语句的结构程序语句的结构程序应当简朴易懂,语句构造应当简朴直接4输入和输出输入输出比较简朴,这里就不作介绍
2.2结构化程序设计
1.结构化程序设计的原则结构化程序设计方法引入了工程思想和结构化思想,使大型软件的开发和编程得到了极大的改善结构化程序设计方法的重要原则为自顶向下、逐步求精、模块化和限制使用goto语句
①自顶向上先考虑整体,再考虑细节;先考虑全局目的,再考虑局部目的;
②逐步求精对复杂问题应设计一些子目的作为过渡,逐步细化;
③模块化把程序要解决的总目的分解为分目的,再进一步分解为具体的小目的,把每个小目的称为一个模块限制使用goto语句在程序开发过程中要限制使用goto语句
2.结构化程序的基本结构结构化程序的基本结构有三种类型顺序结构、选择结构和循环结构1顺序结构是最基本、最普通的结构形式,按照程序中的语句行的先后顺序逐条执行;2选择结构又称为分支结构,它涉及简朴选择和多分支选择结构;
③循环结构根据给定的条件,判断是否要反复执行某一相同的或类似的程序段循环结构相应两类循环语句先判断后执行的循环体称为当型循环结构;先执行循环体后判断的称为直到型循环结构
2.3面向对象方法面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素
1.对象通常把对象的操作也称为方法或服务属性即对象所包含的信息,它在设计对象时拟定,一般只能通过执行对象的操作来改变属性值应当指的是纯粹的数据值,而不能指对象操作描述了对象执行的功能,若通过信息的传递,还可认为其他对象使用对象具有如下特性标记惟一性、分类性、多态性、封装性、模块独立性
2.类和实例类是具有共同属性、共同方法的对象的集合它描述了属于该对象类型的所有对象的性质,而一个对象则是其相应类的一个实例类是关于对象性质的描述,它同对象同样,涉及一组数据属性和在数据上的一组合法操作
3.消息消息是实例之间传递的信息,它请求对象执行某一解决或回答某一规定的信息,它统一了数据流和控制流一个消息由三部分组成接受消息的对象的名称、消息标记符(消息名)和零个或多个参数
4.继承广义地说,继承是指可以直接获得已有的性质和特性,而不必反复定义它们继承分为单继承与多重继承单继承是指,一个类只允许有一个父类,即类等级为树形结构多重继承是指,一个类允许有多个父类
5.多态性对象根据所接受的消息而做出动作,同样的消息被不同的对象接受时可导致完全不同的行动,该现象称为多态性第3章软件工程基础
3.1软件工程基本概念
1.软件定义与软件特点软件指的是计算机系统中与硬件互相依存的另一部分,涉及程序、数据和相关文档的完整集合程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列数据是使程序能正常操纵信息的数据结构文档是与程序的开发、维护和使用有关的图文资料可见,软件由两部分组成□机器可执行的程序和数据;□机器不可执行的,与软件开发、运营、维护、使用等有关的文档根据应用目的的不同,软件可分应用软件、系统软件和支撑软件(或工具软件),见表3-1表3-1软件的分类名称描述应用软件为解决特定领域的应用而开发的软件系统软件计算机管理自身资源,提高计算机使用效率并为计算机用户提供各种服务的软件支撑软件(或工具软件)支撑软件是介于两者之间,协助用户开发软件的工具性软件
2.软件工程为了摆脱软件危机,提出了软件工程的概念软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科所谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护软件工程学的重要研究对象涉及软件开发与维护的技术、方法、工具和管理等方面软件工程涉及3个要素方法、工具和过程,见表3-2表3-2软件工程三要素名称描述方法方法是完毕软件工程项目的技术手段工具工具支持软件的开发、管理、文档生成过程过程支持软件开发的各个环节的控制、管理
3.2软件生命周期
1.软件生命周期概念软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期软件生命周期分为3个时期共8个阶段,□软件定义期涉及问题定义、可行性研究和需求分析3个阶段;□软件开发期涉及概要设计、具体设计、实现和测试4个阶段;口运营维护期即运营维护阶段软件生命周期各个阶段的活动可以有反复,执行时也可以有迭代,如图3-1所示图3-1软件生命周期
2.软件生命周期各阶段的重要任务在图3-1中的软件生命周期各阶段的重要任务,见表3-3表3-3软件生命周期各阶段的重要任务任务描述问题定义拟定规定解决的问题是什么可行性研究与计划制定决定该问题是否存在一个可行的解决办法,指定完毕开发任务的实行计划需求分析对待开发软件提出需求进行分析并给出具体定义编写软件规格说明书及初步的用户手册,提交评审软件设计通常又分为概要设计和具体设计两个阶段,给出软件的结构、模块的划分、功能的分派以及解决流程这阶段提交评审的文档有概要设计说明书、具体设计说明书和测试计划初稿软件实现在软件设计的基础上编写程序这阶段完毕的文档有用户手册、操作手册等面向用户的文档,以及为下一步作准备而编写的单元测试计划软件测试在设计测试用例的基础上,检查软件的各个组成部分编写测试分析报告运营维护将已交付的软件投入运营,同时不断的维护,进行必要并且可行的扩充和删改
3.3软件设计
3.
3.1软件设计基本概念
(1)按技术观点分从技术观点上看,软件设计涉及软件结构设计、数据设计、接口设计、过程设计
①结构设计定义软件系统各重要部件之间的关系;
②数据设计将分析时创建的模型转化为数据结构的定义;
③接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信;
④过程设计则是把系统结构部件转换为软件的过程性描述2按工程管理角度分从工程管理角度来看,软件设计分两步完毕概要设计和具体设计
①概要设计将软件需求转化为软件体系结构、拟定系统级接口、全局数据结构或数据库模式;
②具体设计确立每个模块的实现算法和局部数据结构,用适当方法表达算法和数据结构的细节
3.
3.2软件设计的基本原理
1.软件设计中应当遵循的基本原理和与软件设计有关的概念1抽象软件设计中考虑模块化解决方案时,可以定出多个抽象级别抽象的层次从概要设计到具体设计逐步减少2模块化模块是指把一个待开发的软件分解成若干小的简朴的部分模块化是指解决一个复杂问题时自顶向下逐层把软件系统划提成若干模块的过程3信息隐蔽信息隐蔽是指在一个模块内包含的信息过程或数据,对于不需要这些信息的其他模块来说是不能访问的4模块独立性模块独立性是指每个模块只完毕系统规定的独立的子功能,并且与其他模块的联系最少且接口简朴模块的独立限度是评价设计好坏的重要度量标准衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准内聚性是信息隐蔽和局部化概念的自然扩展一个模块的内聚性越强则该模块的模块独立性越强一个模块与其他模块的耦合性越强则该模块的模块独立性越弱
2.衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准内聚性是度量一个模块功能强度的一个相对指标内聚是从功能角度来衡量模块的联系,它描述的是模块内的功能联系内聚有如下种类,它们之间的内聚度由弱到强排列偶尔内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚耦合性是模块之间互相连接的紧密限度的度量耦合性取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口耦合可以分为多种形势,它们之间的耦合度由高到低排列内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合在程序结构中,各模块的内聚性越强,则耦合性越弱一般较优秀的软件设计,应尽量做到高内聚,低耦合,即减弱模块之间的耦合性和提高模块内的内聚性,有助于提高模块的独立性
3.4结构化分析方法
1.结构化分析方法的定义结构化分析方法就是使用数据流图(DFD)、数据字典(DD)、结构化英语、鉴定表和鉴定树的工具,来建立一种新的、称为结构化规格说明的目的文档结构化分析方法的实质是着眼于数据流、自顶向下、对系统的功能进行逐层分解、以数据流图和数据字典为重要工具,建立系统的逻辑模型
2.结构化分析方法常用工具
(1)数据流图(DFD)数据流图是系统逻辑模型的图形表达,即使不是专业的计算机技术人员也容易理解它,因此它是分析员与用户之间极好的通信工具
(2)数据字典(DD)数据字典是对数据流图中所有元素的定义的集合,是结构化分析的核心数据流图和数据字典共同构成系统的逻辑模型,没有数据字典数据流图就不严格,若没有数据流图,数据字典也难于发挥作用数据字典中有4种类型的条目数据流、数据项、数据存储和加工3鉴定表有些加工的逻辑用语言形式不容易表达清楚,而用表的形式则一目了然假如一个加工逻辑有多个条件、多个操作,并且在不同的条件组合下执行不同的操作,那么可以使用鉴定表来描述4鉴定树鉴定树和鉴定表没有本质的区别,可以用鉴定表表达的加工逻辑都能用鉴定树表达
3.软件需求规格说明书软件需求规格说明书是需求分析阶段的最后成果,是软件开发的重要文档之一它的特点是具有对的性、无歧义性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性
3.5软件测试
3.
5.1软件测试的目的和准则
1.软件测试的目的给出了软件测试的目的□测试是为了发现程序中的错误而执行程序的过程;□好的测试用例testcase能发现迄今为止尚未发现的错误;□一次成功的测试是能发现至今为止尚未发现的错误测试的目的是发现软件中的错误,但是,暴露错误并不是软件测试的最终目的,测试的主线目的是尽也许多地发现并排除软件中隐藏的错误
2.软件测试的准则根据上述软件测试的目的,为了能设计出有效的测试方案,以及好的测试用例,软件测试人员必须进一步理解,并对的运用以下软件测试的基本准则□所有测试都应追溯到用户需求;□在测试之前制定测试计划,并严格执行;□充足注意测试中的群集现象;□避免由程序的编写者测试自己的程序;□不也许进行穷举测试;□妥善保存测试计划、测试用例、犯错记录和最终分析报告,为维护提供方便软件测试的方法和实行
1.软件测试方法软件测试具有多种方法,依据软件是否需要被执行,可以分为静态测试和动态测试方法假如依照功能划分,可以分为白盒测试和黑盒测试方法1静态测试和动态测试1静态测试涉及代码检查、静态结构分析、代码质量度量等其中代码检查分为代码审查、代码走查、桌面检查、静态分析等具体形式;
②动态测试静态测试不实际运营软件,重要通过人工进行分析动态测试就是通常所说的上机测试,是通过运营软件来检查软件中的动态行为和运营结果的对的性动态测试的关键是使用设计高效、合理的测试用例测试用例就是为测试设计的数据,由测试输入数据和预期的输出结果两部份组成测试用例的设计方法一般分为两类黑盒测试方法和白盒测试方法2黑盒测试和白盒测试
①白盒测试白盒测试是把程序当作装在一只透明的白盒子里,测试者完全了解程序的结构和解决过程它根据程序的内部逻辑来设计测试用例,检查程序中的逻辑通路是否都按预定的规定对的地工作;2黑盒测试黑盒测试是把程序当作一只黑盒子,测试者完全不了解,或不考虑程序的结构和解决过程它根据规格说明书的功能来设计测试用例,检查程序的功能是否符合规格说明的规定
2.软件测试的实行软件测试过程分4个环节,即单元测试、集成测试、验收测试和系统测试单元测试是对软件设计的最小单位一一模块程序单元进行对的性检查测试单元测试的技术可以采用静态分析和动态测试集成测试是测试和组装软件的过程,重要目的是发现与接口有关的错误,重要依据是概要设计说明书集成测试所设计的内容涉及软件单元的接口测试、全局数据结构测试、边界条件和非法输入的测试等集成测试时将模块组装成程序,通常采用两种方式非增量方式组装和增量方式组装确认测试的任务是验证软件的功能和性能,以及其他特性是否满足了需求规格说明中拟定的各种需求,涉及软件配置是否完全、对的确认测试的实行一方面运用黑盒测试方法,对软件进行有效性测试,即验证被测软件是否满足需求规格说明确认的标准系统测试是通过测试确认的软件,作为整个基于计算机系统的一个元素,与计算机硬件、外设、支撑软件、数据和人员等其他系统元素组合在一起,在实际运营(使用)环境下对计算机系统进行一系列的集成测试和确认测试系统测试的具体实行一般涉及功能测试、性能测试、操作测试、配置测试、外部接口测试、安全性测试等
3.6程序的调试在对程序进行了成功的测试之后将进入程序调试(通常称Debug,即排错)程序的调试任务是诊断和改正程序中的错误调试重要在开发阶段进行程序调试活动由两部分组成,一是根据错误的迹象拟定程序中错误的确切性质、因素和位置;二是对程序进行修改,排除这个错误程序调试的基本环节
①错误定位从错误的外部表现形式入手,研究有关部分的程序,拟定程序中犯错位置,找犯错误的内在因素;
②修改设计和代码,以排除错误;
③进行回归测试,防止引进新的错误软件调试可分为静态调试和动态调试静态调试重要是指通过人的思维来分析源程序代码和排错,是重要的设计手段,而动态调试是辅助静态调试的重要的调试方法有强行排错法、回溯法和因素排除法3种指互相有关联的数据元素的集合
(2)数据结构研究的3个方面1数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;2在对数据进行解决时,各数据元素在计算机中的存储关系,即数据的存储结构;
③对各种数据结构进行的运算
2.逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表达数据的逻辑结构有两个要素一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R一个数据结构可以表达成B=(D,R)其中,B表达数据结构为了反映D中各数据元素之间的前后件关系,一般用二元组来表达例如,假如把一年四季看作一个数据结构,则可表达成B=(D,R)D={春季,夏季,秋季,冬季}R={(春季,夏季),(夏季,秋季),(秋季佟季)}
3.存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)由于数据元素在计算机存储空间中的位置关系也许与逻辑关系不同,因此,为了表达存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息一种数据的逻辑结构根据需要可以表达成多种存储结构,常用的存储结构有顺序、链接等存储结构顺序存储方式重要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系来体现链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据元素之间逻辑上的第4章数据库设计基础
4.1数据库的基本概念数据是数据库中存储的基本对象,它是描述事物的符号记录数据库是长期储存在计算机内、有组织的、可共享的大量数据的集合,它具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序所共享,所以数据库技术的主线目的是解决数据共享问题数据库管理系统DBMS,Database ManagementSystem是数据库的机构,它是一种系统软件,负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等数据库管理系统是数据系统的核心为完毕数据库管理系统的功能,数据库管理系统提供相应的数据语言数据定义语言、数据操纵语言、数据控制语言
4.2数据库系统的发展和基本特点
1.数据库系统的发展数据管理技术的发展经历了3个阶段人工管理阶段、文献系统阶段和数据库系统阶段关于数据管理三个阶段中的软硬件背景及解决特点,简朴概括可见表4-1人工管理阶段文献管理阶段数据库系统管理阶段背景应用目的科学计算科学计算、管理大规模管理硬件背景无直接存取设备磁盘、磁鼓大容量磁盘软件背景无操作系统有文献系统有数据库管理系统解决方式批解决联机实时解决批解决分布解决、联机实时解决和批解决表4-1数据管理三个阶段的比较特点数据管理者人文献系统数据库管理系统数据面向的对象某个应用程序某个应用程序现实世界数据共享限度无共享,冗余度大共享性差,冗余度大共享性大,冗余度小数据的独立性不独立,完全依赖于程序独立性差具有高度的物理独立性和一定的逻辑独立性数据的结构化无结构记录内有结构,整体无结构整体结构化,用数据模型描述数据控制能力由应用程序控制应用程序控制由DBMS提供数据安全性、完整性、并发控制和恢复
2.数据库系统的特点数据独立性是数据与程序间的互不依赖性,即数据库中的数据独立于应用程序而不依赖于应用程序数据的独立性一般分为物理独立性与逻辑独立性两种
①物理独立性当数据的物理结构(涉及存储结构、存取方式等)改变时,如存储设备的更换、物理存储的更换、存取方式改变等,应用程序都不用改变
②逻辑独立性数据的逻辑结构改变了,如修改数据模式、增长新的数据类型、改变数据间联系等,用户程序都可以不变
3.3数据库系统的内部体系结构
1.数据统系统的3级模式
①概念模式,也称逻辑模式,是对数据库系统中全局数据逻辑结构的描述,是全体用户(应用)公共数据视图一个数据库只有一个概念模式;
②外模式,外模式也称子模式,它是数据库用户可以看见和使用的局部数据的逻辑结构和特性的描述,它是由概念模式推导而出来的,是数据库用户的数据视图,是与某一应用有关的数据的逻辑表达一个概念模式可以有若干个外模式;
③内模式,内模式又称物理模式,它给出了数据库物理存储结构与物理存取方法内模式处在最底层,它反映了数据在计算机物理结构中的实际存储形式,概念模式处在中间层,它反映了设计者的数据全局逻辑规定,而外模式处在最外层,它反映了用户对数据的规定
2.数据库系统的两级映射两级映射保证了数据库系统中数据的独立性
①概念模式到内模式的映射该映射给出了概念模式中数据的全局逻辑结构到数据的物理存储结构间的相应关系;
②外模式到概念模式的映射概念模式是一个全局模式而外模式是用户的局部模式一个概念模式中可以定义多个外模式,而每个外模式是概念模式的一个基本视图
3.4数据模型的基本概念数据模型从抽象层次上描述了数据库系统的静态特性、动态行为和约束条件,因此数据模型通常由数据结构、数据操作及数据约束三部分组成数据库管理系统所支持的数据模型分为3种层次模型、网状模型和关系模型数据模型特点见表4-2o表4-2各种数据模型的特点发展阶段重要特点层次模型用树形结构表达实体及其之间联系的模型称为层次模型,上级结点与下级结点之间为一对多的联系网状模型用网状结构表达实体及其之间联系的模型称为网状模型,网中的每一个结点代表一个实体类型,允许结点有多于一个的父结点,可以有一个以上的结点没有父结点关系模型用二维表结构来表达实体以及实体之间联系的模型称为关系模型,在关系模型中把数据当作是二维表中的元素,一张二维表就是一个关系
4.5E-R模型
1.E-R模型的基本概念
①实体现实世界中的事物可以抽象成为实体,实体是概念世界中的基本单位,它们是客观存在的且又能互相区别的事物;
②属性现实世界中事物均有一些特性,这些特性可以用属性来表达;
③码唯一标记实体的属性集称为码;
④域属性的取值范围称为该属性的域;
⑤联系在现实世界中事物间的关联称为联系两个实体集间的联系事实上是实体集间的函数关系,这种函数关系可以有下面几种一对一的关系、一对多或多对一关系、多对多关系
2.E-R模型的的图示法E-R模型用E-R图来表达
①实体表达法在E-R图中用矩形表达实体集,在矩形内写上该实体集的名字;
②属性表达法在E-R图中用椭圆形表达属性,在椭圆形内写上该属性的名称;
③联系表达法在E-R图中用菱形表达联系,菱形内写上联系名
3.6关系模型关系模式采用二维表来表达,一个关系相应一张二维表可以这么说,一个关系就是一个二维表,但是一个二维表不一定是一个关系•元组在一个二维表(一个具体关系)中,水平方向的行称为元组元组相应存储文献中的一个具体记录;•属性二维表中垂直方向的列称为属性,每一列有一个属性名;•域属性的取值范围,也就是不同元组对同一属性的取值所限定的范围在二维表中惟一标记元组的最小属性值称为该表的键或码二维表中也许有若干个健,它们称为表的侯选码或侯选健从二维表的所有侯选键选取一个作为用户使用的键称为主键或主码表A中的某属性集是某表B的键,则称该属性值为A的外键或外码关系模型采用二维表来表达,二维表一般满足下面7个性质
①二维表中元组个数是有限的一一元组个数有限性;
②二维表中元组均不相同一一元组的唯一性;
③二维表中元组的顺序可以任意互换一一元组的顺序无关性;
④二维表中元组的分量是不可分割的基本数据项一一元组分量的原子性;
⑤二维表中属性名各不相同一一属性名唯一性;
⑥二维表中属性与顺序无关,可任意互换一一属性的顺序无关性;
⑦二维表属性的分量具有与该属性相同的值域一一分量值域的统一性关系操纵数据查询、数据的删除、数据插入、数据修改关系模型允许定义三类数据约束,它们是实体完整性约束、参照完整性约束以及用户定义的完整性约束
4.7关系代数
1.传统的集合运算1投影运算从关系模式中指定若干个属性组成新的关系称为投影投影是从列的角度进行的运算,相称于对关系进行垂直分解通过投影运算可以得到一个新的关系,其关系模式所包含的属性个数往往比原关系少,或者属性的排列顺序不同2选择运算从关系中找出满足给定条件的元组的操作称为选择选择是从行的角度进行的运算,即水平方向抽取记录通过选择运算得到的结果可以形成新的关系,其关系模式不变,但其中的元组是原关系的一个子集3迪卡尔积设有n元关系R和m元关系S,它们分别有p和q个元组,则R与S的笛卡儿积记为R XSo它是一个m+n元关系,元组个数是pXq
2.关系代数的扩充运算1交假设有n元关系R和n元关系S,它们的交仍然是一个n元关系,它由属于关系R且由属于关系S的元组组成,并记为RGS,它可由基本运算推导而得Rns=R-R-S
3.8数据库设计与原理数据库设计中有两种方法,面向数据的方法和面向过程的方法面向数据的方法是以信息需求为主,兼顾解决需求;面向过程的方法是以解决需求为主,兼顾信息需求由于数据在系统中稳定性高,数据已成为系统的核心,因此面向数据的设计方法已成为主流数据库设计目前一般采用生命周期法,即将整个数据库应用系统的开发分解成目的独立的若干阶段它们是需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运营阶段和进一步修改阶段在数据库设计中采用前4个阶段联系线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂限度,一般将数据结构分为两大类型线性结构与非线性结构1假如一个非空的数据结构满足下列两个条件
①有且只有一个根结点;
②每一个结点最多有一个前件,也最多有一个后件则称该数据结构为线性结构线性结构又称线性表在一个线性结构中插入或删除任何一个结点后还应是线性结构栈、队列、串等都为线性结构假如一个数据结构不是线性结构,则称之为非线性结构数组、广义表、树和图等数据结构都是非线性结构2线性表的顺序存储结构具有以下两个基本特点
①线性表中所有元素所占的存储空间是连续的;
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的元素ai的存储地址为ADRai=ADRal+i-lk,ADRal为第一个元素的地址,k代表每个元素占的字节数3顺序表的运算有查找、插入、删除3种
1.3栈
1.栈的基本概念栈stack是一种特殊的线性表,是限定只在一端进行插入与删除的线性表在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素通常称插入、删除的这一端为栈顶,另一端为栈底当表中没有元素时称为空栈栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才干被删除的元素栈是按照“先进后出”或“后进先出”的原则组织数据的例如,枪械的子弹匣就可以用来形象的表达栈结构子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才干被弹出
2.栈的顺序存储及其运算栈的基本运算有3种入栈、退栈与读栈顶元素1入栈运算在栈顶位置插入一个新元素;2退栈运算取出栈顶元素并赋给一个指定的变量;3读栈顶元素将栈顶元素赋给一个指定的变量
1.4队列
1.队列的基本概念队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾当表中没有元素时称为空队列队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,或者后进后出的线性表例如火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾若有队列(,)Q=ql,q2,…qn那么,ql为队头元素(排头元素),qn为队尾元素队列中的元素是按照ql,q2,…,qn的顺序进入的,退出队列也只能按照这个顺序依次退出,即只有在ql,q2,…,qn-1都退队之后,qn才干退出队列因最先进入队列的元素将最先出队,所以队列具有先进先出的特性,体现“先来先服务”的原则队头元素ql是最先被插入的元素,也是最先被删除的元素队尾元素qn是最后被插入的元素,也是最后被删除的元素因此,与栈相反,队列又称为“先进先出(First InFirst Out,简称FIFO)或“后进后出”(Last InLast Out,简称LILO)的线性表
2.队列运算入队运算是往队列队尾插入一个数据元素;退队运算是从队列的队头删除一个数据元素队列的顺序存储结构一般采用队列循环的形式循环队列s=0表达队列空;s=l且frontrear表达队列满计算循环队列的元素个数“尾指针减头指针”,若为负数,再加其容量即可
1.5链表在链式存储方式中,规定每个结点由两部分组成一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域其中指针用于指向该结点的前一个或后一个结点(即前件或后件)链式存储方式既可用于表达线性结构,也可用于表达非线性结构线性链表线性表的链式存储结构称为线性链表在某些应用中,对线性链表中的每个结点设立两个指针,一个称为左指针,用以指向其前件结点;另一个称为右指针,用以指向其后件结点这样的表称为双向链表在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序与逻辑顺序可以不一致在线性链表中进行插入与删除,不需要移动链表中的元素线性单链表中,HEAD称为头指针,HEAD=NULL(或0)称为空表假如是双项链表的两指针左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点线性链表的基本运算查找、插入、删除
(2)带链的栈栈也是线性表,也可以采用链式存储结构带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可运用栈
1.6二叉树
1.
6.1二叉树概念及其基本性质
1.二叉树及其基本概念二叉树是一种很有用的非线性结构,具有以下两个特点
①非空二叉树只有一个根结点;
②每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树在二叉树中,每一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树此外,二叉树中的每个结点的子树被明显地分为左子树和右子树在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树当一个结点既没有左子树也没有右子树时,该结点即为叶子结点例如,一个家族中的族谱关系如图1-1所示A有后代B,C;B有后代D,E;C有后代F典型的二叉树如图1-1所示具体讲解二叉树的基本概念,见表1-2图M二叉树图父结点(根)在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根例如,在图1-1中,结点A是树的根结点子结点和叶子结点在树结构中,每一个结点可以有多个后件,称为该结点的子结点没有后件的结点称为叶子结点例如,在图1-1中,结点D,E,F均为叶子结点度在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度例如,在图1-1中,根结点A和结点B的度为2,结点C的度为1,叶子结点D,E,F的度为0所以,该树的度为2深度定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1树的最大层次称为树的深度例如,在图1-1中,根结点A在第1层,结点B,C在第2层,结点D,E,F在第3层该树的深度为3子树在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树表1-2二叉树的基本概念
2.二叉树基本性质二叉树具有以下几个性质性质1在二叉树的第k层上,最多有2k-l(k21)个结点性质2深度为m的二叉树最多有2m-1个结点性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个性质4具有n个结点的二叉树,其深度至少为[log2n]+l,其中[log2n]表达取log2n的整数部分
3.满二叉树与完全二叉树满二叉树是指这样的一种二叉树除最后一层外,每一层上的所有结点都有两个子结点在满二叉树中,每一层上的结点数都达成最大值,即在满二叉树的第k层上有2k-l个结点,且深度为m的满二叉树有2m-l个结点完全二叉树是指这样的二叉树除最后一层外,每一层上的结点数均达成最大值;在最后一层上只缺少右边的若干结点对于完全二叉树来说,叶子结点只也许在层次最大的两层上出现对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为P+1完全二叉树具有以下两个性质性质1具有n个结点的完全二叉树的深度为[log2n]+l性质2设完全二叉树共有n个结点假如从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=l,2,……,n)的结点有以下结论
①若k=l,则该结点为根结点,它没有父结点;若kl,则该结点的父结点编号为INT(k/2);
②若2kWn,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点);
③若2k+lWn,则编号为k的结点的右子结点编号为2k+l;否则该结点无右子结点二叉树的遍历在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树在先左后右的原则下,根据访问根结点的顺序,二叉树的遍历分为三类中序前序遍历、遍历和后序遍历
(1)前序遍历先访问根结点,然后遍历左子树,最后遍历右子树;并且在遍历左、右子树时,仍需先访问根结点,然后遍历左子树,最后遍历右子树例如,对图1-1中的二叉树进行前序遍历的结果(或称为该二叉树的前序序列)为A,B,D,E,C,Fo
(2)中序遍历先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树例如,对图1-1中的二叉树进行中序遍历的结果(或称为该二叉树的中序序列)为D,B,E,A,C,Fo
(3)后序遍历先遍历左子树、然后遍历右子树,最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点例如,对图1-1中的二叉树进行后序遍历的结果(或称为该二叉树的后序序列)为D,E,B,F,C,Ao
1.7查找
1.
7.1顺序查找查找是指在一个给定的数据结构中查找某个指定的元素从线性表的第一个元素开始,依次将线性表中的元素与被查找的元素相比较,若相等则表达查找成功;若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表达查找失败例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找的数据不相等,接着与第2个元素46进行比较,以此类推,当进行到与第4个元素比较时,它们相等,所以查找成功假如查找数据元素100,则整个线性表扫描完毕,仍未找到与100相等的元素,表达线性表中没有要查找的元素在下列两种情况下也只能采用顺序查找
①假如线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找;
②即使是有序线性表,假如采用链式存储结构,也只能用顺序查找
1.
7.2二分法查找二分法查找,也称拆半查找,是一种高效的查找方法能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件“有序”是特指元素按非递减排列,即从小到大排列,但允许相邻元素相等下一节排序中,有序的含义也是如此对于长度为n的有序线性表,运用二分法查找元素X的过程如下环节I将X与线性表的中间项比较;环节2假如X的值与中间项的值相等,则查找成功,结束查找;环节3假如X小于中间项的值,则在线性表的前半部分以二分法继续查找;环节4假如X大于中间项的值,则在线性表的后半部分以二分法继续查找例如,长度为8的线性表关键码序列为[6,13,27,30,38,46,47,70],被查元素为38,一方面将与线性表的中间项比较,即与第4个数据元素30相比较,38大于中间项30的值,则在线性表[38,46,47,70]中继续查找;接着与中间项比较,即与第2个元素46相比较,38小于46,则在线性表[38]中继续查找,最后一次比较相等,查找成功顺序查找法每一次比较,只将查找范围减少1,而二分法查找,每比较一次,可将查找范围减少为本来的一半,效率大大提高对于长度为n的有序线性表,在最坏情况下,二分法查找只需比较log2n次,而顺序查找需要比较n次
1.8排序
1.互换类排序法1冒泡排序法一方面,从表头开始往后扫描线性表,逐次比较相邻两个元素的大小,若前面的元素大于后面的元素,则将它们互换,不断地将两个相邻元素中的大者往后移动,最后最大者到了线性表的最后然后,从后到前扫描剩下的线性表,逐次比较相邻两个元素的大小,若后面的元素小于前面的元素,则将它们互换,不断地将两个相邻元素中的小者往前移动,最后最小者到了线性表的最前面对剩下的线性表反复上述过程,直到剩下的线性表变空为止,此时已经排好序在最坏的情况下,冒泡排序需要比较次数为nn-l/2o2快速排序法任取待排序序列中的某个元素作为基准一般取第一个元素,通过一次排序,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等于基准元素的排序码,右子序列的。