《2022年公共基础知识总结打印》由会员分享，可在线阅读，更多相关《2022年公共基础知识总结打印（9页珍藏版）》请在金锄头文库上搜索。
1、学习好资料欢迎下载公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不许有模棱两可的解释，不许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，（4）拥有足够的情报。算法的控制结构：顺序结构、选择结构、循环结构。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念数据结构研
2、究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。*：数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构 （也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。线性结构条件：（栈，队列，单向线性链表，）（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。（树）13 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
3、14 栈和队列栈是 限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“ 先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用 top表示栈顶位置，用bottom 表示栈底。队列是指 允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear 指针指向队尾， front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页学习好资料欢迎下载15 线性链表。在链式存储结
4、构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。16 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。（通俗的讲： 结点的度 -该结点的向下分支数。树的度 -所有结点中的向下分支数最大的那个值。树的深度 -树的层数。层数从1开始计算。根是第一层。）*：根据
5、二叉树的概念可知，二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有 2棵子树）。二叉树的特点： （1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：（1）在二叉树的第k 层上，最多有2k-1(k 1)个结点；（2）深度为m的二叉树最多有2m-1 个结点；（3）度为 0 的结点（即叶子结点）总是比度为2 的结点多一个；满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k 层上有2k-1个结点深度为 m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结
6、点。（由满二叉树从最后一个结点依次向前删除，得到完全二叉树）结论： 完全二叉树中度为1 的结点个数：0 或者 1. （只有这两种情况）二叉树的遍历：（必考 ）（1）前序遍历（DLR ），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR ），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD ）首先遍历左子树，然后访问遍历右子树，最后访问根结点。17 查找技术顺序查找： 最坏情况下需要比较n 次。顺序查找一个具有n 个元素的线性表，其平均复杂度为O（n）。二分法查找 只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次。1
7、8 排序技术精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页学习好资料欢迎下载本章应考点拨：本章内容在笔试中会出现5-6 个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10 分。第二章程序设计基础21 程序设计设计方法和风格如何形成良好的程序设计风格 1、源程序文档化； 2 、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。22 结构化程序设计结构化程序设计方法的四条原则是 ：1. 自顶向下； 2. 逐步求精； 3. 模块化； 4. 限制使用goto 语
8、句。23 面向对象的程序设计对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。对象的基本特点：（1）标识惟一性；（2）分类性；（3）多态性；（ 4）封装性；（5）模块独立性好。*：信息隐蔽是通过对象的封装性 来实现的。类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括（1）
9、接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页学习好资料欢迎下载本章应考点拨：本章在考试中会出现约1 个题目，所占分值大约占2 分，是出题量较小的一章。本章内容比较少，也很简单，掌握住基本的概念就可以轻松应对考试了，第三章软件工程基础31 软件工程
10、基本概念计算机软件是包括程序、数据及相关文档的完整集合。软件工程源自软件危机。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题 。软件危机主要表现在成本、质量、生产率等问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3 个要素：方法、工具和过程。软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段: 软件定义、软件开发、运行维护，主要活动阶段是：1）软件定义阶段：包括制定计划和需求分析。制定计划：确定总目标；可行性研究；探讨解决方案；制定开发计划。需求分析：对待开发软件提出的需求进行
11、分析并给出详细的定义。2）软件开发阶段：软件设计：分为概要设计和详细设计两个部分。软件实现：把软件设计转换成计算机可以接受的程序代码。软件测试：在设计测试用例的基础上检验软件的各个组成部分。3）软件运行维护阶段：软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。*：软件生命周期中所花费最多的阶段是软件运行维护阶段。软件工程原则包括抽象、信息隐蔽、 模块化、 局部化、 确定性、 一致性、 完备性和可验证性。局部化：保证模块间具有松散的耦合关系，模块内部有较强的内聚性。（ 高聚低耦 ）32 结构化分析方法1、需求分析需求分析方法有：1）结构化需求分析方法；2）面向对象的分析方法。*：需求分
12、析的任务就是导出目标系统的逻辑模型，解决“做什么”的问题。*：需求分析一般分为需求获取、需求分析、 编写需 求规格说明书和需求评审四个步骤进行。2、结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用。结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。结构化分析的常用工具：1）数据流图（ DFD ） ；2）数据字典（ DD ） ；3）判定树； 4）判定表。数据流图以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。上图是数
13、据流图的基本图形元素：加工（转换） ：输入数据经加工变换产生输出。加工数据流存储文件源、潭精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页学习好资料欢迎下载数据流：沿箭头方向传送数据的通道，一般在旁边标注数据流名。存储文件（数据源） ：表示处理过程中存放各种数据的文件。源，潭：表示系统和环境的接口，属系统之外的实体。（学吧学吧独家稿件）画数据流图的基本步骤：自外向内，自顶向下，逐层细化，完善求精。数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结
14、果有共同的理解。*：数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。*：数据字典是结构化分析方法的核心。3、软件需求规格说明书（SRS ）软件需求规格说明书是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。33 结构化设计方法1、软件设计的基础*：需求分析主要解决“做什么”的问题，而软件设计主要解决“怎么做”的问题。从工程管理角度来看：软件设计分两步完成：概要设计和详细设计。概要设计：又称结构设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式。详细设计：确定每个模块
15、的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。软件设计的基本原理包括：抽象、模块化、信息隐蔽和模块独立性。1）抽象。抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。2）模块化。解决一个复杂问题时自顶向下逐步把软件系统划分成一个个较小的、相对独立但又不相互关联的模块的过程。3）信息隐蔽。每个模块的实施细节对于其他模块来说是隐蔽的。4）模块独立性。软件系统中每个模块只涉及软件要求的具体的子功能，而和软件系统中其他的模块的接口是简单的。*：模块分解的主要指导思想是信息隐蔽和模块独立性。模块的耦合性和内聚性是衡量软件的模块独立性的两个定性指标。内聚性：是一个模块内
16、部各个元素间彼此结合的紧密程度的度量。耦合性：是模块间互相连接的紧密程度的度量。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。软件概要设计的基本任务是：（1）设计软件系统结构；（2）数据结构及数据库设计；（3）编写概要设计文档；（4）概要设计文档评审。常用的软件结构设计工具是结构图，也称程序结构图。程序结构图的基本图符：模块用一个矩形表示，箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。还可用带实心圆的箭头表示传递的是控制信息，空心圆箭心表示传递的是数据信息。典型的数据流类型有两种：变换型和事务型。变换型系统结构图由输入、中心
17、变换、输出三部分组成。事务型数据流的特点是：接受一项事务， 根据事务处理的特点和性质，选择分派一个适当的一般模块数据信息控制信息精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页学习好资料欢迎下载处理单元，然后给出结果。详细设计：是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。常见的过程设计工具有：图形工具 （程序流程图） 、表格工具 （判定表） 、语言工具 （PDL ）。34 软件测试软件测试定义： 使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需
18、求或是弄清预期结果与实际结果之间的差别。软件测试的目的：发现错误而执行程序的过程。软件测试方法：静态测试和动态测试。静态测试包括代码检查、静态结构分析、代码质量度量。 不实际运行软件，主要通过人工进行。动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次。白盒测试法的测试用例是根据程序的内部逻辑来设计的，主要用软件的单元测试，主要方法有逻辑覆盖、基本路径测试等。黑盒测试：是对软件已经实现的功能是否满足需求进行测试和验证。主要诊断功能不对或遗漏、界面错误、数据结构或外
19、部数据库访问错误、性能错误、初始化和终止条件错，用于确认测试。主要方法有等价类划分法、边界值分析法、错误推测法、因果图等。软件测试过程一般按4 个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。35 程序的调试程序 调试的任务 是诊断和改正程序中的错误，主要在开发阶段进行。程序调试的基本步骤：（1）错误定位；（2）修改设计和代码，以排除错误；（3）进行回归测试，防止引进新的错误。软件调试可分表静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，而动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。本章应考
20、点拨：本章在笔试中一般占8 分左右，约3 道选择题， 1 道填空题，是公共基础部分比较重要的一章。从出题的深度来看，本章主要考察对基本概念的识记，有少量对基本原理的理解，没有实际运用，因此考生在复习本章时，重点应放在基本概念的记忆和基本原理的理解上。第四章数据库设计基础41 数据库系统的基本概念数据：实际上就是描述事物的符号记录。数据库（ DB ）：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库管理系统（DBMS ）：一种系统软件，负责数据库中的数据组织、数据操纵
21、、数据维护、控制及保护和数据服务等，是数据库的核心。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页学习好资料欢迎下载数据库管理系统提供以下的数据语言：（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。数据库系统 （DBS ）：由数据库 （数据） 、数据库管理系统 （软件） 、数据库管理员 （人员） 、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。*：DBS包含 DB和 D
22、BMS数据库应用系统：由数据库系统、应用软件及应用界面三者组成。*：数据库技术的根本目标是解决数据的共享问题。2、数据库系统的发展数据库管理发展至今已经历了三个阶段 ：人工管理阶段、文件系统阶段和数据库系统阶段。文件系统阶段： 提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。层次数据库与网状数据库系统阶段：为统一与共享数据提供了有力支撑。关系数据库系统阶段数据库系统的基本特点：（1）数据的高集成性。（2）数据的高共享性与低冗余性。*：数据库系统可以减少数据冗余，但无法避免一切冗余。（3）数据独立性：数据独立性是数据与程序间的互不依赖性，即数据库中数据独立
23、于应用程序而不依赖于应用程序。也就是说， 数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。数据独立性一般分为物理独立性与逻辑独立性两级。1）物理独立性：物理独立性即是数据的物理结构（包括存储结构，存取方式等）的改变，如存储设备的更换、物理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。2）逻辑独立性：数据库总体逻辑结构的改变，如修改数据模式、增加新的数据类型、改变数据间联系等，不需要相应修改应用程序，这就是数据的逻辑独立性。3、数据库系统的内部结构体系（A）数据库系统的三级模式：（ 1）概念模式：数据库系统中全局数据逻辑结构的描述【对程序员而言】（ 2
24、）外模式：也称子模式与用户模式。是用户的数据视图；【对用户而言】（ 3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。【对计算机而言】数据库系统的两级映射：（ 1）概念模式到内模式的映射；（ 2）外模式到概念模式的映射。4.2 数据模型数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件， 为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。 ( 用 E-R 图来表示各种数据模型) E-R 模型的基本概念 (*：E-R 模型的基本成分是实体和联系。) （1）实体：现实世界中的事物；（2）属性：事物的特性；精选学习
25、资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页学习好资料欢迎下载（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。E-R 模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。E-R 模型的图示法：1）实体集：用矩形表示。 2 ）属性：用椭圆形表示。 3 ）联系：用菱形表示。数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种层次模型的基本结构是树形结构。网状模型是一个不加任何条件限制的无向图。关系模型采用二维表来表示，简称
26、表，由表框架及表的元组组成。一个二维表就是一个关系。在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。关系中的数据约束：1）实体完整性约束：要求关系的主键中属性值不能为空值，因为主键是唯一决定元组的，如为空值则其唯一性就成为不可能的了。2）参照完整性约束：关系之间相互关联的基本约束，不允许关系引用不存在的元组，即在关系中的外键要么是所关联关系中实际存在的元组，要么为空值。3）用户定义的完整性约束：反映某一具体应用所涉及的数据必须满足的语义要求。例如某个属性的取值范围在0 100 之间等。4.3
27、 关系代数关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。关系模型的基本运算：（1）插入（2）删除 (3)修改 （ 4）查询（包括投影、选择、笛卡尔积运算）关系运算（交，并，差）及选择、投影、连接运算（1）并（）：（2）交（）（3）： 差（ ）：关系R和 S具有相同的关系模式，R和 S的差是由属于R但不属于S的元组构成的集合。（4）广义笛卡尔积（）：*：根据笛卡尔积的定义：有n 元关系 R及 m元关系 S，它们分别有 p、q 个元组，则关系R与 S经笛卡尔积记为RS，该关系是一个n+m元关系，元组个数是 p q
28、，由 R与 S的有序组组合而成。在关系型数据库管理系统中，基本的关系运算有选择、投影与联接三种操作：1）选择：选择指的是从二维关系表的全部记录中，把那些符合指定条件的记录挑出来。2）投影：投影是从所有字段中选取一部分字段及其值进行操作，它是一种纵向操作。3）联接：联接将两个关系模式拼接成一个更宽的关系模式，生成的新关系中包含满足联接条件的元组。4.4 数据库设计方法和步骤数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。（1）数据库设计阶段包括：需求分析、概念分析、逻辑设计、物理设计。（2）数据库设计的每个阶段都有各自的任务
29、：1）需求分析阶段：这是数据库设计的第一个阶段，任务主要是收集和分析数据，这一阶段收集到的基础数据和数据流图是下一步设计概念结构的基础。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页学习好资料欢迎下载2）概念设计阶段：分析数据间内在语义关联，在此基础上建立一个数据的抽象模型，即形成 E-R 图。*：数据库概念设计的过程包括选择局部应用、视图设计和视图集成。3）逻辑设计阶段：将E-R 图转换成指定RDBMS 中的关系模式。4）物理设计阶段：对数据库内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。本章应考点拨：本章在考试中一般出现4-5 个小题。本章内容概括性强，比较抽象，难于理解，因此建议考生在复习的时候，首先熟读讲义，其次对数据库系统的基本概念及原理等知识要注意理解、加强记忆。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页
