Dujnoua全国计算机等级考试二级公共基础知识点总结.doc

Time will pierce the surface or youth, will be on the beauty of the ditch dug a shallow groove ; Jane will eat rare!A born beauty, anything to escape his sickle sweep .-- Shakespeare 1、算法是指解决方案的准确而完整的描述 2、算法的四个基本特性: 可行性确定性有穷性拥有足够的情报 3、算法有两个基本的要素组成: 一、数据对象的运算和操作二、算法的控制结构 4、计算机中的基本操作算术运算逻辑运算关系运算数据运算 5、算法的控制结构给出了算法的基本框架, 不仅决定了算法中各操作的执行顺序, 而且也直接反应了算法的设计是否符合结构化的原则。一个算法都可以用顺序、选择、循环 3 钟基本控制结构组成 6、算法的复杂度主要包括时间复杂度和空间复杂度 7、算法的时间复杂度是执行算法所需要的计算工作量。他不仅应该与使用的计算机、程序设计语言及程序编制者无关, 而且应该与算法实现过程中的许多细节无关。 8、算法的空间复杂度是指执行这个算法所需要的内存空间。 9、如果一个数据结构中没有一个数据元素,则称该数据结构为空的数据结构。 10、根据数据结构中个数据元素之间前后件关系的复杂程度,一般将数据结构分为线性结构和非线性结构 11、如果一个非空的数据结构满足 1、有且只有一个根结点;2、每一个结点最多有一个前件,也最多有一个后件,则称该数据结构为线性结构。线性结构又称线性表。 12、在一个线性结构中插入或删除任何一个结点后还是线性结构。 13、在计算机中存放线性表,一种最简单的方法是顺序存储。、 14、线性表的顺序存储结构具有两个基本的特点:一、线性表中所有元素所占的存储空间是连续的。二、线性表中各数据在存储空间中是按逻辑顺序依次存放的。 15、线性表的插入运算和删除运算 -9 16、栈是一种特殊的线性表,其插入和删除只能在表的一端进行。 17、在栈中允许插入与删除的一端称为栈顶, 而不允许插入与删除的一端称为栈底, 栈的修改原则是先进后出或后进先出。 18、入栈运算: 1 、首先将栈顶指针进 1 ,然后将新元素入到栈顶指针指向的位置。 19、退栈预算:首先将栈顶元素赋予一个指定的变量,然后将栈顶指针退 1。 20、队列:是指允许在一端进行插入、而在另一端进行删除的线性表,允许插入的一端称为队尾, 允许删除的一端称为排头。队列又称先进先出或后进后出的线性表,体现了“先来先服务的原则” 21、队列的顺序存储结构一般采用循环队列的形式。即将队列的存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供列队循环使用。 22、线性表的顺序存储结构具有简单、运算方便等优点。但是对于大的线性表,特别是元素变动频繁的大线性表不宜采用顺序的存储结构,二是采用链式存储结构 23、链式存储结构中,要求每个结点有两部分组成: 一用于存放数据元素值,称为数据域。另一部分用于存放指针, 称为指针域。其中指针用于指向该结点的前一个或后一个结点。 24、在链式存储结构中的存储空间可以不连续,各数据结点的存储结构与数据之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可以用于表