计算机二级公共基础知识优秀PPT.ppt

计算机二级公共基础知识计算机二级公共基础知识现在学习的是第1页，共21页公共基础知识公共基础知识1.1算法1.2数据结构的基本概念1.3线性表和顺序存储结构1.4栈和队列1.5线性链表1.6树和二叉树1.7查找技术1.8排序技术2.1程序设计方法和风格2.2结构化程序设计2.3面向对象的程序设计3.1软件工程基本概念3.2结构化分析方法3.3结构化设计方法3.4软件测试3.5程序的调试4.1数据库系统的基本概念4.2数据模型4.3关系代数4.4数据库设计与管理现在学习的是第2页，共21页1.1算法算法算法算法：是指解决方案解决方案的准确而完整的描述算法的有穷性有穷性：是指算法必须能在有限的时间有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的复杂度 时间时间复杂度执行算法所需的计算工作量计算工作量 （用基本运算的次数来度量）（用基本运算的次数来度量）两者不相关两者不相关空间空间复杂度执行算法所需的内存空间内存空间算法必须有一个或一个以上的输出算法必须有一个或一个以上的输出必须有输出必须有输出 可以没有输入可以没有输入现在学习的是第3页，共21页1.2数据结构的基本概念数据结构的基本概念数据结构：是指相互有关联的数据元素的集合数据的逻辑逻辑结构：就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间关系的，是独立于计算机独立于计算机的数据的存储存储结构：是研究数据与数据元素之间的关系如何在计算机中表示在计算机中表示的 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构存储结构（也称数据的物理结构）各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的逻辑结构与存储结构之间不是一一对应的逻辑结构与存储结构之间不是一一对应的 根据数据结构中各数据元素之间前后件关系的复杂程度，分为：线性结构：线性结构：满足条件满足条件 一对一关系一对一关系 (1)有且只有一个根结点有且只有一个根结点 (2)每一个结点最多有一个前件，也最多有一个后件 (3)在一个线性结构中插入或删除任何一个结点后还应是线性结构 如：循环链表、双向链表非线性结构非线性结构：一对多或多对一关系一对多或多对一关系Eg.线性表是最简单呢、最常用的一种数据结构 线性表的顺序存储结构和链式存储结构 两者比较现在学习的是第4页，共21页1.6树与二叉树树与二叉树术语术语 父结点：每个节点只有一个前件 根结点：没有前件的结点只有一个 子节点：每个结点可以有多个后件 叶子结点：没有后件 结点的度结点的度：一个结点所拥有的后件个数 树的深度树的深度：树的最大层次什么是二叉树？（树，非线性结构）非空二叉树只有一个根结点每一个结点最多有两颗子树，且分别称为该结点的左子树与右子树二叉树通常采用链式存储结构性质性质 现在学习的是第5页，共21页1.7查找技术查找技术顺序查找顺序查找最坏情况下查找n n次次无序表只能采用顺序查找有序线性表，若为链式存储结构，只能采用顺序查找二分法查找二分法查找只适用于顺序存储的有序表最坏情况下查找2n次次现在学习的是第6页，共21页1.8排序技术排序技术交换类排序法1.冒泡冒泡排序法：相邻两元素的交换 最坏情况下，比较n(n-1)/22.快速快速排序法：分割 最坏情况下，比较n(n-1)/2插入类排序法1.简单插入排序法：无序 插入 有序 最坏情况下，比较n(n-1)/22.希尔排序法：分割插入选择排序法1.普通选择排序法：选最小放最前面2.堆堆排序法 最坏情况下，比较n2n 现在学习的是第7页，共21页2.2结构化程序设计结构化程序设计结构化程序设计的原则(比较)1.自顶向下2.逐步求精逐步求精3.模块化4.限制使用goto语句结构化程序设计的基本结构顺序结构、选择结构、重复（循环）结构结构化程序设计的特点：易读性易读性现在学习的是第8页，共21页2.3面向对象的程序设计面向对象的程序设计对象对象标识唯一性分类性多态性封装性模块独立性（信息隐蔽）没有：一致性没有：一致性消息消息消息是一个实例与另一个实例之间传递的信息现在学习的是第9页，共21页3.1软件危机与软件工程软件危机与软件工程软件危机软件危机软件需求的增长得不到满足软件开发的成本和进度难以控制软件质量难以保障软件不可维护或维护程度非常低软件的成本不断提高软件开发生产率的提高赶不上硬件的发展和应用需求的增长没有：软件过程不规范没有：软件过程不规范软件工程软件工程现在学习的是第10页，共21页软件工程软件工程软件工程软件工程，强调在软件开发过程中需要应用工程化原则3要素要素：方法、工具、过程没有：环境没有：环境软件生命周期生命周期：定义阶段、开发阶段、维护阶段软件工程的原则（原则（比较）抽象（自顶向下）没有：自底向上没有：自底向上信息隐蔽模块化局部化确定性一致性完备性可验证性现在学习的是第11页，共21页软件生命周期软件生命周期定义阶段 可行性研究初步项目计划 需求分析开发阶段 概要设计 详细设计 实现 测试维护阶段 使用 维护 退役现在学习的是第12页，共21页需求分析需求分析定义阶段定义阶段需求分析阶段的工作需求获取获取需求分析分析编制需求规格说明书需求规格说明书需求评审评审需求分析方法结构化分析方法 数据流图（DFD）、数据字典（DD）、判断树、判断表面向对象的分析方法需求分析阶段的最后成果：软件需求规格说明书软件需求规格说明书现在学习的是第13页，共21页软件设计（概要、详细设计）软件设计（概要、详细设计）开发阶段开发阶段概要设计概要设计(总体结构设计)主要任务：建立软件系统的总体结构详细设计详细设计常用过程设计工具有：图形工具：程序流程图（PFD）、N-S、PAD（问题分析图）、HIPO表格工具：判定表语言工具：PDL（过程设计语言、结构化的英语和伪码）软件设计基本原理（比较）抽象模块化信息隐蔽模块独立（内聚性、耦合性）现在学习的是第14页，共21页软件测试软件测试开发阶段开发阶段软件调试软件调试维护阶段维护阶段软件测试测试是为了发现错误发现错误而执行程序的过程软件调试调试的任务是诊断诊断和改正改正程序中的错错误误测试：白盒测试：白盒（结构或逻辑）测试，以程序的内内部部逻辑和指定的覆盖标准确定测试数据。黑盒（功能或数据驱动）测试现在学习的是第15页，共21页顺序存储结构顺序存储结构线性表中所有元素所占的存储空间是连续的存储空间是连续的线性表中的各数据元素在存储空间中是按逻辑顺序依次存放按逻辑顺序依次存放的线性表是线性结构线性结构现在学习的是第16页，共21页链式存储结构链式存储结构链式存储结构 线性链表 循环链表存储数据结构的存储空间可以不连续可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致可以不一致，而数据元素之间的逻辑关系是由指针域来确定。既可用于表示线性结构，也可用于表示非线性结构 线性链表线性链表 循环链表循环链表 现在学习的是第17页，共21页顺序存储结构与链式存储结构的比较顺序存储结构与链式存储结构的比较顺序：(小线性表)链式（大线性表）必须占用整块空间 不要求整块空间栈栈 队列队列插入与删除运算都只在线性表的一端一端进行 在一端一端进行插入，而另一端另一端进行删除允许插入和删除 具有记忆作用“先进后出先进后出”或或“后进先出后进先出”“”“先进先出先进先出”顺序 带链带链的栈，带链带链的队列 数据域 指针域顺序存储结构一般小于链式存储结构现在学习的是第18页，共21页二叉树二叉树性质一性质一在二叉树的第K层上，最多有2(k-1)个结点性质二性质二深度为m的二叉树最多有(2m)-1个结点性质三性质三在任意一颗二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个性质四性质四具有n个结点的二叉树，其深度至少为2n+1现在学习的是第19页，共21页结构化程序设计原则与软件工程原则的比较结构化程序设计原则与软件工程原则的比较结构化程序设计的原则 软件工程的原则原则：1.自顶向下 抽象（自顶向下）2.逐步求精逐步求精 信息隐蔽3.模块化 模块化4.限制使用goto语句 局部化 确定性软件设计基本原理 一致性一致性抽象 完备性模块化 可验证性信息隐蔽模块独立（内聚性、耦合性）1结构2工程3设计现在学习的是第20页，共21页结构化分析方法结构化分析方法结构化设计方法结构化设计方法分析分析方法数据流图数据流图（DFDData Flow Diagram）加工 存储文件 数据流数据流 源,潭 没有：控制流没有：控制流设计设计方法程序流程图程序流程图 控制流控制流 逻辑条件 加工数据模型 E-RE-R模型模型(逻辑设计阶段逻辑设计阶段)实体实体 属性属性 联系联系 1分析2.设计现在学习的是第21页，共21页