二级公共基础知识考点总结

《二级公共基础知识考点总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二级公共基础知识考点总结第一章数据结构与算法考点1：算法的概念和基本特征算法是指解题方案的准确而完整的描述。算法的基本特征包括：（1）可行性：针对实际问题设计的算法，总是在某个特定计算工具上执行，往往要受到计算工具的限制，使执行结果产生偏差。（2）确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。（3）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。（4）拥有足够的情报：拥有足够的输入。考点2：算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度算法的时间复杂度是指执行算法所

2、需要的计算工作量(即算法执行过程中所需基本运算的执行次数)。算法的空间复杂度是指执行这个算法所需要的内存空间。特别注意：时间复杂度与空间复杂度没有必然的正比或反比的关系。考点3：数据的逻辑结构与存储结构数据的逻辑结构是反映数据元素之间逻辑关系的数据结构，与它们在计算机中的存储位置无关。数据的存储结构（也称物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等（包括线性结构和非线性结构）。而采用不同的存储结构，其数据处理的效率是不同的。考点4：线性表的顺序存储结构

3、线性表的顺序存储结构具有以下两个基本特点：1)线性表中所有元素所占的存储空间是连续的2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间11考点5：栈与队列(属于线性结构)1、栈栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。通常用指针top指示栈顶的位置，用指针bottom指向栈底。top-bottom的绝对值加1即为当前栈中元素的个数。栈是按照“先进后出”或“后进先出”的原则组织数据的，用栈顶指针top动态反映了栈中

4、元素的变化情况，而不须改变指针bottom的位置。栈具有记忆作用。2、队列队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针rear指向队尾元素，允许删除的一端称为排头（也称队头），通常用一个排头指针front指向排头元素的前一个位置。队列按照“先进先出”或“后进后出”的原则组织数据，队尾指针rear和排头指针front共同反映了队列中元素动态变化情况。在实际应用中，队列的顺序存储结构一般采用循环队列的形式，循环队列是逻辑上的环状空间，但物理上仍然是线性结构。从排头指针front指向的后一个位置直到队尾

5、指针rear指向的位置之间所有的元素均为队列中的元素。在普通队列中，rear指针位置减去front指针位置的差值即为队列中元素的个数。但在循环队列中，rear指针的位置可能大于front指针的位置，也可能小于front指针的位置，所以循环队列的元素个数计算方法如下：设循环队列总容量为m如果rear>front，则循环队列的元素个数为rear-front如果rear

6、线性链表在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。链式存储结构即可用于表示线性结构，也可用于表示非线性结构，栈与队列也可以采用链式存储结构。★考点7：二叉树的基本性质树是典型的非线性结构，在树中，每个结点的前件称为父结点，没有父结点的只有一个，称为根结点（有且仅有一个）。每个结点拥有的后件称为子结点，没有子结点的称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度，叶子结点的度为0。树的最大层次称为树的深度。二叉树：每个结点最大的度为2，如下图所示性质1：在二叉树的第k层上，最多

7、有2k-1个结点性质2：深度为m的二叉树最多有2m-1个结点性质3：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。满二叉树：每一层上的结点数都达到最大值，即第k层上有2k-111个结点，且深度为m的满二叉树有2m-1个结点完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。当完全二叉树有n个结点，若n为偶数，则有n/2个叶子结点；若n为奇数，则有[n/2]+1个叶子结点（[]表示只取整数部分）。★考点8：二叉树的遍历（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树

8、；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访