计算机二级公共基础知识考点总结.doc

PAGE PAGE 11 二级公共基础知识考点总结 数据结构与算法 考点1：算法的概念和基本特征 算法是指解题方案的准确而完整的描述。 算法的基本特征包括： （1）可行性：针对实际问题设计的算法，总是在某个特定计算工具上执行，往往要受到计算工具的限制，使执行结果产生偏差。（2）确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。（3）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。（4）拥有足够的情报：拥有足够的输入。 考点2：算法复杂度 算法的复杂度主要包括时间复杂度和空间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量(即算法执行过程中所需基本运算的执行次数)。 算法的空间复杂度是指执行这个算法所需要的内存空间。 特别注意：时间复杂度与空间复杂度没有必然的正比或反比的关系。 考点3：数据的逻辑结构与存储结构 数据的逻辑结构是反映数据元素之间逻辑关系的数据结构，与它们在计算机中的存储位置无关。 数据的存储结构（也称物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等（包括线性结构和非线性结构）。而采用不同的存储结构，其数据处理的效率是不同的。 考点4：线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特点： 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间 考点5：栈与队列(属于线性结构) 1、栈 栈是限定在一端进行插入与删除的线性表。 在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。通常用指针top指示栈顶的位置，用指针bottom指向栈底。 top-bottom的绝对值加1即为当前栈中元素的个数。 栈是按照“先进后出”或“后进先出”的原则组织数据的，用栈顶指针top动态反映了栈中元素的变化情况，而不须改变指针bottom的位置。 栈具有记忆作用。 2、队列 队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针rear指向队尾元素，允许删除的一端称为排头（也称队头），通常用一个排头指针front指向排头元素的前一个位置。 队列按照“先进先出”或“后进后出”的原则组织数据，队尾指针rear和排头指针front共同反映了队列中元素动态变化情况。 在实际应用中，队列的顺序存储结构一般采用循环队列的形式，循环队列是逻辑上的环状空间，但物理上仍然是线性结构。从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。 在普通队列中，rear指针位置减去front指针位置的差值即为队列中元素的个数。但在循环队列中，rear指针的位置可能大于front指针的位置，也可能小于front指针的位置，所以循环队列的元素个数计算方法如下： 设循环队列总容量为m 如果rearfront，则循环队列的元素个数为rear-front 如果rearfront，则循环队列的元素个数为m+(rear-front) 栈与队列的共同点：皆为线性结构，只允许在端点处插入与删除，而且不须移动其他元素。 考点6：线性链表 线性表的链式存储结构称为线性链表 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。 链式存储结构即可用于表示线性结构，也可用于表示非线性结构，栈与队列也可以采用链式存储结构。 考点7：二叉树的基本性质 树是典型的非线性结构，在树中，每个结点的前件称为父结点，没有父结点的只有一个，称为根结点（有且仅有一个）。 每个结点拥有的后件称为子结点，没有子结点的称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度，叶子结点的度为0。 树的最大层次称为树的深度。 二叉树：每个结点最大的度为2，如下图所示 性质1：在二叉树的第k层上，最多有2k-1个结点 性质2：深度为m的二叉树最多有2m-1 性质3：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。 满二叉树：每一层上的结点数都达到最大值，即第k层上有2k-1个结点，且深度为m的满二叉树有2m-1 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。当完全二叉树有n个结点，若n为偶数，则有n/2个叶子结点；若n为奇数，则有[n/2]+1个叶子结点（[ ]表示只取整数部分）。 ★考点8：二叉树的遍历 （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LD