公共基础各章重要内容

《公共基础各章重要内容》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、各位同学，以下列出了各章的重点知识，请务必背完，由于第一章的考点比较固定，所以第一章只要记下我下面列出来的内容即可，就不用看书了，但是其他章节请记下相应内容建议再适当看看课本。公共基础复习方法：背我给你们总结的重点+一定要把课后的习题1、2、3、4做完并记完+公共基础历年试卷第1章　数据结构与算法1.1算法算法是指解题方案准确而完整的描述（问题处理方案准确而完整的描述）算法不等于程序，程序也不等于算法算法复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量(算法在执行过程中所需要的基本运算次数)算法的空间复杂度是指算法在执行过

2、程中所需要的计算机存储空间时间复杂度和空间复杂度都是越小越好算法的时间复杂度和空间复杂度没有任何联系。算法的基本特征1.2数据结构1、逻辑结构与存储结构逻辑结构：各数据元素之间所固有的逻辑关系存储结构：数据的逻辑结构在计算机中的表示一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率程序执行的效率与数据的存储结构密切相关逻辑结构和存储结构没有必然联系　2、线性结构与非线性结构只有一个结点的树就是线性的错树是非线性，只要有树这个字的就是非线性的只要有栈和队列的都是线性结构1.3线性表及其顺序存储结构1、线性表的顺序存储顺序存储：只能用于表示线性

3、结构其在内存中存储空间必须连续，且前件元素一定存储在前面。1.4栈和队列每次必考，有时会考两个题栈：栈是线性表，一端（栈底bottom）封闭另一端（栈顶top）开口（在栈中只能插入元素而不能删除元素，在栈中只能删除元素而不能插入元素错误）插入和删除操作都只能在一端（栈顶），并且插入和删除元素只需要改变栈顶指针（top），不需要改变栈底指针（bottom）。在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化。特点：先进后出、后进先出栈具有记忆功能栈中的元素个数计算

4、top-bottom

5、+1队列：先进先出、后进后出数据结构分为线性结构和非线性结构，带链的

6、队列属于线性结构。队列是线性表，一端插入（队尾rear）另一端删除（对头front）线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的顺序存储结构。（循环队列通常采用数组的方式进行数据的存储，因此所有元素所占的存储空间是连续的，各数据元素在存储空间中是按逻辑顺序依次存放的。所以循环队列是队列的顺序存储结构。）循环队列的元素个数：当rear>front时，元素个数为rear－front当rear

7、角度来讲的。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的循环空间。对头指针和队尾指针根据情况变化，循环队列的对头指针可以大于队尾指针也可以小于队尾指针。计算机里面的打印属于栈还是队列，队列1.5线性链表1、线性链表的概念　2、线性链表的基本运算线性表的顺序存储结构称为顺序表线性表的链式存储结构称为线性链表线性表的顺序存储结构①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的（前件元素一定存储在后件元素的前面）。线性表的链式存储结构在链式存储结构中，存储数据结构的存储空间可以不连续，各

8、数据结点的存储顺序与数据元素之间的逻辑关系可以不一致（其前件元素也不一定存储在后件元素的前面）。链式存储方式既可用于表示线性结构也可用于表示非线性结构，而顺序存储方式只能用于表示线性结构。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构eg：一维数组认为是线性的可用顺序存储也可以用链式。1.6树与二叉树（必考）1、第k层最多有2k-1个结点2、深度为k的二叉树，最多有2k-13、度为0（叶子结点）的结点总是比度为2的结点多一个4、二叉树总的结点数=度为0的结点数+度为1的结点数+度为2的结点数二叉树的遍历1.7、查找技术1、顺序查找:最坏n，平均n

9、/2　2、二分法查找1、顺序查找：最坏情况需要比较n次2、二分法查找最坏情况需要比较log2n次只有是有序线性表才能用二分法无序表和采用链式存储结构的线性表都只能用顺序查找顺序查找适应于所有的情况二分法查找只适用于顺序存储的有序表1.8排序技术一、交换类排序：1、冒泡最坏：n(n-1)/22、快速排序最坏：n(n-1)/2二、插入类排序：1、简单插入：最坏：n(n-1)/22、希尔排序：最坏：n1.5三、选择类排序：1、简单选择：最坏：n(n-1)/22、堆排序：最坏：nlog2n第2章　程序设计基础2.1程序设计方法与风格清晰第一、效率第二源程序文档化：标

10、识符要有一定含义（符号名只要符合语法就行错），应具有