全国计算机二级 公共基础高频考点汇总.doc

《全国计算机二级 公共基础高频考点汇总.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章数据结构与算法算法是一组有穷的指令集，通俗地说就是计算机解题的过程。算法有四个基本特征：确定性、有穷性、可行性、拥有足够的情报.算法的组成要素：对数据对象的运算和操作（算术运算、逻辑运算、关系运算、数据传输操作）、控制结构（算法一般由顺序、选择、循环三种基本结构组合而成）。算法的复杂度（复杂度的高低体现在运行该算法时所需占用计算机资源的多少）：算法的时间复杂度是指执行算法所需要的计算H作最，即基本运算次数；算法的空间复杂度是指执行算法所需要的内存空间。数据结构是指相互有关联的数据元索的集合。前后件关系是数据元索之间最

2、基本的关系。依据视点不同，数据结构可以分为数据的逻辑结构（它是面向问题的，与所使川的计算机无关）和存储结构（也称物理结构，它是而向计算机的，是数据的逻辑结构在计算机屮的表示）。一临结点最多有一个依据数据元索Z间的关系,数据结构--般分为线性结构和非线性结构线性结构（也称线性表）：非空的数据结构、有且只有一个根结点前件（也最多有一个厉件）。L綁匚素，当存储空间不足吋,可以动态为其分配内存空间,所以不必估计融塗问的人虑碱屋表可以随机访问任意一个结点，……一二_-•-顺序存储结构的插入运算：在顺序表第i个位置±W-值厂就耍先把第

3、i个元索（包括i）之后的所有元素依次向后移动-个位置，然后加1.顺序存储结构的删除运算：要删除第i个表项，则必须把第i个元索（不包括i）之厉的所有元索依次向前移动一个位宜，把第i个表项覆盖血最后长度减1.栈是一种后进先岀（先进后岀）的线麴具仆记忆功能。栈的基本运算有：入栈，出栈-（删除栈顶元素），初始化、置空、判断栈是否为空或满、提线性表的顺序存储结构的特点是逻辑关系相邻的结点物理位HVrli链表的优点是在进行插入和删除运算吋，只需要改銮指针即可，不而链表必须从第一个数据结点出发I逐一查扌爭个结点■个、——取栈顶元素等，对

4、栈峻祚瞬在栈顶进行的C列队只允许在表的一•端插入（队尾），翼另■端删除（队头），是-•种先进先出（片进后出）的线性表。栈和队饗共同点：都是操作受限的线性表，只允许在表的端点处进行操作。树（假性结构）对于任意空新都具有两个特性：有且只有一•个根结点；当n（结点）>1时，除根结点外的其余结，矗J分为m（nr>0）个互不相交的有限集。结点的度：结的子树棵数。度为0的结点为叶子结点。树的度：树结点的度的最人值。树的深度则为所处层次最大的那个结点的层次。总结点数二总度数+1（—棵树屮每个结点的度树之和与边的条数相等）二叉树的基本性质

5、:遷：叉树的第k层上，最多有2的kJ次方个结点；深度为m的二叉树最多有2的m次方-1个结点；任意二义树屮，度为0的结点（叶子结点）总比度为2的结点多一个；具有n个结点的二叉树，其深度不小于[log2n]+l（“[]”取整）满二叉树就是每一层上的所有结点数都到达最大值；完全二叉树：具有n个结点的完全二叉树的深度为[log以2为底n的对数]+1；完全二叉树屮度为1的结点数为0或1；二叉树的编历如果二义树为空，则执行空操作;前序遍历：访问根结点，前序遍历左子树，前序遍历右子树中序遍历：中序遍历左子树，访问根结点，屮序遍历右子树厉

6、序遍历：厉序遍历左子树，厉序遍历右子树，访问根结点。（层层分左右根）顺序査找，从表的一端开始，依次扫描表屮的元索，若查找失败则返冋-1（失败时元索的位置），在i个有n个元素的线性表屮进行顺序查找，则查找成功时的平均比较次数为（n+1）/2次，最坏的情况则是比较n次。二分查找，先将线性表屮的元索进行排序，然后再依次进行折中查找。（只用于顺序存储的有序表）在长度为n的有序线性表屮进行二分杳找，需要的比较次数为log2n,最坏惜况下需要比较的次数是O（log2n）希尔排序，在最坏情况下需要比较0（十§）次。堆排序，在最坏情况下需

7、要比较nlog2n次。第二章程序设计基础X）、白顶向下、逐步求精、冒泡排序，在最坏情况下需要比较n（ii・l）/2次，时间复杂度为O（n（n-1）/2）（冒泡排序需耍经过n・l趟排序），（简单插入排序、快速排序也一样）。程序设计的主导风格“清晰第一，效率第二”程序设计的方法主要有两种：结构化程序设计和面向对彖程序设计结构化程序设计必须遵循的原则：模块化（以模限制使用goto语句。构（重复结构）。对象具有5个基本特点：标识唯一结构化程序的基本结构：顺序结构、选择结构（分】面向对象方法的基本概念有：对象是其最基木的概念，性、分

8、类性、多态性、封装性（实现信息隐驱）、她独立性（与信息隐蔽的概念直接相关）好。类和实例，类的实例称为对象（薦是类的实例£类描述的是具有相似性质的一组对象川以共亨程序代码和数时可产生完全不同的彳1三章软件工程基础Q完整集合；按功能可分为三人类：应用软件、系统象集合；消息（一个对象通裁另一对象发送信息来请求