导图社区 计算机公共基础
- 28
- 1
- 1
- 举报
计算机公共基础
这是一个关于计算机公共基础的思维导图，包含数据结构与算法、程序设计基础、数据库设计基础、软件工程基础等。
编辑于2024-03-12 21:47:43- 软件工程
- 计算机二级
- 相似推荐
- 大纲
计算机公共基础
1. 数据结构与算法
1. 算法
1. 算法的定义
1. 解题方案的准确而完整的表述（算法不等于程序，程序的编制不可能优于算法的设计） 简单来说：算法就是为了解决一个问题而采取的方法和步骤
2. 算法的基本特征
2. （1）可行性 ：在现有的环境和条件下是可以实现的，算法对于计算机的可行性是指对于计算机硬件上通过运行能够得到正确的结果 （2）确定性 ： 算法中的每个步骤必须是明确定义的，不允许模棱两可，每个步骤必须有含义，且不能有异意 （3）有穷性 ：算法必须在有限的时间内做完，必须在执行有限个步骤后终止，不能出现死循环 （4）足够的情报： 算法要有一定的输入数据和输出数据
3. 算法的基本要素
3. （1）对数据对象的运算和操作 算术运算、逻辑运算、关系运算、数据传输 （2）算法的控制结构： 1）算法中各操作之间的执行顺序 2）描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等 3）一个算法一般可以用顺序、选择（分支）、循环（重复）三种基本结构组合而成
4. 算法的时间和空间复杂度
4. （1）时间复杂度： 是指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量 （2）空间复杂度： 是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间 （3）算法的时间复杂度和算法的空间复杂度相互独立
2. 数据结构的基本概念
1. 数据
1. （1）数据： 需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征 1）数据元素是数据的基本单位，即数据集中的个体 2）有时一个数据元素可有若干个数据项组成，数据项是数据的最小单位
2. 结构
2. 是集合中各个数据元素之间存在的某种关系（或联系）
3. 数据结构
3. 是指相互关联的数据元素的集合
1. 数据结构的分类
1. （1）逻辑结构： 线性结构（线性表、栈、队列）；非线性结构（数、图） （2）存储结构： 顺序存储、链式存储 （3）运算：插入、删除、查找、排序
1. 逻辑结构
1. 反应数据元素间的逻辑关系（即前后件关系）的数据结构，逻辑结构与所使用的计算机无关
1. 线性结构 有序
1. （1）线性结构（线性表）： eg：春--->夏--->秋---->冬 1）有且仅有一个根节点，它无前件 2）每一个节点最多有一个前件，也最多有一个后件 （2）线性表是线性结构中的一种
1. 线性表
1. 线性表的含义
1. （1）线性表的含义 线性表示n（n>=0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件 eg： 英文字母表，地理学中的四向，表格
2. 线性表的顺序存储结构
1. 顺序表
1. （1）通常，线性表可以采用顺序存储和链式存储，但一般使用顺序存储结构。线性表的顺序存储有叫做顺序表（顺序分配） （2）特点： 1）线性表中所有元素所占的存储空间是连续的 2）线性表中数据元素在存储空间中是按逻辑顺序依次存放的 3）可以随机访问数据元素 4）当插入、删除时需要移动大量元素，因此线性表不便于插入和删除元素
3. 线性表的链式存储结构
3.
1. 线性链表
1. （1）线性表可以采用顺序存储和链式存储。线性表的顺序存储叫做顺序表，线性表的链式结构叫做线性链表。线性表的链式存储结构中的每个节点上都至少包含一 个指针域 （2）特点： 1）各数据节点的存储空间可以不连续 2）各数据元素的存储顺序和逻辑顺序可以不一致 3）线性表的链式存储所占存储空间大于顺序存储结构 4）查找节点时链式存储要比顺序存储慢 5）链式存储插入、删除元素要比顺序存储灵活 （3）线性链表的操作： 在线性链表中进行插入与删除，不需要移动链表中的元素 （4）eg：
2. 双向链表
2.
3. 循环链表
3.
4. 栈和队列
1. 栈
1. （1）含义：栈是限定与一端进行插入和删除的线性表 （2）特点： 1）栈是只能在栈顶进行插入和删除 2）栈的修改原则是“先进后出”或“后进先出” 3）栈底指针bottom，栈顶指针top，入栈（栈顶指针向上移动），栈满，出栈（栈顶指针向下移动） 4）栈底指针不变，栈中元素随栈顶的变化而动态变化 5）栈具有记忆功能 6）栈支持子程序调用 （3）eg：
2. 队列
2. （1）含义：队列是指允许在一端进行插入，而在另一端进行删除的线性表 （2）特点： 1）队列只允许在队尾进行插入，而在队头进行删除 2）队列的修改原则是“先进先出”或“后进后出” 3）队列指针front，队尾指针rear，入队，出队 4）队列中元素随队头指针和队尾指针的变化而动态变化
3. 循环队列
3. （1）含义：循环队列就是将存储空间的最后一个位置绕道第一个位置，形成逻辑上的环状空间，是一种线性结构 rear＞front：s=rear-front（s表示队列中的元素个数） rear＜front：s=容量+rear-front rear=front：s=1或者s=0
2. 非线性结构 无序
2. （1）非线性结构： 1）不满足线性结构的两个基本条件的数据结构就叫做非线性结构 2）非线性结构主要是指树形结构和网状结构
1. 树
1. （1）含义： 是n(n>0)个元素的有限集合。它有且仅有一个称为根的元素；其余元素是互不相交的子树 （2）常用术语： 1）父结点、子结点 2）根结点、叶子结点 ： 没有前件的结点叫做根结点，没有后件的结点叫做叶子结点 3）结点的度、树的度： 结点的度就是一个结点的后件数，树的度为所有结点的度的最大值 4）树的深度： 简单理解有几层（有几代） 5）子树： 以某个节点的第一个子节点为根构成的树称为该节点的一个子树
1. 二叉树
1. （1）二叉树含义： 1）是一个有限的节点集合，该集合或者为空，或者有一个根节点及其两颗互不相交的左右二叉树所组成 2）二叉树与一般的树相比，在结构上具有规范性和确定性 3）树的每一个结点上的度不同会使得存储起来比较困难，对树的处理运算更加复杂，为此引出了二叉树 （2）二叉树的特点： 1）非空二叉树只有一个根结点 2）每一个结点最多有两颗子树，且分别称为该节点的左子树与右子树，次序不能任意颠倒 （3） 二叉树的五种基本形态： 1）空二叉树 2）只有一个结点的二叉树 3）只有左子树的二叉树 4）只有右子树的二叉树 5）左右子树双全的二叉树
1. 特殊二叉树
1. 满二叉树
1. （1）含义：除最后一层外，每一层上的结点树达到最大值（除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树）
2. 完全二叉树
2. （1）标准定义： 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i 的 结点 在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 （2）简单理解：除最后一层和倒数第二层左边外，其余层的结点树达到最大值（只缺少倒数第二层的右边若干结点） （3）注意：完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树
2. 非空二叉树的特点
2. （1）非空二叉树含义： 非空二叉树只有一个根结点，每个结点最多有两颗子树，分别称为左子树和右子树 （2）特点： 1） 在二叉树的第K层上，最多有2 **（k-1)个结点 （针对某一层结点数） 2）深度为m的二叉树最多有（2*m - 1）个结点： （针对总的结点数） 3）度为0的结点（叶子结点）总比度为2的结点多一个 4） 有n个结点的二叉树深度至少为[log2n]+1（向下取整） eg：
3. 二叉树的遍历
3. （1）认识: （2）eg：
1. 前序遍历 根左右
1. eg：
2. 中序遍历 左根右
3. 后序遍历 左右根
3. eg：
2. 存储结构
2. 存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空间的存放方式。数据的存储结构与数据处理的效率密切相关 注意：一种逻辑结构可以有多种存储结构；不同的存储结构其数据处理的效率不同
1. 顺序存储结构
1. （1）顺序存储结构： 主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里
2. 链式存储结构
2. （1）链式存储结构： 每一个节点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系
3. 运算
3. （1）运算：插入、删除、查找、排序
1. 数据的查找
1. eg：
1. 顺序查找
1. （1）顺序查找： 逐个将线性表中的元素与被查找的元素进行比较 对于长度为n的线性表，最好情况进行1次比较，最坏情况进行n次比较，平均要进行 n/2次比较 顺序查找适用于无序表或线性表（不管无序还是有序）
2. 二分查找（折半查找）
2. （1）二分查找： 适用于顺序存储的有序表，对长度为n的线性表，在最坏的情况下进行log2 n次比较 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找
2. 数据的排序
2. （1）： （2）eg：
1. 交换类
1. 冒泡排序
2. 快速排序
2. （1）基本思想： 1）在要排序中找一个数作为基准数（通常为第一个数） 2）通过交换将这个序列中所有比基准数大的放在有边，比基准数小的数放在左边 3）以基准数作为分割线分为两个子表，对两个子表重复上述步骤
2. 插入类
1. 插入排序
2. 希尔排序
3. 选择类
1. 选择排序
1. （1）选择排序： 从n个元素中选择最小值，如果它不在第一位，就将它与第一位的数字进行交换 （2）eg：
2. 堆排序
2. 程序设计基础
1. 程序设计方法与风格
1. 良好的程序设计风格
1. 清晰第一，效率第二
2. 如何形成良好的程序设计风格
2. （1）源程序内部文档化（可以生成一些内部文档，帮助阅读、理解） （2）数据说明（有一定的注释） （3）语句的结构（程序正确，尽可能模块化） （4）输入和输出
3. 源程序内部文档化
3. （1）选择标识符的名字 （2）注释（序言性和功能性注释）： <1>序言性注释一般位于模块的首部，用于说明模块的相关信息（标题、功能的说明、主要的算法、模块接口、开发历史、程序设计者、复审者和复审日期） <2>功能性注释位于源程序模块内部 （3）程序的视觉组织
2. 结构化程序设计
2. （1）eg：
1. 结构化程序设计原则
1. （1）自顶向下：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标 （2）逐步求精：对复杂问题，先设计一个目标作为过渡，然后逐步细化 （3）模块化：把程序要解决的总目标分解为一个一个的模块 （4）限用goto: 限制使用goto语句（实现跳转功能），程序的质量与goto语句数量成反比
2. 结构化程序的基本结构
2. 结构化程序常采用顺序、选择（分支）和循环（重复）三种基本结构
3. 程序设计语言的基本成分
3. 数据成分、运算成分、控制成分和传输成分
3. 面向对象的程序设计
3. （1）eg：
1. 几个术语
1. （1）对象：在现实世界中，每个实体都是对象（例如大学生、汽车、电视机、空调等） （2）属性：用于描述对象的状态 （3）方法：用于描述对象的行为 （4）类：类是一组具有相同属性和相同操作的对象的集合（基于同一类产生的对象可以分别设置各自的属性）
2. 对象的基本特点
2. （1）标识唯一性：对象可由内在本质区分，而不是通过描述来区分 （2）分类性：可以将具有相同属性和操作的对象抽象成类 （3）多态性：同一操作可以是不同对象的行为 （4）封装性：从外面看不到对象的内部，只能看到对象的外部特征 （5）模块独立性好：对象是面向对象的软件的基本模块，内聚性强
3. 继承
3. 使用已有的类建立新类的定义技术。能直接获得已有的性质，不必重复定义
4. 消息
4. （1）含义：是一个实例与另一个实例之间传递的消息。对象间的通信靠消息传递 （2）组成：接收消息的对象的名称（eg：小王）；消息标识符（也称消息名）（eg：吃饭）；零个或多个参数（eg：食堂，8点
5. 多态性
5. 是指同样的消息被不同的对象接收时可导致完全不同的行动的现象
3. 软件工程基础
3.
1. 软件工程基本概念
1. （1）eg：
2. 结构化分析方法 做什么
2. （1）结构化分析方法： 1）需求分析方法有： 结构化需求分析方法和面向对象的需求分析 2）结构化分析方法：在需求分析阶段，使用数据流程图（DFD）、数据字典（DD）、判断表和判定树工具，来建立系统的逻辑模型 （2）eg：
1. 数据流图（DFD）
1. （1）数据流图的图形元素： <1> 〇 加工：输入数据经加工变换产生输出 <2> → 数据流：沿箭头方向传递数据的通道 <3> ＝ 存储文件（数据源）：存放各种数据的文件 <4> □ 源（潭）：系统和环境的接口 （2）数据字典（DD）是对数据流图中所有元素定义的集合，是结构化分析的核心
3. 结构化设计方法 怎么做
3. （1）软件分析是确定系统的逻辑模型，软件设计是确定系统的物理模型 软件设计的目标是用比较抽象概括的方法确定目标系统如何完成预定的一个任务 （2）eg：
1. 软件设计的划分
1. （1）从工程管理角度划分：概要设计、详细设计 （2）按技术观点划分：结构设计、数据设计、接口设计、过程设计
2. 软件设计基本原理
2. （1） 抽象：在软件设计中，可以定出多个抽象级别，抽象层次从概要设计到详细设计逐步降低 （2） 模块化：把一个待开发的软件分解成若干小的简单的部分，自顶向下逐层把软件换分成若干模块 （3） 信息隐蔽：一个模块内的信息，对于不需要这些信息的其他模块来说不能访问 （4） 模块独立性：每个模块只完成独立的子功能，并且与其他模块的联系少且接口简单。模块的独立程度是评价设计好坏的重要度量标 准（高内聚，低耦合）
3. 软件模块独立性
3. （1）内聚性：指一个模块内部各个元素件彼此结合的紧密程度（高内聚） （2）耦合性：指模块间相互连接的紧密程度（低耦合） （3）耦合的种类：非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合、内容耦合 (由弱到强)
4. 概要设计
4. （1）概要设计的任务： <1>设计软件系统结构 <2>数据结构及数据库设计 <3>编写概要设计文档 <4>概要设计文档评审 （2）概要设计的工具是程序结构图（SC）
5. 详细设计
5. （1） 详细设计的任务：确立每个模块的实现算法和局部数据结构，用适当方法标识算法和数据结构的细节。 （2） 详细设计的常用工具： <1>图形工具：程序流程图、N-S图、PAD、HIPO <2>表格工具：判定表 <3>语言工具：PDL（伪码）
6. 程序流程图的基本图符
6. （1） 控制流：表示为→或↓ （2） 加工步骤：表示为□ （3） 逻辑条件：表示为◇
4. 软件测试 发现错误
4. （1）软件测试： 1）软件测试的目的：发现开发程序中的错误 2）软件测测试的准则： <1>所有测试都应追溯到用户需求 <2>在测试之前指定测试计划，并严格执行 <3>充分注意测试中的群集现象 <4>避免由程序的编写者测试自己的程序 <5>不可能进行穷举测试 <6>妥善保存测试分析报告，为维护提供方便 （2）eg：
1. 静态测试和动态测试
1. （1）静态测试： 不实际运行软件，通过人发挥思维优势发现程序的错误（软件不执行） （2）动态测试： 基于计算机的测试，是为了发现错误而执行的过程（软件执行）
2. 白盒测试和黑盒测试：（功能划分）
2. （1）白盒测试：把测试对象看做一个打开的盒子，利用程序内部的逻辑结构，对程序所有逻辑路径进行测试（针对程序的内部逻辑结构） <1> 逻辑覆盖测试 <2> 基本路径测试 （2）黑盒测试：完全不考虑程序内部的逻辑结构，只检查程序是否能接收输入数据并产生正确的输出信息（针对程序的外部功能） <1>等价类划分法 <2> 边界值分析法 <3>错误推测法
3. 软件测试步骤（顺序不可换
3. （1）单元测试：是对软件的最小单位——模块进行测试，目的是发现模块内部的错误 （2）集成测试：是把模块按照设计要求组装起来的同时进行测试，目的是发现与接口有关的错误 （3）确认测试：是验证软件功能和性能是否满足各种要求，以及软件配置是否完全、正确 （4）系统测试：是将一个软件作为一个元素，与计算机系统其他元素组合在一起，进行集成测试
5. 程序的调试 改正错误
5. （1）程序调试： 1）对程序进行了成功的测试之后将进入程序调试，通常称为Debug（排错），主要在开发阶段进行 2）程序调试的主要任务是诊断和改正程序的错误 3）基本步骤： <1>错误定位： <2>修改设计和代码，以排除错误 <3>进行回归测试，防止引进新的错误 4）软件调试方法：强行排除法，回溯法、原因排除法 （2）eg：
4. 数据库设计基础
1. 数据库设计的基本概念
1. eg：
1. 数据库应用系统（DBAS）
1. 数据库应用系统包括：数据库系统、应用软件以及应用界面
数据库系统（DBS）
（1）组成： 1）数据库（数据）：集成、共享（特点） 2）数据库管理系统DBMS（软件）（核心）：定义、构建、操纵、检查、控制、服务、DDL、DML、DCL（功能与语言） 3）数据库管理员DBA（人员）：设计、维护、改善性能、提高效率（主要工作） 4）软件平台：操作系统，开发工具，软件接口 5）硬件平台：计算机、网络
应用软件
应用界面
2. 数据管理三个阶段
2. （1）三个阶段：人工管理、文件管理、数据库系统 数据库技术的根本目标是：解决数据共享问题
3. 数据库系统特点
3. （1）特点：集成性、高共享低冗余、独立性、统一管理控制
4. 三级模式和两极映射
4. （1）数据库的产品很多，它支持不同的数据模型，使用不同的数据库语言，建立在不同的数据系统上，数据的存储结构也各有不相同， 但它的体系结构基本上有共同的特征，为此采用了三级映射和两级模式来管理数据库内部的系统结构 （2）三级模式： 1）概念模式（概念数据库）：是全体数据的逻辑结构，是全体用户的公共数据视图 2）外模式（子模式 \ 用户模式）：用户的数据视图（用户可以看到、可以使用的局部逻辑结构和特征的描述） 3）内模式（数理模式）：是数据物理存储结构和存储方式的描述，是数据在数据库内部的表示方式 模式的三个级别反映了模式的三个不同环境及其它们的不同要求。其中内模式处于最底层，它反映了数据在计算机结构中的实 际 存储形式；概念模式处于中层，反映了设计者的 数据的全局逻辑要求；外模式处于外层它反映了用户对数据的要求 （3）两级映射： 1）外模式--概念模式之间的映射 2）概念模式与内模式之间的映射 两级映射保证了数据库中数据有较高的逻辑独立性和物理独立性
2. 数据模型
2. （1）三要素：数据结构、数据操作、数据约束 （2）分类：（按照不同的应用层次） 1）概念数据模型（概念模型）：是一种面向客观时间、面向用户的模型，它与具体的数据库管理系统和具体的计算机平台无关，着重与对客观世界复杂事物的描述以及对它们内在联系的刻画。 eg：E-R模型（实体联系模型） 2）逻辑数据模型（数据模型）：是运用的最多的数据模型，是面向数据库系统的模型，着重与数据库的一级实现 eg：层次模型、网状模型、关系模型、面向对象模型 3）物理数据模型（物理模型）：面向计算机物理实现的模型，该模型给出了数据模型在计算机上的物理结构的表示
概念数据模型（概念模型）
E-R（实体联系模型）
（1）实体（长方形表示）：客观存在并且可以相互区别的事物实体 （2）属性（椭圆表示）：描述实体的特征 （3）联系（菱形表示）：实体之间对应的关系。联系的分类：一对一，一对多，多对多 （4）eg：
逻辑数据模型（数据模型）
层次模型（树）
网状模型（无向图）
关系模型（二维表）
（1）关系模型采用二维表来表示，简称表，每一个二维表称为一个关系 （2）属性：二维表中的一列称为属性，属性的个数称为属性元数 （3）元组：二维表中的一行称为元组（一个元组可由若干个元组分量组成，元组分量的个数等于属性元数，分量不可在分） （4）关系操纵：查询、增加、删除、修改 （5）关系中的数据约束： 1）实体完整性约束 2）参照完整性约束 3）用户定义的完整性约束 （6）eg：
物理数据模型（物理模型）
3. 关系代数
3. 关系代数中的五种基本运算：差、并、投影、选择、笛卡尔积运算 eg：
关系模型的基本操作
插入
删除
修改
查询
投影运算 选择列
（1）投影运算是指从关系模型中指定若干个属性组成新的关系 投影选择列 （2）eg：
选择运算 选择行
（1）选择运算是指从关系中找出满足给定条件的元组的操作 选择运算选择行 （2）eg：
笛卡尔积运算 T =R x S
（1）笛卡尔积元素是将两个表中的元素相乘 T = R x S （2）eg：
关系代数的扩充运算
并 T = R + S
（1）求并集 （2）eg：
差 T= R - S
（1）求差集： （2）eg：
交
（1）求交集 （2）eg：
除 T =R / S
（1）eg：从R表中找到完全满足S的行，再删除S表中已有的列
自然拼接
（1）eg：找出R和T共有的列，然后根据列中共同的元素连接，得到的属性可能会增加
4. 数据库设计与管理
4. （1）eg：
数据库设计概述
设计一个能满足用户要求、性能良好的数据库，数据库设计的根本目的是解决数据共享问题 （1）基本任务： 根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式 （2）两种方法： 1）以信息需求为主，兼顾处理需求（面向数据的方法，是主流方法） 2）以处理需求为主，兼顾信息需求（面向过程的方法）
数据库设计的步骤
（1）数据库设计目前一般采用生命周期法，分为若干阶段： 1）需求分析阶段：分析用户的需求，建立数据字典 2）概念设计阶段：分析数据间的语意关联，在此基础上建立数据的抽象模型及它的概念模型，设计E-R图 3）逻辑设计阶段：把E-R图转为关系模式。实体与联系表示成关系，E-R图中属性转换成关系的属性 4）物理设计阶段：数据库在物理设备上的一个存储结构以及它的存取方式 5）编码阶段 6）测试阶段 7）运行阶段 8）进一步修改阶段 在数据库设计中采用前四个阶段，并且重点以数据结构与模型的设计为主线
数据库管理
（1）数据库的建立 （2）数据库的调整 （3）数据库的重组 （4）数据库安全性控制与完整性控制 （5）数据库的故障修复 （6）数据库监控