计算机二级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)：度不为零的结点称为分支结点。

树中某个结点的子树之根称为该结点 …… 此处隐藏：6093字，全部文档内容请下载后查看。喜欢就下载吧 ……