2022年二级公共基础知识考点总结 .docx

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

1、精品_精品资料_二级公共基础学问考点总结第一章 数据结构与算法考点 1：算法的概念和基本特点算法是指解题方案的精确而完整的描述.算法的基本特点包括：（1） 可行性：针对实际问题设计的算法,总是在某个特定运算工具上执行,往往要受到运算工具的限制,使执行结果产生偏差.（2） 确定性：算法中每一步骤都必需有明确定义,不充许有模棱两可的说明,不答应有多义性.（3） 有穷性：算法必需能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义.（4） 拥有足够的情报：拥有足够的输入.考点 2：算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度算法的时间复杂度是指执行算法所需要的运算工作量

2、 即算法执行过程中所需基本运算的执行次数 .算法的空间复杂度是指执行这个算法所需要的内存空间.特殊留意：时间复杂度与空间复杂度没有必定的正比或反比的关系.考点 3：数据的规律结构与储备结构数据的规律结构是反映数据元素之间规律关系的数据结构,与它们在运算机中的储备位置无关.数据的储备结构（也称物理结构）是指数据的规律结构在运算机储备空间中的存放形式.一种数据的规律结构依据需要可以表示成多种储备结构,常用的储备结构有次序、 链接、 索引等（包括线性结构和非线性结构）.而采纳不同的储备结构, 其数据处理的效率是不同的.考点 4：线性表的次序储备结构线性表的次序储备结构具有以下两个基本特点：1) 线性

3、表中全部元素所占的储备空间是连续的2) 线性表中各数据元素在储备空间中是按规律次序依次存放的在程序设计语言中,通常定义一个一维数组来表示线性表的次序储备空间可编辑资料 - - - 欢迎下载精品_精品资料_考点 5：栈与队列 属于线性结构 1、栈栈是限定在一端进行插入与删除的线性表.在栈中, 答应插入与删除的一端称为栈顶,不答应插入与删除的另一端称为栈底.通常用指针 top 指示栈顶的位置,用指针bottom 指向栈底.top-bottom 的肯定值加 1 即为当前栈中元素的个数.栈是依据“先进后出”或“后进先出”的原就组织数据的,用栈顶指针top 动态反映了栈中元素的变化情形,而不须转变指针b

4、ottom 的位置.栈具有记忆作用.2、队列队列是指答应在一端进行插入、而在另一端进行删除的线性表.答应插入的一端称为队尾,通常用一个尾指针rear 指向队尾元素,答应删除的一端称为排头（也称队头）,通常用一个排头指针 front 指向排头元素的前一个位置.队列依据“先进先出”或“后进后出”的原就组织数据,队尾指针rear 和排头指针front 共同反映了队列中元素动态变化情形.在实际应用中, 队列的次序储备结构一般采纳循环队列的形式,循环队列是规律上的环状空间,但物理上仍旧是线性结构.从排头指针front 指向的后一个位置直到队尾指针rear 指向的位置之间全部的元素均为队列中的元素.在一般

5、队列中, rear 指针位置减去 front 指针位置的差值即为队列中元素的个数.但在循环队列中, rear 指针的位置可能大于front 指针的位置,也可能小于front 指针的位置,所以循环队列的元素个数运算方法如下：设循环队列总容量为m假如 rearfront ,就循环队列的元素个数为rear-front假如 rearfront ,就循环队列的元素个数为m+rear-front栈与队列的共同点：皆为线性结构,只答应在端点处插入与删除,而且不须移动其他元素.可编辑资料 - - - 欢迎下载精品_精品资料_考点 6：线性链表线性表的链式储备结构称为线性链表在链式储备结构中, 储备数据结构的储

6、备空间可以不连续,各数据结点的储备次序与数据元素之间的规律关系可以不一样.链式储备结构即可用于表示线性结构,也可用于表示非线性结构, 栈与队列也可以采纳链式储备结构. 考点 7：二叉树的基本性质树是典型的非线性结构,在树中,每个结点的前件称为父结点,没有父结点的只有一个,称为根结点（有且仅有一个）.每个结点拥有的后件称为子结点,没有子结点的称为叶子结点.一个结点所拥有的子结点的个数称为该结点的度,叶子结点的度为树的最大层次称为树的深度.0.二叉树：每个结点最大的度为2,如下图所示2k-1性质 1：在二叉树的第 k 层上,最多有个结点m性质 2：深度为 m的二叉树最多有 2 -1 个结点性质 3

7、：在任意一棵二叉树中,度为0 的结点（叶子结点）总是比度为2 的结点多一个.可编辑资料 - - - 欢迎下载精品_精品资料_2k-1满二叉树：每一层上的结点数都达到最大值,即第k 层上有个结点,且深度为m的满可编辑资料 - - - 欢迎下载精品_精品资料_m二叉树有 2 -1 个结点完全二叉树： 除最终一层外, 每一层上的结点数均达到最大值.在最终一层上只缺少右边的如干结点.当完全二叉树有n 个结点,如 n 为偶数,就有 n/2 个叶子结点.如 n 为奇数,就有n/2+1 个叶子结点（ 表示只取整数部分） .考点 8：二叉树的遍历（1） 前序遍历（ DLR）,第一拜访根结点,然后遍历左子树,最

8、终遍历右子树.（2） 中序遍历（ LDR）,第一遍历左子树,然后拜访根结点,最终遍历右子树.（3） 后序遍历（ LRD）第一遍历左子树,然后拜访遍历右子树,最终拜访根结点.考点 9：查找技术对于长度为 n 的线性表：次序查找在最坏情形下,需要比较n 次.二分法查找只适用于次序储备的有序表,在最坏情形下只需要比较log2n 次.考点 10：排序技术在最坏情形下,对于长度为n 的线性表,冒泡排序法、快速排序法、简洁插入排序法、简洁挑选排序法都需要比较nn-1/2次.希尔排序法需要比较On1.5 次.堆排序法需要比较Onlog 2n次.在各种排序法中,冒泡排序法最简洁,比较次数最少（通常少于nn-1

9、/2 次）.可编辑资料 - - - 欢迎下载精品_精品资料_查找技术n最坏情形下的次数（时间复杂度）次序查找log 2 n二分法查找排序技术冒泡排序法nn-1/2交换类排序快速排序法插入类排序简洁插入排序法希尔排序法On 1.5 挑选 类排序简洁挑选排序法堆排序法Onlog 2 n其次章 程序设计基础考点 1：程序设计风格主要风格：清楚第一,效率其次形成良好的程序设计风格应留意的因素：1. 源程序的文档化：要包含必要的程序注释2. 数据说明的方法：数据说明的次序规范化3. 语句的结构4. 输入与输出考点 2：结构化程序设计的原就1. 自顶向下2. 逐步求精3. 模块化4. 限制使用 goto

10、语句结构化程序设计的基本结构包括次序结构、挑选结构和循环结构.考点 3：面对对象的基本概念1、 对象的特点：标识唯独性、分类性、多态性、封装性（实现信息隐藏）、模块独立性2、 类是具有共同属性、共同方法的对象的集合,类具有继承性3、类与对象的关系：类是对象的抽象,对象就是其对应类的一个实例可编辑资料 - - - 欢迎下载精品_精品资料_考点 1：软件的定义及特点第三章 软件工程基础可编辑资料 - - - 欢迎下载精品_精品资料_运算机软件是包括程序、数据及相关文档的完整集合.软件的特点包括：（1） 软件是一种规律实体,而不是物理实体.（2） 软件的生产与硬件不同,它没有明显的制作过程.（3）

11、软件在运行、使用期间不存在磨损、老化问题.（4） 软件的开发、运行对运算机系统具有依靠性,受运算机系统的限制,这导致了软件移可编辑资料 - - - 欢迎下载精品_精品资料_植的问题.（5） 软件复杂性高,成本昂贵.（6） 软件开发涉及诸多的社会因素.软件按功能可以分为：应用软件、系统软件和支撑软件或工具软件.考点 2：软件工程的定义软件工程强调在软件开发过程中应用工程化原就软件工程包括3 个要素： 方法、 工具和过程. 方法是完成软件工程项目的技术手段.工具支持软件开发、治理、文档生成.过程支持软件开发的各个环节的掌握、治理考点 3：软件生命周期1. 定义阶段：可行性讨论、需求分析2. 开发阶

12、段：概要设计、具体设计、实现、测试3. 爱护阶段：使用、爱护、退役考点 4：结构化分析方法1、结构化分析的常用工具(1) 数据流图（ DFD ）加工数据流储备文件 数据源 源、潭(2) 数据字典：作用是对DFD 中显现的被命名的图形元素的准确说明(3) 判定树(4) 判定表2、软件需求规格说明书：是需求分析阶段的最终成果.其最重要的特点是无歧义性.考点 5：结构化设计方法1、软件设计的分类从技术观点来看,软件设计包括软件结构设计、数据设计、接口设计、过程设计从工程治理角度来看,软件设计分两步完成：概要设计和具体设计2、衡量软件模块独立性的两个标准内聚性：是一个模块内部各个元素间彼此结合的紧密程

13、度的度量耦合性：是模块间相互连接的紧密程度的度量在程序结构中,各模块的内聚性越强,就耦合性越弱.优秀的软件设计应尽量做到高内聚、低耦合.可编辑资料 - - - 欢迎下载精品_精品资料_3、概要设计（软件结构设计）概要设计的常用工具是结构图（SC）结构图的有关术语：1) 深度：结构图的最大层次数2) 宽度：结构图横向上最大模块数3) 扇出：一个模块拥有的下级从属模块的个数4) 扇入：一个模块拥有的上级模块的个数留意：软件模块的规模要适中4、具体设计（软件过程设计） 常用的过程设计工具有：图形工具：程序流程图、N-S 图、 PAD 图、 HIPO 图表格工具：判定表语言工具： PDL （伪代码）

14、程序流程图的基本图符掌握流加工步骤规律条件可编辑资料 - - - 欢迎下载精品_精品资料_考点 6：软件测试1、软件测试的目的：尽可能多的发觉错误,而不是证明程序是否正确.2、软件测试的准就1) 全部测试都应回溯到需求2) 严格执行方案,排除随便性3) 充分留意测试中的群集现象4) 程序员应防止检查自己的程序5) 穷举测试不行能6) 妥当储存测试方案3、软件测试的方法(1) 静态测试：包括代码走查、静态结构分析、代码质量度量等,可以由人工进行.(2) 动态测试：是基于运算机的测试,设计合理的测试用例去运行程序,以便发觉错误.测试用例的格式为 （输入值集） , 输出值集 常用的动态测试方法又分为

15、：白盒测试： 针对软件程序内部规律结构进行测试,其基本原就是保证所测模块中每一独立路径至少执行一次.白盒测试的主要方法有规律掩盖、基本路径测试.黑盒测试： 完全不考虑程序内部的规律结构和内部特性,只是对软件已经实现的功能是否满意需求进行测试,检查程序的功能是否符合它的功能说明.黑盒测试方法主要有等价类划分法、边界值分析法、错误估计法、因果图等.4、软件测试的实施软件测试分 4 个步骤：单元测试、集成测试、验收测试（确认测试）和系统测试特殊留意 4 个步骤的次序考点 7：程序的调试 debug程序调试的任务是诊断和改正程序中的错误程序调试的基本步骤：1. 错误定位2. 修改设计和代码,以排除错误

16、3. 进行回来测试,防止引进新的错误可编辑资料 - - - 欢迎下载精品_精品资料_考点 1：数据库系统的基本概念第四章 数据库设计基础可编辑资料 - - - 欢迎下载精品_精品资料_(1) 数据库设计的根本目标：实现数据共享(2) 数据库治理系统 （ DBMS ）：是数据库系统的核心, 是实现各种数据治理功能的核心软件.是在操作系统支持下的系统软件.数据库治理系统通过供应数据语言完成各项功能,主要包括：数据定义语言（ DDL ）：负责数据的模式定义与数据的物理存取构建数据操纵语言（ DML ）：负责数据的操纵,包括查询及增、删、改等操作数据掌握语言（ DCL ）：负责数据完整性、安全性的定义

17、与检查以及并发掌握、故障复原等功能(3) 数据库系统（ DBS ）由五部分组成：数据库、数据库治理系统、数据库治理员、硬件平台、软件平台数据库系统需要操作系统（OS）的支持可编辑资料 - - - 欢迎下载精品_精品资料_考点 2：数据库系统的进展分三个阶段：人工治理、 文件系统、 数据库系统. 其中数据库系统阶段实现的数据共享程度最大,数据独立性最高.考点 3：数据库系统的基本特点（1） 数据的集成性如在关系数据库中采纳二维表作为统一的结构方式.（2） 数据的高共享性与低冗余性数据一样性是指在系统中同一数据的不同显现应保持相同的值.（3） 数据独立性数据独立性是数据与程序间的互不依靠性,即数据

18、库中数据独立于应用程序而不依靠于应用程序.分为物理独立性和规律独立性.物理独立性：数据的物理结构（包括储备结构、存取方式等）的转变,不影响数据库的规律结构,从而不致引起应用程序的变化.规律独立性：数据库总体规律结构的转变,不需要相应修改应用程序.（4） 数据统一治理与掌握数据的完整性检查数据的安全性爱护并发掌握考点 4：数据库系统的内部结构体系数据库系统具有三级模式：（1） 概念模式：数据库系统中全局数据规律结构的描述,全体用户公共数据视图.（2） 外模式：也称子模式与用户模式.是用户的数据视图,也就是用户所见到的数据模式. 一个概念模式可以推导出多个外模式.（3） 内模式：又称物理模式,它给

19、出了数据库物理储备结构与物理存取方法.如索引等 考点 5： E-R 模型E-R 模型的三个要素：1. 实体：现实世界中的事物.在 E-R 图中用矩形框表示.2. 属性：事物的特性.在 E-R 图中用椭圆表示.3. 联系： 现实世界中事物间的关系.在 E-R 图中用菱形框表示.联系类型有 3 种：1 对 1, 1 对多,多对多.特殊留意实体间联系的举例,如学校与校长、同学与宿舍、同学与课程等.考点 6：关系模型的特点关系模型采纳二维表（也称为关系）表示,二维表中列称为属性,行称为元组,凡能惟一标识元组的最小属性集称为该表的键或码.二维表应满意7 个性质：二维表中元组个数是有限的元组个数有限性二维

20、表中元组均不相同元组的惟一性二维表中元组的次序可以任意交换元组的次序无关性二维表中元组的重量是不行分割的基本数据项元组重量的原子性二维表中属性名各不相同属性名惟一性二维表中属性与次序无关,可任意交换属性的次序无关性可编辑资料 - - - 欢迎下载精品_精品资料_二维表属性的重量具有与该属性相同的值域重量值域的同一性考点 7：关系运算（看图题）挑选运算、投影运算、笛卡尔积运算 并运算、交运算、差运算自然连接运算| |R S（并运算）R S 交运算 A 47B 58C 69R S差运算 设有关系 R 与 SABRCASBC123456456789789101112ABC12345678910111

21、2ABC123设有关系R 与RS:SR1R2R3S1S2S3abcjkldefmnoghipqrR S笛卡尔积R1R2R3S1S2S3abcjklabcmnoabcPqrdefjkldefmnodefpqrghijklghimnoghipqr可编辑资料 - - - 欢迎下载精品_精品资料_设有关系 R 与 S:设有关系 R,经过投影运算得到RS设有关系 R,经过挑选运算得到R考点 8：数据库设计数据库设计分四个阶段：需求分析、概念设计、规律设计、物理设计DSE51647368RABCD1234158324261147R | S（自然联接）A2B4C2D6E42426811473ABCAB123124564578978ABC123456789SABC123456数据库规律设计的主要工作是将E-R图转换成指定RDBMS 中的关系模式E-R 模型属性关系属性E-R 模型实体集关系关系实体元组联系关系可编辑资料 - - - 欢迎下载