搜索
二级公共基础考前辅导Email:huxiaoli@guet.edu.cn主讲教师：胡晓丽桂林电子科技大学相关知识在二级考试中，占总分的30%数据结构与算法程序设计基础软件工程基础数据库设计基础各部分所占比例图比例图数据结构与算法30%程序设计基础10%软件工程基础30%数据库设计基础30%数据结构与算法高频考点Top1：算法的基本概念Top2：算法的复杂度Top3：逻辑结构与存储结构Top4：线性结构与非线性结构Top5：栈Top6：队列Top7：链表Top8：二叉树及其基本性质数据结构与算法高频考点Top9：二叉树的遍历Top10：顺序查找Top11：二分法查找Top12：排序Top1：算法的基本概念知识点算法是解决问题准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。严格来说，一个算法必须满足下面5个主要特性。Top1：算法的基本概念1.有穷性：一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。2.确定性：算法中每条指令必须有确定的含义，且在任何条件下，算法只有唯一的一条执行路径。3.可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4.有输入：一个算法可以有0个或多个输入。5.有输出：一个算法必须有1个或多个输出。Top1：算法的基本概念真题分析（2011年9月）下列说法中正确的是——A、算法就是程序B、设计算法时只需考虑数据结构的设计C、设计算法时只需考虑结果的可靠性D、以上三种说法都不对D算法是描述解决问题的方法与步骤，它与数据结构、运算结果的状态无关。程序是采用某种程序设计语言对问题的对象和解题的步骤进行描述。软件的主体是程序，程序的核心是算法。Top1：算法的基本概念真题分析（2008年4月）算法的有穷性是指——A、算法程序的运行时间是有限的B、算法程序所处理的数据量是有限的C、算法程序的长度是有限的D、算法只能被有限的用户使用A一个算法必须在执行有穷步之后结束（对任何合法的输入值），而且每一步都必须在有穷时间内完成。Top1：算法的基本概念真题分析（2005年4月）算法具有5个特性，下列选项中不属于算法特性的是——A、有穷性B、简洁性C、可行性D、确定性B有穷性确定性可行性有输入（可以是0个）有输出（至少是1个）Top1：算法的基本概念练习题1、算法的五个重要特性是有穷性、——、确定性、有输入和有输出。可行性Top2：算法的复杂度知识点衡量算法优劣的两个标准一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的是在于选择合适的算法和改进算法。评价一个算法的好坏有两个标准：时间复杂度和空间复杂度。Top2：算法的复杂度1.算法的时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需要的基本运算的执行次数来度量；2.算法的空间复杂度是指执行这个算法所需要的内存空间的大小。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：逻辑结构与存储结构知识点1.逻辑结构是反映元素之间逻辑关系的，即前后件关系，分为线性结构（常见的有线性表、栈和列队）和非线性结构（常见的有树和图）2.存储结构（物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各种数据元素的信息，还要存放元素之间的前后件关系的信息。Top3：逻辑结构与存储结构知识点3.数据的逻辑结构与数据的存储结构并不是一一对应的。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有顺序、链接、索引、散列等。采用不同的存储结构，其数据的处理效率是不同的。Top3：逻辑结构与存储结构真题分析（2005年9月）下列叙述中正确的是——A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构。C、一个逻辑数据结构可以有多种存储结构，且种存储结构不影响数据处理的效率。D、一个逻辑数据结构可以有多种存储结构，且种存储结构影响数据处理的效率。D一种逻辑结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。逻辑结构分为线性结构与非线性结构。Top3：逻辑结构与存储结构真题分析（2005年9月）数据结构可以分为逻辑结构和存储结构，循环队列属于——结构。存储循环队列是指将队列存储空间的最后一个位置绕到第一个位置，形成一个环状空间，供队列循环使用。所以循环队列是属于存储结构。Top3：逻辑结构与存储结构真题分析（2005年4月）数据的存储结构是指——A、存储在外存中的数据B、数据所占的存储空间C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示DTop3：逻辑结构与存储结构真题分析（2007年9月）下列叙述中正确的是——A、程序执行的效率与数据的存储结构密切相关B、顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C、程序执行的效率只取决于所处理的数据量D、以上三种说法都不对ATop3：逻辑结构与存储结构练习题1、数据结构中，与所使用的计算机无关的是数据的——A、存储结构B、物理结构C、逻辑结构D、逻辑结构和物理结构CTop3：逻辑结构与存储结构练习题2、在数据结构中，从逻辑上可以把数据结构分成——A、动态结构和静态结构B、线性结构和非线性结构C、集合结构和非集合结构D、树形结构和图状结构BTop4：线性结构与非线性结构知识点1.根据数据结构中各数据元素之间前后件的复杂程序，一般将数据结构分为两大类型：线性结构和非线性结构。2.如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点②每个结点最多有一个前件，也最多只有一个后件。则称该数据结构为线性结构。线性表是典型的线性结构，如栈、队列、串。3.如果一个数据结构不是线性结构，则称为非线性结构。如多维数组、广义表、树和图等。Top4：线性结构与非线性结构真题分析（2006年9月）数据结构分为线性结构和非线性结构，带链的队列属于——队列是特殊的线性表，可以采用顺序存储，也可以采用链式存储。所以带链的队列属于线性结构。线性结构Top4：线性结构与非线性结构真题分析（2011年9月）数据结构分为线性结构和非线性结构，带链的栈属于——。（填空题第一题）线性结构Top4：线性结构与非线性结构真题分析（2006年4月）下列叙述中正确的是——A、线性链表是线性表的链式存储结构B、栈与队列是非线性结构C、双向链表是非线性结构D、只有根结构的二叉树是线性结构A线性链表就是指线性表的链式存储结构，简称链表。线性表链式存储结构的基本单位称为存储结点，每个结点包括数据域和指针域两个部分。栈、队列和双向链表都是线性结构二叉树是非线性结构。线性结构和非线性结构是从数据的逻辑结构角度来讲的，与该数据结构中有多少个元素没有关系，即使是空的二叉树也是非线性结构。Top4：线性结构与非线性结构真题分析（2007年9月）下列叙述中正确的是——A、数据的逻辑结构与存储结构必定是一一对应的B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C、程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构D、以上三种说法都不对B一种逻辑结构可以对应多种存储结构存储结构一定是线性的。一般是在内存中开辟一块连续的存储单元用来存放数据元素。数组可以用来处理线性结构，也可以用来存储非线性结构。Top4：线性结构与非线性结构真题分析（2008年9月）下列叙述中正确的是——A、顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B、顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C、顺序存储结构能存储有序表，链式存储结构不能存储有序表D、链式存储结构比顺序存储结构节省存储空间A链式存储结构的存储空间可以是连续的，也可以是不连续的。链式存储主要是通过指针域来找到下一个结点所在的存储单元。10001002100410061008100A100C123451002100410061008\0123453251410081000\01002100410001002100410061008100A100C100010021004100612345链式存储顺序存储Top4：线性结构与非线性结构真题分析（2011年3月）下列叙述中正确的是——A、有一个以上根结点的数据结构不一定是非线性结构B)只有一个根结点的数据结构不一定是线性结构C)循环链表是非线性结构D)双向链表是非线性结构B线性结构的定义是：（1）只有一个根结点（2）除了根结点外，每个结点只有一个前件，也只有一个后件。只有一个根结点的数据结构也可能是非线性结构，如树，也只有一个根结点。Top4：线性结构与非线性结构练习题1、下列叙述中正确的是——A、线性表是线性结构B、栈与队列是非线性结构C、线性链表是非线性结构D、二叉树是线性结构ATop4：线性结构与非线性结构练习题2、以下数据结构中不属于线性数据结构的是——A、队列B、线性表C、二叉树D、栈CTop5：栈知识点1.栈（堆栈STACK）是一种运算受限制的线性表。限制其只能在表的一端进行插入和删除操作，此端称为栈顶，栈顶的第一个元素称为栈顶元素，相对地，把另一端称为栈底。2.向一个栈插入新元素称为入栈，从栈中删除一个元素称为出栈出退栈。3.由于栈的插入和删除只能在一端进行，后进栈的元素必定先出栈，所以栈又称为后进先出表LIFO；先进栈的元素必定后出栈，所以栈又称为先进后出FILO表。Top5：栈栈底dcba栈顶入栈出栈结论：后进先出，先进后出栈顶栈顶栈顶Top5：栈真题分析（2006年9月）按“后进先出”原则组织数据的数据结构是——栈Top5：栈真题分析（2006年4月）按照“后进先出”原则组织数据的数据结构是——A、队列B、栈C、双向链表D、二叉树BTop5：栈真题分析（2005年9月）下列关于栈的描述中正确的是——A、在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除D、栈是特殊的线性表，只能在一端插入，在另一端删除。CTop5：栈真题分析（2005年4月）下列关于栈的描述错误的是——A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入和删除操作中，不需要改变栈底指针BTop5：栈真题分析（2008年4月）下列关于栈的叙述正确的是——A、栈按“先进先出”组织数据