2022年全国计算机二级基础知识要点 .pdf

《2022年全国计算机二级基础知识要点 .pdf》由会员分享，可在线阅读，更多相关《2022年全国计算机二级基础知识要点 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、算法1、算法的时间复杂度：是指执行算法所需的计算工作量。2、算法的空间复杂度：是指执行算法所需的内存空间。内存空间： 1、输入数据所占的存储空间2、程序本身所占的存储空间3、算法执行过程中所需要的额外的空间3、前后件关系为数据之间最基本的关系。4、数据存储方式：1、顺序存储结构（逻辑结构与物理结构相一致）2、链式存储结构5、根结点：数据结构没有前件的结点终端结点（叶子结点） ：没有后件的结点6、线性结构： 1、有且只有一个根结点；2、每个结点最多有一个前件，最多一个后件（队列、线性表、栈、双向列表）；其余为非线性结构（二叉树）7、栈： 1、修改原则： “先进后出”或“后进先出”2、用针 t

2、op 来指示栈顶，用bottom 来指示栈底8、队列：“先进先出”或“后进后出”9、树：以分支关系定义的非线性结构1、父结点：只有一个前件；2、根：没有前件的结点（只有一个）3、子结点：每个结点可以有多个后件；4、叶子结点：没有后件5、度：一个结点拥有后件的个数为结点的度，所有结点中最大的度为树的度6、深度：一棵树根所在的层次为1，其他结点所在的层次等于他的父结点所在层次加1，树的最大层次为树的深度10、二叉树：具有规范性和确定性1、特点： 1、二叉树可以为空；2、非空二叉树只有一个根结点3、每个结点最多有两颗子树，子树有左右之分，次序不可随意颠倒2、满二叉树：第i 层上有 2(i-1) 个结

3、点，一共有 (2k-1) 个几结点 （k 为树的最大深度）3、满二叉树一定为完全二叉树，但完全二叉树不一定为满二叉树4、对于任何一个二叉树，度为0 的结点总比度为2 的结点多一个5、具有 n 个结点的二叉树，深度至少为不大于（2（n+1） ）的最大整数6、二叉树的遍历(如下图 ) 1、前序（ DLR ） ：根左子树右子树（ ABDECF ）2、中序（ LDR ） ：左子树根右子树(DEBACF) 3、后序（ LRD ） ：左子树右子树根(DEBFCA) B C D E F A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

4、精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 二、查找顺序查找：平均情况下查找n/2 次，最好情况下1 次，最坏情况下n 次二分法查找：条件1、顺序存储结构，2、线性表为有序表。最坏要查log2n 次交换类排序：1、冒泡排序法最坏情况下要查找n*(n-1)/2 次2、快速排序法最坏情况下要查找n*(n-1)/2 次插入类排序： 1、简单插入法最坏情况下要查找n*(n-1)/2 次2、希尔排序法最坏情况下要查找o（n1.5）次排序选择类排序： 1、简单选择法最坏情况下要查找n*(n-1)/2 次2、堆排序法最坏情况下要查找o（n*log2n）次

5、三、程序1、程序设计：设计、编制、调试程序的方法和过程2、优化程序设计方法的重要原则：自顶而下、逐步求精、模块化、限制使用goto 语句3、面向对象方法包括对象、类和实例、继承、消息、多态性4、面向对象方法的优点：1、与人类习惯的思维方法一致；2、稳定性好；3、可重用性好； 4、容易开发大型软件产品；5、可维护性好四、软件1、软件的特点：1、逻辑实体，具有抽象性；2、没有明显的制作过程3、在使用期间不存在磨损、老化问题；4、复杂性高，成本昂贵；5、涉及诸多社会因素2、软件的分类：1、系统软件：操作系统，数据库管理系统、编译程序、汇编程序网络软件2、应用软件：为了应用特定的领域而开发的3、支撑软

6、件：协助用户开发软件的工具型软件3、软件危机：1、软件开发和维护的方法不正确；2、软件本身的特点如复杂度高，规模庞大4、软件工程3 要素：方法、工具、过程5、软件的生命周期：从提出、实现、使用、维护到停止使用、退役的过程问题定义：确定解决的问题是什么软件的定义期可行性研究：决定问题是否存在一个可行的解决方法；完成开发任务的实施计划需求分析：提出需求分析并详细定义；完成软件规格说明书，初步用户手册，提交评审名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - -

7、- - - - - - 概要设计给出软件的结构，模块的划分，功能的分配，处理流程。完成设计说明书、详细计划说明书、测试计划初详细设计稿软件开发期实现：在软件设计基础上编写程序（用户手册，操作手册，单元测试计划测试：尽可能多的发现程序中的错误运行维护6、需求分析阶段的工作：需求获取、需求分析、编写需求规格说明书、需求评审需求分析方法的常用工具：1、流程图（ DFD ） ；2、数据字典（DD） ；3 判定表7、软件设计的基本原理的原则：模块化、抽象、信息隐藏、模块独立性（降低耦合性，提高内聚性）耦合性：不同模块彼此间相互依赖的紧密程度内聚性：一个模块内部各个元素彼此结合的紧密程度8、软件调试：在测

8、试发现错误后排除错误五、数据库设计基础1、数据库系统：数据库(DB) 、数据库管理系统(DBMS) 、数据库管理员、系统平台数据库的根本目的：数据共享问题。数据库的特点：集成与共享2、一定的数据模型组织具有较小的冗余度，较高的数据独立性，易扩展性3、DBMS 数据语言：1、定义语言：负责数据的模式定义与数据的物理存取构建2、操作语言：负责数据的操作包括查询与增、改、删等3、控制语言：负责数据完整性、安全性的定义与检查以及并发控制故障恢复等功能4、数据库管理员：对数据库的规划、设计、维护、监视的工作5、数据库的三级模式：概念模式、内模式、外模式1、概念模式是数据库系统中全局数据逻辑结构的描述，全

9、体用户的公共数据视图2、内模式 （子模式或用户模式）是用户的数据视图，也就是用户所能够看见和使用的局部数据的逻辑结构和特征的描述3、外模式（物理模式）是数据物理结构和存储方式的描述6、一个数据库：一个概念模式，一个内模式，多个外模式实体：客观存在并且可以相互区别7、数据模型的事物（矩形）实体联系模型（E-R）属性：描述实体的特性（椭圆）1、概念数据模型面向对象模型联系：实体之间的对应关系（菱形）2、逻辑数据模型：1、层次模型； 2、网状模型； 3、关系模型； 4、面向对象模型3、物理数据模型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

10、 - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 8、关系模型的数据结构1、关系（二维表，简称表）由表框架几表的元组组成2、属性：二维表中的一列3、元组：二维表中的一行4、值域：每个属性的取值范围9、关系代数1、投影运算：从关系模式指定若干个属性组成新的关系2、选择运算：从关系中找出满足给定条件的元组的操作3、笛卡尔积10、关系代数的扩充运算：1、交； 2、连接与自然连接；3、除11、数据库设计的方法面向数据的方法：以信息需求为主，兼顾处理需求面向过程的方法：以处理需求为主，兼顾信息需求12、结构化分析方法：自顶向下，逐步分解13、

11、数据库概念设计的方法：1、集中式模式设计法，2、视图集成设计法设计的过程：选择局部应用；视图设计；视图集成视图设计的策略：自顶向下，自底向上，由内向外视图集成中会引起的冲突1、 命名冲突：相同意义的属性，在不同的分E-R 图上有不同的命名，或者名称相同的属性在不同的分E-R 图中代表着不同的意义2、 概念冲突：同一概念在一处为实体而在另一处为属性或联系3、 域冲突：相同的属性在不同的视图中有不同的域4、 约束冲突：不同的视图可能有不同的约束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -