二级公共基础重点

《二级公共基础重点》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二级公共基础考点总结第一章笫一章数据结构与算法（八大考点）考点一:算法1•葆法是指解题方案的准确而完整的描述。它有4个基木特征，分别是可行•性、确定性、玄穷性和拥冇足够的情报。2.算法的复杂度主要包括时间复杂度和空间复杂度算法的时间复杂度是指执行算法所需要的计算所需要的计算工作量（或算法执行过程中所需要的基木运算次数）算法的空间复杂度是指执行这个算法所需要的内存空间.考点二:数据结构的基本概念1•数据结构是研究数据元素及其Z间的相互关系和数据运算的一门学科.数据结构概念一般包括3个方血的内容：数据

2、之间的逻辑关系（逻辑结构）、数据在计算机中的存储方式（存储结构）以及在这些数据上定义的运算的集介（数据的运算）.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计算机存储空间小的存放形式。在数据的存储结构屮，不仅耍存放各数据元素的信息，还需要存放各数据沅素之间的前后件关系的信息。2.在链式存储结构中，存储数据结构的存储空间可以是连续的，也町以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。3.—般来说，一种数据结构根据需耍可以表示成多种存

3、储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。4.线性结构是指各数据元素Z间的逻辑关系对以用一个线性序列简单地表示出来。否则称Z为非线性结构。考点三:线性表及其顺序存储结构1・当线性农采用顺序存储结构实现存储时，其主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元屮。在存储单兀中各兀素的物理位置和逻辑结构屮各结点间的相邻关系是一•致的。考点四:栈和队列1

4、.1.栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种〃示进先出〃的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种〃先进先出〃的线性表。栈和队列的共同特点是只允许在端点处插入和删除元素2.2.常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够人的存储空间。但实际屮，很难准确地估计，若每个栈都分配过人的存储空间，势必造成系统空间紧张：若让多个栈共用一个足够大的连续存储空间

5、，则可利用栈的动态特性使他们的存储空间互补。所以，由两个栈共享一个存储空间的好处是节省存储空间，降低上溢发生的机率（设有两个串P和q,求q在P中首次出现位置的运算称作模式匹配）（n个顶点的连通图小边的条数至少为n-1）考点五:线性链表1.链表采用的是链式存储结构（链式存储屮每个结点由两部分组成:数据域和指针域）,它克服了顺序存储结构的缺点：它的纟？i点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针來指示,不需要移动数据元索。但是链式存储结构也有不足Z处：①每个结点中的指针域需额外占•用

6、存储空间；②链式存储结构是一种非随机存储结构。用链农农示线性表的突出优点是便丁•插入和删除操作.考点六:树与二叉树1•树是一个或多个结点组成的冇限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时乂是一棵树。树有且只有1个根结点。1.二叉树的遍历是指不重复地访问二叉树中的所冇结点二义树的遍历可以分为三种：a.a.前序遍历(DLR)是指先访问根结点，然后遍历左了树，最后遍历右了树.(先根后左再右)b.b.中序遍历(LDR)是指先遍历左子树，然后访问根结点，最后遍历右子树.(

7、先左后根再右)c.c.后序遍历(LRD)是指先遍历左子树，然后遍历右子树，最后访问根结点.(先左后右再根)如：已知二义树后序遍历序列是dabcc,中序遍历序列是debac,它的前序遍历序列是cedba解题思路：山后序或前序遍历可判断根结点，再山中序遍历可判断左右子树.考点七:查找技术一.顺序查找顺序查找的方法是：用待查关键码值•线性表中各结点的关键码值逐个比较，直到找出相等的关键码值，则查找成功；或者找遍所有结点都不相等，则查找失败。顺序査找的优点：对线性表的结点的逻辑次序无要求(不必按关键码值排

8、序)，对线性表的存储结构无要求(顺序存储、链接存储皆可。)二二分法查找二分法杳衣是一种效率较高的线性表查找方法。要进行二分法杳找，则线性表结点必须进按关键码值排好序的，n线性表以顺序方式存储。二分法杏找的方法：首先用要杳找的关键码值与线性表屮间位置结点的关键码值和比较，这个中间结点把线性表分成了两个子表，比较相等则査找完成，不等则根据比较结果确定下一步的杳找应在哪一个子表中进行，如此进行下去，肓•到找到满足条件的结点，或者确定表屮没有这样的结点。对于二分法杏找的缺点是线性表排序需花