二级公共基础教案高频考点分析与真题解析PPT课件

二级公共基础考前辅导 Email huxiaoli 主讲教师 胡晓丽 桂林电子科技大学 1 相关知识 在二级考试中 占总分的30 数据结构与算法程序设计基础软件工程基础数据库设计基础 2 各部分所占比例图 3 数据结构与算法高频考点 Top1 算法的基本概念Top2 算法的复杂度Top3 逻辑结构与存储结构Top4 线性结构与非线性结构Top5 栈Top6 队列Top7 链表Top8 二叉树及其基本性质 4 数据结构与算法高频考点 Top9 二叉树的遍历Top10 顺序查找Top11 二分法查找Top12 排序 5 Top1 算法的基本概念 知识点算法是解决问题准确而完整的描述 它是对特定问题求解步骤的一种描述 是指令的有限序列 其中每条指令表示一个或多个操作 严格来说 一个算法必须满足下面5个主要特性 6 Top1 算法的基本概念 有穷性 一个算法必须在执行有穷步之后结束 对任何合法的输入值 而且每一步都必须在有穷时间内完成 确定性 算法中每条指令必须有确定的含义 且在任何条件下 算法只有唯一的一条执行路径 可行性 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 有输入 一个算法可以有0个或多个输入 有输出 一个算法必须有1个或多个输出 7 Top1 算法的基本概念 真题分析 2011年9月 下列说法中正确的是 A 算法就是程序B 设计算法时只需考虑数据结构的设计C 设计算法时只需考虑结果的可靠性D 以上三种说法都不对 D 算法是描述解决问题的方法与步骤 它与数据结构 运算结果的状态无关 程序是采用某种程序设计语言对问题的对象和解题的步骤进行描述 软件的主体是程序 程序的核心是算法 8 Top1 算法的基本概念 真题分析 2008年4月 算法的有穷性是指 A 算法程序的运行时间是有限的B 算法程序所处理的数据量是有限的C 算法程序的长度是有限的D 算法只能被有限的用户使用 A 一个算法必须在执行有穷步之后结束 对任何合法的输入值 而且每一步都必须在有穷时间内完成 9 Top1 算法的基本概念 真题分析 2005年4月 算法具有5个特性 下列选项中不属于算法特性的是 A 有穷性B 简洁性C 可行性D 确定性 B 有穷性确定性可行性有输入 可以是0个 有输出 至少是1个 10 Top1 算法的基本概念 练习题1 算法的五个重要特性是有穷性 确定性 有输入和有输出 可行性 11 Top2 算法的复杂度 知识点衡量算法优劣的两个标准一个算法的优劣将影响到算法乃至程序的效率 算法分析的目的是在于选择合适的算法和改进算法 评价一个算法的好坏有两个标准 时间复杂度和空间复杂度 12 Top2 算法的复杂度 算法的时间复杂度是指执行算法所需要的计算工作量 可以用执行算法的过程中所需要的基本运算的执行次数来度量 算法的空间复杂度是指执行这个算法所需要的内存空间的大小 13 Top2 算法的复杂度 真题分析 2007年4月 下列叙述中正确的是 A 算法的效率只与问题的规模有关 而与数据的存储结构无关 B 算法的时间复杂度是指执行算法所需要的计算工作量 C 数据的逻辑结构与存储结构是一一对应的 D 算法的空间复杂度与时间复杂度一定相关 B 算法的效率不仅与问题的规模与关 还与数据结构有关 数据的逻辑结构 存储结构 一种逻辑结构可以对应多种存储结构 时间复杂度与空间复杂度不相关 14 Top2 算法的复杂度 真题分析 2006年9月 下列叙述中正确的是 A 一个算法的空间复杂度大 则其时间复杂度必定大 B 一个算法的空间复杂度大 则其时间复杂度必定小 C 一个算法的时间复杂度大 则其空间复杂度必定小 D 上述三种说法都不对 D 时间复杂度与空间复杂度不相关 15 Top2 算法的复杂度 真题分析 2005年9月 算法的复杂度主要包括时间复杂度和 复杂度 空间 16 Top2 算法的复杂度 练习题1 算法的时间复杂度是指 A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数 C 17 Top2 算法的复杂度 练习题2 算法的空间复杂度是指 A 算法程序的长度B 算法程序中的指令条数C 算法程序所占用的存储空间D 算法执行过程中所占用的存储空间 D 在算法执行时所需要的内存空间 其中包括 算法程序所占用的空间 输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间 其中额外空间还包括算法执行过程中的工作单元以及某种数据结构所需要的附加存储空间 18 Top3 逻辑结构与存储结构 知识点逻辑结构是反映元素之间逻辑关系的 即前后件关系 分为线性结构 常见的有线性表 栈和列队 和非线性结构 常见的有树和图 存储结构 物理结构 是数据的逻辑结构在计算机存储空间中的存放形式 在数据的存储结构中 不仅要存放各种数据元素的信息 还要存放元素之间的前后件关系的信息 19 Top3 逻辑结构与存储结构 知识点数据的逻辑结构与数据的存储结构并不是一一对应的 一般来说 一种数据的逻辑结构根据需要可以表示成多种存储结构 常见的存储结构有顺序 链接 索引 散列等 采用不同的存储结构 其数据的处理效率是不同的 20 Top3 逻辑结构与存储结构 真题分析 2005年9月 下列叙述中正确的是 A 一个逻辑数据结构只能有一种存储结构B 数据的逻辑结构属于线性结构 存储结构属于非线性结构 C 一个逻辑数据结构可以有多种存储结构 且种存储结构不影响数据处理的效率 D 一个逻辑数据结构可以有多种存储结构 且种存储结构影响数据处理的效率 D 一种逻辑结构可以有多种存储结构 且不同的存储结构影响数据处理的效率 逻辑结构分为线性结构与非线性结构 21 Top3 逻辑结构与存储结构 真题分析 2005年9月 数据结构可以分为逻辑结构和存储结构 循环队列属于 结构 存储 循环队列是指将队列存储空间的最后一个位置绕到第一个位置 形成一个环状空间 供队列循环使用 所以循环队列是属于存储结构 22 Top3 逻辑结构与存储结构 真题分析 2005年4月 数据的存储结构是指 A 存储在外存中的数据B 数据所占的存储空间C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 D 23 Top3 逻辑结构与存储结构 真题分析 2007年9月 下列叙述中正确的是 A 程序执行的效率与数据的存储结构密切相关B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 程序执行的效率只取决于所处理的数据量D 以上三种说法都不对 A 24 Top3 逻辑结构与存储结构 练习题1 数据结构中 与所使用的计算机无关的是数据的 A 存储结构B 物理结构C 逻辑结构D 逻辑结构和物理结构 C 25 Top3 逻辑结构与存储结构 练习题2 在数据结构中 从逻辑上可以把数据结构分成 A 动态结构和静态结构B 线性结构和非线性结构C 集合结构和非集合结构D 树形结构和图状结构 B 26 Top4 线性结构与非线性结构 知识点根据数据结构中各数据元素之间前后件的复杂程序 一般将数据结构分为两大类型 线性结构和非线性结构 如果一个非空的数据结构满足下列两个条件 有且只有一个根结点 每个结点最多有一个前件 也最多只有一个后件 则称该数据结构为线性结构 线性表是典型的线性结构 如栈 队列 串 如果一个数据结构不是线性结构 则称为非线性结构 如多维数组 广义表 树和图等 27 Top4 线性结构与非线性结构 真题分析 2006年9月 数据结构分为线性结构和非线性结构 带链的队列属于 队列是特殊的线性表 可以采用顺序存储 也可以采用链式存储 所以带链的队列属于线性结构 线性结构 28 Top4 线性结构与非线性结构 真题分析 2011年9月 数据结构分为线性结构和非线性结构 带链的栈属于 填空题第一题 线性结构 29 Top4 线性结构与非线性结构 真题分析 2006年4月 下列叙述中正确的是 A 线性链表是线性表的链式存储结构B 栈与队列是非线性结构C 双向链表是非线性结构D 只有根结构的二叉树是线性结构 A 线性链表就是指线性表的链式存储结构 简称链表 线性表链式存储结构的基本单位称为存储结点 每个结点包括数据域和指针域两个部分 栈 队列和双向链表都是线性结构 二叉树是非线性结构 线性结构和非线性结构是从数据的逻辑结构角度来讲的 与该数据结构中有多少个元素没有关系 即使是空的二叉树也是非线性结构 30 Top4 线性结构与非线性结构 真题分析 2007年9月 下列叙述中正确的是 A 数据的逻辑结构与存储结构必定是一一对应的B 由于计算机存储空间是向量式的存储结构 因此 数据的存储结构一定是线性结构C 程序设计语言中的数组一般是顺序存储结构 因此 利用数组只能处理线线结构D 以上三种说法都不对 B 一种逻辑结构可以对应多种存储结构 存储结构一定是线性的 一般是在内存中开辟一块连续的存储单元用来存放数据元素 数组可以用来处理线性结构 也可以用来存储非线性结构 31 Top4 线性结构与非线性结构 真题分析 2008年9月 下列叙述中正确的是 A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 A 链式存储结构的存储空间可以是连续的 也可以是不连续的 链式存储主要是通过指针域来找到下一个结点所在的存储单元 32 1000 1002 1004 1006 1008 100A 100C 1 2 3 4 5 1002 1004 1006 1008 0 1 2 3 4 5 3 2 5 1 4 1008 1000 0 1002 1004 1000 1002 1004 1006 1008 100A 100C 1000 1002 1004 1006 1 2 3 4 5 链式存储 顺序存储 33 Top4 线性结构与非线性结构 真题分析 2011年3月 下列叙述中正确的是 A 有一个以上根结点的数据结构不一定是非线性结构B 只有一个根结点的数据结构不一定是线性结构C 循环链表是非线性结构D 双向链表是非线性结构 B 线性结构的定义是 1 只有一个根结点 2 除了根结点外 每个结点只有一个前件 也只有一个后件 只有一个根结点的数据结构也可能是非线性结构 如树 也只有一个根结点 34 Top4 线性结构与非线性结构 练习题1 下列叙述中正确的是 A 线性表是线性结构B 栈与队列是非线性结构C 线性链表是非线性结构D 二叉树是线性结构 A 35 Top4 线性结构与非线性结构 练习题2 以下数据结构中不属于线性数据结构的是 A 队列B 线性表C 二叉树D 栈 C 36 Top5 栈 知识点栈 堆栈STACK 是一种运算受限制的线性表 限制其只能在表的一端进行插入和删除操作 此端称为栈顶 栈顶的第一个元素称为栈顶元素 相对地 把另一端称为栈底 向一个栈插入新元素称为入栈 从栈中删除一个元素称为出栈出退栈 由于栈的插入和删除只能在一端进行 后进栈的元素必定先出栈 所以栈又称为后进先出表LIFO 先进栈的元素必定后出栈 所以栈又称为先进后出FILO表 37 Top5 栈 栈底 d c b a 栈顶 入栈 出栈 结论 后进先出 先进后出 栈顶 栈顶 栈顶 38 Top5 栈 真题分析 2006年9月 按 后进先出 原则组织数据的数据结构是 栈 39 Top5 栈 真题分析 2006年4月 按照 后进先出 原则组织数据的数据结构是 A 队列B 栈C 双向链表D 二叉树 B 40 Top5 栈 真题分析 2005年9月 下列关于栈的描述中正确的是 A 在栈中只能插入元素而不能删除元素B 在栈中只能删除元素而不能插入元素C 栈是特殊的线性表 只能在一端插入或删除D 栈是特殊的线性表 只能在一端插入 在另一端删除 C 41 Top5 栈 真题分析 2005年4月 下列关于栈的描述错误的是 A 栈是先进后出的线性表B 栈只能顺序存储C 栈具有记忆作用D 对栈的插入和删除操作中 不需要改变栈底指针 B 42 Top5 栈 真题分析 2008年4月 下列关于栈的叙述正确的是 A 栈按 先进先出 组织数据B 栈按 先进后出 组织数据C 只能在栈底插入数据D 不能删除数据 B 43 Top5 栈 真题分析 2008年9月 一个栈的初始状态为空 现将元素1 2 3 4 5 A B C D E依次入栈 然后再依次出栈 则元素出栈的顺序是 A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA B 44 Top5 栈 真题分析 2009年4月 支持子程序调用的数据结构是A 栈B 树C 队列D 二叉树 A 45 Top5 栈 真题分析 2011年3月 下列关于栈的叙述中正确的是 选择题第1题 A 栈顶元素最先能被删除B 栈顶元素最后才能被删除C 栈底元素永远不能被删除D 以上三种说法都不对 A 46 Top5 栈 练习题1 如果进栈序列为e1 e2 e3 e4 则可能的出栈序列是 A e3 e1 e4 e2B e2 e4 e3 e1C e3 e4 e1 e2D 任意顺序 B 47 Top5 栈 e4 e3 e2 e1 入栈 栈底 栈顶 栈顶 栈顶 e4 e3 e2 e1 栈底 出栈 出栈 入栈 48 Top5 栈 练习题2 下列关于栈的叙述中正确的是 A 在栈中只能插入元素B 在栈中只能删除元素C 栈是先进先出的线性表D 栈是先进后出的线性表 D 49 Top6 队列 知识点队列 QUEUE 简称队 和栈一样 也是一种运算受限制的线性表 其限制体现在仅允许在表的一端进行插入 队尾 在另一端进行删除 队首 向队列中插入新元素称为进队或入队 新元素进入后就成为新的队尾元素 从队列中删除元素称为离队或出队 元素离队后 其后继元素成为队首元素 由于队列的插入和删除操作分别是在各自的一端进行的 每个元素必然按照进入的次序离队 所以队列称为先进先出表 FIFO 或后进后出表 LILO 50 Top6 队列 e4 e3 e2 e1 队首 入队 队尾 队尾 队尾 出队 e4 e3 e2 e1 结论 先进先出 后进后出 51 Top6 队列 循环队列 rear front e1 队列为空时 头指针等于尾指针 e2 队列中元素个数为rear front rear rear 52 Top6 队列 e4 e3 e2 e1 front rear e7 e6 e5 rear front e8 rear 队头指针大于队尾指针时 元素个数 队尾 m 队头 e9 e10 rear 队头指针等于队尾指针时 队列满 53 Top6 队列 真题分析 2007年4月 下列队列的叙述中正确的是 A 队列属于非线性表B 队列按 先进后出 原则组织数据C 队列在队尾删除数据D 队列按 先进先出 原则组织数据 D 54 Top6 队列 真题分析 2008年9月 下列叙述中正确的是 A 循环队列有队头和队尾两个指针 因此 循环队列是非线性结构B 在循环队列中 只需要队头指针就能反应队列中元素的动态变化情况C 在循环队列中 只需要队尾指针就能反应队列中元素的动态变化情况D 循环队列中元素的个数是由队头和队尾指针共同决定 D 55 Top6 队列 真题分析 2007年9月 线性表的存储结构主要分为顺序存储结构和链式存储结构 队列是一种特殊的线性表 循环队列是队列的 存储结构 顺序 56 Top6 队列 真题分析 2008年4月 设某循环队列的容量为50 头指针front 5 指向队头元素的前一位置 尾指针rear 29 指向队尾元素 则该循环队列中共有 个元素 24 57 Top6 队列 练习题1 栈和队列的共同特点是 A 都是先进先出B 都是后进后出C 只允许在端点处插入和删除元素D 没有共同点 C 58 Top6 队列 练习题2 下列关于队列的叙述中正确的是 A 在队列中只能插入元素B 在队列中只能删除元素C 队列是先进先出的线性表D 队列是后进先出的线性表 C 59 Top6 队列 练习题3 一个队列的入队序列是a b c d 则队列的输出序列是 A d c b aB a b c dC a d c bD c b d a B 60 Top7 链表 单链表 知识点数据结构中 每个数据存储在一个存储单元中 这个存储单元称为 结点 在链式 单链 存储方式中 要求每个结点由两部分组成 存放数据元素的数据域和存放指针的指针域 其中指针指向该结点的前一个或后一个结点 在链式存储结构中 存储数据结构的存储空间可以不连续 各个数据结点存储顺序与数据元素的逻辑关系可以不一致 而数据元素之间的逻辑关系是由指针来确定的 线性表的链式存储结构称为线性链表 61 Top7 链表 单链表 2 0 3 1005 1003 1 1001 1002 1003 1004 1005 1006 1007 1008 head 1 head 2 3 单链表的逻辑结构 单链表的存储结构 null 62 Top7 链表 单链表 真题分析 2005年4月 下列对于线性链表的描述中正确的是 A 存储空间不一定是连续 且各元素的存储顺序是任意的 B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必定连续 且各前件元素一定存储在后件元素的前面D 存储空间必定连续 且各元素的存储顺序是任意的 A 63 Top7 链表 单链表 真题分析 2009年4月 下列叙述中正确的是A 栈是先进先出的线性表B 队列是 先进后出 的线性表C 循环队列是非线性结构D 有序线性表即可以采用顺序存储结构 也可以采用链式存储结构 D 64 Top7 链表 单链表 真题分析 2011年9月 下列关于线性链表的叙述中 正确的是 A 各个数据结点的存储空间可以不连续 但它们的存储顺序与逻辑顺序必须一致B 各个数据结点的存储顺序与逻辑顺序或以不一致 但它们的存储空间必须连续C 进行插入与删除时 不需要移动表中的元素D 以上三种说法都不对 65 Top7 链表 单链表 2 0 3 1005 1003 1 1001 1002 1003 1004 1005 1006 1007 1008 head 1 head 2 3 单链表的逻辑结构 单链表的存储结构 null 5 1007 5 1003 66 Top7 链表 单链表 真题分析 2011年9月 下列关于线性链表的叙述中 正确的是 A 各个数据结点的存储空间可以不连续 但它们的存储顺序与逻辑顺序必须一致B 各个数据结点的存储顺序与逻辑顺序或以不一致 但它们的存储空间必须连续C 进行插入与删除时 不需要移动表中的元素D 以上三种说法都不对 C 67 Top7 链表 单链表 练习题1 用链表来表示线性表的优点是 A 便于随机存取B 花费的存储空间较顺序存储少C 便于插入和删除操作D 数据元素的物理顺序与逻辑顺序相同 C 68 Top7 链表 单链表 练习题2 线性表的链式存储结构是一种 的存储结构A 随机存储B 顺序存储C 索引存储D 散列存储 B 线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素 还包括指针 每一个指针指向一个与本结点有逻辑关系的结点 此类存储属于顺序存储 69 Top8 二叉树及其基本性质 知识点树是一种非线性结构 所有数据元素之间的关系具有明显的层次性 结点 度 叶子 宽度 深 高度 70 Top8 二叉树及其基本性质 知识点二叉树具有两个特点 非空二叉树只有一个根结点 每一个结点最多有两棵子树 且分另称为左子树和右子树 A B C D E G F 71 Top8 二叉树及其基本性质 知识点二叉树的性质 在二叉树中 第i层上的结点数不超过2i 1 深度为h h 1 的二叉树最多有2h 1个结点 最少有h个结点 对于任意一棵二叉树 如果其叶子结点数 度为0 为x 而度为2的结点总数为Y 则X Y 1 具有n个结点的完全二叉树的深度为int log2n 1 72 Top8 二叉树及其基本性质 知识点完全二叉树 除最后一层外 每一层上的结点都达到最大值 2 在最后一层上的结点都集中在该层最左边的若干位置 也就是说 只能缺少右边的若干结点 A B C D E G F A B C D E H F G 73 Top8 二叉树及其基本性质 A B C D E H F G A B C D E H F G I 完全二叉树特点 有n个结点的完全二叉树 其深度为log2n 1 74 Top8 二叉树及其基本性质 知识点满二叉树 除最后一层外 其它每一层上的结点都有两个子结点 A B C D E F E A B C 75 Top8 二叉树及其基本性质 真题分析 2011年9月 下列关于二叉树的叙述中 正确的是 选择题第3题 A 叶子结点总是比度为2的结点少一个B 叶子结点总是比度为2的结点多一个C 叶子结点数是度为2的结点数的两倍D 度为2的结点是度为1的结点数的两倍 B 性质3 对于任意一棵二叉树 如果其叶子结点数 度为0 为x 而度为2的结点总数为Y 则X Y 1 76 Top8 二叉树及其基本性质 真题分析 2007年4月 某二叉树中有n个度为2的结点 则该二叉树中 叶子结点数为 A n 1B n 1C 2nD n 2 A 77 Top8 二叉树及其基本性质 真题分析 2007年4月 在深度为7的满二叉树中 度为2的结点个数为 27 1 N0 N2 N2 N0 1 127 N0 N0 1 N0 64 N2 63 63 78 Top8 二叉树及其基本性质 真题分析 2006年4月 在深度为7的满二叉树中 叶子结点的个数为 A 32B 31C 64D 63 C 满二叉树每一层上的结点数都是最大结点数2i 1 79 Top8 二叉树及其基本性质 真题分析 2011年3月 某二叉树共有7个结点 其中叶子结点只有1个 则该二叉树的深度为 假设根结点在第1层 选择题第3题 A 3B 4C 6D 7 D A B C D E F G 80 Top8 二叉树及其基本性质 真题分析 2005年9月 一棵二叉树第六层 根结点为第1层 的结点数最多为 个 二叉树性质 在二叉树中 第i层上的结点数不超过2i 1 32 81 Top8 二叉树及其基本性质 真题分析 2005年4月 某二叉树中 度为2的结点数有18个 则该二叉树中有 个叶子结点 19 82 Top8 二叉树及其基本性质 真题分析 2007年9月 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A 219B 221C 229D 231 A 83 Top8 二叉树及其基本性质 真题分析 2008年4月 深度为5的满二叉树有 个叶子结点 16 84 Top8 二叉树及其基本性质 真题分析 2009年4月 某二叉树有5个读为2的结点 则该二叉树中的叶子结点数是A 10B 8C 6D 4 C 85 Top8 二叉树及其基本性质 练习题1 在一棵二叉树第5层上的结点数最多是 个A 8B 16C 32D 15 B 86 Top8 二叉树及其基本性质 练习题2 在深度为5的满二叉树中 叶子结点的个数为 A 32B 31C 16D 15 C 87 Top8 二叉树及其基本性质 练习题3 设一棵完全二叉树共有699个结点 则在该二叉树中的叶子结点数为 A 349B 350C 255D 351 B A B C D E F G 88 Top9 二叉树的遍历 知识点遍历是对树的一种最基本的运算 所谓遍历二叉树 就是按一定的规则和顺序走遍二叉树的所有结点 所每个结点都被访问一次 且仅被访问一次 按访问根结点先后顺序 遍历分为先序遍历 中序遍历和后序遍历 89 Top9 二叉树的遍历 A B C D E F G 先序遍历 先访问根结点 然后访问左子树 最后访问右子树 H 后序遍历结果为 A B D H E C F G 90 Top9 二叉树的遍历 A B C D E F G 中序遍历 先访问左子树 然后访问根结点 最后访问右子树 H 后序遍历结果为 D H B E A F C G 91 Top9 二叉树的遍历 A B C D E F G H 后序遍历 先访问左子树 然后右子树 最后根结点 后序遍历结果为 H D E B F G C A 92 Top9 二叉树的遍历 真题分析 2007年4月 对下列二叉树 进行前序遍历的结果是 A DYBEAFCZXB YDEBFZXCAC ABDYECFXZD ABCDEFXYZ A B C D E F X Y Z C 93 Top9 二叉树的遍历 真题分析 2006年9月 对下列二叉树 进行中序遍历的结果是 A ACBDFEGB ACBDFGEC ABDCGEFD FCADBEG F C E A D B G A 94 Top9 二叉树的遍历 真题分析 2007年9月 对下列二叉树进行中序遍历的结果为 F C E A D B G H P A C B D F E H G P 95 Top9 二叉树的遍历 真题分析 2008年9月 对下列二叉树进行中序遍历的结果是 A D X B C E F Y Z DBXEAYFZC 96 Top9 二叉树的遍历 真题分析 2011年3月 一棵二叉树的中序遍历结果为DBEAFC 前序遍历结果为ABDECF 则后序遍历结果为 填空题第3题 A B C F D E D E B F C A 97 Top9 二叉树的遍历 练习题1 已经二叉树后序遍历序列是dabec 中序遍历序列是debac 它的前序遍历顺序是 A acbedB decabC deabcD cedba C d a b e D 98 Top9 二叉树的遍历 练习题2 在先左后右的原则下 根据访问根结点的次序 二叉树的遍历可以分为三种 前序遍历 和后序遍历 中序遍历 99 Top10 顺序查找 知识点顺序查找是一种最基本和最简单的查找方法 它的思路就是拿给定的值与表中的元素逐一比较 直到两者相同 表示查找成功 否则查找失败 对于大的线性表而言 顺序查找的效率很低 但是对于无序线性表 或者线性表虽然有序 但是采用链式存储时 都只能使用顺序查找 100 Top10 顺序查找 6 3 8 0 17 5 5 最坏情况 比较n次 6 6 3 8 0 17 5 最好情况 比较1次 101 Top10 顺序查找 真题分析 2006年9月 在长度为64的有序线性表中进行顺序查找 最坏情况下 需要比较的次数为 A 63B 64C 6D 7 B 102 Top10 顺序查找 真题分析 2005年4月 对于长度为n的线性表进行顺序查找 在最坏情况下 所需要比较的次数为 A log2nB n 2C nD n 1 C 103 Top10 顺序查找 练习题1 对长度为n的无序线性表进行查找 应该使用 查找 顺序 104 Top11 二分法查找 知识点二分查找是针对顺序存储的有序表进行查找的简单 有效而又较常用的方法 0 6 3 5 6 8 17 最坏情况 比较log2n次 0 5 3 5 6 8 17 最好情况 比较1次 105 Top11 二分法查找 真题分析 2005年9月 下列数据结构中 能用二分法查找的是 A 顺序存储的有序线性表B 线性链表C 二叉链表D 有序线性链表 A 106 Top11 二分法查找 真题分析 2008年9月 在长度为n的有序线性表中进行二分查找 最坏情况下需要比较的次数是 A O N B O n2 C O log2n D O nlog2n C 107 Top11 二分法查找 练习题1 有一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 当二分查找为82的结点时 次比较后查找成功 A 1B 2C 4D 8 C 108 Top12 排序 知识点排序是将一个无序序列整理成一个按值非递减顺序排列的序列 0 3 5 6 8 17 6 3 8 0 17 5 109 Top12 排序 知识点常用的排序方法有 交换类排序冒泡排序法 需要比较的次数为n n 1 2快速排序法 最坏情况需要比较n n 1 2次插入类排序简单插入排序法 最坏情况需要比较n n 1 2次希尔排序法 最坏情况需要比较O n1 5 次选择类排序简单选择排序法 最坏需要比较n n 1 2次堆排序法 最坏情况需要O nlog2n 次比较 110 Top12 排序 冒泡 6 3 8 0 17 5 原始序列 第一遍 3 6 0 8 5 17 第二遍 0 6 5 8 17 第三遍 3 3 0 6 5 第四遍 3 0 5 第五遍 3 0 111 Top12 排序 真题分析 2006年4月 对长度为10的线性表进行冒泡排序 最坏情况下需要比较的次数是 n n 1 2 45 112 Top12 排序 真题分析 2005年4月 对于长度为n的线性表 在最坏情况下 下列各排序法所对应的比较次数正确的是 A 冒泡排序n 2B 冒泡排序nC 快速排序nD 快速排序为n n 1 2 D 113 Top12 排序 真题分析 2007年9月 冒泡排序在最坏情况下的比较次数是 A n n 1 2B nlog2nC n n 1 2D n 2 C 114 Top12 排序 真题分析 2008年4月 对长度为n的线性表排序 在最坏情况下 比较次数不是n n 1 2的排序方法是 A 快速排序B 冒泡排序C 直接插入排序D 堆排序 D 115 Top12 排序 真题分析 2011年9月 在长度为n的顺序存储的线性表中插入一个元素 最坏情况下需要移动表中 个元素 填空题第2题 n 1 6 5 4 3 2 1 116 Top12 排序 练习题1 已经数据表A中每个元素距其最终位置不远 为节省时间 应采用的排序算法是 A 堆排序B 插入类排序C 快速排序D 直接选择排序 B 117 Top12 排序 练习题2 在待排序的元素序列基本有序的前提下 效率最高的排序方法是 A 冒泡排序B 选择排序C 快速排序D 归并排序 A 118 程序设计基础高频考点 Top1 程序设计方法与风格Top2 结构化程序设计Top3 面向对象方法 119 Top1 程序设计方法与风格 知识点养成良好的程序设计风格 清晰第一 效率第二 主要考虑下述要素 源程序文档化 符号命名要见名知义 要有正确的注释 程序层次清晰数据说明的方法 数据说明的次序规范 说明语句中变量安排有序化 使用注释说明复杂数据结构语句的结构 程序应简单易懂 语句构造应该简单直接 避免滥用goto语句 输入和输出 输入输出的格式应尽可能方便用户使用 120 Top1 程序设计方法与风格 真题分析 2006年9月 下列选项中不符合良好的程序设计风格的是 A 源程序要文档化B 数据说明的次序要规范化C 避免滥用goto语句D 模块设计要保证高耦合 低内聚 D 121 Top1 程序设计方法与风格 真题分析 2007年9月 下列叙述中 不符合良好程序设计风格的是 A 程序的效率第一 清晰第二B 程序的可读性好C 程序中有必要的注释D 输入数据前要有提示信息 A 122 Top1 程序设计方法与风格 练习题1 对建立良好的程序设计风格 下面描述正确的是 A 程序应简单 清晰 可读性好B 符号名的命名只要符合语法C 充分考虑程序的执行效率D 程序的注释可有可无 A 123 Top2 结构化程序设计 知识点结构化程序设计主要目的是使程序结构良好 易读 易理解 易维护 主要原则包括 自顶向下逐步求精模块化限制使用goto语句 124 Top2 结构化程序设计 知识点结构化程序设计方法可用三种基本结构实现 顺序结构选择结构 条件 循环结构 125 Top2 结构化程序设计 知识点在结构化程序实施中 要把握如下要素 使用程序语言中的顺序 选择 循环等控制结构表示程序的控制逻辑 选用的控制结构只准许有一个入口和一个出口 程序语句组成容易识别的程序专项 每块只有一个入口和一个出口 复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现 126 Top2 结构化程序设计 真题分析 2006年4月 下列选项中 不属于结构化程序设计方法的是 A 自顶向下B 逐步求精C 模块化D 可复用 D 可复用性是指在软件不加修改或稍加修改就可在不同软件开发过程中重复使用的性质 软件可复用性是软件工程追求的目标之一 面向对象方法具有可复用性 127 Top2 结构化程序设计 真题分析 2011年9月 常见的软件开发方法有结构化方法和面向对象方法 对某应用系统经过需求分析建立数据流图 DFD 则应采用 方法 填空题第3题 结构化方法 结构化 SA StructuredAnalysis SA方法从最上层组织机构入手 采用自顶向下逐层分解的方法分析系统 128 Top2 结构化程序设计 真题分析 2008年4月 结构化程序设计的基本原则不包括 A 多态性B 自顶向下C 模块化D 逐步求精 A 129 Top2 结构化程序设计 真题分析 2011年3月 结构化程序所要求的基本结构不包括 选择题第5题 A 顺序结构B GOTO跳转C 选择 分支 结构D 重复 循环 结构 B 130 Top2 结构化程序设计 练习题1 下列描述中 符合结构化程序设计风格的是 A 使用顺序 选择和循环三种基本控制结构表示程序的控制逻辑B 模块只有一个入口 可以有多个出口C 注重提高程序的执行效率D 不使用goto语句 A 131 Top3 面向对象方法 知识点对象 Object 对象是用来表示客观世界中的任何实体 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体 是构成系统的一个基本单位 它是由一组表示其静态特征的属性和它可执行的一组操作组成 类 Class 和实例 Instance 将属性 操作类似的对象归为类 类是具有共同属性 共同方法的对象的集合 一个具体对象称为类的实例 132 Top3 面向对象方法 知识点消息 Message 面向对象的世界是通过对象与对象间彼此的相互合作来推动的 对象间的这种相互合作需要一个机制协助进行 这个机制称为 消息 消息 是一个实例与另一个实例之间传递的信息 它请求对象执行某一处理或回答某一要求的信息 它统一了数据流和控制流 133 Top3 面向对象方法 知识点继承 Inheritance 继承是面向对象的方法的一个主要特征 继承是使用已有的类定义作为基础 直接获得已有的性质和特征 建立新类的定义技术 已有的类可以当做基类使用 则新类可当做派生类使用 优点是提高软件的可重用性 便于软件修改和维护 多态性 Polymorphism 对象根据所接受的消息而做出动作 同样的消息被不同的对象接受时可导致完全不同的行动 该现象称为多态性 封装性 外面只有看到对象的外部特征 对象的内部状态对外是不可见的 继承性 多态性和封装性是面向对象程序设计的3个主要特征 134 Top3 面向对象方法 真题分析 2007年4月 下面选项中不属于面向对象特征的是 A 继承性B 多态性C 类比性D 封闭性 D 135 Top3 面向对象方法 真题分析 2006年4月 在面向对象方法中 描述是具有相似属性与操作的一组对象 类 136 Top3 面向对象方法 真题分析 2005年4月 在面向对象方法中 类的实例称为 对象 137 Top3 面向对象方法 真题分析 2007年9月 在面向对象方法中 实现信息隐蔽是依靠 A 对象的继承B 对象的多态C 对象的封装D 对象的分类 C 138 Top3 面向对象方法 真题分析 2008年9月 在面向对象方法中 不属于 对象 基本特点的是 A 一致性B 分类性C 多态性D 标识唯一性 A 139 Top3 面向对象方法 真题分析 2011年9月 下列选项中属于面向对象设计方法主要特征的是 选择题第10题 A 继承B 自顶向下C 模块化D 逐步求精 A 140 Top3 面向对象方法 真题分析 2011年3月 定义无符号整数类为UInt 下面可以作为类UInt实例化值的是 选择题第10题 A 369B 369C 0 369D 整数集合 1 2 3 4 5 B 141 Top3 面向对象方法 练习题1 在面向对象方法中 类之间共享属性和操作的机制称为 继承 142 Top3 面向对象方法 练习题2 在面向对象的设计中 用来请求对象执行某一处理或回答某些信息的要求称为 消息 143 软件工程基础高频考点 Top1 软件工程基本概念Top2 软件生命周期Top3 软件设计基本概念Top4 软件设计的基本原理Top5 结构化分析方法Top6 软件测试的目的和测试的准则Top7 软件测试的方法和实施Top8 程序的调试 144 Top1 软件工程基本概念 知识点软件工程概念的出现源自软件危机 软件危机主要表现在成本 质量 生产率等方面 具体表现 软件需求的增长得不到满足 用户对系统不满意的情况时有发生 软件开发成本和进度无法控制软件质量难以保证软件的不可维护或维护程度非常低软件的成本不断提高软件开发生产率的提高赶不上硬件的发懂和应用需求的增长 145 Top1 软件工程基本概念 软件工程的主要思想 在软件开发过程中应用工程化原则 软件工程的主要研究对象 软件开发与维护的技术 方法 工具和管理等方面 软件的定义 程序 数据及相关文档的集合 软件工程三要素 方法 工具和过程 146 Top1 软件工程基本概念 方法 是完成软件工程项目的技术手段 工具 支持软件的开发 管理 文档生成 过程 支持软件开发的各个环节的控制 管理 软件工程三要素 方法 工具和过程 147 Top1 软件工程基本概念 真题分析 2005年9月 下列描述正确的是 A 软件工程只是解决软件项目的管理问题B 软件工程主要解决软件产品的生产率问题C 软件工程的主要思想是强调在软件开发中应用工程化原则D 软件工程只是解决软件开发中的技术问题 C 148 Top1 软件工程基本概念 真题分析 2011年9月 软件按功能可以分为应用软件 系统软件和支撑软件 或工具软件 下面属于应用软件的是 选择题第4题 A 学生成绩管理系统B C语言编译程序C UNIX操作系统D 数据库管理系统 A 系统软件包括操作系统 程序编译程序 数据库管理系统等三大大部份 149 Top1 软件工程基本概念 真题分析 2005年4月 下列描述正确的是 A 程序就是软件B 软件开发不受计算机系统的限制C 软件既是逻辑实体 又是物理实体D 软件是程序 数据和相关文档的集合 D 150 Top1 软件工程基本概念 真题分析 2007年9月 软件是指 A 程序B 程序和文档C 算法加数据结构D 程序 数据和相关文档的集合 D 151 Top1 软件工程基本概念 真题分析 2008年9月 软件工程三要素包括方法 工具和过程 其中 支持软件开发的各个环节的控制和管理 过程 152 Top1 软件工程基本概念 真题分析 2009年4月 软件按功能可以分为 应用软件 系统软件和支撑软件 或工具软件 下列属于应用软件的是A 编译程序B 操作系统C 教务管理系统D 汇编程序 C 153 Top1 软件工程基本概念 练习题1 下列不属于软件工程三要素的是 A 工具B 过程C 方法D 环境 D 154 Top1 软件工程基本概念 练习题2 软件工程的出现是由于 A 程序设计方法学的影响B 软件产业化的需要C 软件危机的出现D 计算机的发展 C 155 Top2 软件生命周期 知识点软件生命周期 产品从提出 实现 使用维护到停止使用退役的过程 软件生命周期的三个阶段 软件定义 软件开发及软件运行维护 软件生命周期的主要活动 可行性研究与计划制定需要分析软件设计软件实现软件测试运行和维护 156 Top2 软件生命周期 可行性研究初步项目计划 需求分析 概要设计 详细设计 实现 测试 使用 维护 退役 定义阶段 开发阶段 维护阶段 需求获取 需求分析 编写需要规格说明书 需求评审 正确性 可行性 必要性 无岐义性 完整性 可验证性 157 Top2 软件生命周期 真题分析 2011年3月 在软件开发中 需求分析阶段产生的主要文档是 A 软件集成测试计划B 软件详细设计说明书C 用户手册D 软件需求规格说明书 D 158 Top2 软件生命周期 真题分析 2007年4月 软件生命周期可分为多个阶段 一般分为定义阶段 开发阶段和维护阶段 编码和测试属于 阶段 开发 159 Top2 软件生命周期 真题分析 2006年9月 下列选项中不属于软件生命周期开发阶段任务的是 A 软件测试B 概要设计C 软件维护D 详细设计 C 160 Top2 软件生命周期 真题分析 2005年9月 下列叙述中正确的是 A 软件交付使用后还需要进行维护B 软件一旦交付使用后就不需要再进行维护C 软件交付使用后其生命周期就结束D 软件维护是指修复程序中被破坏的指令 A 161 Top2 软件生命周期 真题分析 2007年9月 软件需求规格说明书应具有完整性 无歧义性 正确性 可验证性 可修改性等特性 其中最重要的 无歧义性 162 Top2 软件生命周期 真题分析 2008年4月 在软件开发中 需求分析阶段产生的主要文档是 A 可行性分析报告B 软件需求规格说明书C 概要设计说明书D 集成测试计划 B 163 Top2 软件生命周期 练习题1 软件生命周期中所花费用最多的阶段是 A 详细设计B 软件编码C 软件测试D 软件维护 D 164 Top2 软件生命周期 练习题2 软件开发的结构化生命周期方法将软件生命周期划分为 A 定义 开发 运行维护B 设计阶段 编程阶段 测试阶段C 总体设计 详细设计 编程调试D 需求分析 功能定义 系统设计 A 165 Top3 软件设计基本概念 知识点从工程管理角度来看 软件设计包括 概要设计和详细设计 从技术角度来看 软件设计包括 结构设计 定义软件系统各主要部件之间的关系 数据设计 将分析时创建的模型转换为数据结构的定义接口设计 描述软件内部 软件和协作系统之间以及软件与人之间如何通信过程设计 把系统结构部件转换成软件的描述过程 166 Top3 软件设计基本概念 真题分析 2006年9月 从工程管理角度看 软件设计一般分为两步完成 它们是 A 概要设计与详细设计B 数据设计与接口设计C 软件结构设计与数据设计D 过程设计与数据设计 A 167 Top3 软件设计基本概念 练习题1 软件设计包括软件的结构 数据接口和过程设计 其中软件的过程设计是指 A 模块间的关系B 系统结构部件转换成软件的过程描述C 软件层次结构D 软件开发过程 B 168 Top4 软件设计的基本原理 知识点软件设计中应遵循的基本原理与软件设计有关的概念抽象 把事物的本质的共同特性提取出来而不考虑其他细节 模块化 把一个待开发的软件分解成若干个小的简单的部分 信息隐蔽 一个模块内部包含的信息 对于不需要这些信息的其它模块来说是不能访问的 模块独立性 每个模块只完成系统要求的独立的子功能 并且与其它模块的联系最少且接口简单 169 Top4 软件设计的基本原理 知识点衡量模块独立性的两个标准内聚性 一个模块内部各元素之间的彼此结合的紧密程序 耦合性 模块间相互连接的紧密程序 软件设计应尽量做到 高内聚 低耦合 170