公共基础知识考试点

第 1 章  数据结构与算法

考点1:算法具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报。

      确定性:是指算法中每一个步骤都必须是有明确定义的,不允许模棱两可的定义

      有穷性:是指算法必须能在有限的时间内做完

      一个算法由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构

考点2:算法复杂度包括时间复杂度和空间复杂度

       时间复杂度       执行算法所需要的计算工作量

       空间复杂度       执行这个算法所需要的内存空间

考点3:数据结构

一:讨论的问题:1.数据元素之间的逻辑关系,即数据的逻辑结构

             2.数据元素在计算机中的存储关系,即数据的存储结构

             3.对各种数据结构进行的运算

考点4:数据结构分为两大类型：线性结构与非线性结构。

     （1）如果一个非空的数据结构满足下列两个条件：

         ① 有且只有一个根结点；

         ② 每一个结点最多有一个前件，也最多有一个后件。

     则称该数据结构为线性结构。

     如果一个数据结构不是线性结构，则称之为非线性结构。

考点5:线性表

     特点: (1) 线性表中所有元素所占的存储空间是连续的

          (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

考点5:  栈的基本概念

     栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。

     栈是按照“先进后出”或“后进先出”的原则组织数据的。

考点6:队列的基本概念

     队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。当表中没有元素时称为空队列。即先进先出表。循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用

考点7: 链表

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。

考点8:二叉树性质

(1)     在树结构中,每一个结点只有一个前件,称为父结点,没有父结点的只有一个,成为根结点

(2)     没有后件的结点成为叶子结点

(3)     一个结点所拥有的后件个数称为该结点的度,在树中,所有结点中最大的度称为树的度

(4)     树的最大层次称为树的深度

(5)     在二叉树的第k层上,最多有2^(k-1)个结点

(6)     深度为m的二叉树最多有2^m-1个结点

(7)     任意一棵二叉树,度为0的结点(即叶子结点)总是比度为2的结点多一个

(8)     满二叉树:除最后一层外,每一层上的所有结点都有两个子节点

(9)     完全二叉树:除最后一层外,每一层上的结点数都达到最大值,在最后一层上只缺少右边的若干结点

考点9: 二叉树的遍历

根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。

      （1）前序遍历

     先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树

时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。

      （2）中序遍历

     先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子

树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图 1-1

中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）

      （3）后序遍历

     先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子

树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

考点10:各种排序的复杂度

       (1)顺序查找需要比较n 次

       (2)冒泡排序在最坏的情况下需要比较次数为n(n-1)/2 。

       (3)简单插入排序法，最坏情况需要n(n-1)/2 次比较；

       (4)希尔排序法，最坏情况需要O(n1.5)次比较。

       (5) 简单选择排序法，最坏情况需要n(n-1)/2 次比较；

       (6)堆排序法，最坏情况需要O(nlog2n)次比较。

第二章:程序设计基础

考点1:结构化程序设计的原则

     (1) 自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标；

     (2) 逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化；

     (3) 模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。

     (4) 限制使用goto 语句：在程序开发过程中要限制使用goto 语句。

考点2:结构化程序的基本结构

     结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。

考点3: 面向对象方法涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。

       对象是面向对象方法中最基本的概念,主要特点:

       (1)标识惟一型   (2)分类性（3）多态性  (4)封装性  (5)模块独立性好

考点4:消息:对象间的相互合作需要一个机制来协助进行,这个机制就是消息

考点5:继承是面向对象的方法的一个主要特征,分为单继承和多重继承

第三章:软件工程基础

考点1: 计算机软件是包括程序、数据以及相关文档的完整集合,软件工程包括3 个要素：方法、工具和过程

考点2: 软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。

       软件生命周期还可以分为软件定义、软件开发、软件运行维护阶段

       软件定义阶段包括:可行性研究、需求分析

       软件开发阶段包括:概要设计、详细设计、实现、测试

       软件维护阶段包括:使用、维护、退役

考点3:软件工程的理论和技术性研究主要包括:软件开发技术和软件工程管理

考点4:数据流图图符的含义

      圆形表示加工,箭头表示数据流,等于号表示存储文件,矩形表示源、潭

考点5:数据字典:是结构化分析方法的核心,数据字典是对所有与系统相关的数据元素的一个有组织的列表

考点6:软件需求规格说明书是需求分析阶段的最后成果

考点7:模块独立性

      衡量模块独立性的定性标准:内聚性与耦合性

      内聚性:是一个模块内部各个元素间彼此结合的紧密程度的度量

      耦合性:模块间互相连接的紧密程度的度量

      一个优秀的设计应尽量做到高内聚、低耦合

考点8:典型的数据流类型有两种:变换型和事务型

考点9:程序流程图图符的含义

考点10:软件测试是为了发现错误而执行程序的过程

       静态测试是由人工进行的测试

       动态测试是基于计算机的测试

考点11:白盒测试主要方法:逻辑覆盖、基本路径测试

       黑盒测试主要方法:等价类划分法、边界值分析法、错误推测法、因果图等

软件测试过程一般按4个步骤来进行:单元测试、集成测试、验收测试、系统测试

考点12:程序调试的任务是诊断和改正程序中的错误,与测试不同,软件测试是尽可能多的发现错误

第四章:数据库设计基础

考点1:数据库管理系统是数据库的机构,它是一种系统软件,负责数据库中的数据组织,数据操纵，数据维护,控制及保护和数据服务等

考点2:数据库系统提供的数据语言:

(1)     数据定义语言:该语言负责数据的模式定义与数据的物理存取构建

(2)     数据操纵语言负责数据的操纵,包括查询及增、删、改等

(3)     数据控制语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等

考点3:数据库系统由如下几部分组成:数据库、数据库管理系统、数据库管理员、硬件平台与软件平台

考点4:数据独立性是数据与程序间的互不依赖性,即数据库中数据独立于应用程序而不依赖于应用程序,数据独立性分为物理独立性和逻辑独立性

考点5:数据库的三级模式

(1)     概念模式:是数据库系统中全局数据逻辑结构的描述,是全体用户公共数据视图

(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图中实体与联系都可以转换成关系,属性也可以转换成关系的属性