软件考试重点内容Word文件下载.docx
《软件考试重点内容Word文件下载.docx》由会员分享，可在线阅读，更多相关《软件考试重点内容Word文件下载.docx（24页珍藏版）》请在冰点文库上搜索。
在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系来描述。
1数据的逻辑结构
所谓结构实际上是指数据元素之间的前后件关系。
一个数据结构应该包含以下两方面的信息：
（1）表示数据元素的信息：
数据元素的集合D
（2）表示各数据元素之间的前后件关系：
D上的关系R
2 数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。
在数据的存储结构中，不仅要存放各数据元素的信息，还要存放各数据元素的前后件关系的信息。
一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构，采用不同的存储结构，其数据处理的效率不同。
在进行数据处理时，选择合适的存储结构是很重要的。
2.2线性表及其顺序存储结构
2.2.1线性表及其运算P21
1 什么是线性表
线性表是由n（n>
=0）个数据元素a1,a2,…an组成的一个有限序列，表中的每一个数据元素，除了第一个以外，有且只有一个前件，除了最后一个以外，有且只有一个后件。
即线性表或是一个空表，或可表示为：
（a1,a2,…ai…an）
其中ai（i=1,2,…n）是属于数据对象的元素，通常也称为线性表中的一个结点。
数据元素在线性表中的位置只取决于它自己的序号，即数据元素之间的相对位置是线性的。
非空线性表有如下一些结构特征：
（1）有且只有一个根结点a1,它无前件；
（2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其它所有结点都有且只有一个前件，也有且只有一个后件。
线性表的结点的个数n称为线性表的长度。
2 线性表的顺序存储结构
线性表的存储结构有以下特点：
（1）线性表中所有的元素所占的在存储空间是连续的；
（2）线性表中的各数据元素在存储空间中是按逻辑顺序依次存放的。
假设线性表中的第一个数据元素的存储地址为ADR（ai），每一个数据元素占k个字节，则线性表中的第i个元素ai在计算机存储空间中的存储地址为：
ADR（ai）=ADR（a1）+（i-1）k
在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储结构。
对线性表的运算主要有：
插入、删除、
3 线性表在顺序存储下的插入运算
插入一个新元素时，首先要将从最后一个元素开始，直到第i个元素之间共n-i+1个元素，依次向后移动一个位置，第i个位置被空出，新元素插入到第i项，线性表的长度加1。
算法2－1：
表V最大空间为m，现已有n个元素，在第i个元素之前插入新元素b.
C语言描述如下：
voidinsl（v,m,n,i,b）
Tv[],b;
intm,*n,i
{if（*n==m）
{printf（“overflow\n”）;
return;
}
if（i>
=*n）i=*n+1;
if（i<
1）i=1;
for（j=*n;
j>
=i;
j--）v[j]=v[j-1];
v[i-1]=b;
*n=*n+1;
return;
4.线性表在顺序存储结构下的删除操作
算法2－2 在长度为n的线性表中删除第i个元素
voiddel（v,m,n,i）
T*v;
intm,*n,i
{
intk;
if（n==0）
{
printf（“underlow!
\n”）;
if（（i<
1）||（i>
*n））
printf（“Notthiselementinthelist!
return;
for（k=i;
k<
*n;
k++）
v[k-1]=v[k];
*n=*n-1;
2.2.2 栈及其应用
1 什么是栈
栈（stack）是限定在一端进行插入和删除操作的线性表。
栈顶（top）、栈底（bottom）、入栈（push）、退栈（pop）、先进后出（filo）
2栈的顺序存储及其运算
与一般的线性表一样，在程序设计语言中，用一维数组S（1：
m）作为栈的顺序存储空间。
其中m为栈的最大存储容量
栈顶元素表示为S（top），栈底元素表示为S（bottom）
（1）入栈运算
算法2-3在容量为m的栈s中插入一个新元素
C语言描述：
voidpush（s,m,top,x）
ETs[],x;
intm,*top
{if（*top==m）{printf（“Stack–overflow\n”）;
*top=*top+1;
s[*top-1]=x;
}
（2）退栈运算
算法2-4在容量为m的栈S中删除栈顶元素
Tpop（T*s,inm,int*top）
Ty;
if（*top==0）{printf（“Stack-underflow\n”）;
y=s[*top-1];
*top=*top-1;
return（y）;
2.2.3队列及其应用
1什么是队列
需要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出。
队尾（rear）、排头（front）、入队运算、退队运算
front：
总是指向排头元素的前一个位置；
rear：
总是指向最后一个被插入的元素。
用一维数组作为队列的顺序存储空间。
（a）一个队列（b）删除一个元素（c）插入一个元素
图2-14队列示意图
2循环队列及其运算
就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。
从front到rear之间所有的元素均为队列中的元素。
对于空队列，rear=front=m
图2-15循环队列
每进行一次入队运算rear加1，当rear=m+1时，置rear=1;
每进行一次退队运算front加1，当front=m+1时，置front=1
如果rear>
front,循环队列中元素的个数为rear-front
如果rear<
front,循环队列中元素的个数为m+（rear-front）
2．3线性链表及其运算
2.3.1线性链表的基本概念P51
在链式存储方式中，每个结点由两部分组成：
一部分用于存放数据元素的值，称为数据域，另一部分用于存放指针，用于指向该结点的前一个或后一个结点（即前件或后件），称为指针域。
在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点，即存放线性表中第一个数据元素的存储结点的序号。
线性表中的最后一个元素没有后件，其指针域为空（NULL或0）。
如下图。
图2-20线性链表的逻辑结构
图2-20线性链表
2.3.2线性链表的插入与删除
线性表基本运算：
插入、删除
1线性链表的插入
可利用栈：
计算机将不用的存储空间收集起来，组成可利用栈。
用到存储空间时申请，用毕送回可利用栈。
（1）从可利用栈（其头结点为TOP）取得一个结点p；
（2）找到包含元素x的前一个结点q;
（3）p插入到q后面。
2线性链表的删除
i
2.3.3带链的栈与队列
将计算机存储空间中所有空闲的存储结点收集起来，组成带链的栈叫可利用栈。
图2-25可利用栈及其运算
1、带链的栈
入栈：
P62
退栈：
2、带链的队列P63
入队运算
退队运算:
2.3.4循环链表P67
图2-28循环链表的逻辑状态
循环链表的特点：
（1）增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。
循环链表的头指针指向表头结点。
（2）循环链表的最后一个结点的指针域不是空，而是指向表头结点。
2.5数组
2.5.3一般稀疏矩阵的表示
矩阵中只有少量的非0元素。
一般只存储非0元素。
1稀疏矩阵的三列二维数组表示
在压缩存储中，每一个非0元素包括以下三方面的信息：
（1）行号i;
（2）列号j;
（3）元素的值V
即每一个非0元素可以用一个三元组（i,j,v）来表示。
上述A中，其三元组为：
（1，3，3），（1，8，1），（3，1，9），（4，5，7），（5，7，6），（6，4，2），（6，6，3），（7，3，5）。
该三元组没有表示出稀疏矩阵的总行数和总列数。
为了表示的唯一性，在非0元素的三元组之前再加一个三元组（I,J,t）,其中，I、J表示稀疏矩阵的总行、总列数，t表示稀疏矩阵中非0元素的个数。
上述A中，三元组为：
（7，8，8），（1，3，3），（1，8，1），（3，1，9），（4，5，7），（5，7，6），（6，4，2），（6，6，3），（7，3，5）。
具有t个非0元素的稀疏矩阵可以用t+1个三元组来表示，可以将这些三元组组织成三列二维表格的形式，或表示成三列二维数组。
P89
当稀疏矩阵中非零元素个数较多时，通常会扫描到整个三列二维数组的所有行，为了访问方便，通常还附设两个长度与稀疏矩阵A的行数相同的向量POS和NUM。
其中POS（k）表示稀疏矩阵A中第k行的第一个非0元素在三列二维数组B中的行号，NUM（k）表示稀疏矩阵A中第k行中非0元素的个数。
即
POS
（1）=2
POS（k）=POS（k-1）+NUM（k-1）2<
=k<
=m
对于上述稀疏矩阵A，其POS（k）、NUM（k）如下表：
k
1
2
3
4
5
6
7
POS（k）
4
7
9
NUM（k）
0
2.6树与二叉树
2.6.1树的基本概念P111
树是一种简单的非线性结构，所有的数据元素之间具有明显的层次特性。
树结构中，一个结点所拥有的后件的个数称为该结点的度。
所有结点中的最大度称为树的度。
树的最大层次称为树的深度。
叶子结点没有子树。
2.6.2二叉树及其基本性质P114
1什么是二叉树
特点：
（1）非空二叉树只有一个根结点
（2）每一个结点最多有两棵子树----左子树、右子树
2二叉树的基本性质
性质1：
在二叉树的第k层上，最多有2k-1（k>
=1）个结点；
每一层所拥有的结点数为：
1，2，4，8，...，2k-1
性质2：
深度为m的二叉树最多有2m-1个结点；
1+2+4+...+2m-1=2m-1
性质3：
任意一棵二叉树中，度为0的结点总比度为2的结点多1个；
性质4：
具有n个结点的二叉树，其深度至少为log2n+1.
由性质2获得。
3满二叉树与完全二叉树
（1）满二叉树
除最后一层外，每一层上的所有结点都有两个子结点。
（2）完全二叉树
除最后一层外，每一层上的结点数均达到最大值，在最后一层上，只缺少右边的若干个结点。
完全二叉树具有以下性质：
具有n个结点的完全二叉树深度为log2n+1
设完全二叉树具有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1,2,…n给结点进行编号，则对于编号为k（k=1,2,..n）的结点有以下结论：
（以P117图2-49.b为例进行说明）
（1）若k=1，则该结点为根结点，它没有父结点；
若k>
1，则该结点的父结点的编号为INT（k/2）。
（2）若2k<
=n，则编号为k的结点的左子结点编号为2k,否则该结点无左子结点。
（3）若2k+1<
=n，则编号为k的结点的右子结点的编号为2k+1,否则该结点无右子结点。
根据完全二叉树以上性质，如果按从上到下、从左到右顺序存储完全二叉树各结点，则很容易确定每一个结点的父结点、左子结点、右子结点的位置。
2.6.3二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
1前序遍历
首先访问根结点，然后遍历左子树，最后遍历右子树，并且在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
2中序遍历
首先遍历左子树，然后访问根结点，最后遍历右子树，并且在遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
3后序遍历
首先遍历左子树，然后遍历右子树，最后访问根结点，，并且在遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
2.6.4二叉树的存储结构
1二叉链表
指针域有两个：
一个用于指向该结点的左子结点的存储地址----左指针，另一个指向该结点的右子结点的存储地址----右指针。
头指针BT用于指向二叉树根结点。
2.6.6表达式的线性化
1有序树的二叉树表示
在一般的树结构中，每一个结点的度是任意的，即树中每一个结点可以有任意个子结点，如果对某个结点的所有子结点按从左到右排上次序，即称该树为有序树。
将有序树转化为二叉树的原则如下：
（1）有序树T中的结点与二叉树BT中的结点一一对应；
（2）有序树T中某个结点N的第一个子结点（即最左边的子结点）N1，在二叉树BT中为对应结点N的左子结点；
（3）有序树T中某个结点N的第一个子结点以后的其它子结点，在二叉树BT中被依次链接成一串起始于N1的右子结点。
图2.51表达式a*（b+c/d）+e*h-g*f（s,t,x+y）
波兰表示式：
abcd/+*eh*gstxy+f*-+
2表达式的线性化
所谓的表达式的线性化，是指将一般的表达式化为波兰表示式（即后缀表示）。
实现表达式线性化的方法不是唯一的。
利用树结构与二叉树结构对表达式线性化的步骤如下：
（1）将表达式用有序树表示，即构造表达式树；
（2）将表达式树化为二叉树；
（3）对相应的二叉树进行中序遍历，其遍历序列即为表达式的波兰表示式。
图2-56（b）中序遍历结果为：
这个序列即为该表达式的波兰表示式。
2.7图
2.7.1图的基本概念
如果数据元素集合D中的各数据元素之间存在任意的前后件关系，则此数据结构称为图。
一个结点的后件个数称为该结点的出度，前件个数称为该结点的入度，入度与出度之和称为该结点的度。
对于无向图，每一个结点的入度与其出度相同。
图中结点的最大度称为图的度。
在实际应用中，如果图中的任意两个结点a与b之间规定了一个值f（a,b）,则称该图为有值图。
2.7.2图的存储结构
1关联矩阵
假设图中共有n个结点，其结点值分别为d1,d2,…dn，并用自然数将它们依次编号为1,2,…n。
为了存储图，首先用一个长度为n的一维数组D（1：
n）来存放图中各数据结点的信息，再用一个n阶的二维数组R（1:
n,1:
n）来存放图中各结点的关联信息。
其中二维数组R称为图的关联矩阵。
在关联矩阵R中，每一个元素R（i,j）（1<
=i<
=n,1<
=j<
=n）的定义如下：
无向图的关联矩阵是对称的。
且其对角线上的元素均为0。
关联矩阵也称为邻接矩阵。
2求值矩阵
为了表示有值图中每两个结点之间的求值函数，可以用另外一个求值矩阵V来存储。
为了完整地存储一个有值图，可以用一维数组来存储图中各结点的数据信息，用关联矩阵存储图中任意两个结点之间的关联信息，用求值矩阵来存储图中任意两个结点之间的求值函数。
第3章查找与排序技术
3.1基本的查找技术
3.1.1顺序查找P152
（1）无序表只能顺序查找
（2）有序链表只能顺序查找
3.1.2有序表的对分查找P152
#include"
stdlib.h"
stdio.h"
/*上机4,有序表的对分查找，P153*/
intbserch（intv[],intn,intx）
{inti,j,k;
i=1,j=n;
while（i<
=j）
{k=（i+j）/2;
if（v[k-1]==x）return（k-1）;
if（v[k-1]>
x）j=k-1;
elsei=k+1;
return（-1）;
main（）
{inta[11]={1,2,3,4,5,6,7,8,9,10,11};
intp;
p=bserch（a,11,6）;
printf（"
p=%d\n"
p）;
getch（）;
}_
3.2哈希表技术
3.2.1哈希表的基本概念P158
1Hash表
Hash表技术的关键是要处理好表中元素的冲突问题：
（1）构造合适的Hash码以便尽量减少表中元素冲突的次数；
（2）当表中的元素发生冲突时要进行适当的处理。
3.2.2几种常用的哈希表
1线性Hash表P161
线性Hash表的长度n一般设置为n=2k,
（1）线性Hash表的填入：
计算关键字k的Hash码i=i（k）;
检查表中第i项的内容：
空，填入
非空，令i=mod（i+1,n）,重复上述过程。
（2）取出
若有关键字k，则取出；
若空，则表中无该关键字；
非空且不是关键字k，则令i=mod（i+1,n），再查。
例3-2将关键字序列（9，31，26，19，01，13，02，11，27，16，05，21）依次填入长度n=12的线性Hash表中。
设i=int（k/3）+1.
序号
1
2
3
4
5
6
7
8
9
10
11
12
关键字K
13
19
16
26
27
31
21
冲突次数
i（k）=1时，Hash表的查找即为顺序查找。
2随机Hash表P165
当Hash表的长度设计为n=2k时，可以采用随机Hash表：
一旦发生冲突，表项序号i的改变不是采用加1取模的方法，而是用某种伪随机数来改变。
（1）填入：
计算关键字k的Hash码i0=i（k）,并令i=i0；
伪随机数序列初始化，令j=1；
检查表中第i顶的内容：
空，填入；
不空，令i=MOD（i0+RN（j），n），再检查。
（2）取出：
3溢出Hash表P169
包括溢出Hash表和溢出表两部分。
填入过程中，将冲突的元素填入溢出表，查找过程中发现冲突时在溢出中顺序查找。
3.3基本的排序技术
3.3.1冒泡排序
1冒泡排序
（1）从表头开始往后扫描线性表，在扫描的过程中逐次比较两相邻元素的大小，若前面的大于后面的，则将它们互换。
（2）从后到前扫描剩余的元素，并逐次比较相邻元素的大小，后面的小于前面的则互换。
（3）重复
（1）
（2），至到剩余的线性表空为止。
3.3.2简单插入排序与希尔排序
1简单插入排序P127
是指将无序序列中的各元素依次插入到有序的线性表中。
首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素依次向后移动一个位置，直到发现一个元素不大于T为止，此时将T插入到移出的空位置中。
有序子表的长度变为j.
2希尔排序P128
将整个无序序列分割成若干个小的子序列分别进行插入排序。
将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减到1时进行一次插入排序。
增量序列一般取ht=n/2k（k=1,2,…,log2n）.
3.3.3简单选择排序与堆排序P186
1简单选择排序
扫描整个线性表从中选出最小元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表为空。
2堆排序
堆的定义如下：
具有n个元素的序列（h1,h2,…hn）,当且仅当满足：
时称为堆。
序列{91，85，53，36，47，30，24，12}是一个堆。
堆顶元素为最大项。
调整建堆：
在一棵具有n个结点的完全二叉树（以H（1:
n）表示）中，假设H（m）的左右子树均为堆，将以H（m）为根结点的子树也调整为堆的过程。
建堆过程：
将根结点值与左右子树的根结点值进行比较，若不满足堆的条件，则将左右子树根结点的较大者与根结点值进行交换，直到所有子树均为堆为止。
堆排序方法如下：
将一个无序序列建成堆；
堆顶元素与堆中最后一个元素交换。
不考虑已经交换的最后一个元素，只考虑前n-1个元素构成的子序列，该子序列忆不是堆，但左右子树仍为堆，将子序列调整为堆，重复上述过程，直到子序列为空。
堆排序的方法对于规模较小的线性表并不合适，但对于规模较大的线性表来说是很有效的。
3.4二叉排序树及其查找
3.4.1二叉排序树及其构造
所谓二叉排序树是指满足下列条件的二叉树：
（1）左子树上的所有结点的值均小于根结点的值
（2）右子树上的所有结点的值均不小于根结点的值
（3）左右子树也满足上述两个条件。
二叉排序树的构造：
依次读入给定序列中的每一个元素，然后进行下列处理：
（1）若当前的二叉排序树为空，则读入的元素为根结点
（2）若读入的元素的值小于根结点的值，则将元素插入到左子树中
升级会员 