计算机二级公共基础知识重点.doc

计算机二级公共基础知识重点
计算机二级公共基础知识重点
计算机二级公共基础知识

一、数据结构及算法

1.1.1 数据结构的基本概念

数据结构指相互有关联的数据元素的集合。数据逻辑结构反映数据元素之间的逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，分为顺序存储、链式存储、索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为如下两种:

(1)线性结构：有且只有一个根节点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构。

(2)非线性结构：不满足线性结构的数据结构。

1.1.2 算法

1. 算法的基本概念

（1）概念：算法是指解题方案的准确而完善的描述。

（2）基本特征：可行性、确定性、有穷性、拥有足够的情报。

（3）基本要素：对数据对象的运算和操作、算法和控制结构。

（4）设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术、回溯法。

2. 算法的复杂度

（1）算法的时间复杂度：执行算法所需要的计算工作量。

（2）算法的空间复杂度：执行算法所需的内存空间。

1.1.3 线性表及其顺序存储结构

1. 线性表的基本概念

线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。
2. 线性表的顺序存储结构

顺序存储结构的特点如下：

（1）元素所占的存储空间必须连接。

（2）元素在存储空间的位置是按逻辑顺序依次存放的。

3. 线性表的插入运算

若在第i 个元素之前插入一个新元素，可先把原来第i 个结点至第n 个结点依次往后移一个元素位置。然后把新结点放在第i 个位置上，最后修正线性表的结点个数。

4. 线性表的删去运算

若要删去第i 个位置的元素，可先把第i 个之后不包括第i 个元素的 个元素依次前移一个位置，然后修正线性表的结点数。

1.1.4 栈和列队

1. 栈及其基本运算

栈是一种特殊的线性表，其插入运算及删除运算都只在线性表的一端进行，又称为先进后出表或后进先出表。

栈顶是允许插入及删除的一端，而栈底是栈顶的另一端。

所谓空栈就是栈中没有元素的栈。栈的特点如下：

（1）栈顶元素师最后被插入和最早被删除的元素。

（2）栈底元素师最早被插入和最后被删除的元素。

（3）栈有记忆的作用。

（4）在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。

（5）栈顶指针 动态反映了栈中元素的变化情况。

顺序存储和运算包括人栈运算、退栈运算和读栈顶运算。

2. 列队及其基本运算

队列是指允许在一端进行插入，在另一端进行删除的线性表、又称“先进先出”的线性表。 队尾就是允许插入的一端，一般用尾指针指向队尾元素。

排头就是允许删除的一端，一般用头指针指向头元素的前一位置。

循环列队及其运算包括入队运算及退队运算。
1.1.5 树及二叉树

1. 树的基本概念

树是一种简单的非线性结构，树中有且仅有一个没有前驱的结点为“根”，其余结点互不相交的有限点分成m 个互不相交的有限集合T1，T2„„ ，每个集合又是一棵树，称为T1，T2„„ 为跟结点的子树。

（1）父结点：每一个结点只有一个前件，无前件的结点只有一个，称为树的根结点

（2）子结点：每一个结点可以有多个后件，无后件的结点称为叶子结点。

（3）树的度：所以结点最大的度

（4）树的深度：树的最大层次。

2. 二叉树及其基本性质

二叉树是一种非线性结构，是有限的结点的集合，改集合为空或由一个根结点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

二叉树具有如下特点：

（1）二叉树可为空，空的二叉树无结点，非空二叉树有且只有一个根结点；

（2）每个结点最多可有两棵子树，分别称为左子树和右子树。

3. 二叉树的存储结构

二叉树通常采用链式存储结构，存储结点由数据域和指针域组成。对满二叉树和完全二叉树可按层次进行顺序存储。

4. 二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中所以结点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历分为前序遍历、中序遍历和后序遍历。

1.1.6 查找技术

（1）顺序查找：在线性表中查找指定的元素。

（2）二分查找：这种查找只适用于顺序存储结构的线性表，且必是有序表，应有二分查找时，会反复查找知道成功或子表长度为0时结束。

1.1.7 排序技术

（1）交换类排序法：借助数据元素之间的互相交换进行排序，如冒泡排序法和快速排序法。
（2）插入类排序法：将无序序列中的各元素依次插入到有序的线性表中，如简单插入排序法和希尔排序法。

（3）选择类排序法：从整个线性表中选出最小的元素，将其交换到表的最前面，然后查找余下元素中的最小的，交换至上一个最小元素的后面，以此类推，包括简单选择排序法和推排序法。

1.2 程序设计基础

1.2.1 程序设计方法及风格

（1）程序设计指设计、编制、调试程序的方法和过程，程序设计方法主要有结构化程序设计方法、软件过程方法和面向对象方法。

（2）良好的设计风格要注重源程序文档化、数据说明方法、语句的结构和输入输出等因素。

1.2.2 面向对象的程序设计

面向对象方法的本质是主张从客观世界固有的事物出发来构造系统，强调建立的系统能映射问题域。面向对象的方法中可能涉及的主要概念如下：

（1）对象：用来表示客观世界中任何实体，可以是任何有明确边界和意义的东西。

（2）类：具有共同属性、共同方法的对象的集合。

（3）消息：实例间传递的信息，它统一了数据流和控制流。

（4）继承：使用已有的类定义作为基础建立新类的定义技术。

（5）实例：一个具体对象就是其对应分类的一个实例。

（6）多态性：指对象根据所接受到底信息而做出动作，同样的信息被不同的对象接受时有不同行动的现象。

面向对象程序设计的优点：及人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。

1.3 软件工程基础

1.3.1 软件工程基本概念

1. 软件的定义及特点

软件是指及计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档和数据。

软件具有如下的特点：

（1）是逻辑实体，有抽象性；

（2）生产没有明显的制作过程。

（3）运行使用期间不存在磨损老化的问题。

（4）开发、运行对计算机系统有依赖性，故软件存在移植问题。

（5）复杂性较高，成本昂贵。

（6）开发涉及诸多社会因素。

2. 软件危机及软件工程

（1）软件危机：泛指在计算机软件的开发和维护中所遇到的一系列严重的问题。

（2）软件工程：应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

（3）软件工程包括开发技术和软件工程管理两部分。

（4）软件工程过程：把输入转换为输出的一组彼此相关的资源和活动。

（5）软件生命周期：软件产品从提出、实现、使用维护到停止使用的过程。

（6）软件工程的目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可试用性、可移植性、可追踪性和可互操作性且满足用户需求的产品。

（7）软件工程到底原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

（8）软件开发工具：从初期的单向工具向集成工具发展，软件开发的方法必须得到相应工具的支持。

（9）软件开发环境：全面支持开发过程的软件工具的集合。计算机辅助软件工程是当前研究工作和发展方向。

1.3.2 结构化分析方法

需求分析可概括为：需求获取、需求分析、编写需求规格说明书和需求评审。

常用的分析方法如下：

（1）结构化分析方法：实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，常用数据流图、数字字典、判断树和判断表等工具。

（2）面向对象分析方法。

1.3.3 结构化设计方法

1. 软件设计的基本概念和方法

软件设计就是把软件需求转换为软件表示的过程。

（1）基本原理：抽象、模块化、信息隐蔽、模块独立性。

（2）基本思想：将软件设计成有相对独立、单一功能的模块组成的结构。
2. 概要设计

（1）概要设计包括4个任务：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档审评。

（2）面向数据流的设计方法：数据流图的信息分为交换流和事物流，结构形式有交换型和事务型。

3. 详细设计的工具

（1）图形工具：程序流程图、 、 、 。

（2）表格工具：判定表。

（3）语言工具： （伪码）。

1.3.4 软件测试

软件测试的目的是为了发现错误，其相应的准则如下：

（1）所以测试应追溯到用户需求。

（2）严格执行测试计划，排除测试的随意性。

（3）充分注意测试中的群集现象。

（4）程序员应避免检查自己的程序。

（5）穷举测试不可能。

（6）妥善保存设计计划、测试用例、出错统计和最终分析报告。

软件测试的方法从是否需要执行被测试软件的角度，可分为静态测试和动态测试，按功能可分为白盒测试和黑盒测试。

（1）白盒测试：又称结构测试，是根据软件的内部逻辑设计和工作过程，检查软件内部成分。主要方法有逻辑覆盖测试、基本路径测试等。

（2）黑盒测试：又称功能测试，是根据规格说明书的功能来设计测试的，主要方法有等价划分、边界值分析法、错误推测法、因果图发等。

1.3.5 程序的调试

程序调试的主要任务是诊断和改正程序中的错误，应用的主要方法有强行排错法、回溯法和原因排除法。

1.4 数据库设计基础

1.4.1 数据库系统的基本概念

（1）数据：描述事物的符号记录，分为临时性数据和永久性数据。

（2）数据库：长期存储在计算机内的、有组织的、可共享的数据集合。
（3）数据库管理系统：负责数据库中：数据组织、数据操作、数据维护、控制及保护和数据服务的一种系统软件。

（4）数据库技术发展经历了人工管理阶段、文件系统阶段、数据库系统阶段等3个阶段。

（5）数据库系统具有集成性、高共享性、低冗余性、数据统一管理及控制等特点。

（6）三级模式（概念模式、内模式、外模式）和二级模式（外模式/概念模式的映射、概念模式/内模式的映射）构成了数据库系统内部的抽象结构体系。

1.4.2 数据模型

数据模型从抽象层次上描述了系统的静态特征、动态行为和约束条件，描述的内容包括数据机构、数据操作和数据约束。概念数据模型、逻辑数据模型和物理数据模型是数据模型的3个层次。

（1） 模型：提供了表示实体、属性和联系的方法。实体及实体之间联系有“一对一”、“一对多”和“多对多”。

（2）层次模型：利用树形结构表示实体及其之间的联系，其中结点是实体，树枝是联系，从上到下是一对多的关系。

（3）网状模型：用网状结构表示实体及其之间的联系，是层次模型的扩展。网状模型以记录型为结点，反映现实中较为复杂的事物联系。

（4）关系模型：采用二维表来表示，可进行数据查询、增加、删除及修改等操作。关系模型允许定义“实体完整性”、“参照完整性”和“用户定义的完整性”3种约束。

1. 键：二维表中唯一能标识元祖的最小属性集。

2. 候选键：二维表中可能有点所有的键。

3. 主键：从二维表所有键中被取出的一个作为用户使用的键。

1.4.3 关系代数

（1）传统的集合运算包括关系并运算、关系交运算、关系差运算和广义笛卡尔积、

（2）专门的关系运算包括选择、投影和连接。

1.4.4 数据库设计及管理

1. 数据库设计概述

数据库的设计一般以过程迭代和逐步求精为基本思想，是应用面向数据的方法和面向过程的方法进行的

数据库的设计步骤如下：需求分析—〉概念设计—〉逻辑设计—〉物理数据—〉编码—〉测试—〉运行—〉进一步修改

2. 数据库设计的需求分析

需求收集和分析师数据库设计的第一阶段。在这一阶段常用结构化分析方法和面向对象的方法，其主要工作有绘制数据流程图、数据分析、功能分析、确定功能处理模块和数据间关系。

数据字典包括数据项、数据结构、数据流、数据存储和处理过程，是对系统中数据的详尽描述。

3. 数据库的设计

（1）概念设计：任务是分析数据间内在的语义关联，以建立数据的抽象模型。

（2）逻辑设计：任务是从 图向关系模型转换，逻辑模式规范化，关系视图设计可以根据用户需求随时创建。

（3）物理设计：任务是设计是数据在物理设备上的存储结构及存钱方法，目的是对数据库内部物理结构作出调整并选择合理到底存取路径，以提高速度和存储空间。

4. 数据库管理

数据库管理包括建立、调整、重组、安全性及完整性控制、故障恢复和监控。
19 / 19