计算机等级考试二级公共基础知识部分重点归纳.doc

《计算机等级考试二级公共基础知识部分重点归纳.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机等级考试二级公共基础知识部分重点归纳.txt男人偷腥时的智商仅次于爱因斯坦。美丽让男人停下，智慧让男人留下。任何东西都不能以健康做交换。本文由蓝鸟知道贡献doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。计算机等级考试二级公共基础知识部分重点归纳计算机等级考试二级公共基础知识部分重点归纳2010-08-0216:311.算法是一种设计好的计算序列，用来解决一类问题。12.算法复杂的包括：时间复杂度和空间复杂度。时间复杂度指计算工作量，空间复杂度指内存空间的要求。3.数据元素的集合，记为D

2、，数据之间的前后关系，记为R，B=（D,R）,B表示数据结构。二元组表示D中各元素间的前后关系。4.数据的逻辑结构在计算机存储空间中的存放形式称为存储结构（物理结构）。5.常用的存储结构：顺序存储，链接存储。6.数据的存储结构中，不接要存放数据元素的信息，还要存放数据元素之间的前后件关系的信息。7.线性结构（条件：非空数据结构）：1有且只有一个根节点；2每一个节点最多有一个前件，有最多有一个后件。8.栈、队列、串等都是线性结构。9.数组、广义表、树和图等数据结构都是非线性结构。10.根据数据结构中各数据元素之间前后件关系的复杂

3、度分：线性结构和非线性结构。11.栈，特殊的线性表，按“先进后出”或“先出后进”原则组织数据。如射击时射出子弹，顺序为后进弹匣先射出。12.栈的一端封闭，另一端开口，仅开口端允许插入和删除元素。允许插入与删除的一端称为栈顶，另一端称为栈底。无元素为空栈。13.栈的基本运算有3种：入栈、退栈、与读栈顶元素。14.队列只允许在一端（队头）进行删除，另一端（队尾）进行插入。无元素为空队列。15队列的修改是依照先进先出的原则进行。16.链式存储方式可用于两种数据结构中的任一种。17.链式中的结点由两部分组成：一部分用于存放数据元素值，

4、称为数据域，另一部分用于存放指针，称为指针域。指针用于指向该结点的前一个或后一个结点（即前件或后件）。18.二叉树是非线性结构，具有两个特点：1非空二叉树只有一个根节点；2每一个结点最多有两个子树，分别称为左子树右子树。。19.二叉树中，每个结点的度最大为2，因此所有子树也均为二叉树。20.二叉树中，一个结点可以只有左子树或右子树，当结点没有左子树或右子树时，该结点即为叶子结点。21.二叉树具有的性质：1在二叉树的第k层上，最多有2的k-1次方（k=》1）个结点。2深度为m的二叉树最多有2的m-1次方个结点。3在任意一棵二叉树

5、中，度为0的结点（即叶子结点）总是比度为2的结点多一个。4具有m个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。1计算机等级考试二级公共基础知识部分重点归纳222.遍历子树一般先遍历左子树再遍历右子树，即先左后右。根据访问根节点的次序，二叉树的遍历分为3类，前序遍历、中序遍历、后序遍历。23.查找是指在一个给定的数据结构中查找某一个指定的元素。24.二分法查找也称拆半查找，只是用于顺序存储的有序表。25.对于长度为n的有序线性表，利用二分法查找流程：1将X与线性表中间项比较。2若相

6、等则查找成功，结束查找。3若X小于中间项值，则在线性表前半部分以二分法继续查找。（X大于中间项值方法相同。）26.比较顺序查找与二分法查找，在最坏情况下，二分法查找只需log2n次，顺序查找则要n次。27.冒泡排序法和快速排序法都属于交换类排序法。其中冒泡法在最坏情况下需比较n(n-1/2次，同此数排序还有快速排序、直接插入排序、简单插入排序、简单选择排序。28.结构化程序设计的基本结构有3类，顺序结构、选择结构、循环结构。29.结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。30.对象是面向

7、对象中最基本的概念，通常把对象的操作也称为方法和服务。31.对象有5个特征：标识唯一性、分类性、多态性、封装性、模块独立性。32.类是具有共同属性，共同方法的对象的集合，类是对象的抽象，它包含了该对象类型中所有对象的性质，而一个对象则是其对应类的一个实例。33.一个消息由3部分组成：接收消息的对象的名称，消息标识符（消息名）和零个或多个参数。34.继承指的是可以直接获得已有的性质和特征，而不必重复定义它们。35.继承分为单继承与多重继承，单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。36.多态性指对象根据所接

8、受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动。37.软件包括程序、数据、和相关文档的完整集合。38.软件根据应用目标的不同可分为应用软件、系统软件、支撑软件（或工具软件）。39.软件由两部分组成：1机器可执行的程序和数据；2机器不可执行的，与软件开发、