企业培训_微固讲师团二级c公共基础知识

公共基础知识 电科三班刘扬 数据结构与算法软件工程基础数据库设计基础程序设计基础 数据结构与算法 重点 栈 队列 二叉树 排序与查找难点 主要集中在二叉树 考核形式包括给出前序 中序遍历 求后序遍历等问题 满二叉树和完全二叉树的结点问题 栈限定在一端进行插入与删除的线性表 其允许插入与删除的一端称为栈顶 不允许插入与删除的另一端称为栈底 栈按照 先进后出 或 后进先出 组织数据 栈的存储方式有顺序存储和链式存储栈的基本运算 1 入栈运算 2 退栈运算 删除元素 3 读栈顶元素 栈顶 栈的输入序列为1 2 3 n 1 n 输出序列的第一个元素为n 则第i个元素为 A n i 1B n 1C iD 那个元素都无所谓 A 假设用一个长度为50的数组 数组元素的下标从0到49 作为栈的存储空间 栈底指针bottom指向栈底元素 栈顶指针top执向栈顶元素 如果bottom 49 top 30 数组下标 则栈具有 个元素 2009 3 元素个数为栈底元素下标 栈顶元素下标 1 20 队列指允许在一端 队尾 进入插入 而在另一端 队头 进行删除的线性表 队列是 先进先出 或 后进后出 的线性表 队列运算包括 1 入队运算 2 退队运算计算循环队列的元素个数 尾指针减头指针 若为负数 再加其容量即可 某循环队列的容量为50 头指针front 5 指向队头元素的前一位置 尾指针rear 29 指向队尾元素 则该循环队列中共有 个元素 2008 4 当frontrear时 循环队列中元素的个数为 N front rear 其中N为循环队列的容量 24 根 节点 子树叶子 没有后继节点 或终端节点 分支节点 非叶子节点 或非终端节点 树的度 树中各节点的度的最大值节点的层次 根节点的层次为一 其他任何层数等于它的父节点的层数加一树的深度 节点的最大层次值 二叉树的特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 满二叉树是指除最后一层外 每一层上的所有结点有两个子结点 则k层上有2k 1个结点 深度为m的满二叉树有2m 1个结点 完全二叉树是指除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 二叉树的性质 1 在二叉树的第k层上 最多有2k 1 k 1 个结点2 深度为m的二叉树最多有2m 1个结点 3 度为0的结点 即叶子结点 总是比度为2的结点多一个 即 n0 n2 14 具有n个结点的二叉树 其深度至少为 log2n 1 其中 log2n 表示取log2n的整数部分 具有n个结点的完全二叉树的深度为 log2n 1 深度为5的满二叉树有 个叶子结点 具有88个节点的二叉树 其深度至少为 某二叉树有5个度为2的结点 则该二叉树中叶子结点的个数为 对于一个非空的二叉树 叶子结点个数 度为2的结点个数 1 6 二叉树存储结构采用链式存储结构 对于满二叉树与完全二叉树可以按层序进行顺序存储 二叉树的遍历 1 前序遍历 DLR 首先访问根结点 然后遍历左子树 最后遍历右子树 2 中序遍历 LDR 首先遍历左子树 然后访问根结点 最后遍历右子树 3 后序遍历 LRD 首先遍历左子树 然后访问遍历右子树 最后访问根结点 根左右 左根右 左右根 如图 二叉树进行前序遍历的结果为 2006 4 ABDYECFXZ voidpreorder bnode BT if BT NULL return else visit BT if BT LC NULL preorder BT LC if BT RC NULL preorder BT RC 查找技术 二分法查找 设有序线性表的长度为n 被查找的元素为x 则二分法查找的方法如下 1 将x与线性表的中间项比较 2 若x的值与中间项的值相等 则说明查到 查找结束 3 若x小于中间项的值 则在线性表的前半部分以相同的方法查找 4 若x大于中间项的值 则在线性表的后半部分以相同的方法查找 顺序查找 从表中的的第一个元素开始 将给定的值与表中逐个元素的关键字进行比较 直到两者相符查到所要找的元素为止 负责就是表中没有要找的元素 查找不成功 二分法查找只适用于顺序存储线性表 对于无序线性表和线性表的链式存储结构只能用顺序查找 有一个有序表 2 4 6 14 34 40 45 62 75 78 82 95 110 当用二分法查找值为82的结点时 次比较后能查找成功 4 intlow high mid mid low high 2 交换类排序法 1 冒泡排序法 需要比较的次数为n n 1 2 2 快速排序法 插入类排序法 1 简单插入排序法 最坏情况需要n n 1 2次比较 2 希尔排序法 时间复杂度为O n1 5 次比较 选择类排序法 1 简单选择排序法 最坏情况需要n n 1 2次比较 2 堆排序法 时间复杂度为O nlog2n 相比以上几种 除希尔排序法外 堆排序法的时间复杂度最小 排序技术 下列排序方法中 最坏情况下比较次数最少的是 2007 4 A 冒泡排序B 简单选择排序C直接插入排序D 堆排序 D 软件工程基础 重点 软件工程与软件生命周期的概念 结构化设计方法中的软件设计原理 软件测试与软件调试的概念与方法 软件工程概述 计算机软件是计算机系统中与硬件相互依存的一部分 包括程序 数据及相关文档的完整集合软件按功能可以分为应用软件 系统软件和支撑软件 或工具软件 例如教务管理系统属于应用软件 操作系统属于系统软件 汇编程序与编译程序属于支撑软件 或工具软件 软件工程是应用于计算机软件的定义 开发和维护的一整套方法 工具 文档 实践标准和工序 简单的说就是使软件走向工程化 软件工程的核心思想是把软件产品看作是一个工程产品来处理 软件工程包括3个要素 方法 工具和过程 软件工程的理论和技术性研究的内容主要包括 软件开发技术和软件工程管理 软件开发技术包括 软件开发方法学 开发过程 开发工具和软件工程环境 软件是指 2007 9 A 程序B程序和文档C算法加数据结构D程序 数据及相关文档的完整集合 D 软件的生存周期 一个软件从用户提出开发要求 到软件在使用中消退的全过程软件的生存周期分为三个阶段 制定计划 开发 运行的维护计划时期 主要任务是分析用户需求 分析软件系统所追求的目标 分析开发系统的可行性开发时期 包括设计和实现两个任务 其中设计包括需求分析和设计两个阶段 实现包括编程和测试两个阶段运行与维护 软件的生命周期可分为多个阶段 一般分为定义阶段 开发阶段和维护阶段 编码和测试属于 开发阶段 软件测试定义 使用人工或自动手段来运行或测定某个系统的过程 其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别 软件测试的目的 发现错误而执行程序的过程 软件测试方法 静态测试和动态测试 软件测试过程一般按4个步骤进行 单元测试 集成测试 验收测试 确认测试 系统测试 软件测试 程序设计分为静态分析和动态分析 其中 是指不执行程序 而对程序文本进行检查 通过阅读和讨论 分析和发现程序中的错误 2006 4 静态测试 指人工评审软件文档或程序 借以发现其中的错误 动态测试 基于计算机的测试 为了发现错误而执行程序的过程 静态分析 动态测试的设计测试实例方法 白盒测试法 根据程序的内部逻辑来设计的 主要用于软件的单元测试 主要方法有逻辑覆盖和基本路径测试等黑盒测试法 是对程序功能的测试 主要用于软件的确认测试 主要方法有等价类划分法 边界值分析法和错误推测法 软件测试分为黑盒测试和白盒测试 等价划分法属于 测试 2008 9 软件测试可分为黑盒测试和白盒测试 基本路径测试属于 测试 2009 3 黑盒 白盒 程序调试的任务是诊断和改正程序中的错误 主要在开发阶段进行 程序调试的基本步骤 1 错误定位 2 修改设计和代码 以排除错误 3 进行回归测试 防止引进新的错误 软件调试可分为静态调试和动态调试 主要调试方法有 1 强行排错法 2 回溯法 3 原因排除法 程序的调试 软件设计的基本原理 软件设计的基本原理包括抽象 模块化 信息隐蔽和模块独立性模块独立性 是指软件系统中每个模块只涉及软件要求的具体子功能 它和软件系统中的其他模块的接口是简单的 例如 若一个模块只具有单一的功能且与其他模块没有太多的联系 那么称此模块具有模块独立性 模块的耦合性和内聚性是衡量软件模块独立性的两个定性指标耦合性是指模块间互相联系的紧密程度 内聚性是指一个模块内部各个元素间彼此结合的紧密程度 一个设计良好的软件系统应该具有高内聚 低耦合的特征 耦合性和内聚性是对模块独立性度量的两个标准 下列叙述正确的是 2009 3 A 提高耦合性降低内聚性利于提高模块的独立性B 降低耦合性提高内聚性利于提高模块的独立性C 耦合性是指一个模块内部各个元素间彼此结合的紧密程度D 内聚性是指模块间互相联系的紧密程度 B 数据库设计基础 重点难点 数据库系统的基本概念 数据独立性 层次模型 关系模型以及E R图的表示 此外还有笛卡尔积运算 数据库设计方法和步骤 在数据库系统中需要对数据进行集中 统一的管理 已达到数据被多个应用程序共享的目标 数据库技术的的根本目标是解决数据的共享问题 数据库系统 DBS 是由数据库 DB 数据库管理系统 DBMS 数据库管理人员 人员 系统平台之一 硬件平台 硬件 系统平台之二 软件平台 软件 五个部分构成 数据库系统的核心是数据库 DB 数据库系统的基本概念 数据库 DB 数据库系统 DBS 数据库管理系统 DBMS 之间的关系是 A DB包含DBS和DBMSB DBMS包含DB和DBSC DBS包含DB和DBMSD 没有任何关系 C 数据库系统的基本特点 数据的集成性 数据的高共享性与低冗余性 数据独立性 物理独立性与逻辑独立性 数据统一管理与控制 数据的独立性 物理独立性和逻辑独立性 物理独立性 指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 也就是说应用程序要处理的是数据的逻辑结构 这样即使当数据的物理存储结构改变了 应用程序也不变逻辑独立性 指用户的应用程序与数据库的逻辑结构是相互独立的 也就是说 数据的逻辑结构即使改变了 用户程序也可以不变 数据独立性分为逻辑独立性和物理独立性 当数据存储结构改变时 其逻辑结构可以不变 因此 基于逻辑结构的应用程序不必修改 称为 2006 9 物理独立性 数据库系统的三级模式 1 概念模式 数据库系统中全局数据逻辑结构的描述 全体用户公共数据视图 2 外模式 也称子模式与用户模式 是用户的数据视图 也就是用户所见到的数据模式 3 内模式 又称物理模式 它给出了数据库物理存储结构与物理存取方法 在数据库系统中 用户所见的数据模式为 2006 9 A 概念模式B 外模式C 内模式D 物理模式 B 数据模型 数据模型可以按照不同的应用层次分为三种类型概念数据模型 E R模型 拓展的E R模型 面向对象模型以及谓词模型等逻辑数据模型 层次模型 网状模型 关系模型和面向对象模型物理数据模型 E R模型 E R模型是一种广泛使用的概念数据模型 该模型将现实世界的要求转化为实体 联系和属性等几个基本概念 以及他们之间的两种基本联系 并可以用一种直观图形表示出来 E R模型的基本元素是实体 联系和属性 实体 现实世界中的事物可以抽象为实体 实体是概念世界中的基本单位 它是客观存在的且又能相互区别的事物 属性 现实世界中事物均有一些特性 这些特性可以用属性来表示 属性刻画了实体的特征 联系 实体内部的联系和实体之间的联系 联系也是实体 两个实体集之间的联系实际上是实体集之间的函数关系 这种函数关系可以由以下三种 1 一对一 实体集A中的每一个实体 实体B中至多有一个 也可以没有 实体与之联系 反之亦然 2 一对多或多对一 实体A中的每一个实体 实体B中有m m不小于0 与之联系 反之 实体集B中的每一个实体 实体A中至多有一个与之联系 3 多对多 实体集A中的每一个实体 实体B中有n个实体与之联系 反之 体集B中的每一个实体 实体B中有m个实体与之联系 一件宿舍可住多个学生 则实体宿舍与学生之间的联系是 2008 9 A 一对一B一对多C多对一D多对多 B E R型的图示法 E R模型可以用一种非常直观的图的形式来表示 这种图称为E R图 用不同的几何图形表示E R模型中的三个概念与两个联系之间的关系1 实体集 用矩形表示 矩形内写上该实体集的名字 2 属性 用椭圆表示 再椭圆中写上该属性的名称3 联系 用菱形表示 在菱形内写上联系名 4 实体集 联系 与属性之间的关系 用无向线段表示 在E R图中 用来表示实体的图形是 2006 4 在E R图中 用来表示实体之间的联系的图形是 2007 4 矩形 无向线段 关系模型 关系模型是目前最重要的一种逻辑模型 其每个关系都类似一张表 或者在某种程度上类似于一个 平面 记录文件 关系模型采用二维表来表示 关系数据模型的主要术语关系 一个关系就是一张二维表元组 表中的一行称为一个元组属性 表中的一列称为关系的一个属性 即元祖的数据项关系模式 对一个关系的结构描述 每个描述包括关系名 关系代数 传统关系运算 1 并 由属于R或属于S的元组组成的集合 2 差 R与S的差是由属于R但是不属于S的元组构成的集合 3 交 有属于R且属于S的元组构成的集合 4 广义笛卡尔积 设关系R和S的属性个数分别为m n 则R和S的笛卡尔积是一个有 m n 列的元组的集合 每个元组的前n列来自R的一个元组 后m列来自S的一个元组 记为R S 专门的关系运算 1 选择 选择运算是在关系中选择满足某些条件的元组 即消去某些行 2 投影 投影运算是在关系中选择默写属性列 即消去某些列 3 链接 其含义是在关系R和S的广义笛卡尔积R S中 选取R关系在A属性组上的值与S关系在B属性上的值满足比较关系 的元组 链接分为等值链接和自然连接等值连接当连接条件中的比较运算符 为 时 称为等值连接自然连接是一种较特殊的等值连接 它要求连接时两个关系中进行比较的分量必然是相同属性组 且在结果中将相同的属性列去掉 设如图所示的三个关系表 则下