2022年公共基础知识总结打印.docx

《2022年公共基础知识总结打印.docx》由会员分享，可在线阅读，更多相关《2022年公共基础知识总结打印.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品_精品资料_公共基础学问总结第一章数据结构与算法1.1 算法算法：是指解题方案的精确而完整的描述.算法不等于程序,也不等运算机方法,程序的编制不行能优于算法的设计.算法的基本特点：（1） 可行性.（2） 确定性,算法中每一步骤都必需有明确定义,不许有模棱两可的说明, 不许有多义性.（3） 有穷性,算法必需能在有限的时间内做完,即能在执行有限个步骤后终止,（4） 拥有足够的情报.算法的掌握结构：次序结构、挑选结构、循环结构.算法复杂度：算法时间复杂度和算法空间复杂度. 算法时间复杂度是指执行算法所需要的运算工作量.算法空间复杂度是指执行这个算法所需要的内存空间.1.2 数据结构的基本基本概念

2、数据结构讨论的三个方面：（1） 数据集合中各数据元素之间所固有的规律关系,即数据的规律结构.（2） 在对数据进行处理时,各数据元素在运算机中的储备关系,即数据的储备结构.（3） 对各种数据结构进行的运算.* ：数据的规律结构反映数据元素之间的规律关系,数据的储备结构 （也称数据的物理结构） 是数据的规律结构在运算机储备空间中的存放形式.线性结构条件：（栈,队列,单向线性链表,）（1）有且只有一个根结点.（2）每一个结点最多有一个前件,也最多有一个后件.非线性结构：不满意线性结构条件的数据结构.（树）1 3 线性表及其次序储备结构线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之

3、间的相对位置是线性的.1 4 栈和队列栈是 限定在一端进行插入与删除的线性表,答应插入与删除的一端称为栈顶,不答应插入与删除的另一端称为栈底.栈依据“ 先进后出”（ FILO）或“后进先出”（ LIFO）组织数据,栈具有记忆作用.用 top表示栈顶位置,用bottom 表示栈底.队列是指 答应在一端（队尾）进入插入,而在另一端（队头）进行删除的线性表.Rear 指针指向队尾, front指针指向队头.队列是“先进先出”（FIFO）或“后进后出”（ LILO ）的线性表.可编辑资料 - - - 欢迎下载精品_精品资料_1 5 线性链表.在链式储备结构中, 储备数据结构的储备空间可以不连续,各数据

4、结点的储备次序与数据元素之间的规律关系可以不一样,而数据元素之间的规律关系是由指针域来确定的.链式储备方式即可用于表示线性结构,也可用于表示非线性结构.1 6 树与二叉树树是一种简洁的非线性结构,全部元素之间具有明显的层次特性.在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件的结点称为叶子结点.（通俗的讲： 结点的度该结点的向下分支数.树的度 -全部结点中的向下分支数最大的那个值.树的深度 -树的层数.层数从1 开头运算.根是第一层.）* ：依据二叉树的概念可知,二叉树的度可以为0（叶结点

5、）、1（只有一棵子树）或2（有 2棵子树）.二叉树的特点： （ 1）非空二叉树只有一个根结点.（ 2）每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树.二叉树的基本性质：k-1（1） 在二叉树的第 k 层上,最多有 2k 1 个结点.m（2） 深度为 m的二叉树最多有 2 -1 个结点.（3） 度为 0 的结点（即叶子结点）总是比度为2 的结点多一个.2k-1满二叉树是指除最终一层外,每一层上的全部结点有两个子结点,就k 层上有个结点m深度为 m的满二叉树有2 -1 个结点.完全二叉树是指除最终一层外,每一层上的结点数均达到最大值,在最终一层上只缺少右边的如干结点.（由 满二叉树从最

6、终一个结点依次向前删除,得到完全二叉树）结论： 完全二叉树中度为1 的结点个数： 0 或者 1. （只有这两种情形） 二叉树的遍历：（ 必考 ）（1） 前序遍历（ DLR）,第一拜访根结点,然后遍历左子树,最终遍历右子树.（2） 中序遍历（ LDR）,第一遍历左子树,然后拜访根结点,最终遍历右子树.（3） 后序遍历（ LRD）第一遍历左子树,然后拜访遍历右子树,最终拜访根结点.1 7 查找技术次序查找： 最坏情形下需要比较n 次.次序查找一个具有n 个元素的线性表,其平均复杂度为O（ n）.二分法查找 只适用于次序储备的有序表,对于长度为n 的有序线性表,最坏情形只需比较log2n 次.1.

7、8 排序技术可编辑资料 - - - 欢迎下载精品_精品资料_本章应考点拨：本章内容在笔试中会显现5-6个题目,是公共基础学问部分出题量比较多的一章,所占分值也比较大,约10 分.其次章程序设计基础2. 1 程序设计设计方法和风格如何形成良好的程序设计风格1、源程序文档化.2 、数据说明的方法. 3、语句的结构.4、输入和输出.注释分序言性注释和功能性注释,语句结构清楚第一、效率其次.2 2 结构化程序设计结构化程序设计方法的四条原就是 ： 1.自顶向下. 2.逐步求精. 3. 模块化. 4. 限制使用goto 语句.2. 3 面对对象的程序设计对象是面对对象方法中最基本的概念,可以用来表示客观

8、世界中的任何实体.面对对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,由一组表示其静态特点的属性和它可执行的一组操作组成.属性即对象所包含的信息,操作描述了对象执行的功能,操作也称为方法或服务.对象的基本特点 ：（1）标识惟一性.（2）分类性.（ 3）多态性.（ 4）封装性.（ 5）模块独立性好.* ：信息隐藏是通过对象的封装性 来实现的.类是指具有共同属性、共同方法的对象的集合.所以类是对象的抽象,对象是对应类的一个实例.消息是一个实例与另一个实例之间传递的信息.消息的组成包括（ 1）接收消息的对象的名称.（2）消息标识符,也称消息名.（3）零个或多个

9、参数.继承是指能够直接获得已有的性质和特点,而不必重复定义他们.继承分单继承和多重继承.单继承指一个类只答应有一个父类,多重继承指一个类答应有多个父类.多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象.可编辑资料 - - - 欢迎下载精品_精品资料_本章应考点拨：本章在考试中会显现约1 个题目,所占分值大约占2 分,是出题量较小的一章.本章内容比较少,也很简洁,把握住基本的概念就可以轻松应对考试了,第三章软件工程基础3. 1 软件工程基本概念运算机软件是包括程序、数据及相关文档的完整集合.软件工程源自软件危机. 所谓软件危机是泛指在运算机软件的开发和爱护过程中所遇到的一系列严峻

10、问题 .软件危机主要表现在成本、质量、生产率等问题.软件工程是应用于运算机软件的定义、开发和爱护的一整套方法、工具、文档、实践标准和工序.软件工程包括3 个要素：方法、工具和过程.软件生命周期：软件产品从提出、实现、使用爱护到停止使用退役的过程. 软件生命周期三个阶段: 软件定义、软件开发、运行爱护,主要活动阶段是： 1）软件定义阶段：包括制定方案和需求分析.制定方案：确定总目标.可行性讨论.探讨解决方案.制定开发方案.需求分析：对待开发软件提出的需求进行分析并给出具体的定义. 2）软件开发阶段：软件设计：分为概要设计和具体设计两个部分.软件实现：把软件设计转换成运算机可以接受的程序代码.软件

11、测试：在设计测试用例的基础上检验软件的各个组成部分.3）软件运行爱护阶段：软件投入运行,并在使用中不断的爱护,进行必要的扩充和删改.* ：软件生命周期中所花费最多的阶段是软件运行爱护阶段.软件工程原就包括抽象、 信息隐藏、 模块化、 局部化、 确定性、 一样性、 完备性和可验证性.局部化：保证模块间具有松散的耦合关系,模块内部有较强的内聚性.（ 高聚低耦 ）3 2 结构化分析方法1、需求分析需求分析方法有： 1）结构化需求分析方法.2）面对对象的分析方法.* ：需求分析的任务就是导出目标系统的规律模型,解决“做什么”的问题.* ：需求分析一般分为需求猎取、需求分析、 编写需 求规格说明书 和需

12、求评审四个步骤进行.2、结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用.结构化分析方法的实质：着眼于数据流,自顶向下,逐层分解,建立系统的处理流程,以数据流图和数据字典为主要工具,建立系统的规律模型.结构化分析的常用工具：1）数据流图（ DFD）.2）数据字典（ DD）. 3）判定树. 4）判定表.数据流图以图形的方式描画数据在系统中流淌和处理的过程,它反映了系统必需完成的逻辑功能,是结构化分析方法中用于表示系统规律模型的一种工具.加工数据流储备文件源、潭上图是数据流图的基本图形元素：加工（转换） ：输入数据经加工变换产生输出.可编辑资料 - - - 欢迎下载精品_精

13、品资料_数据流：沿箭头方向传送数据的通道,一般在旁边标注数据流名.储备文件（数据源） ：表示处理过程中存放各种数据的文件.源,潭：表示系统和环境的接口,属系统之外的实体.（学吧学吧独家稿件） 画数据流图的基本步骤：自外向内,自顶向下,逐层细化,完善求精.数据字典：对全部与系统相关的数据元素的一个有组织的列表,以及精确的、严格的定义,使得用户和系统分析员对于输入、输出、储备成分和中间运算结果有共同的懂得.* ：数据字典的作用是对数据流图中显现的被命名的图形元素的准确说明.* ：数据字典是结构化分析方法的核心.3、软件需求规格说明书（SRS）软件需求规格说明书是需求分析阶段的最终成果,通过建立完整

14、的信息描述、具体的功能 和行为描述、性能需求和设计约束的说明、合适的验收标准,给出对目标软件的各种需求.3 3 结构化设计方法1、软件设计的基础* ：需求分析主要解决“做什么”的问题,而软件设计主要解决“怎么做”的问题.从工程治理角度来看：软件设计分两步完成：概要设计和具体设计.概要设计：又称结构设计,将软件需求转化为软件体系结构,确定系统级接口、全局数据结构或数据库模式.具体设计：确定每个模块的实现算法和局部数据结构,用适当方法表示算法和数据结构的细节.软件设计的基本原理包括：抽象、模块化、信息隐藏和模块独立性.1） 抽象.抽象是一种思维工具,就是把事物本质的共同特性提取出来而不考虑其他细节

15、.2） 模块化.解决一个复杂问题时自顶向下逐步把软件系统划分成一个个较小的、相对独立但又不相互关联的模块的过程. 3）信息隐藏.每个模块的实施细节对于其他模块来说是隐藏的.4）模块独立性.软件系统中每个模块只涉及软件要求的具体的子功能,而和软件系统中其他的模块的接口是简洁的.* ：模块分解的主要指导思想是信息隐藏和模块独立性.模块的耦合性和内聚性是衡量软件的模块独立性的两个定性指标.内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量.耦合性：是模块间相互连接的紧密程度的度量.在程序结构中各模块的内聚性越强,就耦合性越弱.优秀软件应高内聚,低耦合.软件概要设计的基本任务是：（1）设计软件系

16、统结构.（ 2）数据结构及数据库设计.（3）编写概要设计文档.（ 4）概要设计文档评审.常用的软件结构设计工具是结构图,也称程序结构图.程序结构图的基本图符：模块用一个矩形表示, 箭头表示模块间的调用关系.在结构图中仍可以用带注释的箭头表示 模块调用过程中来回传递的信息.仍可用带实心圆的箭头表示传递的是掌握信息,空心圆箭心表示传递的是数据信息.一般模块数据信息掌握信息典型的数据流类型有两种：变换型和事务型.变换型系统结构图由输入、中心变换、输出三部分组成.事务型数据流的特点是：接受一项事务, 依据事务处理的特点和性质,挑选分派一个适当的可编辑资料 - - - 欢迎下载精品_精品资料_处理单元,

17、然后给出结果.具体设计：是为软件结构图中的每一个模块确定实现算法和局部数据结构,用某种选定的表达工具表示算法和数据结构的细节.常见的过程设计工具有： 图形工具 （程序流程图） 、表格工具 （判定表） 、语言工具 （ PDL）.3 4 软件测试软件测试定义： 使用人工或自动手段来运行或测定某个系统的过程,其目的在于检验它是否满意规定的需求或是弄清预期结果与实际结果之间的差别.软件测试的目的：发觉错误而执行程序的过程.软件测试方法：静态测试和动态测试.静态测试包括代码检查、静态结构分析、 代码质量度量. 不实际运行软件, 主要通过人工进行.动态测试：是基本运算机的测试,主要包括白盒测试方法和黑盒测

18、试方法.白盒测试：在程序内部进行,主要用于完成软件内部操作的验证.白盒测试的基本原就： 保证所测模块中每一独立路径至少执行一次.白盒测试法的测试用例是依据程序的内部规律来设计的,主要用软件的单元测试,主要方法有规律掩盖、 基本路径测试等.黑盒测试：是对软件已经实现的功能是否满意需求进行测试和验证.主要诊断功能不对或 遗漏、界面错误、数据结构或外部数据库拜访错误、性能错误、初始化和终止条件错,用于确认测试.主要方法有等价类划分法、边界值分析法、错误估计法、因果图等.软件测试过程一般按4 个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试.3. 5 程序的调试程序 调试的任务 是诊断和

19、改正程序中的错误,主要在开发阶段进行.程序调试的基本步骤：（1）错误定位.（ 2）修改设计和代码,以排除错误.（3）进行回来测试,防止引进新的错误.软件调试可分表静态调试和动态调试.静态调试主要是指通过人的思维来分析源程序代码和排错,是主要的设计手段,而动态调试是帮助静态调试.主要调试方法有：（1）强行排错法.（2）回溯法.（ 3）缘由排除法.本章应考点拨：本章在笔试中一般占8 分左右,约 3 道挑选题, 1 道填空题,是公共基础部分比较重要的一章.从出题的深度来看,本章主要考察对基本概念的识记,有少量对基本原理的懂得,没有实际运用,因此考生在复习本章时,重点应放在基本概念的记忆和基本原理的懂

20、得上.第四章数据库设计基础4. 1 数据库系统的基本概念数据：实际上就是描述事物的符号记录.数据库（ DB）：是数据的集合,具有统一的结构形式并存放于统一的储备介质内,是多种应用数据的集成,并可被各个应用程序共享.数据库存放数据是按数据所供应的数据模式存放的,具有集成与共享的特点.数据库治理系统（ DBMS）：一种系统软件,负责数据库中的数据组织、数据操纵、数据爱护、掌握及爱护和数据服务等,是数据库的核心 .可编辑资料 - - - 欢迎下载精品_精品资料_数据库治理系统供应以下的数据语言：（1） 数据定义语言：负责数据的模式定义与数据的物理存取构建.（2） 数据操纵语言：负责数据的操纵,如查询

21、与增、删、改等.（3） 数据掌握语言：负责数据完整性、安全性的定义与检查以及并发掌握、故障复原等.数据库系统 （ DBS）：由数据库 （数据） 、数据库治理系统 （软件） 、数据库治理员 （人员） 、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体.* ： DBS包含 DB和 DBMS数据库应用系统：由数据库系统、应用软件及应用界面三者组成.* ：数据库技术的根本目标是解决数据的共享问题.2、数据库系统的进展数据库治理进展至今已经受了三个阶段 ：人工治理阶段、文件系统阶段和数据库系统阶段.文件系统阶段： 供应了简洁的数据共享与数据治理才能,但是它无法供应完整的、 统一的、治理和数据共享

22、的才能.层次数据库与网状数据库系统阶段：为统一与共享数据供应了有力支撑.关系数据库系统阶段数据库系统的基本特点：（1） 数据的高集成性.（2） 数据的高共享性与低冗余性.* ：数据库系统可以削减数据冗余,但无法防止一切冗余.（3） 数据独立性：数据独立性是数据与程序间的互不依靠性,即数据库中数据独立于应用程序而不依靠于应用程序.也就是说, 数据的规律结构、 储备结构与存取方式的转变不会影响应用程序.数据独立性一般分为物理独立性与规律独立性两级.1）物理独立性：物理独立性即是数据的物理结构（包括储备结构,存取方式等）的转变,如储备设备的更换、 物理储备的更换、 存取方式转变等都不影响数据库的规律

23、结构,从而不致引起应用程序的变化. 2）规律独立性：数据库总体规律结构的转变,如修改数据模式、增加新的数据类型、转变数据间联系等,不需要相应修改应用程序,这就是数据的规律独立性.3、数据库系统的内部结构体系（A）数据库系统的三级模式：（ 1）概念模式：数据库系统中全局数据规律结构的描述【对程序员而言】（ 2）外模式：也称子模式与用户模式.是用户的数据视图.【对用户而言】（ 3）内模式：又称物理模式,它给出了数据库物理储备结构与物理存取方法.【对运算机而言】数据库系统的两级映射：（ 1）概念模式到内模式的映射.（ 2）外模式到概念模式的映射.4.2 数据模型数据模型的概念： 是数据特点的抽象,

24、从抽象层次上描述了系统的静态特点、 动态行为和约束条件, 为数据库系统的信息表与操作供应一个抽象的框架. 描述了数据结构、 数据操作及数据约束. 用 E-R 图来表示各种数据模型 E-R 模型的基本概念 * ： E-R 模型的基本成分是实体和联系. （1）实体：现实世界中的事物.（ 2）属性：事物的特性.可编辑资料 - - - 欢迎下载精品_精品资料_（3）联系：现实世界中事物间的关系.实体集的关系有一对一、一对多、多对多的联系.E-R 模型三个基本概念之间的联接关系：实体是概念世界中的基本单位,属性有属性域,每个实体可取属性域内的值.一个实体的全部属性值叫元组.E-R 模型的图示法：1）实体

25、集：用矩形表示.2 ）属性：用椭圆形表示.3 ）联系：用菱形表示.数据库治理系统常见的数据模型有层次模型、网状模型和关系模型三种层次模型的基本结构是树形结构.网状模型是一个不加任何条件限制的无向图.关系模型采纳二维表来表示,简称表,由表框架及表的元组组成.一个二维表就是一个关系.在二维表中凡能唯独标识元组的最小属性称为键或码.从全部侯选健中选取一个作为用户使用的键称主键.表A 中的某属性是某表B 的键,就称该属性集为A 的外键或外码.关系中的数据约束： 1）实体完整性约束：要求关系的主键中属性值不能为空值,由于主键是唯独打算元组的, 如为空值就其唯独性就成为不行能的了. 2）参照完整性约束：关

26、系之间相互关联的基本约束,不答应关系引用不存在的元组,即在关系中的外键要么是所关联关系中实际存在的元组,要么为空值. 3）用户定义的完整性约束：反映某一具体应用所涉及的数据必需满意的语义要求.例如某个属性的取值范畴在0 100 之间等.4.3 关系代数关系数据库系统的特点之一是它建立在数据理论的基础之上,有许多数据理论可以表示关系模型的数据操作,其中最为闻名的是关系代数与关系演算.关系模型的基本运算：（1）插入 （ 2）删除 3修改 （ 4）查询（包括投影、挑选、笛卡尔积运算） 关系运算（交,并,差）及挑选、投影、连接运算（1）并（）：（ 2） 交（）（3） ： 差（ ）：关系 R 和 S 具

27、有相同的关系模式,R 和 S 的差是由属于 R但不属于 S 的元组构成的集合.（4） 广义笛卡尔积（）：* ：依据笛卡尔积的定义：有n 元关系 R及 m元关系 S,它们分别有 p、q 个元组,就关系 R 与 S 经笛卡尔积记为 RS,该关系是一个 n+m元关系,元组个数是 p q,由 R 与 S 的有序组组合而成.在关系型数据库治理系统中,基本的关系运算有挑选、投影与联接三种操作：1） 挑选：挑选指的是从二维关系表的全部记录中,把那些符合指定条件的记录挑出来.2） 投影：投影是从全部字段中选取一部分字段及其值进行操作,它是一种纵向操作.3） 联接：联接将两个关系模式拼接成一个更宽的关系模式,生

28、成的新关系中包含满意联接条件的元组.4.4 数据库设计方法和步骤数据库的生命周期：需求分析阶段、概念设计阶段、规律设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段.（1） 数据库设计阶段包括：需求分析、概念分析、规律设计、物理设计.（2） 数据库设计的每个阶段都有各自的任务： 1）需求分析阶段：这是数据库设计的第一个阶段,任务主要是收集和分析数据,这一阶段收集到的基础数据和数据流图是下一步设计概念结构的基础.可编辑资料 - - - 欢迎下载精品_精品资料_2）概念设计阶段：分析数据间内在语义关联,在此基础上建立一个数据的抽象模型,即形成 E-R 图.* ：数据库概念设计的过程包括挑选局部应用、视图设计和视图集成.3）规律设计阶段：将E-R 图转换成指定 RDBMS中的关系模式.4）物理设计阶段：对数据库内部物理结构作调整并挑选合理的存取路径,以提高数据库访问速度及有效利用储备空间.本章应考点拨：本章在考试中一般显现4-5 个小题.本章内容概括性强,比较抽象,难于懂得,因此建议考生在复习的时候,第一熟读讲义,其次对数据库系统的基本概念及原理等学问要留意懂得、加强记忆.可编辑资料 - - - 欢迎下载