基础知识补充内容

循环队列

循环队列图

1、rear：队尾指针 front：队头指针

2、循环队列的初始状态为空front=rear=6（图a） 3、入队运算：插入一个新元素后：rear（队尾指针）=6+1=1（这表示在最后一个位置插入元素后，紧接着在第一个位置插入新元素，这是由循环队列特性决定的）（图b） 4、队列满时rear=front=6（图c）

5、退队运算：首先队头指针加1：front=6+1=1；然后删除指针指向的元素(图d)

6、判断队列满还是队列空要增加一个标志S：S=0表示队列空 S=1表示队列非空 队列空的条件：S=0

队列满的条件：S=1 且 front=rear

线性链表

一、线性链表示例

二、线性链表的逻辑状态

1、 Null：未知或不存在

2、 指向第一个数据元素的头指针(HEAD)=Null（或者为0）时，称为空表 三、线性链表的基本运算

1、查找指定元素：从队头指针出发，沿着指针域Next逐个结点搜索，直到找到指定元素或链表尾部为止。在链表中，如果有指定元素，则扫描到等于该元素值的结点时，停止扫描，返回该结点的位置，因此，如果链表中有多个等于指定元素值的结点，只返回第一个结点的位置。如果链表中没有

元素的值等于指定元素，则扫描完所有元素后，返回Null。 2、线性链表元素的插入：在线性链表中包含元素x的结点前插入一个新元素b

(1)从可利用的栈取得一个结点，设该结点号为p，并置结点p的数据域插入的元素值b（见图b）

(2)在线性链表中寻找包含元素x的前一个结点，并设该结点号为q（见图b）

(3)最后将结点p插入到结点q之后，两个结点（p、q）指针变化如下：

A）使结点p指向包含元素x的结点 B）使结点q的指针域内容改为指向结点p 结果见图c，插入完成。

3、 线性链表元素的删除：在线性链表中删除包含x的结点

（1） 在线性链表中寻找包含元素x的前一个结点，设结点

号为q

（2） 将结点q后的结点p从线性链表中删除，即让结点q

的指针指向包含x的结点p的指针指向的结点。经过上述两步后，线性链表如图b所示

（3） 将包含元素x的结点p送回可利用栈，经过这一步后，

要利用栈的状态如图c所示，此时线性链表的删除运算完成。

二叉树的遍历

二叉树的三种遍历方式：先序遍历、中序遍历、后序遍历 先序：

始终执行以下步骤，

1、访问根节点 2、遍历左子树 3、遍历右子树 中序：

始终执行以下步骤， 1、遍历左子树 2、访问根节点 3、遍历右子树 后序：

始终执行以下步骤， 1、遍历左子树 2、遍历右子树 3、访问根节点

“始终”：为什么要说“始终”执行呢？因为二叉树的每一个子树又可以看成是一个新的二叉树，遍历步骤、方式都保持一样，所以应该“始终”执行同样的操作，我们也应该始终把它看成一棵新的二叉树。 一些技巧：

1、先序遍历第一个元素一定是根节点

2、中序遍历中，任何一个元素的前一个元素一定在二叉树中它的左边，比如D在G前面，则D在G左边 3、后序遍历最后一个元素一定是根节点

4、先、中、后意思是说访问根节点的先后顺序，而且始终从左往右，从上往下

A B C

先序遍历为：ABC 中序遍历为：BAC 后序遍历为：BCA

A B C D E F G

先序遍历为：ABDECFG 中序遍历为：DBEAFCG 后序遍历为：AEBFGCA

a b e c d f 前序遍历：abcdef 中序遍历：cbdaef 后序遍历：cdbfea

A B D G E C F

先序遍历为：ABDGCEF 中序遍历为：DGBAECF 后序遍历为：GDBEFCA

前序遍历结果为 a b d e h i c f g 中序遍历结果为 d b h e i a f c g 后序遍历结果为 d h i e b f g c a

F C E A D G B H P

前序遍历结果为 FCADBEGHP 中序遍历结果为 ACBDFEHGP

后序遍历结果为 ABDCHPGEF

前序遍历为： — ＋ a

* b — c d 中序遍历为： a ＋ b * c — d — e / f 后序遍历为： a b c d — * ＋ e

前序遍历结果为 ABDHEICFG 中序遍历结果为 HDBEIACGF 后序遍历结果为 HDIEBGFCA

/ e f f / —

由先序序列ABCDEFGH和中序序列CBEDAGHF恢复二叉树： 方法：

先序序列ABCDEFGH（注：A是根） 中序序列CBEDAGHF

A 以A为根的左、右子树先序序列示意图

? 由左子树先序序列：BCDE和左子树中序序列：CBED构造A的左子树

? 同理，由右子树先序序列：FGH和右子树中序序列GHF构造A的右子树：

B C D E F G H

A B C D E

A F G H E H B C F D G

1. 已知某二叉树的其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，求后序遍历序列（4275631）。 2、已知二叉树前序12453，中序42513。求后序。答案(45231)

这样的题怎么解？我们首先得牢记三种递归规则： 1、前根遍历：根—左—右 2、中根遍历：左—根—右 2、后根遍历：左—右—根

从规则可以看出：前根序列的第一个值肯定是整个二叉树的根。后根序列的最后一个值肯定是整个二叉树的根。而知道中根序列和前、后根的一个序列后，必然中根序列将分以根分为两个部分：左子树和右子树。这样，在子树里面找到做子树根的那个值，继续分左右子树，这样下去即可确定二叉树的形态。同时，我们可以看到，如果只知道前、后根遍历。不知道中根，则二叉树形态无法唯一确定。

这样，我们来解答第一道题：前序为1243576中序为4215736.由前序可得1为二叉树的根。将中序分为左右两子树。左子树为42，右子树为5736。左子树前序序列中2在4的前面，中序2在4的后面，可知2为这个左子树的根，4为这个左子树的左节点。右子树中序5736，前序3576，可得3为右子树的根，以3为根的子树左边为57，右边为节点6。57这个子树5为根，7为右节点。这样我们就得到了这个二叉树的结构图形。后序遍历为4275631。

已知二叉树后序遍历序列是dabec，中序遍历序列debac，它的前序遍历的序列是:

由后序（左子树，右子树，根节点）dabec知道根节点为c,再通过中序（左子树，根节点，右子树）知道右子树为空 接着由dabe知道其根节点为e,所以在中序deba中左子树为d右子树为ba

再来，后序ab,中序ba,b为节点，a为右子树 前序遍历序列为cedba

c e d b a

（2）若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 A）bdgcefha B）gdbecfha C）bdgaechf D）gdbehfca 正确答案: D

查找

一、顺序查找

逐个元素找，如果有，则记录位置，然后跳出循环;否则，查找失败。 二、二分法查找

顺序查找效率低下，当数组有序排列时，可以使用二分法查找提高效率。 例要查找“21”

E-R模型

注：Student：学生 course：课程 S#：学号 Sn：姓名 Sa：年龄

关系代数

关系代数的运算可分为两类：

．传统的集合运算，如并、交、差、广义笛卡尔积。这类运算将关系看成元组的集合，其运算是以关系的行为单位来进行的。

．专门的关系运算，如选择、投影、连接、除。这类运算表达了实用系统中应用最普遍的查询操作。

上述两类运算的运算对象是关系，运算结果也是关系。 一、传统的集合运算

传统的集合运算包括四种运算：并（∪）、交（∩）、差（—）、广义笛卡尔积（X）。 1．并（Union）（行方向的运算）

设关系R和关系S具有相同的目n，且相应的属性取自同一个域。则关系R和关系S的并记为R∪S，其结果仍为n目关系，由属于R或属于S的元组组成。如R和S的元组分别用两个圆表示,则R∪S的集合如图4.1所示虚影部分元组。

图4．1 集合R∪S集合

【例4．1】设某公司有两个子公司，其营业库如表4．所示。

表4．1 某公司两个子公司营业库内容示意 营业库1

商品子公司代品名 数量 单价 代码 码 1 Comp1 钢笔 50 10．00 2 Comp1 圆珠200 6．00 笔 3 comp1 练习1000 3．00 本 4 comp1 笔记1000 8．00 本 营业库2

1

A A1 A2 B 101 201

C A1 A2 A3

D 81 82 83 E 85 70 90 表4．12 关系R与S的连接运算 A A1 A2

如算术比较符为“＝”，称为等值连接。

自然连接（Natural Join）是一种特殊而常用的连接。若R和S具有相同名的属性组，且连接条件为R和S中两关系所对应的同名属性列的值相等，则称为自然连接。 对于自然连接，无须标明条件表达式F，在结果中要把重复的属性去掉。如果表4．11中关系S的字段“C”名字改为“A”，关系R和S可作自然连接，写作R∞S，结果如表4．13所示。

B 101 201 C A1 A2 D 81 82 E 85 70 表4．13 关系R与S的自然连接运算

A A1 A2

在关系优化过程中分解为高一级范式后的两个关系如能通过自然连接得到原来的关系，称之为实现“无损连接”。 关系优化过程要求分解具有“无损连接性”，这是关系分解的准则之一。

4．除（Division）（列方向的运算）

给定关系R（x，y）与S（z）其中x，y，z为属性集（也可为单属性）,R中的y和S中的z是同名的属性（集）也可以有不同的属性名， 但必须出自相同的域集。在求解R÷S时，对R按x的值的分组，然后检查每一组，如某一组中的y包含S中全部的z，则取该组中的x的值作为关系P中的一个元组， 否则不取。R÷S的商等于关系P。

【例4．9】从表4．2关系“营业库”中求既销售钢笔，又销售圆珠笔的子公司代码。

B 101 201 D 81 82 E 85 70 从营业库中求在子公司代码和品名上的投影R，再设计关系S，如表4.14所示。

视子公司代码为X，品名为Y，对R按子公司代码的值分组，共分为两组：Comp1和Comp2，其中第一组的品名值包含了S中所有品名。故所求问题的解为R ÷S ，如表4.14所示。

字符串匹配函数

格式：Instr（[首字符位置，]字符串1，字符串2[，n]） 功能：该函数在“字符串1”中查找“字符串2”，如果找到了，则返回“字符串2”的第一个字符在“字符串1”中的位置。“字符串1”的第一个字符的位置为1。 例：a$=”Microsoft Visual Basic”

x=Instr(1,a$,”Visual”) ?x 结果：11

注：（1）首字符缺省就从第一个字符开始查找，有，就从指定的位置找；

（2）“n”可选，0：二进制比较 1：忽略大小写 2：基于数据库中包含的信息进行比较（仅用于Access），默认为0。

VB考试前三天复习方法

1、 将上学期上课所用教材（或课件）完完整整、认认真真

地看一遍；

2、 将《计算机强化训练教程》上的公共基础知识完整地看

一遍；

3、 将补充的120道公共基础知识题认真地理解或背一遍；

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库基础知识补充内容在线全文阅读。