资源描述：
《全国计算机二级公共基础知识要点汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第一章数据结构与算法1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报2.算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构一个算法一般都可以用顺序,循环,选择三种基本控制结构组合而成3.算法设计基本方法:列举法,归纳法,递推,递归,减半递推技术,回溯法4.算法复杂度主要包括:时间复杂度,空间复杂度 所谓时间复杂度是指算法所需要的计算工作量 所谓空间复杂度是指执行这个算法所需要的内存空间5.数据结构作为计算机的一门科学,主要研究和讨论的问题有以下三个方面:数据的逻辑结构， 数据的存储结构，对各种数据结构进行的运算 一
2、般情况下,在具有相同特征的数据元素集合中,各个数据元素之间存在某种关系(即联系),这种关系反映了该集合中的数据元素艘固有的一种结构.在数据处理领域中,通常把数据元素之间这种固有的关系简单的用前后件关系来描述(即前件与后件).1)数据的逻辑结构:更通俗地说,数据结构是指带有结构的数据元素的集合数据元素之间的前后件关系是指它们的逻辑关系,而与它们在计算机中的存储位置无关.因此,上面所述的数据结构实际上是数据的逻辑结构2)数据的存储结构:是指数据的逻辑结构在计算机存储空间中的存放形式也叫数据的物理结构一般来说,一种数据的逻辑结构根据需要可以表示成
3、多种存储结构,常用的存储结构有顺序,链接,索引等存储结构6.根据数据结构中各数据元素之间前后件关系的复杂度,一般将数据结构分为两大类型:线性结构，非线性结构 说明:在一个线性结构中插入或删除任何一个结点后还应是线性结构 7.线性表:是一种线性结构;是最简单,最常用的一种数据结构线性表的顺序存储结构具有以下两个基本特征:线性表中所有元素所占的存储空间是连续的线性表中各数据元素在存储空间中是按逻辑顺序依次存放的8.栈及其基本运算:1)栈实际上也是线性表,只不过是一种特殊的线性表.在这种特殊的线性表中,其插入与删除运算都只在线性表的一端进行
4、 2)在栈中允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底3)栈是按照"先进后出"或"后进先出"的原则组织数据的9.队列:是指允许在一端进行插入,而在另一端进行删除的线性表10.线性链表:在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域11.树:1)在树结构中,每个结点只有一个前件,成为父结点 没有前件的结点只有一个,称为树的根结点,简称为树的根2)在树结构中,一个结点可以有多个后件,它们都称为该结点的子结点。没有后件的结点称为叶子结点3)在
5、树结构中,一个结点所拥有的后件个数称为该结点的度。所有结点中的最大的度称为树的度4)树结构具有明显的层次关系,即树是一种层次结构。树的最大层次称为树的深度12.二叉树:1)二叉树是一种很有用的非线性结构 2)二叉树具有以下两个特点:非空二叉树只有一个根结点每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树由以上特点可以看出,在二叉树中,没一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树. 在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树 而没有左子树3)二叉树的基本性质:性质1,2,3,4,54)
6、两种特殊形态的二叉树:满二叉树:指的是除最后一层外,每一层上的所有结点都有两个子结点 完全二叉树:指的是除最后一层外,每一层的结点数均达到最大值;在最后一层上只缺少右边的若干结点 5)二叉树的遍历(很重要哦肯定要有这儿的题的!)13.查找技术:1)二分法查找:当有序线性表为顺序存储是才能采用二分查找,并且,二分查找的效率要比顺序查找高得多.2)冒泡排序法:假设线性表的长度为n,则在最坏的情况下,冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描,需要的比较次数为n(n-1)/2. 3)简单插入排序法:在简单插入排序法中,每一
7、次后最多移掉一个逆序,因此,这种方法的效率与冒泡排序法相同.在最坏情况下,简单插入排序需要n(n-1)/2次比较4)希尔排序法:希尔排序的效率与所选的增量序列有关 5)简单选择排序法:在最坏情况下需要比较n(n-1)次第二章 程序设计基础1.结构化程序设计的原则:1)自顶向下2)逐步求精3)模块化 4)限制使用goto语句2.结构化程序设计方法是程序设计的先进方法和工具.采用结构化程序设计方法编写程序,可使程序结构良好易读.易理解,易维护主要有三种结构:顺序结构,选择结构,重复结构遵循结构化程序的设计原则,按结构化程序设计方法设计出的程序
8、具有明显的优点:其一,程序易于理解,使用和维护 其二,提高了编程工作的效率,降低了软件开发成本3.面向对象的程序设计:1)面向对象方法之所以日益受到人们的重视和应用,成为流行的软
