《公共基础复习资料(2)打印》由会员分享，可在线阅读，更多相关《公共基础复习资料(2)打印（5页珍藏版）》请在金锄头文库上搜索。
1、我上学期的计算机笔试差几分，就是因为没怎么准备公共基础知识。非常的悔，所以放假在家没事做的时候，为自己也为大家准备了一点资料，自认为比买的资料要简洁些。这上面的知识点不是全部，但几乎每个点都曾在试卷上出现过，红色起一个警醒提示的作用。9月考试在即，如果大家还没有把重点放在这上面，希望这份东西可以给要考试的同学带来好运。 -quan 二级公共基础知识总结第一章 数据结构与算法算法是指解题方案的准确而完整的描述。算法的基本特征：是一组运算顺序的规则，此顺序将在有限的次数下终止。 （1）可行性； 特征 （2）确定性；（每步明确，清楚） 基本特征 （3）拥有足够的情报。（4）有穷性，算法必须在有限的时
2、间内做完，即能在执行有限个步骤后终止； 一是对数据对象的操作和运算 基本运算：运算运算，逻辑运算，关系运算，数据传输算法的基本要素 投影 选择 连接顺序结构二是算法的控制结构 选择结构，循环结构。算法复杂度：算法时间复杂度和算法空间复杂度。都是评价算法的，但是无关联。算法的效率与数据的存储结构有关。算法时间复杂度是指计算工作量（次数，不是数据量）。算法空间复杂度是指算法所需要的内存空间。数据结构是指相互有关联的数据元素的集合。 （1）各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）各数据元素在计算机中的存储关系，即数据的存储结构； 顺序、链接、索引等。 数据的逻辑结构可以表示为多种存
3、储结构，并不一一对应。程序执行的效率与数据存储结构密切相关。数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。 结点由两部分组成：数据域，指针域线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。（也就是说不一定要有前后件）非线性结构：不满足线性结构条件的数据结构。 线性结构可以处理非线性结构 Egg:数组是顺序存储结构，但是利用数组可以处理二叉树(非线性结构)。线性表，由一组数据元素构成，元素之间的相对位置是线性的。由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件Egg:存储一个学生信息的数据单位是记
4、录。结点个数n称为线性表的长度，当n=0时，称为空表（即线性表不一定有元素）。队列 ：允许在一端进入插入（队尾），而在另一端进行删除（对头）的线性表。“先进先出”或“后进后出队头指针可以大于，也可以小于队尾指针。队头指针和队尾指针共同决定循环队列的元素的个数。栈 ：限定在同一端进行插入与删除的线性表。“先进后出”或“后进先出”允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。支持子程序调用的结构。链式所需的存储空间顺序。链式存储结构空间不一定是连续的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构二叉树存储结构采用链式存储结构。顺序存储空间一定是连续的，同时各元素是按逻
5、辑顺序（不是大小）依次存放。 树与二叉树都是非线性结构 只有一个前件的节点，称为父结点。没有前件的结点称为树的根结点，简称树的根。没有后件的结点称为叶子结点。每一个结点可以有多个后件，称为该结点的子结点。 非空二叉树只有一个根结点；二叉树的特点 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。深度为n的满二叉树,总结点的个数：2k-1.深度为n的满二叉树，叶子结点的个数：2k-1 度为0的结点（即叶子结点）总是比度为2的结点多一个； 前序遍历，首先访问根结点，然后遍历左子树，最后遍历右子树；二叉树的遍历 中序遍历，首先遍历左子树，然后访问根结点，最后遍历右子树； 后序遍历，首先遍历
6、左子树，然后访问遍历右子树，最后访问根结点对于长度为n的有序线性表，用顺序查找时最坏情况需比较n次。用二分法. log2n次. 交换类排序法：（1）冒泡排序法，需坏n(n-1)/2 （2）快速排序法 插入类排序法：（1）简单插入排序法，最坏n(n-1)/2（2）希尔排序法，最坏O(n1.5) 选择类排序法：（1）简单选择排序法, 最坏n(n-1)/2（2）堆排序法，最坏O(nlog2n)第二章程序设计基础 1、源程序文档化（可读性好） 良好的程序设计风格 2、数据说明的方法（注释分序言性注释和功能性注释）3、语句的结构（清晰第一、效率第二）4、输入和输出（提示信息） 自顶向下；结构化程序设计方
7、法的四条原则 逐步求精；模块化；限制使用goto语句。 选择结构结构化程序的基本结构 循环结构 顺序结构面向对象的程序设计主要是为了提高软件的可重用性。 特征：继承，多态，封装，分类。 对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体。 基本特点：（1）标识惟一性（2）分类性（3）多态性；4）封装性；（5）模块独立性好类是指具有共同属性、共同方法的对象的集合。消息是一个实例与另一个实例之间传递的信息。继承，是指类之间共享属性和操作的机制。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。第三章软件工程基础定义：软件是包括程序、数据及相关文档的完整集合。软件按功能
8、分为应用软件、系统软件、支撑软件（或工具软件）。编译程序，操作系统，汇编程序，三者都是系统软件软件危机主要表现在成本、质量、生产率等问题。软件工程包括3个要素：方法、工具和过程。方法是完成工程项目的技术手段。工具支持软件的开发，管理，文档的生成。过程支持软件开发的各个环节的控制，管理。软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段:软件定义、软件开发、运行维护软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。需求分析方法有（1）结构化需求分析方法； （2）面向对象的分析的方法。从需求分析建立的模型的特性来分：静态分析和动态分析。需求求分析
9、阶段的任务：确定软件的系统功能。需求求分析阶段产生的主要文档：软件需求的规格说明书。结构化方法的核心和基础是结构化程序设计理论。结构化分析的常用工具（1）数据流图DFD； （2）数据字典DD； （3）判定树； （4）判定表。 数据字典是结构化分析的核心，作用就是描述系统中所用到的全部数据和文件的信息，即用户对数据的访问。数据流图中带有箭头的线段表示数据流典型的数据流类型有两种：变换型和事务型。 软件设计是将需求准确地转化为完整的软件产品或系统的唯一途径，是确定系统的物理模型。 技术观点来看，包括：结构设计、数据设计、接口设计、过程设计。 从工程管理角度来看：概要设计和详细设计衡量软件模块独立性
10、使用耦合性和内聚性两个定性的度量标准。软件应高内聚，低耦合。接口越简单，耦合低，内聚高，则软件越优秀。在程序结构中各模块的内聚性越强，则耦合性越弱，两者是相反的。常见的过程设计工具有：图形工具（程序流程图）、表格工具（判定表）、语言工具（PDL）。程序流程图中箭头表示控制流。详细设计（属于开发阶段）的结果基本决定了程序的最终代码。 软件测试的目的：发现还没有发现的错误。调试的目的：改正错误。主要在开发阶段进行。程序测试应避免由程序员自己去完成。软件测试方法：静态测试和动态测试。步骤：单元测试，集成测试，验收测试，系统测试。静态测试：不实际运行软件，主要通过人工进行。动态测试：是基本计算机的测试
11、，主要包括白盒测试方法和黑盒测试方法。白盒测试：在程序内部进行黑盒测试： 软件调试：静态调试和动态调试。第四章 数据库设计基础数据是数据库管理系统的核心。数据库设计是数据应用的核心。数据库技术：解决数据共享问题。层次型，网状型，关系型数据划分原则：数据之间的联系方式。数据库系统=由数据库+数据库管理系统+数据库管理员+硬件平台+软件平台计算机系统 数据 软件（是基础） 人员 数据库系统的基本特点：数据的高共享性与低冗余性 、数据独立性，数据（类型）一致性。 数据的独立是指：物理独立性和逻辑独立性。 数据的物理结构和逻辑结构不一定要一致。 需求分析数据库设计的4个阶段 概念设计（的目的是分析数据
12、内在语义关系） 逻辑设计（e-r图转化为关系数据模型） 物理设计数据库管理系统提供以下的数据语言：（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复数据库系统的三级模式：（1）概念模式：全体用户公共数据视图；（2）外模式：也称子模式与用户模式。是用户所见到的数据模式。（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。数据库系统的两级映射： （1）概念模式到内模式的映射； （2）外模式到概念模式的映射。（1）实体：现实世界中的事物；用 表示（2）属性：事物的特性；用 表示 （3）联系：现实世界中事物间的关系。用 表示实体集的关系有一对一、一对多、多对多的联系。实体和联系可以转化为关系，属性也可以转化为关系的属性。一个具有n个属性的关系称为n元关系。一个实体的所有属性叫元组。关系中各元组的分量是不可再分的数据项。一个关系的属性名表称为关系模型。关系模型采用二维表来表示，简称表。一个二维表就是一个关系。关系表中，每一行称为一个元组，每一列称为表的属性。关系模型和数据模型是完全不同的数据模型。在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集
