计算机二级VB公共基础知识

一．数据结构与算法

数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。

包括文本类型的数据(如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。

数据元素(Data Element)：是数据的基本单位，有时也称为元素、结点、顶

点、记录，可以有若干个数据项（字段、域、属性）组成。

数据结构（Data Structure）：指的是数据之间的相互关系，即数据的组织

形式。其包括三个部分：

1、逻辑结构：数据元素之间的逻辑关系

2、存储结构：数据元素及其关系在计算机存储器内的表示。

3、数据的运算（算法）：即对数据施加的操作

数据的逻辑结构有两大类：

1、线性结构：

特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。

例：一维数组、链表、栈、队列、串

2、非线性结构：

特征是：一个结点可能有多个直接前趋和直接后继。

例：多维数组、广义表、树、图

数据的存储结构有以下基本存储方法：

1、顺序存储方法：

该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。

2、链接存储方法：

该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。

3、索引存储方法：

该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。

4、散列存储方法：

该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。例：除余法散列函数、相乘取整法散列函数

算法的基本特征：

1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。

2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。

3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。

时间复杂度：该算法执行的时间耗费，它是该算法所求解问题规模n的函数。 空间复杂度：该算法执行时所耗费的存储空间，它也是问题规模n的函数。

二、线性表：

线性表(Linear List)：是由n(n>=0)个数据元素(结点)a1,a2,a3,·,an组成的有

限序列。对于非空的线性表，有且仅有一个开始结点a1，它没有直接前趋；有且仅有一个终端结点an，它没有直接后继；其余的结点有且仅有一个直接前趋结点和一个直接后继结点。

线性表的存储结构：

1、顺序存储(Sequential List)：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。

2、链式存储(Linked List)：逻辑上相邻的结点，物理上也相邻，存储单元可以是连续的，也可以是不连续的，在存储每个结点值的同时，还存储指向其后继结点的地址，用这种方法存储的线性表称为链表。

常见的运算有：

表的初始化、求表的长度、取表中的第i个结点、查找结点、插入新的结点、删除结点。

顺序表和链表的比较：

1、基于空间的考虑：

A、顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。

B、顺序表占的存储空间必须是连续的，而链表占的存储空间可以是连续的，也可是不连续的

C、顺序表存储密度为1，而链表中的每个结点，除了数据域外，还要额外的设置指针域，存储密度小于1

2、基于时间的考虑：

A、在链表中的任何位置上进行插入和删除，只需要修改指针，而顺序表中平均将要移动近一半的结点。

B、顺序表是随机存取结构，它的存取时间为O(1)，而链表需从头结点顺着链扫描链表。

总之，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构；当线性表的长度变化较大，难以估计其存储规模时，以采用链表作为存储结构为好。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；对于频繁进行插入和删除的线性表，宜采用链表做存储结构。

例：关于线性表的描述中，错误的是（ ）

A、线性表是线性结构 B、线性表的顺序存储结构，必须占用一片连续的存储单元

C、线性表是单链表 D、线性表的链式存储结构，不必占用一片连续的存储单元

用数组表示线性表的优点是（ ）

A、便于插入和删除操作 B、便于随机存取

C、可以动态地分配存储空间 D、不需要占用一片连续的存储空间

栈(Stack)：是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、

删除的这一端为栈顶(Top)，另一端称为栈底(Bottom)。当表中没有元素时称为空栈。是一种后进先出的线性表，又称为LIFO表。

栈的基本运算有：

栈的初始化、判栈空、判栈满、进栈、出栈等

栈的存储：

顺序存储、链式存储

例：若进栈的输入序列是A、B、C、D、E，并且在它们进栈的过程中可以进行出栈操作，则不可能出现的出栈序列是（ ）

A、EDCBA B、DECBA C、DCEAB D、ABCDE

四、队列：

队列(Queue)：也是一种运算受限的线性表，它只允许在表的一端进行插入，

而在另一端进行删除。允许删除的一段称为队头(Front)，允许插入的一段称为队尾(Rear)。（类似于生活中的购物排队）。是一种先进先出的线性表，又称为FIFO表。

队列的基本运算：

队列的初始化、判队空、判队满、入队、出队

队列的存储实现：

顺序存储、链式存储

例：一个队列的入队序列是1，2，3，4，则队列的输出序列是 （ ）

A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1

串(String)：是零个或多个字符组成的有限序列。

串中所包含的字符个数称为该串的长度。

串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串

注：空串是任意串的子串，任意串是其自身的子串

串有串常量、串变量之分：

1、串常量在程序中只能被引用但不能改变其值，即只能读不能写。

2、串变量其值是可以改变的。

串的基本运算：

求串长、串复制、串联接、串比较、字符定位、

树(Tree)：是n(n>=0)个结点的有限集T，T(n=0)为空时称为空树，否则它

满足如下两个条件：

1、有且仅有一个特定的称为根(Root)的结点

2、其余的结点可分为m(m>=0)个互不相交的子集T1，T2，…….，Tm，其

中每个子集本身又是一棵树，并称其为根的子树(Subtree)。

在树的树形图表示中，结点通常是用圆圈表示的，结点的名字一般是写在圆

圈旁边，有时亦可写在圆圈内。

度(Degree)：一个结点拥有的子树数称为该结点的度。一棵树的度是指该树

中结点的最大度数。

叶子(Leaf)：度为零的结点称为叶子或终端结点

分支结点(Node)：度不为零的结点称为分支结点。

树中某个结点的子树之根称为该结点的孩子(Child)结点或子结点，相应的该

结点称为孩子结点的双亲(Parents)结点或父结点。

同一个双亲的孩子称为兄弟结点(Sibling)

结点的层数(Level)是从根起算,设根的层数为1,其余结点的层数等于其双亲

结点的层数加1.

树中结点的最大层数称为树的高度(Height)或深度(Depth).

森林(Forest)：是m(m>=0)棵互不相交的树的集合。删去一棵树的根，就

得到一个森林，反之，加上一个结点作树根，森林就变为一棵树。

二叉树(Binary Tree)：是n(n>=0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。

二叉树的五种基本形态：

例：具有3个结点的二叉树有几种形态。

满二叉树(Full Binary Tree)：一棵深度为k且有2k-1个结点的二叉树称为

满二叉树

完全二叉树(Complete Binary Tree)：若一棵二叉树至多只有最下面的两层

上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

二叉树的性质：

性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)

性质2：深度为k的二叉树至多有2k-1个结点(k>=1)

性质3：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为[错误！未找到引用源。]+1(取下整) 或 [错误！未找到引用源。](取上整)。

例：一棵二叉树的结点数为18个，求它的最小高度

已知度为2的结点数为15个，求叶子结点数 15

二叉树的遍历：

遍历(Traversal)：是指沿着某条搜索路线，依次对树中每个结点均做一次且

仅做一次访问。

前序遍历：（又称为先序遍历、先根

遍

历）

若二叉树为空，则执行空操作。否则：

1、访问根结点；

2、前序遍历左子树；

3、前序遍历右子树。

中序遍历：（又称为中根遍历）

若二叉树为空，则执行空操作。否则：

1、中序遍历左子树；

2、访问根结点；

3、中序遍历右子树。

后序遍历：（又称为后根遍历）

若二叉树为空，则执行空操作。否则：

1、后序遍历左子树；

2、后序遍历右子树；

3、访问根结点。

例：已知一棵二叉树的中序遍历序列是：FDGBACHE，其后序遍历序列是：FGDBHECA

求其前序遍历序列。 一棵二叉树的前序遍历序列为ABDGCFK，中序遍历序列为DGBAFCK，则结点的后序遍历序列是（ ）

A、ACFKDBG B、GDBFKCA C、KCFAGDB D、ABCDFKG

所谓排序，就是指整理文件中的记录，使之按关键字递增（或递减）次序排

列起来。

冒泡排序(Bubble Sorting)：

通过对待排序序列从后向前或从前向后(从下标较大的元素开始)，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元）。 直接选择排序(Selection Sorting)：

扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩

下的子表采用同样的方法，直到子表空为止。

直接插入排序(Insertion Sorting)：

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

快速排序(Quick Sorting)：任取待排序序列中的某个元素作为基准(一般取

第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。

各种内部排序方法的比较

例：对一个具有n个元素的序列进行冒泡排序，在最坏情况下，要进行交换的次数是（ ）

A、n(n+1)/2 B、n(n-1)/2 C、n*n/2 D、n(n+1)/2-1 对n个元素进行冒泡排序过程中，最好情况下的时间复杂性为（ ）

A、O(1) B、O(log2n) C、O(n2) D、O(n)

对n个元素进行快速排序的过程中，平均情况下的时间复杂性为（ ）

A、O(1) B、O(lgn) C、O(n2) D、O(nlgn) 八、查找(Searching)：

所谓查找是指给定一个值K，在含有n个结点的表中找出关键字等于给定值

K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的提示信息。

顺序查找(Sequential Search)的基本思想是：从表的一端开始，顺序扫描线

性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找即适用顺序存储结构，又适用链式存储结构。 查找成功的平均查找长度为：(n为结点数目)

(1+2+3+4+·+n) / n = (n+1)/2

二分查找(Binary Search)又称折半查找，它是一种效率较高的查找方法，二

分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。另外，二分查找只适用顺序存储结构，在链式存储结构上无法实现二分查找。

查找成功时的平均查找长度：(n为结点数目)

n 1lg(n 1) 1n

当n很大时，可用近似公式： lg(n+1)-1 表示

二．程序设计 2.1 程序设计方法与风格

程序设计是一门技术，需要相应理论、技术、方法和工具来支持。程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。 养成良好的程序设计的设计风格，主要考虑下述的因素：

1. 源程序文档化

源程序文档化应考虑如下几点：

（1）符号名的命名：符号名的命名有一定含义，便于理解

（2）程序注释：正确的注释帮助读者理解程序

（3）视觉组织：程序层次清晰

2. 数据说明的方法

数据说明应考虑如下几点：

（1）数据说明的次序规范化

（2）说明语句中变量安排有序化。

（3）使用注释来说明复杂数据结构

3. 语句的结构

程序应该简单易懂，语句构造应该简单直接。应该注意的是：

（1）在一行内只写一条语句

（2）程序编写应优选考虑清晰性

（3）除非对效率有特殊要求，程序编写要清晰第一、效率第二

（4）首先要保证程序正确，然后要求提高速度

（5）避免使用临时变量而使程序可读性下降

（6）避免不必要的转移

（7）尽可能使用库函数

（8）避免使用复杂的条件语句

（9）尽量减少使用“否定”条件的条件语句

（10）数据结构要有利于程序的简化

（11）要模块化，使模块功能尽可能单一化

（12）利用信息隐藏，确保每一个模块的独立性

（13）从数据出发去构造程序

（14）不要修补不好的程序，要重新编写

4. 输入和输出

无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应该考虑如下原则：

（1）对所有的输入数据都要检验数据的合理性

（2）检查输入项的各种重要组合的合理性

（3）输入格式要简单。

（4）输入数据时，应允许使用自由格式

（5）应允许缺省值

（6）输入一批数据时，最好使用输入结束标志

（7）在交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入要求，在数据输入过程中和输入结束时应在屏幕给出状态信息

（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输出语句的一致性。给所有输入加注释，并设计输出报表格式。

2.2 结构化程序设计

2.2.1 结构化程序设计的原则

结构化程序设计方法主要原则包括：

1. 自顶向下。设计程序时先考虑总体，后考虑细节

2. 逐步求精。对复杂问题，逐步细化。

3. 模块化。

4. 限制使用goto语句

2.2.2 结构化程序的基本结构与特点

结构化程序设计方法是程序设计的先进方法和。和采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序设计方法基本可用三种基本结构就可实现。

1. 顺序结构

顺序结构是顺序顺序执行结构，即是按照程序语句的自然顺序，一条一条语句地执行。

2. 选择结构

选择结构又称分支结构，它包括简单选择和多分支选择，这种结构可以根据给定条件，判断执行哪一个分支中的语句。

3. 重复结构

重复结构又称为循环结构。它根据给定的条件判断是否重复执行某一段相同的程序。

2.2.3 结构化程序设计原则和方法的应用

在结构化程序设计的具体实施中，要注意把握如下要素：

（1）使用程序设计语言中的顺序、选择、循环等控制结构表示程序的控制逻辑

（2）选用的控制结构只准许有一个入口和一个出口

（3）程序语句组成容易识别的程序专项，每块只有一个入口和一个出口

（4）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现

（5）语言中所没有的控制结构，应该采用前后一致的方法来模拟

（6）严格控制GOTO语句使用。

2.3 面向对象的程序设计

2.3.1 关于面向对象方法

面向对象（Object Oriented）方法已经发展成为主流的软件开发方法。面向对象方法的形成起源于实现语言，首先对设计语言的研究，随之形成面向对象分析和设计方法。

面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象以及对象之间的关系能够如实反映问题域中固有事物及其关系。

面向对象方法有如下优点：

1. 与人类习惯的思维方法一致

面向对象和技术以对象为核心，对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。如CD播放器、媒体播放器、软件窗口等等

2. 稳定性好

面向对象的软件系统的结构是根据问题领域的模型建立起来的，当对系统的功能需求变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的修改。