全国计算机等级考试二级基础部分.ppt

全国计算机等级考试二级 考试方式1 笔试 90分钟 满分100分 其中含公共基础知识部分的30分 2 上机操作 90分钟 满分100分上机操作包括 1 基本操作 2 简单应用 3 综合应用 公共基础知识部分 第一章数据结构与算法 本章考试要点 算法的基本概念 算法复杂度的概念和意义 时间复杂度和空间复杂度 数据结构的定义 数据的逻辑结构与存储结构 数据结构的图形表示 线性结构与非线性结构 线性表的定义 线性表的顺序存储结构及其插入与删除 栈和队列的定义 栈和队列的顺序存储结构有其基本运算 线性单链表 双向链表与循环链表的结构及其基本运算 树的基本概念 二叉树的定义及其存储结构 二叉树的前序 中序和后序遍历 顺序查找与二分法查找算法 基本排序算法 交换类排序 选择类排序 插入类排序 1 1算法 1 算法的基本特征 可行性算法的每一条指令都必须是基本的 可执行的 确定性算法的每一个步骤都必须是有明确定义的 不允许有模棱两可的解释 也不允许有多义性 有穷性算法必须在有限的时间内完成 即算法必须能在执行有限个步骤之后终止 拥有足够的情报不同的输入将会有不同的结果 当算法拥有足够的情报时 算法才有效 算法是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 且是明确的 此顺序将在有限的次数下终止 2 算法的基本要素 数据对象的运算和操作基本运算和操作包括以下四类 算术运算 逻辑运算 关系运算 数据传输 算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构 一个算法通常由顺序 选择 循环三种基本控制结构组合而成 3 算法设计基本方法 列举法 归纳法 递推 递归 减半递推技术 回溯法4 算法复杂度 算法的时间复杂度指执行算法所需要的计算工作量 用基本运算的次数来度量 算法的空间复杂度指执行算法所需要的内存空间 例1 下列叙述中正确的是 D A 算法就是程序B 设计算法时只需要考虑数据结构的设计C 设计算法时只需要考虑结果的可靠性D 以上三种说法都不对分析 算法的基本特征 是一组严谨地定义运算顺序的规则 每一个规则都是有效的 是明确的 此顺序将在有限的次数下终止 算法不等于程序 程序不可能优于算法 答案 D 11 9 例2 下面叙述正确的是 C A 算法的执行效率与数据的存储结构无关B 算法的空间复杂度是指算法程序中指令 或语句 的条数C 算法的有穷性是指算法必须能在执行有限个步骤之后终止D 以上三种描述都不对 例3 下列叙述中正确的是 B A 算法的效率只与问题的规模有关 而与数据的存储结构无关B 算法的时间复杂度是指执行算法所需要的计算工作量C 数据的逻辑结构与存储结构是一一对应的D 算法的时间复杂度与空间复杂度一定相关 例4 算法的时间复杂度是指 D A 算法的执行时间B 算法所处理的数据量C 算法程序中的语句或指令条数D 算法在执行过程中所需要的基本运算次数 10 3 例5 算法的空间复杂度是指 A 算法在执行过程中所需要的计算机存储空间B 算法所处理的数据量C 算法程序中的语句或指令条数D 算法在执行过程中所需要的临时工作单元数答案A解析 算法的空间复杂度是指执行算法所需要的内存空间 包括算法程序所占空间 输入的初始数据所占空间和执行过程中所需要的额外空间 09 9 1 2数据结构的基本概念 1 数据结构的定义 数据结构是指相互有关联的数据元素的集合 在数据处理领域里 每一个需要处理的对象都可以抽象数据元素 元素 在具有相同牲的数据元素集合中 各个数据之间存在有某种关系 即联系 这种关系反映了该集合中的数据元素所固有的一种结构 通常把数据元素之间这种固有的关系简单地用前后件关系 或直接前驱与直接后继 来描述 数据结构是指反映数据元素之间关系的数据元素集合的表示 或者说 数据结构是指带有结构的数据元素的集合 所谓结构实际上就是指数据元素之间的前后件关系 1 数据的逻辑结构一个数据结构应包含两个方面的信息 表示数据元素的信息 表示各数据元素之间的前后件关系 逻辑关系 与数据在计算机中的存储位置无关 所谓数据的逻辑结构 是指反映数据元素之间逻辑关系的数据结构 2 数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 物理结构 在数据的存储结构中 不仅要存放各数据元素的信息 还需要存放各数据元素之间的前后件关系 常用的存储结构有顺序 链接 索引等存储结构 采用不同的存储结构 其数据处理的效率是不同的 插入与删除是对数据结构的两种基本运算 2 数据结构的图形表示每一个数据元素用中间标有元素值的方框表示 称之为数据结点 用一条有向线段从前件指向后件 以表示数据元素之间的前后件关系 没有前件的结点称为根结点 没有后件的结点称为终端结点 叶子结点 3 线性结构与非线性结构如果在一个数据结构中一个数据元素都没有 则该数据结构称为空的数据结构 根据数据结构中各数据元素之间的前后件关系的复杂程度 将数据结构分为两大类 线性结构和非线性结构 1 线性结构一个非空数据结构如果 有且只有一个根结点 每一个结点最多有一个前件和一个后件则称之为线性结构 线性表 一个线性结构中插入或删除任何一个结点后还应是线性结构 如果一个线性结构满足上述两个条件 但当在此数据结构中插入或删除任何一个结点后不再满足上述条件 则该数据结构不能称线性结构 2 非线性结构一个数据结构不是线性结构 则称之为非线性结构 线性结构和非线性结构都可以是空的数据结构 空的数据结构是线性结构还是非线性结构 要根据具体情况定 对该数据结构的运算按线性结构的规则处理 则属线性结构 对该数据结构的运算按非线性结构的规则处理 则属非线性结构 例1 数据的存储结构是指 C A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 例2 下列叙述中正确的是 D A 数据的逻辑结构与存储结构必定是一一对应的B 由于计算机存储空间是向量式的存储结构 因此 数据的存储结构一定是线性结构C 程序设计语言中的数组一般是顺序存储结构 因此 利用数组只能处理线性结构D 以上三种说法都不对 例3 下列叙述中正确的是 B A 有一个以上根结点的数据结构不一定是非线性结构B 只有一个根结点的数据结构不一定是线性结构C 循环链表是非线性结构D 双向链表是非线性结构 1 3线性表及其顺序存储结构 1 线性表的概念 线性表是最简单 最常用的一种数据结构 线性表由一组数据元素构成 一个数据元素可以是个简单项 也可以由若干个数据项组成 由若干个数据项组成的数据元素称为记录 而由多个记录构成的线性表称为文件 线性表线性表是由n n 0 个数据a1 a2 a3 ai an组成的一个有限序列 表中的每一个数据元素 除第一个外 有且只有一个前件 除了最后一个外 有且只有一个后件 即线性表可能表示为 a1 a2 a3 ai an 线性表中结点的个数n称为线性表的长度 当n 0时 称为空表 非空线性表的结构特征 有且只有一个根结点a1 它无前件 有且只有一个终结点an 它无后件 除根结点与终结点外 其它所有结点有且只有一个前件 也有且只有一个后件 2 线性表的顺序存储结构线性表的顺序存储结构有以下两个基本特点 线性表中所有元素所占的存储空间是连续的线性表中各元素在存储结构中是按逻辑顺序依次存放的 3 线性表的插入运算 插入运算是指在结构中的某指定位置上增加一个新结点 线性表的插入操作是指在线性表的第i 1个数据元素和第i个数据元素之间插入一个新的数据元素 使长度为n的线性表变为长度为n 1的线性表 一般情况下 要在第i 1 i n 个元素之前插入一个新元素时 首先要从最后一个 即第n个元素 开始 直到第i个元素之间共n i 1个元素依次向后移动一个位置后 在空出的第i个位置上插入新元素项 在平均情况下 要在线性表中插入一个新元素 需要移动表中一半的数据元素 插入操作使数据元素ai 1和ai之间的逻辑关系发生了变化 4 线性表的删除运算 删除运算是指撤消结构中某结点的内容 与插入操作相反 线性表的删除操作使长度为n的线性表变为长度为n 1的线性表 删除操作使数据元素ai 1 ai和ai 1之间的逻辑关系发生了变化 一般情况下 要删除第i 1 i n 个元素时 首先要从第i 1一个元素开始 直到第n个元素之间共n i个元素依次向前移动一个位置 例1 下列叙述中正确的是 D A 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D 上述三种说法都不对 例2 如果一个线性表第1个元素的存储地址是100 每个元素的长度是2 则第5个元素的地址是 分析 数据元素的存储地址取决于第1个元素的存储地址 即 第i个元素的存储地址 第1个元素的地址 i 1 每个元素r长度 108 例 下列叙述中正确的是 A 有一个以上根结点的数据结构不一定是非线性结构B 只有一个根结点的数据结构不一定是线性结构C 循环链表是非线性结构D 双向链表是非线性结构 11 3 B 1 4栈和队列 1 栈及其基本运算 1 栈的概念 栈是限定在一端进行插入与删除操作的特殊的线性表 栈中允许插入与删除操作的一端称为栈顶 不允许插入与删除的一端称为栈底 栈顶元素总是最后被插入的元素 从而也是最先被删除的元素 即栈是按 先进后出 FILO 的原则组织数据的 因此 栈具有记忆作用 通常用指针top指示栈顶位置 指针bottom指向栈底位置 2 栈的顺序存储及其运算 栈的顺序存储结构是指利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针指示栈顶元素在顺序栈中的位置 详见教材P20图 栈的基本运算有三个 入栈在栈顶位置插入一个新元素 可分为两个基本操作 将栈顶指针进一 将新元素插入到栈顶指针指向的位置当栈顶指针指向存储空间的最后一个位置时 栈空间已满 不能再进行入栈操作 称作 上溢 错误 退栈取出栈顶并赋于一个指定的变量 可分为两个基本的操作 将栈顶元素 栈顶指针指向的元素 赋于一个指定的变量 栈顶指针退一当栈顶指针为零时 栈已空 不能再进行退栈操作 称作 下溢 错误 读栈顶元素将栈顶元素赋于一个指定变量 读栈顶元素时 并不删除栈顶元素 只是将它的值赋于一个变量 因此栈顶指针不会改变 当栈顶指针为零时 栈已空 读不到栈顶元素 2 队列及其基本运算 1 队列的概念 队列是指允许在一端进行插入 而在另一端进行删除的线性表 允许插入的一端称为队尾 队尾指针 rear 指向队尾元素 最后被插入的元素 允许删除的一端称为排头 排头指针 front 指向排头元素的前一个位置 队列中 最先被插入的元素 最先被删除 即队列是一个 先进先出 FIFO 的线性表 2 循环队列及其运算队列的顺序存储结构一般采用循环队列的形式 循环队列就是将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用 P22 在循环队列中 用队尾指针 rear 指向队列中的队尾元素 用排头指针 front 指向排头元素的前一个位置 从排头指针指向的后一个位置到队尾指针指向的位置之间所有的元素均为队列中的元素 循环队列的初始状态为空 即 rear front m 循环队列有两种基本运算 入队运算每进行一次入队运算 队尾指针就进一 当队尾指针rear m 1时 则置rear 1 退队运算每进行一次退队运算 排头指针就进一 当排头指针front m 1时 则置front 1 当循环队列满时 有front rear 而当循环队列空时 也有front rear 即不能根据front rear来判断队列的满还是空 循环队列的满与空由增加的标志s定义 s 0 队列为空 s 1 队列非空 因此 队列为空的条件 s 0队列非空的条件 s 1且front rear m 入队运算在队尾加入一个新元素 可分为两个基本的操作 队尾指针进一 即 rear rear 1 并当rear m 1时 置rear 1 将新元素插入到队尾指针指向的位置当循环队列非空且队尾指针等于排头指针时 循环队列已满 不能进行入队运算 称作 上溢 退队运算在队头位置退出一个元素并赋给指定的变量 可分为两个基本的操作 排头指针进一 即 front front 1 并当front m 1时 置front 1 将排头指针指向的元素赋给指定的变量 当循环队列为空进 不能进行退队运算 称作 下溢 1 下列关于栈叙述正确的是 A A 栈顶元素最先能被删除B 栈顶元素最后才能被删除C 栈底元素永远不能被删除D 以上三种说法都不对 11 3 2 下列数据结构中 能够按照 先进后出 原则存取数据的是 A 循环队列B 栈C 队列D 二叉树答案B解析 栈是先进后出或后进先出的线性表 09 9 3 下列叙述中正确的是 D A 栈是 先进先出 的线性表B 队列是 先进后出 的线性表C 循环队列是非线性结构D 有序线性表既可以采用顺序存储结构 也可以采用链式存储结构 09 3 4 一个栈的初始状态为空 现将元素1 2 3 4 5 A B C D E依次入栈 然后再依次出栈 则元素出栈的顺序是 B A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 08 9 5 下列关于栈的描述中错误的是 A A 栈是先进后出的线性表B 栈只能顺序存储C 栈具有记忆作用D 对栈的插入与删除操作中 不需要改变栈底指针 6 下列叙述中正确的是 A 在栈中 栈中元素随栈底指针与栈顶指针的变化而动态变化B 在栈中 栈顶指针不变 栈中元素随栈底指针的变化而动态变化C 在栈中 栈底指针不变 栈中元素随栈顶指针的变化而动态变化D 上述三种说法都不对 7 一个栈的入栈序列是1 2 3 n 其出栈序列是P1 P2 P3 Pn 如果P1 n 那么Pi为 分析 栈是先进后出的线性表 当P1 n 即n是最先出栈的 n必定是最后入栈的 那么 进栈顺序是 1 2 3 n 则出栈的顺序是 n n 1 n 2 1 n i 1 1 5线性链表 1 线性链表的基本概念 数据结构中的每一个数据结点对应于一个存储单元 此存储单元称为存储结点 结点 在链式存储结构中 每个结点由两部分构成 数据域存放数据元素值 指针域存放下一个元素 后件 结点地址 链式存储结构中 存储数据结构的存储空间可以不连续 数据元素之间的逻辑关系由指针域确定 链式存储方式既可以表示线性结构 也可以表示非线性结构 1 线性链表 线性表的链式存储结构称为线性链表 在线性链表中 用一个指针HEAD指向线性链表中的第一个数据元素的结点 序号 线性表中最后一个元素没有后件 因此线性链表中最后一个结点的指针域为空 NULL或0 表示链表终止 在线性表的链式存储结构中 各数据结点的存储序号是不连续的 且各结点在存储空间中的位置关系与逻辑关系也不一致 在线性链表中 各数据元素之间的前后件关系由各结点的指针域来指示 当指向第一个结点的头指针HEAD NULL 或0 时称空表 如果对线性链表中的每一个结点设置两个指针 左指针指向其前件结点 右指针指向其后件结点这样的线性链表称为双向链表 2 带链的栈和队列 栈和队列都是线性表 因此也可以采用链式存储结构 2 线性链表的基本运算 1 在线性链表中查找指定元素在线性链表中寻找包含指定元素值x的前一个结点p 基本方法从头指针指向的结点开始往后沿指针进行扫描 直到后面已没有结点或下一个结点的数据域为x为止 查找的结果 线性表链表中存在包含元素x的结点时 则找到的p为第一次遇到的包含元素x的前一个结点序号 线性链表中不存在包含元素x的结点时 则找到的p为线性链表中的最后一个结点序号 2 在线性链表的插入线性链表的插入是指在链式存储结构下的线性表中插入一个新元素 给新元素分配一个结点 新结点利用栈取得 将存放新元素值的结点链接到线性链表中指定的位置 3 在线性链表的删除线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点 在线性链表中删除元素仅需修改被删除元素前件的指针域 3 循环链表及其基本运算 循环链表是另一种形式的链式存储结构 与线性链表相比 其特点是 循环链表中增加了表头结点 其数据域为任意或者根据需要来设置 指针域指向线性表的第一个元素的结点 循环链表中最后一个结点的指针域不为空 而是指向表头结点 形成一个环状链 1 下列关于线性链表的叙述中 正确的是 C A 各数据结点的存储空间可以不连续 但它们有存储顺序与逻辑顺序必须一致B 各数据结点的存储顺序与逻辑顺序可以不一致 但它们的存储空间必须连续C 进行插入与删除时 不需要移动表中的元素D 以上三种说法都不对 11 9 2 下列叙述中正确的是 A A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 08 9 3 下列对于线性链表的描述中正确的是 A A 存储空间不一定连续 且各元素的存储顺序是任意的B 存储空间不一定连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 4 对于循环队列 下列叙述中正确的是 A 队头指针是固定不变的B 队头指针一定大于队尾指针C 队头指针一定小于队尾指针D 队头指针可以大于队尾指针 也可以小于队尾指针答案D解析 如果队头指针大于队尾指针说明队列已经循环存放数据了 如果队头指针小于队尾指针说明没有进行循环存放 09 9 5 下列叙述中正确的是 D A 循环队列有队头和队尾两个指针 因此 循环队列是非线性结构B 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况C 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况D 循环队列中元素的个数是由队头指针和队尾指针共同决定 08 9 6 某循环队列的容量是50 如果排头指针front 45 队尾指针rear 10 则该循环队列中共有 个元素 分析 循环队列的排头指针指向第一个元素的前一个位置 队尾指针指向队尾元素 从排头指针指向的后一个位置到队尾指针指向的位置之间所有的元素均为队列中的元素 即 46 47 50 1 2 10 15 例 一个容量为15的循环队列中 如果其头指针front 6 尾指针rear 9 则该循环队列中共有 个元素 3 1 6树与二叉树 1 树的基本概念 树是一种简单的非线性结构 在树中 每一个结点只有一个前件 父结点 没有前件的结点只有一个 称根结点 树根 每一个结点都可以有多个后件 子结点 没有子结点的结点称叶子结点 一个结点所拥有的后件个数称为该结点的度 树的最大层次称为树的深度 用树表示算术表达式的原则 表达式中的每一个运算符在树中对应一个结点 称为运算符结点 运算符的每一个运算对象在杩中为该运算符结点的子树 顺序为从左到右 运算对象中的单变量均为叶子结点 2 二叉树及其基本性质 1 二叉树的概念 二叉树是一种很有用的非线性结构 二叉树的特点 非空二叉树只有一个根结点 每一个结点最多有两棵子树 且分别称作该结点的左子树和右子树 2 二叉树的基本性质 在二叉树的k层上最多有2k 1 k 1 个结点 深度为m的二叉树最多有2m 1个结点 在任意一棵二叉树中 度为0的结点 叶子结点 总是比度为2的结点多一个 具有n个结点的二叉树其深度至少为 log2n 1注 log2n 表示取log2n的整数部分 3 满二叉树和完全二叉树 满二叉树 满二叉树是指这样的一种二叉树 除最后一层外 每一层上的所有结点都有两个子结点 满二叉树的每一层上的结点数都达到最大值 即在第k层上有2k 1个结点 深度为m的满二叉树有2m 1个结点 完全二叉树 完全二叉树是指这样的一种二叉树 除最后一层外 每一层上的结点数都达到最大值 在最后一层上只缺少右边的若干个结点 完全二叉树的叶子结点只可能在层次最大的两层出现 满二叉树也是完全二叉树 而完全二叉树一般不是满二叉树 完全二叉树还具有以下两个性质 具有n个结点的完全二叉树的深度为 log2n 设完全二叉树共有n个结点 如果从根结点开始 从上到下 从左到右用自然数1 2 3 n给结点进行编号 则对于编号为k的结点有以下结论 若k 1 则该结点为根结点 它无父结点 若k 1 则该结点的父结点编号为INT k 2 若2k n 则编号为k的结点的左子结点编号为2k 否则该结点无左子结点 显然也无右子结点 若2k 1 n 则编号为k的结点的右子结点编号为2k 1 否则该结点无左子结点 3 二叉树的存储结构 二叉树通常采用链式存储结构 二叉链表 二叉树各元素的存储结点由两部分组成 数据域和指针域 二叉树的指针域有两个 左指针域指向该结点的左子结点存储地址 右指针域指向该结点的右子结点存储地址 4 二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点 二叉树的遍历分为三种 前序遍历 中序遍历 后序遍历 1 前序遍历若二叉树为空 则结束遍历返回 否则 访问根结点 前序遍历左子树 前序遍历右子树 在遍历左 右子树时 仍然先访问根结点 然后前序遍历左子树 最后前序遍历右子树 P38 A B D H I E J K C F L M G N O 2 中序遍历若二叉树为空 则结束遍历返回 否则 中序遍历左子树 访问根结点 中序遍历右子树 在遍历左 右子树时 仍然先中序遍历左子树 然后访问根结点 最后中序遍历右子树 P38 H D I B J E K A L F M C N G O 3 后序遍历若二叉树为空 则结束遍历返回 否则 后序遍历左子树 后序遍历右子树 访问根结点 在遍历左 右子树时 仍然先后序遍历左子树 然后后序遍历右子树 最后访问根结点 P38 H I D J K E B L M F N O G C A 例 下图所示的二叉树的前序遍历是 A B D H E C F I J G A B C D H F G J I E 例 下图所示的二叉树的中序遍历是 D H B E A I F J C G A B C D H F G J I E 例 下图所示的二叉树的后序遍历是 H D E B I J F G C A A B C D H F G J I E 例 设一棵二叉树的中序遍历结果为D B E A F C 前序遍历结果为A B D E C F 则其后序遍历的结果为 分析 1 根据中序遍历的第1个结点为D 且该结点在前序遍历中为第3个结点可知 该二叉树深度为3 且最左的子树为D 根结点为A B是A的左子树 且是D的父结点 2 由中序 D B E可知 B的右子树是E 3 由中序F C和前序C F可知 F是C的左子树 且C是A的右树 P47 D E B F C A 例 设树T的度为4 其中度为1 2 3 4的结点个数分别为 4 2 1 1 则这棵树中的叶子结点有 分析 1 此树的结点数 含根结点和叶子结点 共计 1 4 2 2 3 1 4 1 1 16 2 此树的子树共计 4 2 1 1 8 3 因此该树的叶子结点为 16 8 8 P47 8 例 设一棵完全二叉树共有700个结点 则在该二叉树中有 叶子结点 分析 1 一个深度为n的完全二叉树 从其第1层至其第n 1层必定是满二叉树 而m层的满二叉树的结点数共有2m 1个 由此可知该二叉树共有10层 从第1层至其第9层是满二叉树 共有511个结点 第9层为29 1 256个结点 2 由于该二叉树是完全二叉树 因此其第10层均为叶子结点 计700 511 189个 3 这189个叶子结点来自INT 189 2 95个父结点 即第9层有95棵子树 4 第9层的叶子结点数为 256 95 161 5 该完全二叉树的叶子结点计189 161 350 P47 350 1 对下列二叉树进行中序遍历的结果DBXEAYFZC 08 9 例1 支持子程序调用的数据结构是 A A 栈B 树C 队列D 二叉树 例2 某二叉树有5个度为2的结点 则该二叉树中的叶子结点数是 C A 10B 8C 6D 4 09 3 例3 假设用一个长度为5 的数组 数组元素的下标从0到49 作为栈的存储空间 栈底指针botto 指向栈底元素 栈顶指针七 p指向栈顶元素 如果bottom 49 七 p 30 数组下标 则栈中具有19个元素 09 3 例3 下列数据结构中 属于非线性结构的是 A 循环队列B 带链队列C 二叉树D 带链栈答案C解析树均是非线性结构 09 9 例3 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A A 219B 221C 229D 231 例5 某二叉树共有7个结点 其中叶子结点只有l个 则该二叉树的深度为 假设根结点在第1层 D A 3B 4C 6D 7 11 3 例6 下列关于二叉树的叙述中 正确的是 A 叶子结点总是比度为2的结点少一个B 叶子结点总是比度为2的结点多一个C 叶子结点数是度为2的结点数的两倍D 度为2的结点数据是度为1的结点数的两倍答案 B 11 9 1 7查找技术 查找是指在一个给定的数据结构中查找某个指定的元素 根据不同的数据结构 应采用不同的查找方法 1 顺序查找 一般是指在线性表中查找指定的元素 查找方法 从线性表的第一个元素开始 依次将线性表中的元素与被查找元素进行比较 在下列两种情况下只能采用顺序查找 线性表为无序表 线性表虽然有序 但采用链式存储结构 长度为n的线性表 最坏情况下顺序查找需要比较n次 2 二分法查找 只适用于顺序存储的有序表 按元素值非递减排列 允许相邻元素值相等 查找方法 将表的中间项与查找值x比较 相等说明已查找到 结束查找 大于x在表的上半部分以同样方式查找 小于x在表的下半部分以同样方式查找 长度为n的有序线性表 最坏情况下二分法查找需要比较log2n次 例 有序线性表能进行二分查找的前提是该线性表必须是 存储的 11 3 顺序 1 8排序技术 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列 1 交换类排序 1 冒泡法通过相邻数据元素的交换逐步使表有序 长度为n的线性表 在最坏的情况下 冒泡排序需要经过n 2次的从前至后的扫描和n 2次的从后至前的扫描 需要比较次数为 n n 1 2 2 快速排序法快速排序法的关键是对线性表进行分割 以及对各分割出的子表再进行子分割 2 插入类排序 1 简单插入类排序 将无序序列中的各个数据元素依次插入到已经有序的线性表中 长度为n的线性表 在最坏的情况下 简单插入排序需要经过n n 1 2次的比较 2 希尔排序法 将整个无序序列分割成若干小的子序列分别进行插入排序 长度为n的线性表 在最坏的情况下 希尔排序所需要的比较次数为 O n1 5 3 选择类排序 1 简单选择类排序 扫描整个线性表 从选出最小的元素 将它交换到最前面 对剩下的子表采用同样的方法 直到子表为空 长度为n的序列 在最坏的情况下 简单选择排序法需要经过n n 1 2次的比较 2 堆排序法 长度为n的序列 在最坏的情况下 堆排序的比较次数为O nlog2n 例1 下列叙述中正确的是 A A 对长度为n的有序链表进行查找 最坏情况下需要的比较次数为nB 对长度为n的有序链表进行对分查找 最坏情况下需要的比较次数为 n 2 C 对长度为n的有序链表进行对分查找 最坏情况下需要的比较次数为 log2n D 对长度为n的有序链表进行对分查找 最坏情况下需要的比较次数为 nlog2n 10 3 例2 对于长度为n的线性表 在最坏情况下 下列各排序法所对应的比较次数中正确的是 B A 冒泡排序为n 2B 冒泡排序为nC 快速排序为nD 快速排序为n n 1 2 例3 对长度为n的线性表进行顺序查找 在最坏情况下所需要的比较次数为 B A log2nB n 2C nD n 1 例4 长度为n的有序线性表中进行的二分法查找 需要的比较次数为 例5 在最坏的情况下 冒泡排序的时间复杂度为 log2n n n 1 2 例6 在长度为n的有序线性表中进行二分查找 最坏情况下需要比较的次数是 C A O n B O n2 C O log2n D O nlog2n 08 9 4 下列排序方法中 最坏情况下比较次数最少的是 D A 冒泡排序B 简单选择排序C 直接插入排序D 堆排序 09 3 第二章 程序设计基础 P50 本章考试要点 程序设计方法与风格 结构化程序设计 面向对象的程序设计方法 掌握并理解对象 方法 属性 以及继承与多态性的概念 2 1程序设计方法与风格 1 程序设计方法 结构化程序设计 面向对象程序设计2 程序设计风格主要注重和考虑的因素 源程序文档化 数据说明的方法 语句的结构 输入和输出 2 2结构化程序设计 1 结构化程序设计原则 自顶向下 逐步求精 模块化 限制使用Goto语句2 结构化程序的基本结构与特点 顺序结构 选择结构 分支结构 循环结构 重复结构 3 结构化程序设计原则和方法的应用 2 3面向对象的程序设计 1 对象 面向对象程序设计中的最基本的概念 用来表示客观世界中的任何实体 它既可以是具体的物理实体 也可以是一个抽象的概念 对象具有 标识惟一性 分类性 多态性 封装性和模块独立性 2 属性 对象所包含的信息 一般只能通过执行对象的操作来改变 3 操作 方法 描述了对象的执行功能 若通过信息传递 还可以为其它对象使用 操作过程对外是封闭的 用户只能看到这一操作实施后的结果 4 类和实例 类是具有共同属性 共同方法的对象的集合 类的对象的抽象 它描述了属于该对象类型的所有对象的性质 而一个对象则是其对应类的一个实例 5 消息 事件 面向对象的世界是通过对象与对象间彼此的相互合作来推动的 对象间的这种相互合作需要一个机制协助进行 这样的机制称为 消息 6 继承 继承是使用已有的类定义作为基础建立新类的定义技术 已有的类可当做基类来引用 则新类相应地可当做派生类来引用 继承是指能够直接获得已有的性质和特征 而不必重复定义它们 7 多态性 对象根据所接受的消息而做出的动作 同样的消息被不同的对象接受时可导致完全不同的行动 该现象称为多态性 多态性是指子类对象可以像父类对象那样使用 同样的消息既可以发送给父类对象 也可以发送给子类对象 多态性机制增加了面向对象软件系统的灵活性 进一步减少了信息冗余 例 编制一个好的程序 首先要确保它的正确性和可靠性 还应强调良好的编程风格 在选择标识符的名字时应考虑 A 名字长度越长越好 以便理解变量的含义B 多个变量共用一个名字 以减少变量的数目C 选择含义明确的名字 以正确提示所代表的实体D 尽量用关键字作名字 以使名字标准化 C 例 在面向对象方法中 不属于 对象 基本特点的是 A A 一致性B 分类性C 多态性D 标识唯一性 例 下图所示的流程控制结构称为 选择结构 08 9 例 符合结构化原则的三种基本控制结构是 选择结构 循环结构和顺序结构 09 3 例 下列选项中不属于结构化程序设计原则的是 A 可封装B 自顶向下C 模块化D 逐步求精答案A 例 程序流程图中的菱形框表示的是逻辑分析 09 9 例 面向对象方法中 继承是指 A 一组对象所具有的相似性质B 一个对象具有另一个对象的性质C 各对象之间的共同性质D 类之间共享属性和操作的机制 例 仅由顺序 选择 分支 和重复 循环 结构构成的程序是 程序 10 9 D 结构化 例 下列选项中属于面向对象设计方法主要特征的是 A 继承B 自顶向下C 模块化D 逐步求精答案 A分析 结构化程序设计方法的主要原则是自顶向下 逐步求精 模块化 以及限制使用Goto语句 面向对象程序设计的3个主要特征是 封装性 继承性和多态性 11 9 例 软件设计中划分模块的一个准则是 A 低内聚低耦合B 高内聚低耦合C 低内聚高耦合D 高内聚高耦合答案B解析 模块内部各元素之间的联系要紧密 高内聚 模块间的连接的紧密程度要低 低耦合 这样可以提高模块的独立性 09 9 第三章 软件工程基础 P60 本章考试要点 软件工程基本概念 软件生命周期概念 软件工具与软件开发环境 结构化分析方法 数据流图 数据字典 软件需求规格说明书的概念 结构化设计方法 总体设计与详细设计 软件测试方法 白盒测试与黑盒测试 测试用例设计 软件测试的实施 单元测试 集成测试和测试系统 程序调试 静态调试与动态调试 3 1软件工程基本概念 1 软件定义软件特点 软件是计算机系统中与硬件相互依存的另一部分 它包括 程序 数据及相关文档的完整集合 软件特点2 软件危机与软件工程 软件危机是泛指计算机软件的开发和维护过程中所遇到的一系列严重问题 其主要表现于六个方面 软件工程包括三个要素 方法 工具 过程 软件工程的核心思想 3 软件工程过程与软件生命周期 软件工程过程是把输入转化为输出一组彼此相关的资源和活动 软件的生命周期包括 可行性研究与计划制定 需求分析 软件设计 包括 概要设计和详细设计 软件实现 软件测试 运行和维护其中 是定义阶段 是开发阶段 是维护阶段 含退役 4 软件工程的目标与原则 软件工程的目标是 在给定成本 进度的前提下 开发出具有有效性 可靠性 可理解性 可维护性 可重用性 可适应性 可移植性 可追踪性和可互操作性且满足用户需求的产品 软件工程的原则 详见教材 5 软件开发工具与软件开发环境 计算机辅助软件工程 CASE 集成了软件 硬件和一个软件工程数据库 从而创建了一个软件工程开发的环境 3 2结构化分析方法 1 需求分析与需求分析方法 需求分析的定义 需求分析阶段的工作 需求分析方法 结构化分析方法 面向对象的分析方法 2 结构化分析方法 1 结构化分析方法概述 结构化分析是使用数据流图 DFD 数据字典 DD 结构化英语 判定表和判定树等工具来建立一种新的 称为结构化规格的说明的目标文档 结构化分析的实质是着眼于数据流 自顶向下 逐步分解的系统分析方法来定义系统需求 结构化分析以数据流图和数据字典作为主要工具 建立系统的逻辑模型 数据字典描述了所有在目标系统中使用的和生成的数据对象 围绕结构化分析模型的核心有三个图 实体 关系图 EFD 描述数据对象及数据对象之间的关系 数据流图 DFD 描述数据在系统中如何被传递或变换以及描述如何对数据流进行变换的功能 子功能 状态 迁移图 STD 描述系统对外部事件如何响应 如何动作 其中 ERD用于数据建模 DFD用于功能建模 STD用于行为建模 2 结构化分析的常用工具 数据流图 DFD 数据流图是描述数据处理过程的工具 是需求理解的逻辑模型的图形表示 数据流图中的主要图形元素 数据字典 DD 数据字典是关于数据的信息集合 对数据流图中的各个元素做完整的定义与说明 是数据流图的补充工具 数据流图和数据字典共同构成系统的逻辑模型 3 软件需求规格说明书软件需求规格说明书是需求分析阶段的最后成果 是软件开发中的重要文档之一 3 3结构化设计方法 1 软件设计的基本概念 软件设计包括 软件结构设计 数据设计 接口设计 过程设计 软件设计分为两个步骤 概要设计 详细设计2 软件设计的基本原理3 结构化设计方法结构化设计方法的基本思想是 将软件设计成相对独立 单一功能的模块组成的结构 2 概要设计 概要设计的任务 设计软件系统结构 数据结构及数据库设计 编写概要设计文档 概要设计文档评审 面向数据流的设计方法 数据流类型 变换型和事务型 面向数据流设计方法的实施要点与设计过程 3 详细设计 详细设计的任务 详细设计的主要工具 程序流程图 基本图符及5种控制结构 N S图 基本特征 PAD图 基本特征 基本图符及5种控制结构 PDL 常用词汇 3 4软件测试 1 软件测试概述 软件测试的目的 软件测试的准则2 软件测试技术与方法综述 1 静态测试与动态测试 静态测试 不实际运行代码 包括 代码检查 静态结构分析 代码质量度量等 动态测试 基于计算机的测试 是为了发现错误而执行程序的过程 2 白盒测试方法 白盒测试 结构测试 逻辑驱动测试 的基本思路 白盒测试的基本原则 白盒测试法是穷举路径测试 白盒测试的主要方法 逻辑覆盖测试 语句覆盖 路径覆盖等 基本路径测试 3 黑盒测试方法 黑盒测试的基本思路 黑盒测试的主要诊断功能 黑盒测试法的主要方法 等价类划分法 边界值分析法 错误推测法 因果图法 无论是使用白盒测试方法还是黑盒测试方法或是其它测试方法 针对一种方法设计的测试用例 仅仅是易于发现某种类型的错误 对其它类型的错误不易发现 所以没有一种用例设计方法能能测试方案 而是各有所长 3 软件测试的实施软件测试的实施分为四个步骤 单元测试 集成测试 确认测试 系统测试 3 5程序的调试 1 程序调试的基本概念 程序调试的任务 程序调试的基本步骤 程序调试的原则2 程序调试的方法 强行排错法 回溯法 原因排除法 例 数据流图中带有箭头的线段表示的是 D A 控制流B 事件驱动C 模块调用D 数据流 例 在软件开发中 需求分析阶段可以使用的工具是 B A N S图B DFD图C PAD图D 程序流程图 08 9 例 按照软件测试的一般步骤 集成测试应在单元测试之后进行 例 软件工程三要素包括方法 工具和过程 其中 过程支持软件开发的各个环节的控制和管理 08 9 例 方向叙述中错误的是 A A 软件测试的目的是发现错误并改正错误B 对被调试的程序进行 错误定位 是程序调试的必要步骤C 程序调试通常也称为DebugD 软件测试应严格执行侧试计划 排除测试的随意性 例 软件测试可分为白盒测试和黑盒厕试 基本路径测试属于白盒测试 09 3 例 耦合性和内聚性是刘模块独立性度量的两个标准下列叙述中正确的是 B A 提高祸合性降低内聚性有利于捉高模块的独立性B 降低祸合性提高内聚性有利于提高模块的独立性C 合性是指一个模块内部各个元素间彼此结合的紧密程度D 内聚性是指模块间互相连接的紧密程度 09 3 例 软件详细设计产生的图如下 该图是 A N S图B PAD图C 程序流程图D E R图答案C 09 9 例 软件开发过程主要分为需求分析 设计 编码与测试四个阶段 其中需求分析阶段产生 软件需求规格说明书 09 9 例 软件测试的目的是 A 证明软件系统中存在错误B 找出软件系统中存在的所有错误C 尽可能多地发现软件系统中的错误和缺陷D 证明软件的正确性分析 软件测试的目的不是证明系统的正确或是系统中存在错误 而是要发现错误以便编程人员能够改正 系统中的错误和缺陷往往由于多咱因素的影响 不可能完全发现 只能是尽可能地去发现并加以改正 10 3 C 例 在进行单元测试时 常用的方法是 A 采用白盒测试 辅以黑盒测试B 采用黑盒测试 辅以白盒测试C 只使用白盒测试D 只使用黑盒测试分析 本题考核的是软件测试方法的应用 白盒测试是测试程序内部的逻辑结构及有关信息 黑盒测试只依据程序的需求规格说明书 检查程序的功能是否符合它功能说明 从程序内部的逻辑结构对系统进行测试才是测试的根本 即是比较深层次的测试 A 例 下列叙述正确的是 A 测试与调试工作必须由程序编制者自己完成B 测试用例与调试用例必须一致C 一个程序经调试改正错误后 一般不必再进行测试D 以上三种说法都不对 B 例 下列叙述正确的是 A 黑盒测试方法完全不考虑程序的内部结构和内部特征B 黑盒测试方法主要考虑程序的内部结构和内部特征C 白盒测试主要考虑内部的逻辑结构D 以上三种说法都不对 A 5 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下面属于应用软件的是 C A 编译程序B 操作系统C 教务管理系统D 汇编程序 09 3 例 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下面属于系统软件的是 B A 编辑软件B 操作系统C 教务管理系统D 浏览器 例 软件 程序 调试的任务是 A A 诊断和改正程序中的错误B 尽可能多地发现程序中的错误C 发现并改正程序中的所有错误D 确定程序中错误的性质 10 3 例 数据流程图 DFD图 是 C A 软件概要设计的工具B 软件详细设计的工具C 结构化方法的需求分析工具D 面向对象方法的需求分析工具 例 软件生命周期可分为定义阶段 开发阶段和维护阶段 详细设计属于 B A 定义阶段B 开发阶段C 维护阶段D 上述三个阶段 10 3 例 程序调试的任务是 A 设计测试用例B 验证程序的正确性C 发现程序中的错误D 诊断和改正程序中的错误分析 在完成对程序的测试后将进行程序调试 程序调试的任务是诊断和改正程序中的错误 答案 D 11 9 例 在软件开发中 需求分析阶段产生的主要文档是 D A 软件集成测试计划B 软件详细设计说明书C 用户手册D 软件需求规格说明书 11 3 例 对软件设计的最小单位 模块或程序单元 进行的测试通常称为 测试 单元 例 结构化程序所要求的基本结构不包括 B A 顺序结构B GOTO跳转C 选择 分支 结构D 重复 循环 结构 例 下面描述中错误的是 A A 系统总体结构图支持软件系统的详细设计B 软件设计是将软件需求转换为软件表示的过程C 数据结构与数据库设计是软件设计的任务之一D PAD图是软件详细设计的表示工具 11 3 例 软件按功能可以分为应用软件 系统软件和支撑软件 或工具软件 下面属于应用软件的是 A 学生成绩管理系统B C语言编译程序C UNIX操作系统D 数据库管理系统答案 A 11 9 例 某系统总体结构图如下所示 该系统总体结构图的深度是 C A 7B 6C 3D 2 11 9 例 下列工具中 属于需求分析常用工具的是 A PADB PFDC N SD DFD P99 D 例 在软件的生命周期中 能够准确地确定软件系统必须做什么和必须具备哪些功能的阶段是 A 概要设计阶段B 详细设计阶段C 可行性分析阶段D 需求分析阶段 D 第四章 数据库设计基础 P101 本章考试要点 数据库的基本概念 数据库 数据库管理系统 数据库系统 数据模型 实体联系模型及E R图 从E R图导出关系数据模型 关系代数运算 集合运算及选择 投影 联接运算 数据库规范化理论 数据库设计方法和步骤 需求分析 概念设计 逻辑设计和物理设计的相关策略 4 1数据库系统的基本概念 1 数据 数据库数据库管理系统数据数据库 长期存储在计算机内的 有组织的 可共享的数据集合 数据库是由一个互相关联的数据的集合和一组用以访问这些数据的程序组成 数据库管理系统数据库管理员数据库系统数据库应用系统 2 数据库系统的发展 人工管理阶段 文件系统阶段 数据库系统阶段3 数据库系统的基本特点 数据的集成性 数据的高共享性与低冗余性 数据的独立性 物理独立性与逻辑独立性 数据统一管理与控制 4 数据库系统的内部结构体系 三级模式 概念模式 内模式 外模式 两级映射 概念模式到内模式的映射 外模式到概念模式的映射 4 2数据模型 1 数据模型的基本概念 数据模型的定义 数据模型所描述内容的三个部分 数据结构 数据操作 数据约束 数据模型的类型 概念模型面向用户的模型 逻辑模型 数据模型 面向数据库系统的模型 只有转换成数据模型后才能在数据库中得以表示 物理模型面向计算机的物理表示