1、计算机等级考试二级公共基础知识讲义计算机等级考试二级公共基础知识讲义 数据结构与算法算法算法定义：解题方案的准确而完善的描述。算法的基本特征：可行性 确定性 有穷性 拥有足够的情报算法的基本要素：算法中对数据的运算和操作：包括算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：包括顺序结构、选择结构、循环结构算法设计的基本方法：列举法 归纳法 递推 递归 减半递推技术 回溯法算法的复杂度：包括时间复杂度和空间复杂度算法的时间复杂度：执行算法所需要的计算工作量。算法的空间复杂度：执行这个算法所需要的内存空间大小。数据结构数据结构学科主要研究内容：数据的逻辑结构，数据集合中各数据元素之间所固有
2、的逻辑关系。数据的存储结构，在对数据进行处理时，各数据元素在计算机中的存储关系。对各种数据结构进行的运算。数据结构学科的研究目的：提高数据处理的效率。包括：数据处理速度。尽量节省在数据处理过程中所占用的计算机存储空间。数据处理：对数据集合中的各元素以各种方式进行运算。数据元素：每一个需要处理的对象都可以抽象为数据元素。数据结构：相互关联的数据元素的集合。一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。线性结构和非线性结构线性结构满足如下条件：有且仅有一个根结点。每一个结点最多有一个前件，也最多有一个后件。在一个线性结构中插入或删除任何
3、一个结点后还是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性表及其顺序存储结构线性表定义：线性表是由n(n=0)个数据元素a1,a2, an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。非空线性表结构特征：有且只有一个根结点a1，它无前件。有且只有一个终端结点an,它无后件。除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。线性表的顺序存储结构的基本特点：线性表中所有元素所占的存储空间是连续的。线性表中个数据元素在存储空
4、间中是按逻辑顺序一次存放的。线性表的主要操作：线性表的插入 线性表的删除 线性表的查找 线性表的排序 线性表的分解 线性表的合并 线性表的复制 线性表的逆转栈和队列栈及其基本运算栈的定义：栈是限定在一端进行插入和删除的线性表。它按照“后进先出”的原则组织数据。栈的顺序存储及其运算：在程序设计语言中，一般是用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。栈的基本运算：入栈运算：首先将栈顶指针加1，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能在进行入栈操作。此时发生栈“上溢”错误。退栈运算：首先将栈顶元素赋给一个指定的变
5、量，然后将栈顶指针减1。当栈顶指针为0时，说明栈空，不可能进行退栈操作。此时，发生栈“下溢”错误。读栈顶元素：将栈顶元素赋给一个指定的变量，栈指针不变。当栈顶指针为0时，说明栈空，读栈顶元素操作失败。队列及其基本运算队列的定义：是指允许在一端进入插入、而在另一端进入删除的线性表。它按照“先进先出”的原则组织数据。循环队列空的状态：s=0,且 front=rear=m循环队列满的状态：s=1,且 front=rear循环队列的基本运算：入队运算：首先将队尾指针加1(rear=rear+1)，并当rear=m+1时置rear=1;然后将新元素插入到指针指向的位置。当循环队列满时（s=1,且fron
6、t=rear）入队操作将引起“上溢”错误。退队运算：首先将排头指针加1(front=front+1)，并当front=m+1时置front=1;然后将排头指针指向的元素赋给指定的变量。当循环队列为空时（s=0,front=rear），退队操作将引起“下溢”错误。线性链表线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表线性链表的链式存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后后件结点的存储地址。双向链表的链式存储结构：双向链表的链式存储结构比线性链表的链式存储结构多出一个指针域，它用来存放前件结点的存储地址。带链的栈栈的链式结构：栈的链式结构基本上和线性链表的
7、链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针。带链的队列队列的链式结构：保持两个指针，一个指向队列头的指针和一个指向队列尾的尾指针。线性链表的主要运算：插入、删除、合并、分解、逆转、复制、排序、查找。循环链表特点：在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。循环链表中最后一个结点的指针域不是空，而是指向表头结点。判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。从任何一个结点出发可以访问到表中其他所有的结点。树与二叉树二叉树及其基本性质二叉树的特点：非空二叉树只有一个根结点每一个结点最多有两
8、棵子树。二叉树的基本性质：在二叉树的第k层上，最多有2k-1(k=1)个结点。深度为m的二叉树是指二叉树最多有2m-1个结点。在任意一棵二叉树上，度为0的结点（即叶子结点）总是比度为2的结点多一个。具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示log2n的整数部分。满二叉树和完全二叉树满二叉树的第k层上有2k-1个结点，且其深度为m的满二叉树有2m-1个结点。具有n个结点的完全二叉树的深度为log2n+1设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，, n给结点进行编号，则对与编号为k(k=1,2, n)的结点有以下结论：若k=1，则
9、该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为k/2。若2k=n, 则编号为k的结点的左子结点编号为2k，否则该结点无左子结点（显示也没有右子结点。）若2k+1=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。二叉树的遍历前序遍历：先访问根结点，后前序遍历左子树，再前序遍历右子树。（根-左-右）中序遍历：先序遍历左子树，后访问根结点，再中序遍历右子树。（左-根-右）后序遍历：先后序遍历左子树，后后序遍历右子树，再访问根结点。（左-右-根）查找技术顺序查找：从表头到表尾逐个比较，若相同则结束查找，否则一直继续比较下一个表中元素直到整个表都遍历完。适用场合：无序表
10、或链式存储的有序表。二分查找：每次把待查找值与表中间元素比较，以减半的方式缩小搜索范围。适用场合：顺序存储的有序表。排序技术交换类排序：冒泡排序法 快速排序法插入类排序：简单插入排序法 希尔排序法选择类排序：简单选择排序法 堆排序法全真考题：1如图所示，二叉树的前序遍历序列是：ABDEGHCF 中序遍历序列是：DBGEHACF 后序遍历序列是：DGHEBFCAACBFEDHG2一棵度数为4的树，它的4度结点有1个，3度结点有2个，2度结点有3个，1度结点4个，问它的叶子结点有多少个？ （11个）分析：在数的结点里，n度结点可以射出n条分支，叶子结点是0度结点，因此它射出的分支数为0。此题中知道
11、了1到4度结点的个数，就可以计算出树的总分支数=41+32+23+14=20。因此数的总结点数是21，减去其它度数的结点数就得到0度结点（叶子结点）的个数了。排序表算法类型排序算法最好时间复杂度最坏时间复杂度平均时间复杂度交换类排序法冒泡排序Nn (n-1)/2(n-1)n/4快速排序nlog2n(n-1)n/2O(nlog2n)插入类排序法简单插入排序Nn (n-1)/2(n-1)n/4希尔排序O(n1.5)O(n1.5)O(n1.5)选择类排序法选择排序(n-1)n/2(n-1)n/2n (n-1)/2堆排序nO(nlog2n)O(nlog2n)程序设计基础两个阶段：结构化程序设计和面向对
12、象的程序设计程序设计风格的重要性：会深刻影响软件的质量和可维护性下列因素将影响程序的设计风格：源程序的文档结构组织：符号的命名，程序注释，视觉组织数据说明的方法：数据说明的次序规范化，说明语句中变量安排有序化，使用注释来说明复杂数据结构，语句的结构语句的结构：在一行内只写一条语句，程序编写应优先考试清晰性，除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。首先要保证程序正确，然后才要求提高速度。避免使用临时变量而使程序的可读性下降。避免不必要的转移，尽可能使用库函数。避免采用复杂的条件语句。尽量减少使用“否定”条件的条件语句。数据结构要有利于程序的简化。要模块化，使模块的功能尽可能单一化
13、。利用信息隐蔽，确保每一个模块的独立性。从数据出发去构造程序，不要修补不好的程序，要重新编写。输入和输出：对所有的输入数据都要检验数据的合法性，检查输入项的各种重要组合的合理性。输入格式要简单，以使得输入的步聚和操作尽可能简单。输入数据时，应允许使用自由格式。应允许缺少值，输入一批数据时，最好使用输入结束标志。结构化程序设计结构化程序设计原则：自顶向下，逐步求精，模块化，限制使用goto语句。结构化程序的基本结构：顺序结构、选择结构、重复结构结构化程序设计优点：程序易于理解、使用和维护，提高了编程的效率，降低了软件开发成本结构化程序设计原则和方法的应用：使用程序设计语言中的顺序、选择、循环等有
14、限的控制结构表示控制逻辑。选用的控制结构只准许有一个入口和一个出口。程序语句组成容易识别的块，每块只有一个入口和一个出口。复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。语言所没有的控制结构，应该采用前后一致的方法来模拟。严格控制GOTO语句的使用。面向对象的程序设计面向对象方法的本质：主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。面向对象方法的优点：接近人类习惯的思维方法，稳定性好，可重用性好，易于开发大型软件产品，可维护性好。面向对象方法的基本概念对象：描述该对象属性的数据以及对这些数据施加的所
15、有操作封装在一起构成的统一体。对象的属性：对象所包含的信息。对象的方法（操作）：描述了对象执行的功能面向对象方法中的对象特点：标志唯一性，分类性，多态性，封装性，模块独立性好类和实例类是具有共同属性、共同方法的对象的集合，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。消息：对象间的相互合作的协助机制。消息的组成：由接受消息的对象名称、消息标识符、零个或多个参数组成。继承：是使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承中一个类只允许有一个父类，多继承中一个类允许有多个父类。多态性：同样的消息被不同的对象接受时可导致完全不同
16、的动作的现象。软件工程基础软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，已经可能有的文件、文档及数据。软件三要素：程序、数据和文档。软件特点：是一种逻辑实体，具有抽象性。没有明显的制作过程。在运行、使用期间不存在磨损、老化问题。开发、运行对计算机系统具有依赖性，这导致了软件的移植性。复杂性高，成本昂贵。开发涉及诸多的社会因素。软件分类：应用软件、系统软件、支撑软件软件危机的含义：泛指在计算机软件的开发和维护中所遇到的一系列严重问题。软件危机的表现：需求的增长得不到满足，开发的成本和进度无法控制，质量难以保证，不可维护或维护程序非常低，成本不断提高，开发生产率的提高跟不上硬件的发展
17、和应用需要的增长。软件危机产生的原因：客观方面是由于软件日益深入社会生活的种个层面，对软件需求的增长速度大大超过了技术进步所能带来的软件生产率的提高。而就每一项具体的工程任务来看，软件危机许多困难来源于软件工程所面临的任务和其他工程之间的差异以及软件和其他工业产品的不同。软件工程的定义：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程三要素：方法、工具和过程。软件工程的核心思想：把软件当作一个工程产品来处理。软件工程过程定义：把输入转化为输出的一组相关的资源和活动。软件工程内涵：是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件过程活动。从软件
18、开发的观点来看，它就是使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。软件工程过程包含的基本活动：软件规格说明、软件开发、软件确认和软件演进。软件生命周期的定义：软件产品从提出、实现、使用维护到停止使用退役的全过程。三个阶段：软件定义、软件开发及软件维护。主要活动阶段：可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行和维护。软件工程的目标：在给定成本、进度的前提下，开发出具有时效性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件开发技术：包括软件开发方法学、开发过程、开发工具
19、、软件工程环境等内容。软件工程管理：包括软件管理学，软件工程经济学，软件心理学等内容。软件工程的原则：包括抽象、信息隐藏、模块化、局部化、确定性、一致性、完备性和可验证性。软件开发工具：是从单项工具的开发逐步向集成工具发展的，软件工具为软件工程的方法提供了自动的或半自动的软件支撑环境。软件开发环境：是全面支持软件开发过程的软件工具集合。计算机辅助软件工程（CASE）是当前软件开发环境中富有特色研究工作和发展方向。结构化分析方法需求分析的定义：软件需求分析是发现需求、求精、建模和定义需求的过程。需求分析阶段的工作是需求获取、需求分析、编写需求规格说明书和需求评审。需求分析方法：结构化分析方法和面
20、向对象分析方法两种。结构化分析工具有：数据流图（DFD）、数据字典（DD）、判定树和判定表。其中最重要的工具是数据流图。数据流图中的主要图形元素有加工、数据流、存储文件以及源和潭。建立数据流图的步骤：由外向里、自顶向下、逐层分解。数据流图的构造要遵循一些规则：对加工处理建立唯一、层次性的编号，且每个加工处理通常要求既有输入又有输出的。数据存储之间不应该有数据流。数据流图的一致性。父图、子图关系与平衡规则，子图个数不大于父图中的处理个数。所有子图的输入、输出和父图中相应的输入、输出数据流必须一致。软件需求规格说明书作用：便于用户、开发人员进行理解和交流。反映出用户问题的结构，可以作为软件开发工作
21、的基础和依据。作为确认测试和验收的依据。软件需求规格说明书的特点：具有正确性、无歧异性、完整性、可验证性、一致性、可理解性、可修改性和可追踪性等特点。软件设计的重要性和地位：软件开发阶段占软件项目开发总成本绝大部分，是在软件开发种形成质量的关键环节。软件设计是开发阶段最重要的步骤，是将需求准确的转化化为完整的软件产品或系统唯一途径。软件设计作出的决策，最终影响软件实现的成败。设计是软件工程和软件维护的基础。软件设计的内容：从技术观点看，包括结构设计、数据设计、接口设计和过程设计。从工程管理角度看，包括概要设计、详细设计。软件设计的基本原理：抽象、模块化、信息隐蔽和模块独立性。其中度量模块独立性
22、的两个定性的标准是模块内部的内聚性和模块间的耦合性。模块的内聚性：是指一个模块内部各个元素之间彼此结合的紧密程度的度量。内聚的种类（按照它们之间的内聚性由弱到强的排列）：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、 顺序内聚、功能内聚模块的耦合性：模块间互相连接的紧密程度的度量。耦合的种类（由强到弱）：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合结构化设计方法的基本思想：将软件设计成由相对独立、单一功能的模块组成的结构。为了提高模块的独立性，应该尽量提高模块的内聚性，降低模块间的耦合性。概要设计阶段的任务：将软件需求转化为软件体系结构、确定系统及接口、全局数据结
23、构或数据库模式。 主要步骤：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审软件结构设计工具：结构图（SC），经常使用的结构图有四种模块类型，传入模块类型、传出模块类型、变换模块类型和协调模块类型数据流类型：变换型和事务型详细设计的任务：为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。过程设计的任务：对每个模块规定的功能以及算法的设计，给出适当的算法描述。过程设计的工具：过程设计的常用工具有程序流程图、N-S图、PAD图（问题分析图）和PDL（过程设计语言）软件测试的目的：是为了发现错误而执行程序的过程。软件测试的准
24、则：所有测试都应追溯到需求，严格执行测试计划，排除测试的随意性。充分注意测试中的群集现象，程序员应避免检查自己的程序。穷举测试不可能，妥善保存测试计划、测试用例、出错统计和最终分析报告。软件测试分类：根据是否要执行被测试软件的角度分为，静态测试和动态测试。静态测试：包括代码检查、静态结构分析、代码质量度量。动态测试：是基于计算机的测试、是为了发现错误而执行程序的过程。根据功能分为：白盒测试和黑盒测试白盒测试：根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规范要求。白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所
25、没模块每一循环都在边界条件合一般条件下至少各执行一次；验证所有内部数据结构的有效性。白盒测试的主要要方法：逻辑覆盖测试方法，基本路径测试黑盒测试：是对软件已经实现的功能是否满足需求进行测试和验证黑盒测试的方法：等价类划分法，边界值分析法、错误推测法软件测试的实施：单元测试、集成测试、确认测试、系统测试程序的调试程序调试的基本步骤：错误定位、修改设计和代码、进行回归测试，防止引进新的错误程序调试的原则：分析思考与错误征兆相关的信息，避开死胡同、只把调试工具当作辅助手段来用、避免用试探法，最多只能把它当作最后手段。修改错误时应遵循的原则：在出现错误的地方，还可能有别的错误。不应只修改了错误的征兆或
26、表现而没有修改错误本身。注意修正一个错误的同时有可能会引入新的错误。修改错误的过程将迫使人们暂时回到程序设计阶段。修改源代码程序，不要改变目标代码。软件调试方法：强行排错法、回溯法和原因排除法。其中原因排除法是通过演绎和归纳以及二分法来实现的。数据库设计基础数据：描述事物的符号记录。数据库：数据库是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可以被各个应用程序所共享。数据库管理系统：数据库管理系统是数据库的机构，它是一种系统软件，负责数据中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统具有功能：数据模式定义。数据存取的物理构建。数据
27、操纵。数据的完整性、安全性定义与检查。数据库的并发控制与故障恢复。数据的服务。数据管理系统提供数据定义语言（DDL）、数据操纵语言（DML）和数据控制语言（DCL）三种数据语言以及交互式命令语言和宿主型语言两种数据语言形式。数据库管理员：主要工作是数据库设计，数据库维护和改善系统性能，提高系统效率。数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、系统平台之一（硬件平台）和系统平台之二（软件平台）组成。数据库应用系统：是数据库系统再加上应用软件及应用界面这三者组成。数据系统的发展经历的阶段：文件系统阶段、层次数据库与网状数据库系统阶段、关系数据系统阶段数据库系统的基本
28、特点：数据的集成性、数据的高共享性与低冗余性、数据独立性、数据统一管理与控制数据库系统的三级模式：概念模式、外模式和内模式数据库的两级映射：概念模式到内模式的映射、外模式到概念模式的映射数据模型所描述的内容：数据结构、数据操作、数据约束E-R模型的基本概念：实体、属性、联系实体：两个实体集之间的联系实际上是实体集之间函数关系，这种函数关系包括，一对一、一对多、和多对多联系。E-R模型的图示法：矩形表示实体集、椭圆表示属性、菱形表示联系，无向线段表示实体集（联系）与属性、实体集与联系间的联接关系。数据发展过程中产生过三种基本的数据模型：层次模型、网状模型和关系模型。层次模型的基本结构是树形结构、
29、网状模型的基本结构是一个不加任何限制条件的无向图。关系模型的基本结构是一张二维表。关系的数据结构：关系模型采用二维表来表示。二维表由表框架和表的元组组成。表框架由多个命名的表属性组成。每个属性有一个取值范围称为值域。二维表中的每一行数据称为元组。表示关系模型的二维表满足以下一些性质：元组个数有限性、元组个数唯一性、元组的次序无关性、元组分量的原子性、属性名唯一性、属性的次序无关性、分量值域的同一性。关系操纵：关系模型的数据操纵是建立在关系上的数据操纵、一般有数据查询、数据删除、数据插入和数据修改四种操作。关系中的数据约束：关系模型中提供实体完整性约束、参照完整性约束和用户完整性约束三种数据约束
30、。关系模型提供的基本操作有：关系的属性指定、关系的元组选择、两个关系的合并、一个或多个关系的查询、关系中元组的插入、关系中元组的删除关系模型的基本运算：插入、删除、修改和查询。新的运算：投影、选择和笛卡儿积。关系代数中的扩充运算：交运算、除运算以及连接与自然连接。数据库设计的基本任务：根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式。数据库设计有两种方法：一种是以信息需求为主，兼顾处理需求的面向数据的方法。另一种是以处理需求为主，兼顾信息需求的面向过程的方法。数据库设计的需求分析：信息要求、处理要求、安全性和完事性的要求。数据库概念设计的方法：集中式模式设计法、视图集成设计法。数据库概念设计的过程：选择局部应用、视图设计、视图集成。数据库的逻辑设计：从E-R图向关系模式转换，逻辑模式规范化及调整、实现，关系视图设计数据库的建立：数据模式的建立和数据加载数据库安全性控制和完整性控制：目的是保证数据库数据的正确性、一致性、不被没有授权的用户访问和修改。
