计算机软件基础知识讲座.ppt

信息科学与技术学院 第三讲计算机软件基础知识 2 1 1算法的基本概念及其特征1 算法 是一组有穷指令集 是解题方案的准确而完整的描述 通俗地说 算法就是计算机解题的过程 2 算法的基本特征 1 可行性 算法中的操作能够用已经实现的基本运算执行有限次来实现 2 确定性 算法中的每一步都有确切的含义 3 有穷性 一个算法在执行有穷步骤后能够结束 4 拥有足够多情报 算法执行过程中要尽可能考虑各种情况 一个算法至少有一个输出 第一部分数据结构与算法 3 3 算法的基本要素 1 对数据对象的运算和操作 2 算法的控制结构4 算法设计基本方法 1 列举法 2 归纳法 3 递推 4 递归 5 减半递推 6 回溯法 第一部分数据结构与算法 4 5 算法复杂度 1 算法的时间复杂度 是指算法所需要的计算工作量 用基本运算次数来衡量 与程序中的执行的指令条数密切相关 2 算法的空间复杂度 是指执行这个算法所需要的内存空间 第一部分数据结构与算法 5 例题 1 算法的时间复杂度是指 A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数 2 算法的空间复杂度是指 A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 算法执行过程中所需要的存储空间 第一部分数据结构与算法 6 3 下列叙述中正确的是 A 算法的效率只与问题的规模有关 而与数据的存储结构无关B 算法的时间复杂度是指执行算法所需要的计算工作量C 数据的逻辑结构与存储结构是一一对应的D 算法的时间复杂度与空间复杂度一定相关 4 下列叙述中正确的是 A 一个算法的空间复杂度大 则其时间复杂度也必定大B 一个算法的空间复杂度大 则其时间复杂度必定小C 一个算法的时间复杂度大 则其空间复杂度必定小D 上述三种说法都不对 第一部分数据结构与算法 7 5 问题处理方案的正确而完整的描述称为 6 算法复杂度主要包括时间复杂度和 复杂度 7 以下不属于算法特性的是 A 有穷性B 简捷性C 可行性D 确定性 算法 空间 第一部分数据结构与算法 8 1 2数据结构的基本概念1 数据结构是计算机科学与技术领域广泛使用的一个基本术语 用来反映数据的内部构成 数据结构研究的三个方面 1 数据集合中各数据元素之间所固有的逻辑关系 即数据的逻辑结构 2 在对数据进行处理时 各元素在计算机中的存储关系 即数据的存储结构 物理结构 3 对各种数据结构进行的运算 第一部分数据结构与算法 9 数据结构类型 1 数据的逻辑结构 2 数据的存储结构 3 数据的运算 检索 排序 插入 删除 修改等 A 线性结构 B 非线性结构 A顺序存储 B链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方面 10 数据的逻辑结构线性结构 顺序表 链表 队列 堆栈 非线性结构 树 图 数据的逻辑结构是反映数据元素之间逻辑关系的数据结构 与所使用的计算机无关 数据的逻辑结构包含 1 表示数据元素的信息 2 表示各数据元素之间的前后件关系 第一部分数据结构与算法 11 线性结构 必须满足以下两个条件 1 有且只有一个根结点 2 每个结点最多有一个前件 也最多有一个后件 线性结构也称线性表 图1 1线性结构 第一部分数据结构与算法 12 线性结构和非线性结构 线性结构条件 1 有且只有一个根结点 2 每一个结点最多有一个前件 也最多有一个后件 3 首节点无前件 尾节点无后件 非线性结构 不满足线性结构条件的数据结构注意 在一个线性结构中插入或删除任何一个节点后还应是线性结构 否则 不能称为线性结构 13 图1 1线性结构如果一个结构不是线性结构 则称为非线性结构 如图1 2 图1 3 图1 2非线性结构中的 树 形结构 图1 3非线性结构中的 图 形结构 第一部分数据结构与算法 14 树形结构 树形结构 15 树形结构 树形结构 结点间具有分层次的连接关系 16 图形结构 图形结构 节点间的连接任意 17 存储结构 也称数据的物理结构 是指数据的逻辑结构在计算机存储空间中的存放形式 其形式包括顺序 链接 索引等 顺序存储 逻辑上相邻的结点存储在物理位置相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系 位置 来体现链式存储 不要求逻辑上相邻的结点在物理位置上亦相邻 结点间的逻辑关系是由附加的指针字段表示的 第一部分数据结构与算法 18 顺序存储与链式存储 顺序存储常用于线性数据结构 将逻辑上相邻的数据元素存储在物理上相邻的存储单元里 三个弱点插入或删除操作时 需移动大量元数 长度变化较大时 需按最大空间分配 表的容量难以扩充 19 顺序存储与链式存储 链式存储的地址映射表 20 例题 1 数据的存储结构是指 A 存储在外存中的数据B 数据所占的存储空间C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 2 以下数据结构中不属于线性数据结构的是 A 队列B 线性表C 二叉树D 栈 第一部分数据结构与算法 21 3 下列叙述中正确的是 A 一个逻辑数据结构只能有一种存储结构B 数据的逻辑结构属于线性结构 存储结构属于非线性结构C 一个逻辑结构可以有多种存储结构 且各种存储结构不影响数据处理的效率D 一个逻辑结构可以有多种存储结构 且各种存储结构影响数据处理的效率 第一部分数据结构与算法 22 1 3线性表及其顺序存储结构1 线性表的基本概念 线性表是一种最简单 最常用的一种数据结构 它由一组数据元素构成 2 线性表的顺序存储结构 两个特点 1 线性表中所有元素所占的存储空间是连续的 2 线性表中各元素在存储空间中是按逻辑顺序依次存放的3 元素ai的存储地址为 ADR ai ADR a1 i 1 k ADR a1 为第一个元素的地址 k代表每个元素占的字节数 4 线性表的顺序存储基本操作 插入 删除 查找 第一部分数据结构与算法 23 1 4线性链表概念 用一组任意的存储单元来依次存放线性表的各结点 这组存储单元既可以是连续的 也可以是不连续的 甚至是零散分布在内存中的任意位置上的 因此 链表中结点的逻辑次序和物理次序不一定相同 线性链表的基本运算 插入 删除 查找 第一部分数据结构与算法 24 线性链表的结点由两部分组成 1 用于存储数据元素值 称为数据域 2 用于存放指针 称为指针域 用于指向前一个或后一个结点 在链式存储结构中 存储数据结构的空间可以不连续 各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致 而数据元素之间的逻辑关系是由指针域来确定的 所以 链式存储方式即可用于表示线性结构 也可用于表示非线性结构 第一部分数据结构与算法 25 几种常见的链表 1 单向链表 HEAD称为头指针 HEAD NULL 或0 称为空表 数据域 指针域 head 第一部分数据结构与算法 2 双向链表 左指针 Llink 指向前件结点 右指针 Rlink 指向后件结点 3 循环链表 26 线性表的顺序存储结构称为顺序表线性表的链式存储结构称为线性链表二者的比较 1 顺序表存储数据时在逻辑上相连的在物理上也一定相连 2 链表存储数据时在逻辑上相连的在物理上不一定相连 3 顺序表插入和删除比较麻烦 但是访问每一个结点比较简单4 链表插入和删除比较简单 但是访问每一个结点比较麻烦 第一部分数据结构与算法 27 1 5栈和队列栈 也叫堆栈 是指限定在一端进行插入与删除的线性表 允许插入与删除的一端称为栈顶 不允许插入与删除的另一端称为栈底 栈按照 先进后出 FILO 或 后进先出 LIFO 组织数据 栈具有记忆作用 栈的基本运算 1 插入元素 也称为入栈运算 2 删除元素 也称为退栈运算 3 读栈顶元素 将栈顶元素赋给一个指定的变量 此时指针无变化 第一部分数据结构与算法 28 队列 允许在一端 队尾 进入插入 而在另一端 队头 进行删除的线性表 队列按照 先进先出 FIFO 或 后进后出 LILO 组织数据 队列基本运算 1 入队运算 从队尾插入一个元素 2 退队运算 从队头删除一个元素 循环队列 是将队列的存储空间的最后一个位置绕到第一个位置 形成逻辑上的形状空间 供队列循环使用 其实质还是顺序存储结构 第一部分数据结构与算法 29 例题 1 下列关于栈叙述正确的是 A 在栈中只能插入数据B 在栈中只能删除数据C 栈是先进先出的线性表D 栈是先进后出的线性表 2 下列关于队列的叙述中正确的是 A 在队列中只能插入数据B 在队列中只能删除数据C 队列是先进先出的线性表D 队列是先进后出的线性表 第一部分数据结构与算法 30 3 栈和队列的共同特点是 A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点 4 设输入序列为1 2 3 4 则借助一个栈可以得到的输出序列是 A 1 3 4 2B 3 1 4 2C 4 3 1 2D 4 1 2 3 第一部分数据结构与算法 31 5 在一个容量为15的循环队列中 若队头front 6 队尾rear 9 则该循环队列中有 个元素 答案 3分析 如图1 8与图1 9的两种循环队列存放数据的形式 第一部分数据结构与算法 在非空队列中 头指针始终指向队头元素前一个位置 而尾指针始终指向队尾元素的位置 32 由此可以得出元素的个数为 rear front 3可是当front 9 rear 6的时候 则会出现如下的存放形式 图1 9改变后的存储结构元素的个数为12个 能够查出 这个12通过计算也能够得出 rear front 总容量 6 9 15 12 第一部分数据结构与算法 33 计算循环队列长度 front rear 队列长度 0 frontrear 队列长度 rear size front 34 6 下列叙述中正确的是 A 栈是先进先出的线性表B 队列是 先进后出 的线性表C 循环队列是非线性结构D 有序线性表即可以采用顺序存储结构 也可以采用链式存储结构 7 下列叙述中正确的是 A 线性链表是线性表的链式存储结构B 栈与队列是非线性结构C 双向链表是非线性结构D 只有根结点的二叉树是线性结构 第一部分数据结构与算法 35 8 下列叙述中正确的是 A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 第一部分数据结构与算法 36 9 数据的存储结构是指 A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 10 下列对于线性链表的描述中正确的是 A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 第一部分数据结构与算法 37 11 下列数据结构中 能够按照 先进后出 原则存取数据的是 A 循环队列B 栈C 队列D 二叉树 12 对于循环队列 下列叙述中正确的是 A 队头指针是固定不变的B 队头指针一定大于队尾指针C 队头指针一定小于队尾指针D 队头指针可以大于队尾指针 也可以小于队尾指针 第一部分数据结构与算法 38 13 假设用一个长度为50的数组 数组元素的下标从0到49 作为栈的存储空间 栈底指针bottom指向栈底元素 栈顶指针top指向栈顶元素 如果bottom 49 top 30 数组下标 则栈中具有 个元素 14 支持子程序调用的数据结构是 A 栈B 树C 队列D 二叉树 20 第一部分数据结构与算法 39 15 一个栈的初始状态为空 现将元素1 2 3 4 5 A B C D E依次入栈 然后再依次出栈 则元素出栈的顺序是 A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 第一部分数据结构与算法 40 16 下列叙述中正确的是 A 循环队列有队头和队尾两个指针 因此 循环队列是非线性结构B 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况C 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况D 循环队列中元素的个数是由队头指针和队尾指针共同决定 第一部分数据结构与算法 41 17 下列关于栈的叙述正确的是 A 栈按 先进先出 组织数据B 栈按 先进后出 组织数据C 只能在栈底插入数据D 不能删除数据 18 设某循环队列的容量为50 头指针front 5 指向队头元素的前一位置 尾指针rear 29 指向队尾元素 则该循环队列中共有 个元素 19 线性表的存储结构主要分为顺序存储结构和链式存储结构 队列是一种特殊的线性表 循环队列是队列的 存储结构 24 顺序 第一部分数据结构与算法 42 20 下列对队列的叙述正确的是 A 队列属于非线性表B 队列按 先进后出 原则组织数据C 队列在队尾删除数据D 队列按 先进先出 原则组织数据 21 数据结构分为线性结构和非线性结构 带链的队列属于 23 按照 后进先出 原则组织数据的数据结构是 A 队列B 栈C 双向链表D 二叉树 线性结构 第一部分数据结构与算法 43 1 6树与二叉树1 概念 树是一种简单的非线性结构 所有元素之间具有明显的层次特性 在树结构中 每一个结点只有一个前件 称为父结点 没有前件的结点只有一个 称为树的根结点 简称树的根 每一个结点可以有多个后件 称为该结点的子结点 没有后件的结点称为叶子结点 在树结构中 一个结点所拥有的后件的个数称为该结点的度 所有结点中最大的度称为树的度 树的最大层次称为树的深度 第一部分数据结构与算法 44 2 二叉树 度为2的树 特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 第一部分数据结构与算法 45 二叉树的性质 1 在二叉树的第k层上 最多有2k 1个结点 如图1 11 图1 11性质1的理解 第一部分数据结构与算法 46 2 深度为h的二叉树最多有2h 1个结点 如图1 12 图1 12性质2的理解 第一部分数据结构与算法 47 3 任何一个二叉树中 度为0的结点 即叶子结点N0 总比度为2的结点 N2 多一个 即N0 N2 1 4 具有n个结点的二叉树 其中深度至少为 log2n 1 5 假设e为树的边数 n表示总结点数 则任何树的边数一定比总结点数少1 即e n 1 第一部分数据结构与算法 48 3 满二叉树 除最后一层外 每一层上的所有结点都有两个子结点 4 完全二叉树 若设二叉树的高度为h 除第h层外 其它各层 1 h 1 的结点数都达到最大个数 第h层所有的节点都连续集中在最左边 这就是完全二叉树 完全二叉树是由满二叉树而引出来的 对于深度为K的 有N个结点的二叉树 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应时称之为完全二叉树 完全二叉树中 度为1的结点最多只有1个完全二叉树左右子树的深度之差不大于1 第一部分数据结构与算法 49 满二叉树 特点 所有分支结点都存在左右子树 且所有叶子结点都在同一层上 50 完全二叉树 特点 除最后一层外 每一层都取最大结点数 最后一层结点都集中在该层最左边的若干位置 51 二叉树的基本性质 A 二叉树的第i层上至多有2i 1 i 1 个结点 B 深度为h的二叉树中至多含有2h 1个结点 C 若在任意一棵二叉树中 有n0个叶子结点 度为0 有n2个度为2的结点 则 n0 n2 1D 具有n个结点的完全二叉树的深度为 log2n 1 其中 log2n 表示log2n的整数部分 第三层 i 3 有23 1 4个节点深度h 4 共有24 1 15个节点n0 8 n2 7 n0 n2 115个节点 深度 log215 1 4 52 例题 1 在深度为5的满二叉树中 叶子结点个数为 A 32B 21C 16D 15 第一部分数据结构与算法 53 2 设一棵完全二叉树上有700个结点 则二叉树中有 个叶子结点 根据二叉树的性质 对于一棵非空的二叉树 如果叶子节点数为n0 度为2的结点数为n2 则no n2 1 根据完全二叉树的定义可得 在完全二叉树中度为1的结点n1只能取两种情况 要么为0 要么为1 所以 n0 n1 n2 700n0 n2 1 2n0 701 n1 因为结点数为整数 所以n1 1 no 350 350 54 3 设一棵完全二叉树上有801个结点 则二叉树中有 个叶子结点 4 某二叉树中 度为2的结点有18个 则该二叉树中有 个叶子结点 5 一棵二叉树第6层上的结点数最多为 个 401 19 32 第一部分数据结构与算法 55 二叉树的遍历 1 前序遍历 DLR 首先访问根结点 然后遍历左子树 最后遍历右子树 树根在第一 下走不跳结点 2 中序遍历 LDR 首先遍历左子树 然后访问根结点 最后遍历右子树 有左先左 再寻根 后找右 最左边的结点最先遍历 最右边的结点最后遍历 3 后序遍历 LRD 首先遍历左子树 然后访问遍历右子树 最后访问根结点 有左先左 再找右 后寻根 到最右一路上行 树根在最后 第一部分数据结构与算法 56 第一部分数据结构与算法 57 已知二叉树的前序遍历为ABDEFC 中序遍历为DBFEAC 则二叉树的后序遍历结果是 分析 前序遍历为ABDEFC中序遍历为DBFEAC第一步 确定A为根结点 则由中序遍历 DBFEAC 可以知道DBFE为A的左子树部分 C为A的右子树部分 第一部分数据结构与算法 58 第二步 对于中序中的DBFE 在前序中的结果为BDEF 所以可以得出这四个结点中B为 小根 结点 即B直接和A相连 接着在中序中 DBFE 可以知道D在B的左边 FE在B的右面 第一部分数据结构与算法 59 第三步 对于中序中的FE 在前序中为EF 则可以知道E直接和B相连 在中序中 F在E的左面 即可以得出二叉树图形 第四步 根据二叉树图形写出后序遍历为DFEBCA 第一部分数据结构与算法 60 例题 1 对于如图的二叉树 进行后序遍历的结果为 A ABCDEFB DBEAFCC ABDECFD DEBFCA 第一部分数据结构与算法 61 2 在深度为7的满二叉树中 叶子结点的个数为 A 32B 31C 64D 63 第一部分数据结构与算法 62 3 某二叉树有5个度为2的结点以及3个度为1的结点 则该二叉树中共有 个结点 4 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A 219 70 80 69B 221C 229D 231 14 第一部分数据结构与算法 63 5 设一棵二叉树的中序遍历为DBEAFC 前序遍历为ABDECF 则后序遍历结果为 6 设树T的度为4 其中度为1 2 3 4的结点个数分别为4 2 1 1 则T的叶子结点数为 A 8B 7C 6D 5 DEBFCA 分析 由e 边数 n 总结点数 1入手 假设n0 n1 n2 n3 n4分别为度是0 1 2 3 4结点的个数 那么 e 4 n1 3 n2 2 n3 1 n4 4 1 3 1 2 2 1 4 15所以 n总 16马上可以得到n0 n总 n1 n2 n3 n4 8 第一部分数据结构与算法 64 1 7查找与排序技术1 顺序查找 从表中的最后一个 或第一个 记录开始 逐个进行记录的关键字和给定值的比较 若某个记录的关键字和给定值比较相等 则查找成功 找到了所有查找的记录 反之 若直至第一个记录 其关键字和给定值比较不等 则表明表中没有所查找的记录 查找不成功 若有n个记录 顺序查找的平均查找长度为 n 1 2 最坏情况下的比较次数为n 第一部分数据结构与算法 65 2 二分查找 适用于顺序存储的有序表 二分查找 要求线性表中的结点必须是按关键字值的递增或递减顺序排列 它首先把要查找的关键字k与中间位置的关键字相比较 若相等 则查找成功 若不相等 则缩小范围 根据关键字与中间结点关键字的比较大小确定下一步查找那个子表 这样一直查找下去 直到满足条件的结点或者确认表中没有这样的结点为止 所以在有序表中 二分查找为首选 二分查找的比较次数为log2n 第一部分数据结构与算法 66 顺序查找适用于两种情况 1 线性表为无序表 不管是顺序存储还是链式存储 2 表采用链式存储结构 即使是有序线性表 二分法查找适用于顺序存储的有序表 第一部分数据结构与算法 67 3 排序 将一个无序序列整理成按值非递减 或递增 顺序排列的有序序列 主要分为以下三类 1 交换类排序 主要包括冒泡排序和快速排序 其时间复杂度为O n2 在最坏情况下的比较次数都为n n 1 2 2 插入类排序 主要包括直接插入排序和希尔排序 直接插入排序的时间复杂度为O n2 希尔排序的时间复杂度为O n1 5 在最坏情况下的比较次数都为n n 1 2 3 选择类排序 主要包括选择排序和堆排序 选择排序时间复杂度为O n2 在最坏情况下选择排序的比较次数为n n 1 2 堆排序为nlog2n 第一部分数据结构与算法 68 例题 1 在长度为n的有序线性表中进行二分查找 需要的比较次数为 2 在最坏情况下 冒泡排序的时间复杂度为 3 下列数据结构中 能用二分法进行查找的是 A 顺序存储的有序线性表B 线性链表C 二叉树D 有序线性表 log2n n n 1 2 第一部分数据结构与算法 69 1 下列排序方法中 最坏情况下比较次数最少的是 A 冒泡排序B 简单选择排序C 直接插入排序D 堆排序 2 在长度为n的有序线性表中进行二分查找 最坏情况下需要比较的次数是 A O n B O n2 C O log2n D O nlog2n 第一部分数据结构与算法 70 3 对长度为n的线性表排序 以下排序方法在最坏情况下 比较次数不是n n 1 2的是 A 快速排序B 冒泡排序C 直接插入排序D 堆排序 4 对长度为10的线性表进行冒泡排序 最坏情况下需要比较的次数为 45 第一部分数据结构与算法 71 5 冒泡排序在最坏情况下的比较次数是 A n n 1 2B nlog2nC n n 1 2D n 2 6 在长度为64的有序线性表中进行顺序查找 最坏情况下需要比较的次数为 A 63B 64C 6D 7 第一部分数据结构与算法 72 7 对于长度为n的线性表 在最坏情况下 下列各排序法所对应的比较次数中正确的是 A 冒泡排序为n 2B 冒泡排序为nC 快速排序为nD 快速排序为n n 1 2 8 对长度为n的线性表进行顺序查找 在最坏情况下所需要的比较次数为 A log2nB n 2C nD n 1 第一部分数据结构与算法 73 2 1程序设计方法与风格1 源程序文档化 文档命名统一化 便于理解2 数据说明的方法 正确使用合理的注释3 程序结构 程序构造清晰4 输入和输出 至少有一个输出语句注释语句分为序言性注释和功能性注释 第二部分程序设计基础 74 1 下列叙述中 不符合良好程序设计风格要求的是 A 程序的效率第一 清晰第二B 程序的可读性好C 程序中要有必要的注释D 输入数据前要有提示信息 2 下列叙述中正确的是 A 程序执行的效率与数据的存储结构密切相关B 程序执行的效率只取决于程序的控制结构C 程序执行的效率只取决于所处理的数据量D 以上三种说法都不对 第二部分程序设计基础 75 2 2结构化程序设计结构化程序设计的基本原则 1 自顶向下 2 逐步求精 3 功能模块化 高内聚 低耦合 4 尽量避免使用goto语句 模块间相互连接的紧密程度的度量 模块内部各个元素间彼此结合的紧密程度的度量 第二部分程序设计基础 76 1 下列选项中不符合良好程序设计风格的是 A 源程序要文档化B 数据说明的次序要规范化C 避免滥用goto语句D 模块设计要保证高耦合 高内聚 2 下列选项中不属于结构化程序设计原则的是 A 可封装B 自顶向下C 模块化D 逐步求精 第二部分程序设计基础 77 3 符合结构化原则的三种基本控制结构是 选择结构 循环结构和 4 结构化程序设计的基本原则不包括 A 多态性B 自顶向下C 模块化D 逐步求精 5 下列选项中不属于结构化程序设计方法的是 A 自顶向下B 逐步求精C 模块化D 可复用 顺序结构 第二部分程序设计基础 78 2 3面向对象的程序设计对象 用来描述客观事物的一个实体 由一组表示其静态特征的属性和它可执行的一组操作 即方法 组成 属性 对象所包含的信息操作 描述了对象执行的功能 第二部分程序设计基础 79 类 指具有共同属性 共同方法的对象的集合 类是关于对象性质的描述 实例 一个具体的对象称为该类的实例消息 一个实例与另一个实例之间传递的信息 第二部分程序设计基础 80 封装 在程序上 隐藏对象的属性和实现细节 仅对外公开接口 控制在程序中属性的读和写的访问级别 继承 使用一个已有类 基类 来建立一个新类 派生类 的定义技术 这样 基类和派生类之间将共享一些属性和操作 多态性 相同的操作或函数 过程可作用于多种类型的对象上并获得不同的结果 不同的对象 收到同一消息可以产生不同的结果 这种现象称为多态性 第二部分程序设计基础 81 通过对以上概念的理解 不难看出 一个对象应该具备以下几个方面的特性 1 标识唯一 2 分类 3 继承 4 多态 5 封装 6 模块独立 第二部分程序设计基础 82 1 在面向对象方法中 不属于 对象 基本特点的是 A 一致性B 分类性C 多态性D 标识唯一性 2 在面向对象的方法中 实现信息隐蔽是依靠 A 对象的继承B 对象的多态C 对象的封装D 对象的分类 第二部分程序设计基础 83 3 下面选项中不属于面向对象程序设计特征的是 A 继承性B 多态性C 类比性D 封装性 4 在面向对象方法中 描述的是具有相似属性与操作的一组对象 5 在面向对象方法中 类的实例称为 类 对象 第二部分程序设计基础 84 3 1软件工程基本概念计算机软件 程序 数据及相关文档的完整集合 按功能划分 计算机软件可以分为系统软件 应用软件和工具软件 也叫做支撑软件 软件危机 由于落后的软件生产方式无法满足软件需求而导致 主要表现在以下几个方面 开发费用大 开发效率低 产品质量差 软件可靠性和可维护性差 第三部分软件工程基础 85 软件工程 以工程的思想管理软件过程 包括3个要素 方法 工具和过程 完成软件过程项目的技术手段 软件开发 管理及文档生成 软件开发中各环节的控制和管理 软件的生命周期 软件产品从提出 实现 使用 维护到停止使用 即退役 的过程 整个周期分三阶段 软件定义 可行性研究 制定计划 需求分析 软件开发 软件及数据库的设计 系统实现 功能测试 运行维护 根据实际情况完善系统 第三部分软件工程基础 86 1 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下列属于应用软件的是 A 编译程序B 操作系统C 教务管理系统D 汇编程序 2 软件是指 A 程序B 程序和文档C 算法加数据结构D 程序 数据与相关文档的完整集合 第三部分软件工程基础 87 3 软件工程三要素包括方法 工具和过程 其中 支持软件开发的各个环节的控制和管理 4 软件生命周期可分为多个阶段 一般分为定义阶段 开发阶段和维护阶段 编码和测试属于 阶段 5 下列选项中不属于软件生命周期开发阶段任务的是 A 软件测试B 概要设计C 软件维护D 详细设计 开发 过程 第三部分软件工程基础 88 6 下列描述中正确的是 A 软件工程只是解决软件项目的管理问题B 软件工程主要解决软件产品的生产率问题C 软件工程的主要思想是强调在软件开发过程中需要应用工程化原则D 软件工程只是解决软件开发中的技术问题 7 下列叙述中正确的是 A 软件交付使用后还需要进行维护B 软件一旦交付使用就不需要再进行维护C 软件交付使用后其生命周期就结束D 软件维护是指修复程序中被破坏的指令 第三部分软件工程基础 89 8 下列描述中正确的是 A 程序就是软件B 软件开发不受计算机系统的限制C 软件既是逻辑实体 又是物理实体D 软件是程序 数据与相关文档的集合 第三部分软件工程基础 90 3 2软件定义阶段 做什么 该阶段主要任务 确定研究目标 进行可行性分析 需求分析 探讨解决方案 制定开发计划 该阶段中 结构化分析的常用工具包括 1 数据流图 2 数据字典 3 判定树 4 判定表 第三部分软件工程基础 91 数据流图 DFD 在需求分析阶段中使用的 用于描述数据处理过程的工具 第三部分软件工程基础 92 结构化分析方法 结构化方法的核心和基础是结构化程序设计理论 结构化分析的常用工具 数据流图 数据字典 判定树 判定表 1 数据流图 DFD图 描述数据处理过程的工具 是需求理解的逻辑模型的图形表示 它直接支持系统功能建模 加工 转换 圆框 输入数据经加工变换产生的输出 数据流 箭头 沿箭头方向传递数据的通道 一般在旁边标注数据流名 存储文件 数据源 双横线 表示处理过程中存放各种数据的文件 源 潭 方框 表示系统和环境的接口 属系统之外的实体 93 2 数据字典 对所有与系统相关的数据元素的一个有组织的列表 以及精确的 严格的定义 使得用户和系统分析员对于输入 输出 存储成分和中间计算结果有共同的理解 数据字典是结构化分析的核心 3 判定树 从问题定义的文字描述中分清哪些是判定的条件 哪些是判定的结论 根据描述材料中的连接词找出判定条件之间的从属关系 并列关系 选择关系 根据它们构造判定树 4 判定表 与判定树相似 当数据流图中的加工要依赖于多个逻辑条件的取值 即完成该加工的一组动作是由于某一组条件取值的组合而引发的 使用判定表描述比较适宜 94 数据字典 DD 是描述数据的信息的集合 是对系统中使用的所有数据元素的定义的集合 它是结构化分析的核心 数据流名称 产品入库单标识符F1数据结构 字段名称类型长度日期 RQ 字符型8产品代码 CPDM 字符型3产品名称 CPMC 字符型18单位代码 DWDM 字符型1单位 DW 字符型4规格代码 GGDM 字符型2规格 GG 字符型10入库数量 RKSL 数值型6排列方式 按 入库日期 产品代码 升序排列流量 最大50张 日平均30张 日来源 生产车间去向 产品入库处理 第三部分软件工程基础 95 1 数据流图中带有箭头的线段表示的是 A 控制流B 事件驱动C 模块调用D 数据流 2 在软件开发中 需求分析阶段可以使用的工具是 A N S图B DFD图C PAD图D 程序流程图 第三部分软件工程基础 96 3 在软件设计中 不属于过程设计工具的是 A PDL 过程设计语言 又叫伪码 B PAD图C N S图D DFD图 第三部分软件工程基础 97 4 在软件开发中 需求分析阶段产生的主要文档是 A 可行性分析报告B 软件需求规格说明书 SRS C 概要设计说明书D 集成设计计划 5 软件需求规格说明书应具有完整性 无歧义性 正确性 可验证性 可修改性 一致性 克理解性 可追踪性等特性 其中最重要的是 6 程序流程图中菱形框表示的是 无歧义性 条件判断 第三部分软件工程基础 98 7 耦合性和内聚性是对模块独立性度量的两个标准 下列叙述中正确的是 A 提高耦合性降低内聚性有利于提高模块的独立性B 降低耦合性提高内聚性有利于提高模块的独立性C 耦合性是指一个模块内部各个元素间彼此结合的紧密程度D 内聚性是指模块间互相连接的紧密程度 8 在结构化程序设计中 模块划分的原则是 A 各模块应包括尽量多的功能B 各模块的规模应尽量大C 各模块之间的联系应尽量紧密D 模块内具有高内聚度 模块间具有低耦合度 第三部分软件工程基础 99 3 3软件设计阶段 怎么做 从技术观点角度来看 软件设计分为 1 结构设计 定义系统各部件间的联系 2 数据设计 将模型转化为数据结构 3 接口设计 描述软件内部 软件与协作系统 软件与用户之间的通信接口 4 过程设计 将系统结构部件转换成软件的过程描述 第三部分软件工程基础 100 从工程管理角度来看 软件设计分为 1 概要设计 设计系统结构 数据结构 数据库 编写概要设计文档及概要设计文档评审 2 详细设计 为每个模块确定实现算法及局部数据结构细节 过程设计的常用工具 1 程序流程图 PFD图 2 盒状流程图 N S图 3 问题分析图 PAD图 4 过程设计语言 伪代码 PDL 第三部分软件工程基础 程序流程图中 箭头为控制流 方框为加工步骤 菱形为逻辑条件 101 问题分析图 PAD 在软件设计阶段使用的 利用二维树形结构图来表示程序控制流的分析工具 第三部分软件工程基础 102 程序流程图 PDF 又叫输入 输出图 在软件设计阶段使用的 用于直观地描述一个工作过程的具体步骤 第三部分软件工程基础 103 N S图 盒图 又叫无线流程图 第三部分软件工程基础 104 1 在结构化分析使用的数据流图 DFD 中 利用 对其中的图形元素进行确切解释 2 软件开发过程主要分为需求分析 设计 编码与测试四个阶段 其中 阶段产生 软件需求规格说明书 3 软件详细设计产生的图如下 该图是 A N S图B PAD图C 程序流程图D E R图 数据字典 需求分析 第三部分软件工程基础 105 4 从工程管理角度 软件设计一般分为两步完成 它们是 A 概要设计与详细设计B 数据设计与接口设计C 软件结构设计与数据设计D 过程设计与数据设计 第三部分软件工程基础 106 3 4软件测试阶段软件测试 发现软件中的错误 检验软件是否满足规定的需求 包括静态测试和动态测试两种 静态测试 静态结构分析 度量代码质量 不实际运行软件 动态测试 验证软件内部操作 主要方法是逻辑覆盖和基本路径测试 包括白盒测试和黑盒测试两种基本测试方法 白盒测试 在程序内部进行 主要方法就是逻辑覆盖 语句覆盖 判定覆盖 条件覆盖 路径覆盖 黑盒测试 是在软件接口处进行 主要诊断功能遗漏 界面错误 数据访问错误等 主要方法有等价类划分法 边界值分析法 错误推测法 因果图等 第三部分软件工程基础 107 整个测试过程需要进行4个步骤 1 单元测试 仅对各模块进行正确性检验 2 集成测试 将模块组装在一起进行正确性检测 3 验收测试 也叫确认测试 依据 软件需求规格说明书 验证软件的功能及性能检测 4 系统测试 在真实环境下验证软件的性能 第三部分软件工程基础 软件测试的目的 发现错误而执行程序的过程 108 1 软件测试可以分为白盒测试和黑盒测试 基本路径测试属于 测试 2 按照软件测试的一般步骤 集成测试应在 测试之后进行 3 测试用例包括输入值集和 值集 4 在两种基本测试方法中 测试的原则之一是保证所测模块中每一个独立路径至少要执行一次 5 程序测试分为静态测试和动态测试 其中 测试是指不执行程序 而只是对程序文本进行检查 通过阅读和讨论 分析和发现程序中的错误 白盒 单元 输出 白盒 静态 第三部分软件工程基础 109 6 下列叙述中正确的是 A 软件测试的主要目的是发现程序中的错误B 软件测试的主要目的是确定程序中错误的位置C 为了提高软件测试的效率 最好由程序编制者自己来完成软件测试的工作D 软件测试是证明软件没有错误 第三部分软件工程基础 110 7 软件测试分为白箱 盒 测试和黑箱 盒 测试 等价类划分法属于 测试 8 在进行模块测试时 要为每个被测试的模块另外设计两类模块 驱动模块和承接模块 桩模块 其中 的作用是将测试数据传送给被测试的模块 并显示被测试模块所产生的结果 黑盒 驱动模块 第三部分软件工程基础 111 3 5软件调试阶段程序调试 诊断和改正程序中的错误 基本步骤 1 错误定位 2 修改代码 排除错误 3 进行回归测试程序调试分为2种 1 静态调试 通过人的思维直接分析源代码中的错误 2 动态调试 利用调试工具分析程序执行流程 进而找出错误所在 主要方法有单步调试 断点调试 第三部分软件工程基础 112 1 诊断和改正程序中错误的工作阶段通常称作软件的 2 软件的调试任务 A 发现并改正程序中所有错误B 确定程序中错误的位置C 诊断和改正程序中的错误D 尽可能多的发现程序中的错误 3 下列叙述正确的是 A 软件维护只包括对程序代码的维护B 软件测试应该由程序开发者来完成C 程序调试后可以不需要再测试D 以上说法都不对 调试 第三部分软件工程基础 113 4 1数据库基本概念数据 实际上就是描述事物的符号记录 软件的数据是有一定的结构 有型与值之分 如整型 实型 字符型等 而数据的值给出了符合定型的值 如整型值15 数据库 是指在已有数据库管理系统的基础上建立数据库 是数据的集合 具有统一的结构形式并存放于统一的存储介质内 是多种应用数据的集成 并可被各个应用程序共享 数据库存放数据是按数据所提供的数据模式存放的 具有集成与共享的特点 数据库管理系统 一种系统软件 负责数据库中的数据组织 数据操纵 数据维护 控制及保护和数据服务等 数据库系统中实现各种数据管理功能的核心软件称为数据库管理系统 第四部分数据库设计基础 114 数据库管理系统提供以下的数据语言 1 数据定义语言 DDL 负责数据的模式定义与数据的物理存取构建 2 数据操纵语言 DML 负责数据的操纵 如查询与增 删 改等 3 数据控制语言 DCL 负责数据完整性 安全性的定义与检查以及并发控制 故障恢复等 数据语言按其使用方式具有两种结构形式 交互式命令 又称自含型或自主型语言 宿主型语言 一般可嵌入某些宿主语言中 115 数据库管理员 对数据库进行规划 设计 维护 监视等的专业管理人员 数据库系统