《2010国考二级公共基础知识复习纲要》由会员分享，可在线阅读，更多相关《2010国考二级公共基础知识复习纲要（4页珍藏版）》请在金锄头文库上搜索。
1、2010 二级公共基础知识复习纲要公共基础知识考试点第 1 章 数据结构与算法考点 1:算法具有 4 个基本特征：可行性、确定性、有穷性、拥有足够的情报。确定性:是指算法中每一个步骤都必须是有明确定义的,不允许模棱两可的定义有穷性:是指算法必须能在有限的时间内做完一个算法由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构考点 2:算法复杂度包括时间复杂度和空间复杂度时间复杂度执行算法所需要的计算工作量 空间复杂度执行这个算法所需要的内存空间考点 3:数据结构讨论的问题:1.数据元素之间的逻辑关系,即数据的逻辑结构2. 数据元素在计算机中的存储关系,即数据的存储结构3. 对各种数
2、据结构进行的运算考点 4:数据结构分为两大类型：线性结构与非线性结构。（1）如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。考点 5:线性表特点: (1) 线性表中所有元素所占的存储空间是连续的(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的考点 6:栈的基本概念栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。栈是按照“先进后出”或“后进先出”的原则组织数据的。考点 7:队列的基本概念队列是只允许在一端进行删除,在另一端进行
3、插入的顺序表,通常将允许删除的这一端 称为队头，允许插入的这一端称为队尾。当表中没有元素时称为空队列。即先进先出表。循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列 循环使用考点 8:链表在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。考点 9:二叉树性质(1) 在树结构中,每一个结点只有一个前件,称为父结点,没有父结点的只有一个,成为根结点(2) 没有后件的结点成为叶子结点(3) 一个结点所拥有的后件个数称为该结点的度 ,在树中,
4、所有结点中最大的度称为树的度(4) 树的最大层次称为树的深度(5) 在二叉树的第k 层上,最多有 2(k-1)个结点(6)深度为m 的二叉树最多有 2m-1 个结点(7) 任意一棵二叉树,度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个(8) 满二叉树:除最后一层外,每一层上的所有结点都有两个子节点(9) 完全二叉树:除最后一层外,每一层上的结点数都达到最大值,在最后一层上只缺少右边的若干结点考点 10: 二叉树的遍历根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。（1） 前序遍历先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访
5、问根结点，然后遍历左子树，最后遍历右子树。（2） 中序遍历先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图 1-1 中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）（3） 后序遍历先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。考点 11:各种排序的复杂度(1) 顺序查找需要比较n 次(2) 冒泡排序在最坏的情况下需要比较次数为n(n-1)/2 。(3)简单插入排序法，最坏情况需要n(n-1)/2 次比较； (4)希尔排序法，最坏
6、情况需要O(n1.5)次比较。(5) 简单选择排序法，最坏情况需要n(n-1)/2 次比较；(6) 堆排序法，最坏情况需要O(nlog2n)次比较。第二章:程序设计基础考点 1:结构化程序设计的原则(1) 自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标；(2) 逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化；(3) 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标， 把每个小目标称为一个模块。(4) 限制使用goto 语句：在程序开发过程中要限制使用goto 语句。考点 2:结构化程序的基本结构结构化程序的基本结构有三种类型：顺序结构、选择结构和循
7、环结构。考点 3:面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。对象是面向对象方法中最基本的概念,主要特点:(1)标识惟一型(2)分类性（3）多态性 (4)封装性 (5)模块独立性好考点 4:消息:对象间的相互合作需要一个机制来协助进行,这个机制就是消息考点 5:继承是面向对象的方法的一个主要特征,分为单继承和多重继承第三章:软件工程基础考点 1: 计算机软件是包括程序、数据以及相关文档的完整集合,软件工程包括 3 个要素：方法、工具和过程考点 2: 软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。软件生命周期还可以分为软件定义、软件开发、软件运行维护
8、阶段软件定义阶段包括:可行性研究、需求分析软件开发阶段包括:概要设计、详细设计、实现、测试软件维护阶段包括:使用、维护、退役考点 3:软件工程的理论和技术性研究主要包括:软件开发技术和软件工程管理考点 4:数据流图图符的含义圆形表示加工,箭头表示数据流,等于号表示存储文件,矩形表示源、潭考点 5:数据字典:是结构化分析方法的核心,数据字典是对所有与系统相关的数据元素的一个有组织的列表考点 6:软件需求规格说明书是需求分析阶段的最后成果考点 7:模块独立性衡量模块独立性的定性标准:内聚性与耦合性内聚性:是一个模块内部各个元素间彼此结合的紧密程度的度量耦合性:模块间互相连接的紧密程度的度量一个优秀
9、的设计应尽量做到高内聚、低耦合考点 8:典型的数据流类型有两种:变换型和事务型考点 9:程序流程图图符的含义考点 10:软件测试是为了发现错误而执行程序的过程静态测试是由人工进行的测试动态测试是基于计算机的测试考点 11:白盒测试主要方法:逻辑覆盖、基本路径测试黑盒测试主要方法:等价类划分法、边界值分析法、错误推测法、因果图等软件测试过程一般按 4 个步骤来进行:单元测试、集成测试、验收测试、系统测试考点 12:程序调试的任务是诊断和改正程序中的错误,与测试不同,软件测试是尽可能多的发现错误第四章:数据库设计基础考点 1:数据库管理系统是数据库的机构,它是一种系统软件,负责数据库中的数据组织,
10、数据操纵，数据维护,控制及保护和数据服务等考点 2:数据库系统提供的数据语言:(1)数据定义语言:该语言负责数据的模式定义与数据的物理存取构建(2)数据操纵语言负责数据的操纵,包括查询及增、删、改等(3)数据控制语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等 考点 3:数据库系统由如下几部分组成:数据库、数据库管理系统、数据库管理员、硬件平台与软件平台考点 4:数据独立性是数据与程序间的互不依赖性,即数据库中数据独立于应用程序而不依赖于应用程序,数据独立性分为物理独立性和逻辑独立性考点 5:数据库的三级模式(1)概念模式:是数据库系统中全局数据逻辑结构的描述,是全体用户公共数据
11、视图(2)外模式:是用户的数据视图,也就是用户所见到的数据模式(3)内模式:它给出了数据库物理存储结构与物理存取方法考点 6:数据模型所描述的内容有三个方面:(1)数据结构:主要描述数据的类型、内容、性质以及数据间的联系(2)数据操作:主要描述在相应数据结构上的操作类型与操作方式 (3)数据约束:主要描述数据结构内数据间的语法、语义联系考点 7:E-R 模型(1) E-R 模型由三个基本概念组成:实体、联系和属性(2) 在E-R 图示法中:矩形表示实体集,椭圆形表示属性,菱形表示联系考点 8:关系模型的约束包括实体完整性约束、参照完整性约束、用户自定义完整性约束考点 9:关系代数并运算:关系R 与S 经并运算后所得到的关系是由那些在R 内或在S 内的有序组交运算:关系R 与S 经交运算后所得到的关系是由那些即在R 内又在S 内的有序组差运算:关系R 与S 经差运算后所得到的关系是由那些在R 内但不在S 内的有序组自然连接:考点 10:E-R 图与关系的转换E-R 图中实体与联系都可以转换成关系,属性也可以转换成关系的属性
