[精品]公共基础背诵点

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

1、公共基础背诵知识点第一章数据结构第一节算法1.算法是指解题方案的准确而完整的描述2.算法的特征：可行性、确定性、有穷性、拥有足够的情报算法的确定性，是指算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。算法的有穷性，是指算法必须能在有限的时间内做完，即能在执行有限个步骤后终止3.算法控制结构主耍有顺序、选择和循环三种控制结构4.算法的复杂度主要包括时间复杂度和空间复杂度5.算法时间复杂度并不是指执行算法程序所需要的时间，而是指执行算法所需要的计算工作量，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量，6.算法的空

2、间复杂度是指执行这个算法所需要的内存空间7.时间复杂度和空间复杂度没有直接联系第二节数据结构白勺基本概念1.数据结构分为逻辑结构和物理结7勾，物理结构贏称为存储结构2.逻辑结构是指反映数据元素Z间逻辑关系的数据结构，数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。3.在数据的存储结构屮，不仅耍存放齐数据元素的信息，述需要存放各数据元索之间的前后件关系的信息4.一种数据的逻辑结构根据需要可以表示成多种存储结构5.在实际进行数据处理时，各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能相同也可能不同。6•存储

3、结构影响数据处理的效率，釆用不同的存储结构，艾数据处理的效率是不同的，影响数据处理效率因索不是只有存储结构7.数据的逻辑结构分为线性结构和非线性结构，线性结构有线性表、栈和队列；非线性结构有树、二叉树、完全二叉树和满二叉树。第三节线性表1•线性表小的每一个数据兀素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件2.线性表的顺存储称为顺序表，链式存储称为线性链表，链式存储主要有线性链农、双向链农和循环链表，链式存储需要存放指针，因此顺序存储比链式存储节省存储空间。第四节栈和队列1.栈实际上也是线性表，在栈小其插入与删除运算都只在线性表

4、的•端进行。2.栈是限定在一端进行插入与删除的线性表。允许插入与删除的•端称为栈顶，不允许插入与删除的另一端称为栈底。3.栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后被删除的元素。4•栈按照“先进后出”（FILO）或“后进先出”（LIFO）原则组织数据，栈具冇记忆作用。5.栈可以顺序存储也可以链式存储6.栈的插入（入栈）和删除（退栈）运算不需要改变栈底指针，只需要改变栈顶指针。7.栈是线性结构，带链的栈是线性结构8.队列是指允许在一端进行插入，而在另一端进行删除的线性表。9.队列中允许插入的一端

5、称为队尾，通常用一个称为尾指针(rear)的指针指向队尾，即尾指针总是指向最后被插入的元素；允许删除的…端称为排头，通常用一个排头指针(front)指向排头元索的前一个位置。10.在队列中，最先插入的元素将最先被删除，最后插入的元素将最后才能被删除。队列是“先进行出”(FIFO)或“后进后出”(LTLO)的线性表。11•队列是线性结构，带链的队列是线性结构12.队列可以顺存储也可以链式存储。13循环队列是存储结构，循环队列是顺序存储14循环队列是线性结构；15.循环队列中队头指针与队尾指针都会变化；16.循环队列中队头指针可以大于队尾指针，也可以小于

6、队尾指针。第六节树与二叉树1•树是非线性结构、二义树是非线性结构、只有根接点的的二叉树是非线性结构2在二叉树的第k层上，最多有2k-l(kMl)个结点；3深度为m的二叉树最多有2m-1个结点；4度为0的结点(即叶子结点)总是比度为2的结点多一个第7节查找技术1.二分法查找只适用于顺序存储的有序表2.对于长度为n的有序线性表，顺序查找在最坏情况下需耍比较n次，二分法查找最坏情况只需比较log2n次。第8节排序技术排序分类排序方法最坏情况下比较次数交换类排序法冒泡排序法n(n-l)/2快速排序法插入类排序法简单插入排序法希尔排序法0(n15)选择类排序法

7、简单选择排序法n(n~l)/2堆排序法0(nlog2n)第二章程序设计基础第一节程序设计方法和风格1•清晰第一，效率第二”的论点已成为当今主导的程序设计风格。2.要形成良好的程序设计风格，主要应注重和考虑下述一些因素(1)符号名的命名应具有一定含义，以便于对程序功能的理解。(2)程序注释可帮助读者理解程序°程序注释分为序言性注释和功能性注释。(3)视觉的组织：可以利用空格、空行、缩进等技术使程序能够一目了然。(4)在编写程序时，程序中的数据说明更易于理解和维护；(1)程序应该简单易懂，语句构造应该简单直接，不应该为捉高效率而把语句复杂化；(2)在一行

8、只写一条语句；(3)编写程序时应优先考虑清晰性；(4)除非对效率有特殊要求，程序编写要做到清晰第一，效率第二