《2022年2022年计算机二级基础知识 4.pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机二级基础知识 4.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法算法得基本概念1、 算法 : 就是对问题处理方案得正确而完整得描述, 就是求解问题得方法, 就是指令得有效序列。2、 具有 5 个特性 : (1) 有穷性 ( 在有穷步后完成) 算法程序得运行时间就是有限得(2) 确定性 ( 每一步都有确定得含义) (3) 可行性(4) 输入 ( 一个算法有零个或多个输入) (5) 输出 ( 一个算法有一个或多个输出) 3、 算法得复杂度包括 :时间复杂度与空间复杂度。二者没有必然得联系。时间复杂度 : 执行算法所需要得计算工作量或基本运算次数。空间复杂度 : 算法所需要得空间得度量。数据结构得定义1、 数据结构包括数据得逻辑结构、数据得存储结构
2、、数据得操作数据得逻辑结构: 数据得外部结构, 指各数据元素之间得逻辑关系, 反映人们对数据含义得解释。包括 : 线性结构 ( 线性表、栈、队列) 与非线性结构 ( 树与图 ) 数据得存储结构: 数据得物理结构, 指数据得逻辑结构在计算机中得表示。一个逻辑结构可以有多种存储结构。 线性表 : 线性表中元素得个数n(n=0) 定义为线性表得长度。顺序存储就是线性表得一种最常用得存储方式。线性表得顺序存储结构与线性表得链式存储结构分别就是随机存取得存储结构与顺序存取得存储结构。1、栈 : 就是限定在表尾进行插入与删除操作得线性表。具有记忆功能只能顺序存储( 错) 允许插入与删除得一端叫栈顶。另一端
3、叫栈底。后进先出得线性表2 队列 : 就是限定在一端插入而在另一端删除, 插入端叫队尾, 删除端叫对头。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 先进先出得线性表3 栈与队列得顺序存储结构循环队列属于线性表存储结构中顺序存储结构与链式存储结构得前者。 树1、定义 : 树得结点、度 ( 结点得度 ) 、叶子 ( 终端结点 ) 、数得度、深度、有序树与无序数2、二叉树 : 结点至多有两棵子树, 并且二叉树得子树有之分, 次序不
4、能颠倒。性质 :在二叉树得第i 层上至多有2i1 个结点 深度为 k 得二叉树至多有2k1 个结点。 对任一个二叉树T, 如果其叶子 ( 终端结点数 ) 为 n, 度为二得结点数为m,则 n=m +1、 具有 n 个结点得完全二叉树得深度为k+1, 其中 k 就是 2n 得整数部分。2、 二叉树得遍历先序遍历 ( 根左右 ) 中序遍历 ( 左根右 ) 后序遍历 ( 左右根 ) 查找算法(1) 顺序查找顺序查找得平均查找长度为(n+1) 2, 最坏得情况下比较得次数为n (2) 二分查找最坏情况下次数为log2n 限定于顺序存储得有序线性表排序算法(1) 插入类排序直接插入排序折半插入排序希尔排
5、序、(2) 交换类排序冒泡排序最坏情况下得比较次数n(n1) 2 快速排序最坏情况下得比较次数n(n1) 2 (3) 选择类排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 例题精选 : 1、 设一棵完全二叉树共有699 个结点 , 则在该二叉树中得叶子结点数为:350 2、 已知二叉树后序遍历序列就是dabec, 中序遍历序列就是debac, 它得前序遍历序列为:cedba 3、 要求内存量最大得就是: 归并排序4、 在数据
6、结构中 , 与所使用得计算机无关得就是数据得就是: 逻辑结构5、 栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前 , 栈中元素可以出栈,则出栈序列可能就是:DCBEA 6、 已知数据表A 中每个元素距其最终位置不远, 为节省时间 , 应采取得算法就是:直接插入排序7、 用链式表示线性表得优点就是:便于插入与删除操作。程序设计基础1、程序设计风格好得程序设计风格有利于提高程序得正确性、可读性、 可维护性与可用性。要就是程序有良好得风格概括起来可以分为4 部分 : 源程序文档化、数据说明、语句结构、输入输出方法。用户所定义得标示符必须以字母或下划线开头。大、小写字母代表不同标识。2、结
7、构化程序设计(1) 结构化程序设计得基本特征: 程序有 3 中基本结构组成: 顺序结构、选择结构、循环结构整个程序采用模块化结构。模块划分得原则: 模块内具有高内聚度、模块间具有低耦合度。有限得使用转移语句, 只限定在一个结构得内部跳转, 不允许从一个结构跳到另一结构。程序设计时采用“至顶向下、逐步详细”得实施方法。(2) 结构化程序设计得3 种基本结构 : 顺序结构、选择结构、循环结构3 种基本结构组成得算法只能完成符合结构化得任务(3) 结构化程序设计得方法: 逐步求精与模块化程序设计方法。结构化设计得总体思想就是采用模块化结构, 自上而下 , 逐步求精。3、 面向对象程序设计名师资料总结
8、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 基本概念对象 :系统中运行得实体, 就是有特殊属性( 数据 ) 与方法得实体类: 由属性与方法构成。一组具有相同得数据结构与相同得行为特征得对象得集合称为类在面对对象得方法中, 类得实例称为对象面向对象程序设计特征得就是: 继承性、多态性、封装性在面向对象得方法中, 实现信息隐蔽就是依靠对象得封装任何对象都必须有继承性( 错) 例题精选 : 1、 在面对对象得方法中, 一个对象请求另一个对象为
9、其服务得方式就是通过发送: 信息2、 面对对象得设计方法与传统得面向过程得方法有本质得区别, 它得基本原理就是:使用现实世界得概念抽象得思考问题从而自然地解决问题、3、 结构化方法中 , 软件功能分解属于软件开发阶段中得总体设计4、 结构化程序设计主要强调得就是: 程序得易读性5、 面向对象得设计程序主要考虑得就是: 提高软件得可重用性6、 类通过接口与外界发生关系、软件工程基础1、软件工程得基本概念(1) 定义 : 软件就是程序、数据与相关文档得集合。软件包括系统软件与应用软件(2) 软件工程得基本思想就是软件开发中, 应用工程化原则进行软件开发, 并将这个思想贯穿在软件开发得整个过程中。软
10、件工程得3 要素 : 方法、工具与过程(3) 软件得生命周期: 从软件定义、开发、使用、维护到报废为止得整个过程。分三阶段 : 设计阶段、开发阶段、维护阶段包括 :问题定义、可行性分析、需求分析、总体设计、详细设计、编码、测试与维护问题定义 : 确定开发得任务可行性分析 : 确定问题得可行性需求分析 : 对用户要求进行分析, 明确目标系统要做什么总体设计 : 把软件功能转化为所需要得体系结构, 即如何解决问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - -
11、 - - - - - - - 详细设计 : 怎样具体得解决问题2、结构化分析方法(1) 结构化分析 (SA) 就是面向数据流进行需求分析得方法SA 方法得基本思想正就是运用了分解与抽象两个基本手段, 采用 : 自顶向下 , 逐步分解得分析思路。(2) 数据流图基本图形符号: 在结构化方法中, 用数据流程图(DFD)作为描述工具得软件开发阶段就是: 需求分析(3) 数据字典在结构化分析得数据流图中, 利用数据字典对其中得图形元素进行确切解释、3、软件设计(1) 概要设计 ( 总体设计 ) 包括两个主要阶段: 系统设计 ( 确定具体得实现方案) 与结构设计 ( 确定每个系统得模块组成及模块间得关系
12、) 模块之间联系越紧密, 其耦合性就越强, 模块得独立性就越差; 一个模块内个要素联系越紧密, 则它得内聚性就越高。模块划分原则:高内聚低耦合(2) 详细设计结构化程序设计得要点: 采用自顶向下、 逐步求精得程序设计方法, 一个程序只有一个入口与一个出口。详细设计得常用工具: 程序流程图、盒图、PAD与 PDL (3) 软件测试目得软件测试得目得就是尽可能多得发现程序中得错误。软件测试方法: 静态测试与动态测试( 黑盒测试法与白盒测试法) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -
13、第 5 页，共 7 页 - - - - - - - - - 黑盒测试包括:等价分析法、边值分析法、因果图法与错误推测法白盒测试法测试得原则之一就就是保证所测模块中得每一个独立得路径至少执行一次。(4) 程序调试分为静态调试与动态调试调试得目得 : 改正错误经调试后还必须进行再测试(5) 软件维护软件维护就就是在软件已经交付使用以后, 为改正错误或满足新得需求而修改软件得过程。例题精选 : 1. 分析得结果就是产生需求规格说明书。2. 软件详细设计得主要任务就是确定每一个模块得算法与使用得数据结构。3. 进行单元测试时, 常用得方法时采用白盒测试, 辅以黑盒测试。4. 软件工程得出现就是由于软件
14、危机得出现, 人们提出了软件工程学得原理设计软件。5. 数据字典就是各类数据描述得集合, 通常包括 4 个部分 : 数据项、数据流、数据存储与数据加工。数据库设计基础1、 数据库(1) 数据库设计得根本目得就是要解决数据共享得问题。(2) 数据库得特点 : 数据按一定得数据模型组织与存储。 冗余度较小 数据得独立性较高。数据独立性: 数据得组织结构与存储方法与应用程序互不依赖、彼此独立。易扩展可为多种用户共享2、 数据库管理系统(DBMS) 位于用户与操作系统之间得完成数据管理得系统软件。3、 数据库系统名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
15、- - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 由数据库、数据库管理系统、应用系统、数据库管理员与用户组成。最核心得部分就是数据库管理系统。4、 数据模型(1) 实体联系模型及ER图3 部分 : 实体、联系与属性实体集间得联系: 一对一联系、一对多联系与多对多联系(2) 层次、网状、关系模型层次模型 : 有且只有一个结点无双亲, 其她结点只有一个双亲。用树形结构来表示各实体与实体之间得联系。在关系数据库中,把数据表示成二维表, 每个二维表称为关系。一个关系对应一张二维表。关系得属性名称为关系模式。5、 关系运算(1)
16、 并(2) 差(3) 交(4) 笛卡尔积 ( ) 6、专门关系运算: 选择、连接与投影(1) 从关系中找到满足条件得所有元组称为选择(2) 从关系中挑选若干属性组成新得关系称为投影7、数据库设计步骤: (1) 需求分析阶段(2) 概念设计阶段(3) 逻辑结构设计阶段将 ER图转化数据模型(4) 数据库物理设计阶段数据库内模式 , 给出数据库物理存储结构与物理存取方法。例题精选 : 1、 数据库管理系统得主要功能就是: 定义数据库2、 关系表中每一横行称为一个元组, 每一列称为属性。3、 设计数据库得存储结构属于物理设计、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -