全国计算机等级考试三级数据库考点分析之数据结构算法2

文章作者 100test 发表时间 2007:05:13 21:48:36
来源 100Test.Com百考试题网

计算机等级考试训练软件《百宝箱》

　　　考点5链表

链表分为线性链表和非线性链表二线性链表是线性表的链式存储表示，非线性链表是非线性数据结构树和图的链式存储表示。

1.线性链表

线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。

(1) 在指针一P后插人指针9的关键运算步骤：

q ↑. link：＝P↑．link：

p ↑. link：＝q；

(2)删除指针P后继节点q的关键运算步骤：

q：＝p↑ . link；

p↑. link：＝q↑．link；

(3)在第一个节点(或称头节点)前插人一个指针P的关键运算步骤：

p↑. link：＝head；

head：二P；

(4)删除表中头节点的关键运算步骤：

head：＝head↑ . link：

2.双链表

在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。

(l)若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，步骤如下：

p↑ . llink↑. rlink：＝p↑. rlink；

P↑T．rlink↑. llink：＝P↑．llink；

(2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下：

q ↑. Mink：＝P：

q↑．rlink：＝P↑．rlink.

P↑．rlink r. Rink：＝q；

p↑．rlink：＝q.

3.可利用空间表

可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。

考点6栈

栈又称为堆栈，它是一种运算受限的特殊的线性表，仅允许在表的一端进行插人和删除运算，可进行运算的一端为栈顶( top)，另一端为栈底( bottom)。表中无任何元素的栈称为空栈。由于栈的插人和删除运算仅在栈顶进行，后进栈的元素必定先被删除，所以又把栈称为“后进先出”(LIFO)表。

栈的基本操作有：

(1) push(S,X)。往栈S中插人(或称推人)一个新的栈顶元素x，即进栈。

(2)pop(S)。从栈S中删除(或称弹出)栈顶元素，即出栈。

(3)lop(S，X)：把栈S的栈顶元素读到变量x中，栈保持不变。

(4)empty(S)。判断栈S是否为空栈，是则返回值为真。

(5)makempty。(S)将栈S设置为空。

栈既然是一种线性表，所以线性表的存储结构同样也适用于栈。栈通常用顺序存储方式来存储，分配一块连续的存储区域存放栈中元素，用一个变量来指向当前栈顶。

考点7队列

队列简称为队，它也是一种运算受限的线性表，队列的限定是仅允许在表的一端进行插入，而在另一端进行删除。进行删除操作的一端称做队列的头，进行插人操作的一端称为队列的尾.

队列的基本操作有：

(1) enq(Q, X)。往队列口中插人一个新的队尾元素x，即人队。

(2)deq(口)从队列Q中删除队头元素，即出队。

(3 ) front口,x)将队列口的队头元素值读到变量x中，队列保持不变。

(4)empty ( Q )．判断队歹，l口是否为空，是则返回值为真。

(5)makempty(口)将队列口置为空队列。

和线性表一样、队列的存储方式也有顺序存储和链式存储两种。顺序队列在进行人队操作时，会产生假溢出现象解决的办法是让队列首尾相连，构成一个循环队列。

考点8串

串(或字符串)是由零个或多个字符组成的有限序列。零个字符的串是空串。串中字符的个数就是串的长度串中的字符可以是字母、数字或其他字符。

串的存储同样也有顺序存储和链式存储两种。顺序存储时，既可以采用非紧缩方式，也可以采用紧缩方式。

串的基本运算有连接、赋值、求长度、全等比较、求子串、找子串位置及替换等，其中找子串位置(或称模式匹配)比较重要。

2.3多维数组、稀疏矩阵和广义表

考点9多维数组的顺序存储

多维数组是一维数组的推广。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组就需要按一定次序把所有的元素排在一个线性序列里。常用的排列次序有行优先顺序和列优先顺序两种。

　　考点10稀疏矩阵的存储

稀疏矩阵是指矩阵中含有大量的0元素。对稀疏矩阵可进行压缩存储，即只存储其中的非0元素。若非0元素分布是有规律的，可用顺序方法存储非0元素。对于一般的稀疏矩阵，常见的存储方法还有不元组法和十字链表法，这里就不再介绍了。

　　考点11广义表的定义和存储

广义表(又称列表)是线性表的另一种推广，是由零个或多个单元素或子表所组成的有限序列。它与线性表的区别在于：线性表中的元素都是结构上不可分的单元素，而广义表中的元素既可以是单元素，又可以是有结构的表广义表与线性表相比，具有如下3个方面的特征。

(1)广义表的元素可以是子表，而子表的元素还可以是子表。

(2)广义表可被其他广义表引用二

(3)广义表可以是递归的表，即广义表也可以是自身的一个子表。

　　2.4树型结构

树型结构是节点之间有分支的、层次关系的结构，它类似于自然界中的树，是一类重要的非线性结构常用的树型结构有树和二叉树。

考点12树的定义

树是树型结构的一个重要类型。一棵树或者是没有任何节点的空树，或者是由一个或多个节点组成的有限集合T，其中：

(1)有且仅有一个称为该树根的节点。

(2)除根节点外的其余节点可分为。M(m≥0)个互不相交的有限集71,，兀，…，T ，其中每一个集合本身又是一棵树，并且称为根的子树。

这是一个递归的定义，即在树的定义中又用到了树的概念。这恰好显示了树的固有特性。

考点13二叉树定义

1.二叉树的定义

二叉树是一种最简单而巨重要的树型结构它或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。有两种特殊形态的二＿叉树，它们是满二叉树一和完全二叉树。

2.二叉树与树的区别

尽管树和二叉树的概念之间有许多关系，但它们是两个概念二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和了。子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。