计算机二级考(笔试)复习资料 公共基础知识.doc

一、 算法1. 算法基本概念：算法是在有限的步骤内 求解某一问题 所使用的一组 定义明确的法则。通俗的说就是计算机解决问题的过程（计算方法），这个过程中无论是形成解题思路（推理实现的算法）还是编写程序（操作实现的算法），都是实施某种算法。 算法是一组逻辑步骤 程序是用计算机语言描述的算法2.算法特征：输入（初始条件）、确定性（每一计算步骤都有确切的定义）、有穷性（算法必须保证执行有限步结束）、可行性（算法原则上能精确计算，而且人用纸笔做有限次运算后即可完成）、输出（没输出的结果无意义）。3.算法的表示：传统算法-图形法（如流程图） 目前常用方法-伪代码表示4. 算法的基本要素：对数据对象的运算和操作（算数运算、关系运算、逻辑运算、数据传输）算法的控制结构（顺序、选择、循环）5. 算法的基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法6. 算法的评价：时间复杂度（执行这个算法所需的计算工作量）空间复杂度（执行这个算法所需的内存空间） 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。二、数据结构 程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。包括三个方面：数据结构中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； 在对数据进行处理时，各数据元素在计算机中的储存关系，即数据的储存结构； 对各种数据结构进行计算。1. 逻辑结构 数据的逻辑结构是指反映数据元素之间关系的数据结构。 数据的逻辑结构包含：1）表示数据元素的信息 2）表示各数据元素之间的前后关系。 常见的逻辑结构有：线性结构（结构中每个元素存在一个对一个的关系）、树形结构（存在一个对多个的关系）、图形结构（存在多个对多个的关系）。其中树形结构和图形结构统称为 非线性结构。2. 存储结构（物理结构） 储存结构是指数据结构在存储空间中的具体实现。 只抽象的反应数据元素之间的关系的结构，而不管其储存方式的数据结构称为逻辑结构。 各数据元素在计算机中的储存位置与他们的逻辑关系不一定是相同的。而且一般是不同的。 一种数据结构可以根据需要而选择一种或多种存储结构 常见的存储结构有：顺序存储结构、链式存储结构、索引存储结构。3.数据的运算 检索、插入、删除、更新、排序常见的数据结构1. 线性表 线性表是由n(n=0)个数据元素组成的一个有限的序列（如：春夏秋冬） 线性表的存储结构有两种：顺序存储结构、链式存储结构 线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且个数据元素的存储位置也是任意的。各数据元素的先后关系是由各节点的指针域指示。 链式存储结构每一个存储结点不仅是存储节点的值，而且存储结点之间的关系 采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量的域元素移动。 循环链表是链式存储结构的一种，特点是表中最后一个节点的指针域指向头结点。 双向链表的结点中有两个指针域，其中一个直接指向直接后继，另一个直接指向直接前趋。 线性表的存储结构有两种：顺序存储结构、链式存储结构。 数据元素在计算机存储空间中的位置关系域与他们的逻辑关系不一定是相同的。 一个逻辑数据结构可以有多种存储结构而且不同的存储结构影响数据处理的效率。2. 栈和队列 A）栈是一种特殊的线性表其特点是插入和删除运算都只能在线性表的一端进行。 栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。 栈的物理存储结构可以用顺序结构，也可以用链表结构。 栈的基本运算只有三种：入栈、退栈、和读栈项元素。 B）队列是一种特殊的线性表其特点是：所有的插入在线性表的一端进行，所有的删除运算都在表的另一端进行。即在表的前端进行插入操作，在表的后端进行删除操作。（队列进行插入运算的是队首，进行删除运算的队尾） 队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。即最先插入的元素是最先删除的元素，最后插入的是最后删除的。 队列有三种运算：入队、出队、读队首元素。 循环队列：把队列的存储空间在逻辑上看成一个环，当R指向存储空间的末端时，就把它重新置于始端。 线性表（线性结构）、栈（特殊的线性表）、队列（是一种操作受限制的线性表）、树（是一种重要的非线性数据结构） 非线性结构：一个数据结构不是线性结构就是非线性结构。 线性结构的特点：有且仅有一个根节点 除第一个结点外，每一个结点最多有一个直接前驱节点 除最后一个接点外，每一个结点最多有一个直接后缀结点。3.树与二叉树 树的概念 树的定义，n个结点的有限集。 根只有一个。 如果n=0则称之为空树，否则当n1时，其余结点被分成m(m0)个互不相交的子集，每个子集又是有一棵树。 树型结构的常用术语： 结点的度（一个结点子树的个数）；树的度（树中所有结点度的最大值）；终端结点（度为零的结点）；非终端结点（度不为零的结点）；节点的层次（树中根节点的层次为1，根结点子树的根为第2层，以此类推）；树的深度（树中所有结点层次的最大值）；有序树，无序树（如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称之为有序树，否则称之为无序树） 二叉树的概念 定义 二叉树是一种有序的树形结构，它与一般的树形结构的区别是：每个结点最多有两个子树；子树有左右之分，次序不能任意颠倒。 性质 在二叉树的第i层最多有2(i-1)个结点 深度为h的二叉树最多有2h-1个结点(h=1) 二叉树上叶子结点数比度为2的结点数多1 满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。 完全二叉树：有一颗深度为h，具有n个结点的二叉树，若将他与一颗同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这颗二叉树为完全二叉树。 二叉树的存储：在计算机中，二叉树通常采用链式存储结构。 二叉树的遍历： 遍历指不重复的访问二叉树的所有节点； 二叉树的遍历的次序与树型结构上的大多数运算有联系； 遍历的方式有三种(1)前序遍历（DLR） (2)中序遍历（LDR） (3)后序遍历（LRD）4. 查找技术 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。 若查找到了满足条件的结点，则称查找成功；否则称之为查找失败。 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。 通常根据不同的数据结构采取不同的查找方法：顺序查找、二分查找。 顺序查找：从第一个元素开始依次比较。适用场合，对线性表中元素的排列次序没有要求 对线性表的存储结构没有要求，链式和顺序结构都可。 二分查找：首先在表的中间位置查找比较大小，然后根据比较的大小再确定在那=哪个子表中查找。重复上述过程，直至查找完毕。适用场合，线性表中关键字值以递增或递减的次序排列，线性表采用顺序存储结构。5.排序技术 冒泡排序：A.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换，第一趟扫描完则使最大的数排到表的最后；B.重复A过程，除开最后一个元素，以此类推。对于长度为N的线性列表要扫描N-1遍。 选择排序：从表中找出最小的元素，排在第一位。然后从第二位开始查找最小的元素，排在第二位，以此类推。对于长度为N的线性列表要扫描N-1遍。 最坏情况需要的次数：简单选择排序，最坏要n(n-1)/2次；冒泡排序，最坏要n(n-1)/2次；希尔排序法，最坏要O(n1.5)次比较。堆排序，最坏要O(n乘以 以2为底n的对数）次比较）。三、 程序设计基础结构化程序设计 四条原则：自顶向下；逐步求精；模块化；限制使用goto语句。 基本结构及特点：顺序结构（简单程序设计最基本最常用的结构）；选择结构 又称分支结构（包括简单选择和多分支选择结构）；重复结构 又称循环结构（可根据给定条件判断是否重复执行某一相同程序段）。面向对象的程序设计 对象是面向对象方法中最基本的概念。 对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。 属性即对象所包含的信息 操作描述了对象执行的功能，操作也称为方法或服务。 类是指具有共同属性、共同方法的对象的集合。 所以类是对象的抽象，对象是对应类的一个实例。 消息是一个实例与另一个实例之间传递的信息。（消息的组成包括：接受对象的名称；消息标识符，也称消息名；零个或多个参数） 继承是指能够直接获获得已有的性质和特征，而不必重复定义他们。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。 多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。四、 软件工程基础 软件工程概念 软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。 软件工程包括3个要素：方法、工具和过程。 软件周期：软件产品从提出、实现、使用和维护到停止使用退役的过程。 软件生命周期三个阶段：软件定义（可行性研究，需求分析）、软件开发（概念设计、详细设计、研究、测试）、运行维护（使用、维护、退役）。主要活动阶段：可行性研究与计划的制定；需求分析；软件设计；软件实现；软件测试；运行和维护。结构化分析方法 结构化分析方法：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。 结构化分析的常用工具：数据流图；数据字典；判定树，判定表；软件需求规格说明书。结构化设计方法 软件设计包括：总体设计与详细设计 在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。 常见的过程设计工具有：图形工具（程序流程图，N-S，PAD）；表格工具（判定表）；语言工具（PDL伪码）。软件测试 目的：发现错误而执行程序的过程 软件测试方法： 静态测试：包括检查代码，静态结构分析、代码质量度量。不实际运行软件主要通过人工进行。 动态测试：是基本的计算机测试，主要包括白盒测试方法（逻辑覆盖、基于路基测试）和黑盒测试方法（等价类划分法、边界值分析法、错误推测法、因果图法、判定表驱动法 ）。 软件测试过程一般按四个步骤进行：单元测试、集成测试、验收测试和系统测试。程序调试 程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。 软件调试，静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。动态调试是辅静态调试，主要调试方法（强行排错法，回溯法，原因排除法）五、数据库设计基础数据：实际上就是描述事物的符号记录数据库（DB）：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库管理系统（DBMS）：一种系统软件，负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等，是数据库的核心。数据库系统（DBS）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。数据库应用系统：由数据库系统、应用软件、应用界面三者组成。 数据库系统层次示意图：数据库应用系统最终用户 操作系统计算机硬件数据库管理系统 开发人员数据库管理员 常见的关系数据库软件，小型：Visual FoxPro 、Access 大型：Oracle、Informix、SYBASE、SQL server 等数据系统的基本概念 数据管理系统提供的数据语言，数据定义语言：负责数据的模式定义与数据的物理存取构建；数据操作语言：负责数据的操纵，如查询、增、删、减、改；等；数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。 数据管理系统的发展，文件系统阶段：提供了简单的数据共享与数据管理能力，但它无法提供完整的、统一的。管理数据和数据共享能力。层次数据库与网状数据库系统阶段：为统一于共享数据提供了有力的支撑。关系数据库系统阶段 关系数据库系统的基本特点：数据的集成性，数据的高共享性与低冗余性，数据的独立性，数据的统一管理与控制。 数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。 数据库的三级模式：概念模式；外模式；内模式。数据库内模式(物理数据库)概念模式（概念数据库）外模式（用户数据库）外模式（用户数据库）外模式（用户数据库）应用应用应用 数据库的两级映射：概念模式到内模式的映射；概念模式到外模式的映射。外模式到概念模式映射 概念模式到内模式映射数据模型 数据模型是对客观事物及其关系的客观描述。数据库中的数据模型可以将复杂的现实世界要求反映到计算机数据库中的物理世界。 数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件。 数据模型所描述的内容包含：数据结构、数据操作和数据约束。 E-R模型的基本概念：实体，现实世界中的事物；属性，事物的特征；联系，现实世界中事物的关系，实体集的关系有一对一、一对多、多对多的联系。 E-R模型的图示法：用简单的几何图形表示实体集、属性与联系。 实体集的表示法：在E-R图中用矩形表表示实体集，在矩形内写上实体集的名字。属性表示法：在E-R图中用椭圆形表示属性，在椭圆形内写上该属性的名称。联系表示法：在E-R图中用菱形（内写上联系名）表示联系。实体集与属性间的联系关系：属性依附于实体集它们之间有联系关系用无向线段表示。属性依附于联系，它们之间也有联系，因此用无向线段表示。实体集与联系间的连接关系也用无向线段表示。、 层次模型（采用树形结构） 网络模型（采用无向图形结构） 关系模型（采用二维表结构） 关系操作：数据查询，查询关系数据库中的数据，一个关系内查询以及多个关系间查询。查询的基本单位为元组分量，先定位后操作。数据插入，插入一个元组（不定位）数据删除，删除一个元组（定位、操作）。数据修改，删除需修改的元组再插入修改后的元组。 关系模型的基本运算：插入，集合的并运算（两表属性一致）；删除，集合的差（交）运算；修改，集合的差/并（除）运算；查询 （投影、选择、笛卡尔积运算（是对两个关系的合并操作）数据库设计与管理 数据库设计的两种方法，面向数据：以信息需求为主，兼顾处理需求；面向过程：以处理需求为主，兼顾信息需求。 数据库生命周期：需求分析阶段（分析客户业务和数据处理需求）：结构析方法和面向对象的方法（数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流、数据存储、处理过程）；概念设计阶段（设计数据库的E-R模型图，确认需求信息的正确和完整）；逻辑设计阶段（将E-R图转换为多张表，进行逻辑设计，并应用数据库设计的三大范式进行审核）；物理设计阶段（数据库内模式包括存储结构和存取方法）；编码阶段（选择数据库进行物理实现，并编写代码实现前端应用）；测试阶段；运行阶段；进一步测试阶段6