最新清华大学严蔚敏版数据结构考研要点精华版.docx
《最新清华大学严蔚敏版数据结构考研要点精华版.docx》由会员分享，可在线阅读，更多相关《最新清华大学严蔚敏版数据结构考研要点精华版.docx（49页珍藏版）》请在冰点文库上搜索。
最新清华大学严蔚敏版数据结构考研要点精华版
1数据（Data）:
是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（DataElement）:
是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项（DataItem）组成。
数据项是数据的不可分割的最小单位。
数据项是对客观事物某一方面特性的数据描述。
数据对象（DataObject）:
是性质相同的数据元素的集合，是数据的一个子集。
如字符
集合C={‘A,'B'。
，'C,…}
数据结构（DataStructure）:
是指相互之间具有（存在）一定联系（关系）的数据元素的集合。
元素之间的相互联系（关系）称为逻辑结构。
数据元素之间的逻辑结构有四种基本类型，如图1-3
所示。
1集合：
结构中的数据元素除了“同属于一个集合”外，没有其它关系。
2线性结构：
结构中的数据元素之间存在一对一的关系。
3树型结构：
结构中的数据元素之间存在一对多的关系。
4图状结构或网状结构：
结构中的数据元素之间存在多对多的关系。
2、顺序结构：
数据元素存放的地址是连续的；
链式结构：
数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、C语言中用带指针的结构体类型来描述
typedefstructLnode
{ElemTypedata;/*数据域，保存结点的值*/
structLnode*next;/*指针域*/
}LNode;/*结点的类型*/
4、循环队列为空：
front=rear。
循环队列满：
（rear+1）%MAX_QUEUE_SIZE=front。
5、性质1:
在非空二叉树中，第i层上至多有2i-1个结点（i=1）。
性质2：
深度为k的二叉树至多有2k-1个结点（k±1）。
性质3:
对任何一棵二叉树，若其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。
一棵深度为k且有2k-1个结点的二叉树称为满二叉树（FullBinaryTree）。
完全二叉树的特点：
若完全二叉树的深度为k,则所有的叶子结点都出现在第k层或k-1
层。
对于任一结点，如果其右子树的最大层次为I，则其左子树的最
大层次为I或1+1。
性质4：
n个结点的完全二叉树深度为：
log2n+1。
性质5:
若对一棵有n个结点的完全二叉树（深度为哋2n」+1）的结点按层（从第1层到第g2n+1层）序自左至右进行编号，则对于编号为i（1wiwn）的结占：
八、、♦
⑴若i=1:
则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是i/2。
⑵如果2i>n:
则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
⑶如果2i+1>n:
则结点i无右孩子；否则，其右孩子结点编号是2i+1。
图621森林转换成二叉榊的过程
图6-22二叉树还原成蘇林的过程
6、线索二叉树：
设一棵二叉树有n个结点，则有n-1条边（指针连线），而n个结点共有
2n个指针域（Lchild和Rchild），显然有n+1个空闲指针域未用。
则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。
7、Huffman树：
具有n个叶子结点（每个结点的权值为wi）的二叉树不止一棵，但在所有的
这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树（或称最优树）。
8、完全无向图：
对于无向图，若图中顶点数为n,用e表示边的数目则e[0,n（n-1）/2]。
具有n（n-1）/2条边的无向图称为完全无向图。
完全有向图：
对于有向图，若图中顶点数为n，用e表示弧的数目，则e[0，n（n-1）]。
具有n（n-1）条边的有向图称为完全有向图。
生成树、生成森林：
一个连通图（无向图）的生成树是一个极小连通子图，它含有图中全部n
个顶点和只有足以构成一棵树的n-1条边，称为图的生成树
关于无向图的生成树的几个结论：
1）一棵有n个顶点的生成树有且仅有n-1条边；
2）如果一个图有n个顶点和小于n-1条边，则是非连通图；
3）如果多于n-1条边，则一定有环；
4）有n-1条边的图不--定是生成树。
9、最小生成树（MinimumSpanningTree）:
带权连通图中代价最小的生成树称为最小生成树。
最小生成树在实际中具有重要用途，如设计通信网。
设图的顶点表示城市，边表示两个城市
之间的通信线路，边的权值表示建造通信线路的费用。
n个城市之间最多可以建n'（n-1）/2
条线路，如何选择其中的n-1条，使总的建造费用最低?
W7-22按SsJI悴伉构迢最小‘I屈河的辺种
图AZ3有向图的拓扑排浮过程
（路径上各活动持续时间之和）。
长关键活动是影响整个工程的
10、工程完成最短时间：
从起点到终点的最长路径长度度最长的路径称为关键路径，关键路径上的活动称为关键活动。
11、查找方法比较
顺序查找
折半查找
ASL
最大
最小
表结构
有序表、无序表
有序表
存储结构
顺序存储结构
线性链表
顺序存储结构
分块查找
两者之间
分块有序表顺序存储结构
线性链表
12、在随机情况下，二叉排序树的平均查找长度ASL和log（n）（树的深度）是等数量级的。
二叉排序树（BinarySortTree或BinarySearchTree）的定义为：
二叉排序树或者是空树，或者
是满足下列性质的二叉树。
（1）:
若左子树不为空，则左子树上所有结点的值（关键字）都小于根结点的值；
（2）:
若右子树不为空，则右子树上所有结点的值（关键字）都大于根结点的值；
（3）:
左、右子树都分别是二叉排序树。
结论：
若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。
⑴：
左子树和右子树深度之差的绝对值不大于1;
⑵：
左子树和右子树也都是平衡二叉树。
平衡因子（BalaneeFactor）:
二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。
平衡二叉排序树上进行查找的平均查找长度和吨2n是一个数量级的，平均时间复杂度为
OQog2n）。
四种平衡化旋转，其正确性容易由遍历所得中序序列不变”来证明。
并且，无论是哪种
情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以
a为根结点的平衡二叉排序树的深度相同。
所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。
14、一棵m阶B_树，或者是空树，或者是满足以下性质的m叉树：
⑴根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；
⑵除根结点外，所有非终端结点至少有em/2。
棵子树，至多有m棵子树；
⑶所有叶子结点都在树的同一层上；
⑷每个结点应包含如下信息：
（n,Ao,Ki,Ai,K2,A2,…，Kn,An）
其中氏（1wi是关键字，且KAi-1所指向的子树中所有结点的关键字都小于K,Ai所指向的子树中所有结点的关键字都大
于Ki；n是结点中关键字的个数，且m/2-1wnw-1,n+1为子树的棵数。
根据m阶B_W的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外，所有非终端结点至少有em/2u棵子树，…，第h层上至少有em/2th-2个结点。
在这些结点中：
根结点至少包含1个关键字，其它结点至少包含em/2i-1个关键字，设s=em/2u，贝V总的关
键字数目n满足：
因此有：
h三1+logs（（n+1）/2）=1+em/2u（（n+1）/2）
即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+lo/m/2d（（n+1）/2）。
15、m阶B+树。
它与B_树的主要不同是叶子结点中存储记录。
在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为分界关键字”用来界定某一关键字的记录所在的子树。
一棵m阶B4树与m阶B_树的主要差异是：
⑴若一个结点有n棵子树，则必含有n个关键字；
⑵所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结
点按关键字的大小从小到大顺序链接；
⑶所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大（或
最小）关键字。
16、哈希函数：
在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。
可写成：
addr（ai）=H（ki）,
其中i是表中一个元素，addr（ai）是ai的地址，ki是ai的关键字。
哈希表：
应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这
样构成的表叫哈希表。
哈希查找（又叫散列查找）：
禾U用哈希函数进行查找的过程叫哈希查找。
例1:
设散列表长为7,记录关键字组为:
15,14,28,26,56,23,散列函数：
H（key）=keyMOD
7,冲突处理采用线性探测法。
解：
H（15）=15MOD7=1H（14）=14MOD7=0
H（28）=28
MOD7=0
冲突H1（28）=1又冲突H2（28）=2
H（26）=26MOD7=5
H（56）=56
MOD7=0
冲突
H1（56）=1
又冲突
H2（56）=2
又冲突
H3（56）=3
H（23）=23
MOD7=2
冲突
H1（23）=3
又冲突
H3（23）=4
各种散列函数所构造的散列表的ASL如下:
决中填入的记录数
⑴线性探测法的平均査找长度是*
%成功匕三x（l十］_口>
Sy伏败n舟1+杠二口卜）
⑵二次探测、伪随机探测.再哈希法的平均査找长度弘隔心寻xln（l-cc）
3皿失败nr1
⑶用链地址法解决冲夫的平均査找长度是^
17、排序的稳定性
若记录序列中有两个或两个以上关键字相等的记录：
Ki=Kj（i衣j,j=1,2,，且在）排序
前R先于Rj（i的。
排序的分类
待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。
1待排序的记录数不太多：
所有的记录都能存放在内存中进行排序，称为内部排序；
2待排序的记录数太多：
所有的记录不可能存放在内存中，排序过程中必须在内、外存
之间进行数据交换，这样的排序称为外部排序。
18、插入排序采用的是以“玩桥牌者”的方法为基础的。
即在考察记录Ri之前，设以前的
所有记录R1,R2,….,R已排好序，然后将R插入到已排好序的诸记录的适当位置。
最基本的插入排序是直接插入排序（StraightInsertionSort）。
⑴最好情况：
若待排序记录按关键字从小到大排列（正序）,算法中的内循环无须执行，则一趟排序时：
关键字比较次数1次，记录移动次数2次
⑵最坏情况：
若待排序记录按关键字从大到小排列（逆序），则一趟排序时：
算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。
一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4,则复杂度为0（n2）。
仞h设有关键字序列为=7,
4,-2,19
13,6,直接插
入排序的过程如下ffilo-1所示：
初始记录的关謎字’[7]
4-2
1
19
13
6
第一埴排丿沢|厂
r
7J■孑
19
13
6
第二电排序=（-2
471
19
1
13
6
第三尴排序=12
47
1
1刘
3J
6
第四曲排序二|-2
47
1
13
6
第五趟排序’[-2
厂
46
7
13
■91
图101立接揃入抽序的过程
算法实现
voidstraight,insert_sort（Sqlist*L）
{inti,j;
for（i=2;i<=L->length;i++）
{L->R[0]=L->R[i];j=i-1;/*设置哨兵*/
while（LT（L->R[0].key,L->R[j].key））
{L->R[j+1]=L->R[j];
j__；
}/*查找插入位置*/
L->R[j+1]=L->R[0];/*插入到相应位置*/
}
}
折半插入排序
当将待排序的记录R[i]插入到已排好序的记录子表R[1…-1]中时，由于R1,R2,…,iR已排好序，则查找插入位置可以用折半查找”实现，则直接插入排序就变成为折半插入排序。
从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为0（n2）。
排序示例：
设有一组关键字30,13,70,85,39,42,6,20,采用折半插入排序方法排序的过程
1=
1
<^o>
工3
TO
ws
<>
1=
2
<1^
J<»>
■
*7<»
wes
39
"N
<>
N"
1=
~7
■
u
_*O
39
70
20
盲=
13
30
3■仔t
MN
70
t
20
■«»TrV
IIKMlfl
■
«=
姑
13f
r
UN
VO
«£=；>
20
1
■o為衬i
1tcl
1
1=
2
□.曰
30
rtt
35*
"70
NS）
20
1U
Biilcl
1=
20
2
□.a
20
3°
39
4N
70
-2jrr
⑴算法实现
voidBinary_insert_sort（Sqlist*L）
{inti,j,low,high,mid;
for（i=2;i<=L->length;i++）
{L->R[0]=L->R[i];/*设置哨兵*/
low=1;high=i-1;
while（low<=high）
{if（LT（L->R[0].key,L->R[mid].key））
high=mid-1;
elselow=mid+1;
}/*查找插入位置*/
for（j=i-1;j>=high+1;j--）
L->R[j+1]=L->R[j];
L->R[high+1]=L->R[0];/*插入到相应位置*/
}}2-路插入排序
排序示例：
设有初始关键字集合{49,38,65,13,97,27,76},采用2-路插入排序的过程
Ilunl
Hrst
/
'7xzliual
叭」%⑴
Kd
Hn^l
Iirst
65110-32-站柄入摒序过魁
例：
设有关键字集合{49,38,65,97,76,13,27,49}，采用表插入排序的过程
o
1
2
34
5
6
7
|jVI,AXTISrT
SI
*
13
97
76
T
■
-
■
-
一
■
next鹿葛
1=2
MANirV1
3»
65
13
*>7
27
76
4
2
o
1
—
—
■
■
■
t=3
JMAXJIV1'
49
3«
27
J7^
491
2
3
1
o
■
—
—
—
1=4
IVI^XIIST
9
13
97
sI
4
3
1
LSLJ
2
L2U
■1
1=5
IVI.AXTTX1
49
65
13
97
^7
址9|
|4
73
5
~~6
—
—
I—6
?
V11
13
2?
Z«s
*9
1
4I
J
1
6
2
1-
—
1—7
XIAXIIS1
49I
13
27
7*
±12
4
3
1
7
6
o
2
5
tz:
1
i—s
、■几X丄、可
4
3S
13
27_
7<>
s
1
7
no
2
~G~
3
>4农捆序过和
希尔排序（ShellSort，又称缩小增量法）是一种分组插入排序方法。
排序示例
设有10个待排序的记录，关键字分别为9,13,8,2,5,13,7,1,15,11，增量序列是5,3,1,希尔排序的过程：
初始麦謎宁序列；?
1
L3S2513711511
1
7忖
第一墜排序过程：
18
J1
11
i1
第一趙排序后：
9-
II
r1251313«1511
L1IJI
1
II
第二趙排序后：
2f
第三拾排序后：
12
1.1
；1971311»1513
1S7«911131315
Eui-5希尔推序过程
算法实现
先给出一趟希尔排序的算法，类似直接插入排序。
voidshell_pass（Sqlist*L,intd）
/*对顺序表L进行一趟希尔排序，增量为d*/
{intj,k;
for（j=d+1;j<=L->length;j++）
{L->R[0]=L->R[j];/*设置监视哨兵*/
k=j-d;
while（k>0&<（L->R[0].key,L->R[k].key））
{L->R[k+d]=L->R[k];k=k-d;}
L->R[k+j]=L->R[0];
}
}
voidshell_sort（Sqlist*L,intdk[],intt）
/*按增量序列dk[0••-1t|,对顺序表L进行希尔排序*/
{intm;
for（m=0;m<=t;m++）
shll_pass（L,dk[m]）;
}
冒泡排序
排序示例：
设有9个待排序的记录，关键字分别为23,38,22,45,23,67,31,15,41,冒泡排序的
过程：
杪丿*nx强住字丿》列二
23
2Z
*
23
G7
31
15
4
23
22
3W
23
31
1S
4
07
2.2
工3
23
3H
IS
41
尬7
22
£3
23
31
1
3ft
-tl
*
笫四姥排序眉：
22
23
23
1S
31
3K
41
-4S
希尹桁排序后：
22
Z3
1*5
23
31
41
22
1S
23
31
3W
■41
45
07
笫七雷排序局
1S
22
23
古1
3S
4圧
<>T
1O总
rr也him段
voidBubble_Sort（Sqlist*L）
{intj,k,flag;
for（j=0;jlength;j++）/*共有n-1趟排序*/
{flag=TRUE;
for（k=1;k<=L->length-j;k++）/*一趟排序*/
if（LT（L->R[k+1].key,L->R[k].key））
{flag=FALSE;L->R[0]=L->R[k];
L->R[k]=L->R[k+1];
L->R[k+1]=L->R[0];
}
if（flag==TRUE）break;
}
}
算法分析：
时间复杂度：
最好情况（正序）:
比较次数：
n-1;移动次数：
0;
社动欢数二
最坏情况（逆序）:
故时间复杂度：
T（n）=0（n2）
空间复杂度：
S（n）=0
（1）
快速排序的平均时间复杂度是：
T（n）=O（n吨2n）
从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，
当每次划分比较均匀时，栈的最大深度为赵2n]+1。
•••快速排序的空间复杂度是：
S（n）=0（log2n）
从排序的稳定性来看，快速排序是不稳定的。
一趟排序示例
设有6个待排序的记录，关键字分别为29,38,22,45,23,67,—趟快速排序的过程
初始关键字序列：
29
29f
38
22
45
23
67
31t
j前移2亍位翌后，
29
I1
23
38
22
45
67
J1
31
J
i后移1个位置后，
29
1
23
22
45
J
38
67
31
R[i]放R[j]的位置：
丿
j前移2个位置后，
29
23
1
45
J
38
67
31
R[j]放R[i]的付置：
了
（后前移丄个位屋后,
29
23
1
22
J
29
45
3X
67
31
i和j的位置亟合：
图“7
--趙快速样序过程
算法实现
⑴一趟快速排序算法的实现
intquick_one_pass（Sqlist*L,intlow
升级会员 