全国计算机等级考试二级公共基础知识高频考点教案.pptx

二级公共基础考前辅导主讲教师：胡晓丽桂林电子科技大学Email: huxiaoli@guet.edu.cn相关知识在二级考试中，占总分的30%数据结构与算法程序设计基础软件工程基础数据库设计基础各部分所占比例图数据结构与算法高频考点Top1：算法的基本概念Top2：算法的复杂度Top3：逻辑结构与存储结构Top4：线性结构与非线性结构Top5：栈Top6：队列Top7：链表Top8：二叉树及其基本性质数据结构与算法高频考点Top9：二叉树的遍历Top10：顺序查找Top11：二分法查找Top12：排序Top1：算法的基本概念知识点 算法是解决问题准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 严格来说，一个算法必须满足下面5个主要特性。Top1：算法的基本概念有穷性：一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。确定性：算法中每条指令必须有确定的含义，且在任何条件下，算法只有唯一的一条执行路径。可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。有输入：一个算法可以有0个或多个输入。有输出：一个算法必须有1个或多个输出。Top1：算法的基本概念算法是描述解决问题的方法与步骤，它与数据结构、运算结果的状态无关。D软件的主体是程序，程序的核心是算法。程序是采用某种程序设计语言对问题的对象和解题的步骤进行描述。真题分析（2011年9月）下列说法中正确的是——A、算法就是程序B、设计算法时只需考虑数据结构的设计C、设计算法时只需考虑结果的可靠性D、以上三种说法都不对Top1：算法的基本概念真题分析（2008年4月）算法的有穷性是指——A、算法程序的运行时间是有限的 B、算法程序所处理的数据量是有限的 C、算法程序的长度是有限的 D、算法只能被有限的用户使用 A一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。Top1：算法的基本概念真题分析（2005年4月）算法具有5 个特性，下列选项中不属于算法特性的是——A、有穷性B、简洁性C、可行性D、确定性B有穷性确定性可行性有输入（可以是0个）有输出（至少是1个）Top1：算法的基本概念练习题1、算法的五个重要特性是有穷性、——、确定性、有输入和有输出。 可行性Top2：算法的复杂度知识点衡量算法优劣的两个标准 一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的是在于选择合适的算法和改进算法。评价一个算法的好坏有两个标准：时间复杂度和空间复杂度。Top2：算法的复杂度算法的时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需要的基本运算的执行次数来度量；算法的空间复杂度是指执行这个算法所需要的内存空间的大小。Top2：算法的复杂度真题分析（2007年4月）下列叙述中正确的是——A、算法的效率只与问题的规模有关，而与数据的存储结构无关。B、算法的时间复杂度是指执行算法所需要的计算工作量。C、数据的逻辑结构与存储结构是一一对应的。D、算法的空间复杂度与时间复杂度一定相关。B算法的效率不仅与问题的规模与关，还与数据结构有关（数据的逻辑结构、存储结构）一种逻辑结构可以对应多种存储结构。时间复杂度与空间复杂度不相关Top2：算法的复杂度真题分析（2006年9月）下列叙述中正确的是——A、一个算法的空间复杂度大，则其时间复杂度必定大。B、一个算法的空间复杂度大，则其时间复杂度必定小。C、一个算法的时间复杂度大，则其空间复杂度必定小。D、上述三种说法都不对。D时间复杂度与空间复杂度不相关Top2：算法的复杂度真题分析（2005年9月）算法的复杂度主要包括时间复杂度和————复杂度。空间Top2：算法的复杂度练习题1、算法的时间复杂度是指——A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数CTop2：算法的复杂度练习题2、算法的空间复杂度是指——A、算法程序的长度B、算法程序中的指令条数C、算法程序所占用的存储空间D、算法执行过程中所占用的存储空间D在算法执行时所需要的内存空间，其中包括：算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法执行过程中的工作单元以及某种数据结构所需要的附加存储空间。Top3：逻辑结构与存储结构知识点逻辑结构是反映元素之间逻辑关系的，即前后件关系，分为线性结构（常见的有线性表、栈和列队）和非线性结构（常见的有树和图）存储结构（物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各种数据元素的信息，还要存放元素之间的前后件关系的信息。Top3：逻辑结构