全国计算机二级VB公共基础知识总结

二级公共基础学问总结（30分：10选择+5填空）

第一章数据结构及算法

一.算法

1.概念：是解题方案的精确而完整的描述。算法不等于程序，也不等于计算方法。

2.基本特征：

（1）确定性，算法中每一步骤都必需有明确定义，不允许有模棱两可的说明，

不允许有多义性；

（2）有穷性，算法必需能在有限的时间内做完，即能在执行有限个步骤后终止;

（3）可行性，算法原则上能够精确地执行；

（4）拥有足够的情报。

3.基本要素：一是对数据对象的运算和操作；二是算法的限制结构。

4.指令系统：一个计算机系统能执行的全部指令的集合。

5.基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

6.基本限制结构：依次结构、选择结构、循环结构.

7.基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

8.算法困难度（算法效率的度量）

（1）算法时间困难度：指执行算法所须要的计算工作量。即算法执行过程中所

须要的基本运算次数。通常，一个算法所用的时间包括编译时间和运行时间。

（2）算法空间困难度：指执行这个算法所须要的内存空间。包括算法程序所占

的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。

二.数据结构

1.数据的基本单位是数据元素

2.数据结构：指相互有关联的数据元素的集合。

3.数据的存储结构（也称数据物理结构）：数据的逻辑结构在计算机存储空间中的存

放形式

4.数据的存储结构有依次、链接、索引、散列。

5.数据结构类型（按各元素之间前后件关系的困难度划分）：

（1）线性结构的条件：①有且只有一个根结点；②每一个结点最多有一个前件,

也最多有一个后件。

（2）非线性结构：不满意线性结构条件的数据结构。

6.线性结构：

（1）线性表

①记录：由若干项数据元素组成的数据元素

②文件：由多个记录构成的线性表。

③线性表的依次存储结构基本特点：

a）线性表中全部元素所占的存储空间是连续的；

b）线性表中各数据元素在存储空间中是按逻辑依次依次存放的

@线性链表（线性表的链式存储结构）

数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结

点，简称结点。

结点由两部分组成：

a）用于存储数据元素值，称为数据域；

b）用于存放指针，称为指针域，用于指向前一个或后一个结点。

★在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存

储依次及数据元素之间的逻辑关系可以不一样，而数据元素之间的逻辑关系

是由指针域来确定的。

★链式存储方式即可用于表示线性结构，也可用于表示非线性结构。

★链式存储结构须要更多地存储空间

（2）栈

①限定在一端（即栈顶）进行插入及删除的线性表。

②栈顶位置用指针top表示。栈底位置用指针bottom表示。

③栈依据“先进后出"（FILO）或“后进先出"（LIFO）组织数据，栈具有

记忆作用。

@栈的存储方式有依次存储和链式存储。

⑤栈的基本运算：

a）入栈运算，在栈顶位置插入元素；

b）退栈运算，删除元素（取出栈顶元素并赋给一个指定的变量）；

c）读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变更。

⑥栈的元素个数二bollomTop+1

（3）队列

①指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

②用rear指针指向队尾，用front指针指向队头元素的前一个位置。

③队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。

④队列运算包括：

a）入队运算：从队尾插入一个元素；b）退队运算：从队头删除一个元素。

⑤队列的依次存储结构一般采纳队列循环的形式。

循环队列s=0表示队列空；s=l且front二rear表示队列满。

⑥循环队列的元素个数：

front<rear时，元索个数二rear-front；

front>rear时，元素个数二n（循环队列容量）-front+rear

7.非线性结构

⑴树

①每一个结点只有一个前件，称为父结点。

②没有前件的结点只有一个，称为树的根结点，简称树的根。

③每一个结点可以有多个后件，称为该结点的子结点。

④没有后件的结点称为叶子结点。

⑤一个结点所拥有的后件的个数称为该结点的度，全部结点中最大的度称为

树的度。

⑥树的最大层次称为树的深度。

（2）二叉树

①特点：

a）非空二叉树只有一个根结点；

b）每一个结点最多有两棵子树，且分别称为该结点的左子树及右子树。

②满二叉树是指除最终一层外，每一层上的全部结点有两个子结点，则k层

上有2k-1个结点深度为m的满二叉树有2mT个结点。

完全二叉树是指除最终一层外，每一层上的结点数均达到最大值，在最终

一层上只缺少右边的若干结点。

③基本性质：

a）在二叉树的第k层上，最多有2k-l（k2l）个结点；

b）深度为m的二叉树最多有2m-1个结点；

<：）度为0的结点（即叶子结点）二度为2的结点数+1；

d）一叉树总结点数二度为0的结点数十度为1的结点数十度为2的结点数

e）具有n个结点的二叉树，其深度至少为［log2n］+l,其中［log2n］表示取

log2n的整数部分

f）具有n个结点的完全二叉树的深度为［log2n］+l；

g）完全二叉树中度为1的节点只可能是o或1个

补充：增加度为1的结点不会影响二叉树的叶子结点数，每增加一个度为2

的结点便会增加一个叶子结点，没有度为2的结点时叶子结点数为E

④二叉树存储结构采纳链式存储结构，对于满二叉树及完全二叉树可以按层

序进行依次存储。

⑤二叉树的遍历：

a）前序遍历（DLR）,首先访问根结点，然后遍历左子树，最终遍为右子树;

b）中序遍历（LDR）,首先遍历左子树，然后访问根结点，最终遍历右子树;

c）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最终访问根

结点。

hi

以下遍历以该榜为例

前序遍历结果为abdehicfg；中序遍历结果为dbheiafcg；

后序遍历结果为dhiebfgca

例2：图1.13的二叉树。

(1)前序遍历

先访问整棵二叉树的根结点A,然后再先序遍历左子树口；在访问门时;也以先序遍

历原则，先访问T1的根结点B,然后再先序遍历门的左子树T11；在访问T11时，也

以先序遍历原则，先访问T11的根结点D,然后再先序遍历T11的左子树。由干此时

T11的左子树只有H结点，所以访问H结点，TU的左子树先序遍历结束，依据先序遍

历的原则，进行先序遍历口1的右子树。由于TH的右子树只有I结点，故访问此结

点后T11的右子树的先序遍历结束。先序遍历完T11子树后，返回T1子树，先序遍历

T1的右子树。先序遍历完U子树后，接着先序遍历根结点A的右子树T2。先序遍历

完T2后，该二叉树的全部结点都已经访问过，各结点被访问的依次为：ABDHIECFG

(2)中序遍历：

先中序遍历左子树，然后再访问根结点，最终再中序遍历右子树。对图1.12的二叉树

进行中序遍历，访问各个结点的依次为：HDIBEAFCG

(3)后序遍历：

先后序遍历左子树，然后再后序遍历右子树，最终再访问根结点。对图1.12的二叉树

进行后序遍历，访问各个结点的依次为：IlIDEBFGCAo

下面树的先序、中序、后续遍历的结果依次为—abdcef_、bdaecf_dbefca

小结：逻辑结构可分为线性表和非线性表。

线性表包括栈、队列，其存储方式为依次存储、链式存储均可。链式型有:

线性链表，带链的栈，带链的队列，循环链表等。

非线性表包括树（二叉树），其存储方式为链式存储。

8.查找技术

只能运用依次查找的两种状况：

（1）线性表为无序表，不管是依次存储还是链式存储；

（2）表采纳链式存储结构，即使是有序线性表。

★★二分法查找只适用于依次存储的有序表，对于长度为n的有序线性表，最坏

状况只需比较log2n次，而依次查找须要比较n次。

9.排序技术

排序是指将一个无序序列整理成按值非递减依次排列的有序序列。

类别排序方法最坏状况下的比较次数

冒泡排序n(n-l)/2

交换类

快速排序n(n-l)/2

简洁插入排序n(n-l)/2

插入类

希尔排序0(nl.5)

简洁选择排序n(n-l)/2

选择类

堆排序0(nlog2n)

★相比以上几种（除希尔排序法外），堆排序法的时间困难度最小。

其次章程序设计基础

一.程序设计设计方法和风格

1.“清楚第一、效率其次”已成为当今主导的程序设计风格。

2.形成良好的程序设计风格需留意：

（1）源程序文档化；（2）数据说明的

次序要规范化；

（3）语句的结构应当简洁干脆，不要为提高效率而困难化；（4）输入数据前

要有提示信息和输出信息符合规范。

3.注释：序言性注释和功能性注释。

二.结构化程序设计

1.基本原则：

（1）自顶向下；（2）逐步求精；（3）模块化；（4）限制运用goto语句。

2.基本结构：

（1）依次结构：一种简洁的程序设计，最基本、最常用的结构；

（2）选择结构：又称分支结构，包括简洁选拦和多分支选择结构，可依据条件,

推断应当

选择哪一条分支来执行相应的语句序列；

（3）循环结构：又称重复结构，可依据给定条件，推断是否须要重复执行某一相

同或类似的程序段。

3.基本工具：程序流程图，N-S图

4.特点：只有一个入口和出口

三.面对对象的程序设计（主要考虑的是提高软件的可重用性）

1.面对对象的程序设计的首次提出以60年头末挪威奥斯陆高校和挪威计算机中心

研制的SIMULA语言为标记。

2.面对对象方法的优点：

（1）及人类习惯的思维方法一样；（2）稳定性好；（3）可重用性好；（4）易于开

发大型软件产品；（5）可维护性好。

3.面对对象技术的基本特征：

（1）抽象性

（2）继承性

①继承具有传递性，一个类事实上继承了他上层的全部基类的特性。

②继承分单继承和多重继承。

单继承指一个类只允许有一个父类，即类等级为树形结构；多重继承指一个类

允许有多个父类。

*：类的继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。

（3）多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现

象

（4）封装性

4.对象是属性和方法的封装体，一个对象由对象名、属性和操作三部分组成，对

象是实体的抽象。

（1）基本特点：标识唯一性，分类性，多态性，封装性（实现信息屏蔽）和模

块独立性

（2）属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象

的操作来变更。

操作描述了对象执行的功能，是对象的动态属性，操作也称为方法或服务。

5.类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是

对应类的一个实例。

6.消息是一个实例及另一个实例之间传递的信息。对象间的通信靠消息传递。它

统一了数据流和限制流。

*:在面对对象方法中，一个对象恳求另一个对象为其服务的方式是通过发送消息。

第三章软件工程基础

一.软件工程基本概念

1.计算机软件是包括程序、数据及相关文档的完整集合。

2.软件按功能分为：

应用软件：教务管理系统

系统软件：操作系统

支撑软件（或工具软件）：编译软件，汇编软件

3.软件危机主要表现在成本、质量、生产率等问题。

4.软件工程的核心思想是把软件产品看作是一个工程产品来处理。

5.软件工程包括3个要素：方法、工具和过程。

6.软件生命周期：软件产品从提出、实现、运用维护到停止运用退役的过程。

分三个阶段：（1）定义阶段：可行性探讨及安排制定；需求分析

（2）开发阶段：软件设计（概要设计和具体设计）；软件实现；软件测

试

（3）维护阶段：运行和维护

二.需求分析

1.工作：需求获得，需求分析，编写需求规格说明书，需求评审。

2.从需求分析建立的模型的特性来分：静态分析和动态分析

3.软件需求规格说明书（SRS）是需求分析阶段的最终成果

特点：正确性；无歧义性；完整性；可验证性；一样性；可理解性；可追踪性

4.方法：（1）结构化需求分析方法；（2）面对对象的分析的方法

三.结构化分析方法

I.结构化分析方法（SA）：面对数据流进行需求分析的方法

2.结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理

流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。

3.结构化分析的常用工具：数据流图；数据字典；判定树；判定表。

（1）数据流图（DFD图）：描述数据处理过程的工具，是需求理解的逻辑模型的图

形表示，它干脆支持系统功能建模。

①加工（转换）一一圆框，输入数据经加工变换产生的输出。

②数据流一一箭头，沿箭头方向传递数据的通道，一般在旁边标注数据流名。

③存储文件（数据源）一一双横线，表示处理过程中存放各种数据的文件。

④源、潭一一方框，表示系统和环境的接口，属系统之外的实体。

加工数据流存储文件源、潭

*：数据字典是结构化分析的核心。

四.结构化设计方法

I.软件设计的基本原理是：（1）抽象；（2）模块化；（3）信息隐藏；（4）模

块独立性。

2.衡量软件模块独立性运用耦合性和内聚性两个定性的度量标准。

耦合性是模块见相互连接的紧密程度的度量。内聚性是一个模块内部各个元素间

彼此结合的紧密程度的度量。

*：在程序结构中各模块的内聚性越强，则耦合性越弱。

机优秀软件应高内聚，低耦合，有利于提高模块的独立性。

五.软件设计

1.概要设计的基本任务是:

（1）设计软件系统结构；（2）数据结构及数据库设计；（3）编写概要设计文档；

（4）概要设计文档评审。

在结构图（SC）中，模块用一个矩形表示，箭头表示模块间的调用关系，

可以用带注释的箭头表示模块调用过程中来回传递的信息。

还可用带实心圆的箭头表示传递的是限制信息，空心圆箭心表示传递的是数据。

O-----►•-----.

一般模块数据信息控带（m息

2.具体设计常见工具：

令图形工具：程序流程图（PFD）、N-S图（方据图）、问题分析图（PAD）和HIPO

图

◊表格工具：判定表

◊语言工具：PDL（为码）

*：程序流程图中：箭头为限制流、方框为加工步骤、菱形为逻辑条件。

六.软件测试

1.软件测试的目的：发觉错误而执行程序的过程。

2.软件测试方法：静态测试和动态测试。

（1）静态测试：代码检查、静态结构分析、代码质量度量。不实际运行软件，

主要通过人工进行。

（2）动态测试：足基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。

白盒测试：也称结构测试或逻辑测试。在程序内部进行，主要用于完成软件内部

操作的验证。白盒测试主要考虑内部的逻辑结构。主要方法有逻辑覆

盖、基本路径测试。

黑盒测试：也称功能测试或数据驱动测试。是在软件接口处进行，完胜利能验证。

黑盒测试完全不考虑程序内部的逻辑结构和内部特性，只依据程序的需

求和功能规格说明，检查程序的功能是否符合它的设计要求。用于软件

确认测试。主要方法有等价类划分法、边界值分析法、错误推想法、因

果图等。

3.软件测试过程一般按4个步骤进行：

（1）单元测试、集成测试、验收测试（确认测试）和系统测试。

（2）单元测试是对模块（程序单元）进行，静态动态均有，动态时以白盒为主辅

之以黑盒。

（3）集成测试是测试、组装软件。

（4）确认测试的任务是验证软件的功能和性能及其他特性是否满意了需求规格

说明中的各项需求以及软件配置是否完全正瑜，先用黑盒。

七.程序的调试

1.程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。

2.程序调试的基本步骤：

（1）错误定位；

（2）修改设计和代码，以解除错误；

（3）进行回来测试，防止引进新的错误。

3.软件调试可分为静态调试和动态调试。

静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，

而动态调试是协助静态调试。

主要调试方法有：（1）强行排错法；（2）回溯法；（3）归纳法；（4）演绎

法。

第四章数据库设计基础

一.数据库系统的基本概念

1.数据库管理系统的六大功能：

（1）数据模式定义：即为数据库构建其数据框架；

（2）数据存取的物理构建：为数据模式的物理存取及构建供应有效的存取方法及

手段；

（3）数据操纵：为用户运用数据库的数据供应便利，如查询、插入、修改、删除

等以及简洁的算术运算及统计；

（4）数据的完整性、平安性定义及检查；

（5）数据库的并发限制及故障复原；

（6）数据的服务：如拷贝、转存、重组、性能监测、分析等。

为完成以上功能，数据库管理系统供应以下的数据语言：

（1）数据定义语言（DDL）：负责数据的模式定义及数据的物理存取构建；

（2）数据操纵语言（DML）：负责数据的操纵，如查询及增、删、改等；

（3）数据限制语言（DCL）：负责数据完整性、平安性的定义及检查以及并发限制、

故障复原等。

数据语言按其运用方式具有两种结构形式：

交互式吩咐（又称自含型或自主型语言）；宿主型语言（一般可嵌入某些宿主语言

中）。

2.数据库管理员：对数据库进行规划、设计、维护、监视等的专业管理人员。

3.数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、

硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。数据库系统须

要操作系统的支持.

4.数据库应用系统：由数据库系统、应用软件及应用界面三者组成。

5.数据管理发展的三个阶段：人工管理阶段，文件系统阶段，数据库系统阶段。而

数据独立性最高的是数据库系统。

6.数据库系统的基本特点：数据的集成性、数据的高共享性及低冗余性、数据独

立性（物理独立性及逻辑独立性）、数据统一管理及限制。

6.数据库系统的三级模式：

（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图;

（2）外模式：也称子模式及用户模式。是用户的数据视图，也就是用户所见到的

数据模式；

（3）内模式：又称物理模式，它给出了数据库物理存储结构及物理存取方法。

7.数据库系统的两级映射：

（1）概念模式到内模式的映射；

（2）外模式到概念模式的映射。

二数据模型

1.（1）E-R模型（实体联系模型）的基本概念

①实体：现实世界中的事物；

②属性：事物的特性；

③联系：现实世界中事物间的关系。实体集间的联系有一对一、一对多、多对

多的联系。

E-R模型基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性

域，每个实体可取属性域内的值。一个实体的全部属性值叫元组。

（2）E-R模型的图示法：描述概念模型的常用工具。

实体集表示法一一矩形；属性表法一一椭圆形；联系表示法一一菱形。

2.数据库管理系统常见的数据模型有层次模型、网状模型和关系模型.三种。

▲层次模型的基本结构是树形结构，具有以下特点：

（1）每棵树有且仅有一个无双亲结点，称为根；

（2）树中除根外全部结点有且仅有一个双亲。

▲从图论观点看，网状模型是一个不加任何条件限制的无向图。

▲关系模型是数学化的模型。要用到集合论、离散数学等理论学问。

关系模型采纳二维表来表示，简称表，由表框架及表的元组组成。一个二维表就

是一个关系。

每行数据称为元组.在二维表中凡能唯一标识元组的最小属性称为键或码°从全

部侯选键中选取一个作为用户运用的键称主键,表A中的某属性是某表B的键，

则称该属性集为A的外键或外码。

二维表的表框架由n个命名的属性组成，n称为属性元数。每个属性有一个取值

范围称为值域。表框架对应了关系的模式，即类型的概念。在表框架中按行可以

存放数据，每行数据称为元组，事实上，一个元组是由n个元组重量所组成，每

个元组重量是表框架中每个属性的投影值。

学号姓名性别诞生年月班级籍贯

2007102张洁然男07-07-8807动画1班天津

2007203李一明男05-01-8707播音5班广西南宁

2007305王丽女04-09-8807管理4班辽宁沈阳

2007406刘宏男10-11-8807新闻3班江苏南京

*:同一个关系模型的任两个元组值不能完全相同。

主码；或称为关键字、主键，简称码、键，表中的一个属性或几个属性的组合、其

值能唯一地标识表中一个元组的，称为关系的主码或关键字。例如，学生的学号。

主码属性不能取空值。

外部关键字：或称为外铤，在一个关系中含有及另一个关系的关键字相对应的属性

组称为该关系的外部关键字。外部关键字取空值或为外部表中对应的关键字值。例

如，在学生表中含有的所属班级名字，是班级表中的关键字属性，它是学生表中的

外部关键字。

关系中的数据约束：

(1)实体完整性约束：约束关系的主键中属性值不能为空值；

(2)参照完全性约束：是关系之间的基本约束；

(3)用户定义的完整性约束：它反映了具体应用中数据的语义要求。

3o关系代数

(1).关系数据库系统的特点之一是它建立在数据理论的基础之上，有许多数据理论

可以表示关系模型的数据操作，其中最为闻名的是关系代数及关系演算。

(2)关系数据库管理系统能实现的特地关系运算包括：选择、投影、连接。

(3)关系模型的基本运算：

①插入②删除③修改④查询(包括投影、选择、笛卡尔积运算)

还有扩充运算交、除、连接及自然连接运算。在关系运算中，连接运算后得到的

新表的属性是运算前表中属性相加。即多于原来关系中属性的个数。

（4）集合运算及选择、投影、连接运算

①并（U）：关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的

元组构成的集合。

②差（一）：关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S

的元组构成的集合。

③交（G）：关系R和S具有相同的关系模式，R和S的交是由属于R且属于S的

元组构成的集合。

④广义笛卡尔积（X）：设关系R和S的属性个数分别为n、m,则R和S的广义

笛卡尔

积是一个有（n+m）列的元组的集合。每个元组的前n列来自R的一个元组，后m

列来自S的一个元组，记为RXS。

*:依据笛卡尔积的定义：有n元关系R及m元关系S,它们分别有p、q个元组，

则关系R及S经笛卡尔积记为RXS,该关系是一个n+m元关系，元组个数是pXq,

由R及S的有序组组合而成”

例：有两个关系R和S,分别进行并、差、交和广义笛卡尔积运算。

（5）在关系型数据库管理系统中，基本的关系运算有选择、投影及联接三种操作：

1）选择：选择指的是从二维关系表的全部记录中，把那些符合指定条件的记录挑

出来。（产生新行）

2）投影：投影是从全部字段中选取一部分字段及其值进行操作，它是一种纵向操

作。（产生新列）

3）联接：联接将两个关系模式基于共有属性拼接成一个更宽的关系模式，生成的

新关系中包含满意联接条件的元组。

4.数据库