2023年数据结构期末复习知识点兼容版

《数据构造》期末复习

复习要点：

第一章

1.有关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算

法及其特性等；

◎数据：所有能输入到计算机中并被计算机程序处理的符号总称。

◎数据元素：基本单位。

◎数据项：最小单位。

◎算法特性（5点）：有穷性；确定性；可行性；输入；输出。

2.逻辑构造、存储构造（物理构造）及其类型；

◎逻辑构造有四种基本类型：集合、线性构造、树形构造和网状构造。

◎数据元素之间的关系有两种不一样的表达措施：次序映象和非次序映象，并

由此得到两种不一样的存储构造：次序存储构造和链式存储构造。

◎注：期中考题目

数据构造分为两大类，即为逻辑构造和存储构造。其中逻辑成果又分为线性

构造和非线性构造，存储构造一共有四种（次序、链接、索引、散列）。

3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。

表达措施

◎语句频度：直接写次数。

◎时间复杂度：0（执行次数），如：0（n）o

◎空间复杂度：0（所需空间）

第二章

1.次序表（数组）插入、删除、有序表合并算法及其移动次数计算;

1213212428304277

数据兀素

序号12345678

表达L.elem[0][1][2][3][4][5][6][7]

◎次序表插入

算法思想：假如要在序号5讪插入元素e,需要将序号5〜8向后移动一种

位置。

▲移动次数为4次，公式n-i+l

StatusListInsert_Sq(SqList&L,inti,ElenTypee)

〃在笫i个元素前插入新元素*当前i为5

<

if(i<1||i>L.length+1)returnERROR;/八值不合法

if(L.length>=L.listsize)〃当前存储空间己满，增加分配

<

ElemType*newbace=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeoF(ElemType));

iF(tnewbace)returnERROR;

L.elen=newbace;

L.listsize+=LISTINCREMENT;

>

ElemType*p;

ElenType*q=&(L.elen[i-1]);〃序号5对应L

For(p=&(L.elem[L.length-1]);p>=q;—p)

〃表及L.length值为8,p揖向匠号8,对应L.elem[7]

*(P+1)=*P；〃元素后移

*q=e;〃序号5对应L.elem[町赋值大e

++L.length;

returnOK;

◎次序表删除

算法思想：假如要删除序号5元素，需要将6〜8依次向前移动一位

▲移动次数为3次，公式n-i

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

〃删除第i个元素，并用e返回其值，当前i为5

<

if(i<1||i>L.length)returnERROR;〃1值不合法

ElenType*p=&-1]);〃p为被删除元素梗量

e=*P；〃衩删除元素的值赋宿给e

ElenType*q=L.elen+L.length-1;

〃表尾元素位置L.elem[刃+7,^L.elen[7]

For(++p;p<=q；*+p)

〃P先移到序号6;判断是查小于q

*(P-1)=*P；〃元素前移

-L.length;〃表长减1

returnOK;

◎有序表合并

LA=(3,5,8,ll)

I.R=⑵6,%9,ll,15,20)

则LC=(2,3,5,6,8,8,9,11,11,15,20)

算法思想(以非递减为例)：La和Lb非递减排列，La与Lb中元素逐一比较，较小

W、J先插入Lc中。

▲注：非递减是指递增排序，但元素有也许相等，与之相对的J有非递增排序。

▲移动次数为(La.length+Lb.length)

voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)

<//鬻筛线性表La和Lb的元素按值非递减排列。

〃归井La和Lb得到新的顺序线性表Lc,LC的元素也按值非递减排列。

ElenType*pa,*pb,*pc,*pa_last,*pb_last;

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elen=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

〃pc指向lc・elem[G]

if(?Lc.elen)

exit(OUERFLOW)；//存储分配失收

palast=La.eien+La.length-1;〃pa_last揖向La堡后一个兀塞

pblast=Lb.elem♦Lb.length-1;〃pb_last指向Lb最后一个元素

while(pa<=pa_last&&pb<=pb_last)<//归并

if(*pa<=*pb)*pc++=*pa++;

〃如果pa当前值小于pb当前值，pc当前位置的值赋值为pa当前值

else*pc*+=*pb++;

>

while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元重

while(pb<=pblast)*pc++=*pb++;//插入Lb的剩余元素

〃这两个所i1e语句只会执行其中一个

>//MerqeList

2.链表（有无头节点、单双、循环）插入（前、后）、删除（前、自身、后）的指针挂接、

建立（不带头节点）算法,

◎单链表

▲每个节点有数据域和指针域datanext

m

头ala2a3a4a5a6

带头节点L-N--*-----------------*------

Pt

ala2a3a4a5a6

不带头节点L-匚□一A

Pt

舛一rrurrurnrrurru「

单循环链表

•在P(a3)节点前插入S节点

(1)Q=P;〃先让Q指向a3

(2)P=L;〃P指向第一种节点(带头结点指向头结点，不带头结点指向al)

(3)while(P->next!=Q)P=P->next;〃找到a3H勺前驱a2,P指向a2

(4)S->next=P->next;〃P->next为a3,让S->next等于a3

(5)P->next=S;〃a2指针域指向节点S

•在P(a3)节点后插入S节点

(l)S-next=P->next;

(2)P->next=S;

•删除P(a3)前一种节点

(DQ=P；

(2)P=L;

(3)while(P->next->next!=Q)P=P->next;//找到al

(4)P->next=P->next->next;〃让al指针域指向a3,从而删除a2

・删除P(a3)节点

(1)Q=P；

(2)P=L;

(3)while(P->next!=Q)P=P->next;〃找到a2

(4)P->next=P->next->next;〃让a2指针域指向a4,从而删除a3

•删除P(a3)后一种节点

(l)P->next=P->next->next;〃让a3指针域指向a5,从而删除a4

◎双链表

▲每个节点有前驱指计、数据域、后继指针priordatanext

双循环链表,1匚~工-----T-----q~

头ala2a3a4

・在P(a2)节点前插入S节点

▲技巧：先让S-〉pr:or和S->next与链表建立关系

注：环节(4)必须在环节(3)背面

(l)S->next=P;//先让S-〉next指向a2

(2)S->prior=P->prior;〃S->prior指向al

(3)P->prior->next=S;〃再把al->next指向S

(4)P->prior=S;//a2-〉prior指向S

•在P(a2)节点后插入S节点

注：环节⑷必须在环节⑶背面

(l)S->prior=P;

(2)S->next=P->next;

(3)P->next->prior=S;〃a3->prior指向S

(4)P->next=S;

•删除P(a2)前一种节点al

(1)Q=P->prior;〃、指向要被删除的al;

(2)P->prior=P->prior->prior;〃P->priro指向头

(3)T->prior->next=E;//头一>next指向F

(4)free(Q);〃释放al的存储空间

•删除P(a2)节点

(l)P->next->prior=p->prior;

(2)P->prior->next=p->next;

(3)free(P);

・删除P(a2)后一种节点a3

(1)Q=P->next;

(2)P->next=P->next->next;〃a2->next指向a4

(3)P->next->prior=P;//a4->prior=P

(4)free(Q);〃释放a3存储空间

◎建立（不带头节点）单链表

uoidCreateList_L(LinkList&L,intn)〃建立不带头结点链表

<

LinkListp,q;

For(inti=0;i<n;++i)

p=(LinkList)malloc(sizeoF(LHode));

cin»p->data;〃输入数骸

P->next=NULL;〃p当前为最后一个节点

iHi==0)〃第一个节点

<

L=p；

q=p；

continue;〃不执行后面的语句

}

q->next=p;〃让前一个节点next指针指向p

q=p;〃q指向p

读程序：设n为2（i取0,1）

i=0时，

ptLtqt

i=1时，

LtqtptLtqtpt

[data-八

Ltqtpt

第三章

1.栈的进出序列、栈、队列、循环队列的满/空条件；

▲由于栈的插入、删除操作是限制在栈顶进行U勺，因而后进栈的元素必然是先

出栈，0.因此栈是“后进先出”表。

▲由于队列U勺输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队

列又称为“先进先出”表

◎栈的进出序列

例题：进栈序列为123,也许得到的出栈序列是什么？

答：共五种123/132/213/231/321

进出校状况（以132序列为例）：

1进栈一1出栈，输出1-2进栈一3进栈一3出栈一2出栈输出32

◎栈、队列、循环队列的满/空条件

梭空条件：s.top=s.base;梭满条件：s.top-s.base=stacksize;

队空条件：Q.front=Q.rear;队满条件：q->rear-q->front=MAXSIZE

循环队列空条件：Q.front=Q.rear

循环队列满条件：为防止在队满是队头指针和队尾指针也是重叠的状况，规定队列

中

尚有一种空的存储单元时为队满，即为Q.front=（Q.rear+l）M0Dmaxsize（MOD为取

余

运算符）。因而，这种循环队列不适合用动态数组作为存储构造。

2.栈、队列口勺存储构造、基本操作算法（双向栈）；

◎栈存储构造

・次序栈

typedefstruct{

SElemType*base;

SElemType*top;

intstacksize;

JSqStack;

・链式栈

dataiwxl

◎队列存储构造

・次序存储构造

出队列入队列

从

头尾

图3.8队列的示意图

•链式存储构造

daunext

◎双向栈

012M-1

ITIFITU

栈1底栈1顶栈2顶栈2底

存储构造:

typcdefstruct(

Elemtype*base[2];

Elemtype*top[2];

}BDStacktype;〃双向栈类型

初始化：

StatusInitStack(BDStacktype&tws,intm)/初始化•种大小为m『、J双向栈

tws

(

tws.base.O]=(Elemtype*)malloc(sizeof(Elemtype)*m);

tws.base[l]=tws.base[0]+m;

tws.top[0]=tws.base[0];

tws.top[l]=tws.base[l];

returnOK;

}//InitStack

入栈：

Statuspush(BDStacktype&tws,inti,Elemlypex)

〃x入栈，i=0表达低端栈，i=l表达高端栈

{

if(tws.top[0]>tws.top[l])returnOVERFLOW；

〃注意此时的栈满条件

if(i==0)*tws.top[0]++=x;

elseif(i==1)*lws.top[l]-=x;

elsereturnERROR;

returnOK;

}//push

出栈:

Statuspop(BDStacktype&tws,inti,Elemtype&x)

〃x出栈，i=0表达低端栈，i=l表达高端栈

(

if(i==0)

(

if(tws.top[0]=tws.base[0])returnOVERFLOW;

x=*—tws.top[0];

)

elseif(i==1)

(

if(tws.top[l]==tws.base[l])returnOVERFLOW;

x=*++tws.top[l];

}

elsereturnERROR;

returnOK;

}//pop

第四章

1.字符串模式匹配的简朴算法；

intIndex(SStringS,SStringT,intpos)

{//算法4.5

//返回子串T在主串S中第pos个字符之后的位置。

//若不存在，则函数值为0。

//其中，T非空，：WposWStrLength(S)。

inti=pos：

intj=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){//继续比较后继字符

++i;

++」；

}

else{//指计后退重新开始兀配

i=i-j+2;〃此时i为上次开始比较位置U勺下一位

J=1；

)

)

if(j>T[0])returni-T[0];

elsereturn0;

}//Index

2.计算NEXT。

j:1234567

串：abcabaa

next[j]:0111232

▲技巧：第一二个肯定是0,1!假如要计算next[4],我的字符串必须是以第3个字符

c为结尾，第1个字符a为开头的。

以第6个为例，a前一种字母是b,以第5个字符b为结尾的ab刚好和以第1个字符为

开头的ab匹配，因此next[6]=2+1=3。

第五章

1.二维数组日勺地址（下标）换算；

习题5.1假设有二维数组A6*8,每个元素用相邻的6个字节存储，存储器按字节

编址。已知A日勺起始存储位置（基地址）为1000,计算：

（1）数组A的体积1即存储量）

6*8*6=288字节

（3）按行存储是，元素al4口勺第一种字节的地址

1000+（8*1+4）*6=1072

基址+（每行H勺元素个数*行数十目前列序）*每个元素所占存储单元

（4）按列存储时，元素a47H勺第一种字节的地址

1000+（6*7+4）*6=6276

基址+（每列11勺元素个数*列数+H前行序）*每个元素所占存储单元

习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一种元素II勺字节地址是

100,每个整数占四个字节。问下列元素的存储地址是什么？

（2）allll地址:100+（3*5*8*1+5*8*1+8*1+1）*4=776

（3）a3125地址：100+（3*5*8*3+5*8*1+8*2+5）*4=1784

（4）a8247地址：100+（3*5*8*8+5*8*2+8*4+7）*4=4416

2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；

◎下三角矩阵压缩为一维数组（记忆公式）

▲技巧：推荐把公式（2）背下来（i,j,R范围都是从0开始），其他根据范围变化公

式

⑴若l<=j,j<=n,0<=R<=n(n+l)/2-1

当当=j时,k=i(i-l)/2+j-l;

当当j时,k=j(j-l)/2+i-l.

(2)若0<=i,j<=n-l,0<=R<=n(n+D/2-1

〃注意i,j是0到n-1,下面的公式相称于把⑴中i变成i+1,j变成j+1

当i>=j时，k=(i+l)i/2+j;

当j<j时，k=(j+l)j/2+i.

⑶若l<=j,j<=n,l<=R<=n(n+l)/2

〃注怠K是1到「(n+l)/2,下面公式相称于把⑴中k变成k-1

当i>=j时，k=i(i-l)/2+j;

当i<j时，k=j(j-l)/2+i;

(4)若0<=j,1,l<=R<=n(n+l)/2

当i〉=j时,k=(i+l)i/2+.j+l;

当i<j时,k=(j+l)j/2+i+l;

3.稀疏矩阵的三元组表达。

iJe

厂15000910、

11115

0110000

21591

030000

T〜32211

220(5000

4323

000000

00000J54122

6436

5J5.9T761-15

图510T的三元短表bdaJs

4.稀疏矩阵应用的算法。(略)

第六章

1.二叉树日勺性质；

性质1：O

性质2:深度为k的二叉树至多有个结点(kDo

性质3:对任何一棵二叉树T,假如其终端结点数为no,度为2日勺结点数为n2,则

n0=n2+lo

性质4:o

性质5:假如对一棵有n个结点的完全二叉树的结点按层序编号，

则对任一结点i(lin),有：

(1)假如i=l,则结点i是二叉树的根，无双亲；

假如>1,则其双亲是i/2o

(2)假如2i>n,则结点i无左孩子：

假如2in,则其左孩子是2i。

(3)假如2i+l>n,则结点i无右孩子；

假如2i+ln,则其右孩子是2i+lo

2.二叉树的先序、中序、后序、层次遍历过程；树的先序、后序、层次遍历过程;

+

先仔遍-+a*b-cd/ef

中仔遍历：a+b*c-d-e/f

后，遍历：abcd-*+ef/

U次通〃八-+/a*efb-cd

二叉树遍历过程:

先（根）序遍历：根一左子树一右子树

中（根）序遍历：左子树一根一右子树

后（根）序遍历：左子树一右子树f根

层次遍历：从上到下，从左往右，逐一遍历

树的遍历过程:

先根（次序）遍历：先访问根结点，然后依次先根遍历根H勺每棵子树（根一

子树）

后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树一

根）

层次遍历：从上到下，从左往右，逐一遍历

▲注：树与二叉树互相转化后

树的I先根遍历相称于二叉树日勺先序遍历

树的后根遍历相称于二叉树的中序遍历

3.给出两个遍历序列，画出树（二叉树、树）

习题6.23画出和下列已知序列对应的树T:

（1）树的先根次序方向序列为GbKDAlEBCHJ;

（2）树的后根次序访问序列为DIAEKFCJHBG。

注：树日勺后根遍历相称于二叉树的中序遍历

①由⑴知G为根；

（2）G为根,联络（2）知G无右子树:

③观测（1）,F为G左子树；

④根据③，观测（2）知DIAEK在E左边,

/\CJHB在F右边;

⑤观测（1）,K为F左子树：

⑥根据⑤，观测⑵知K无右子树；

⑦观测（1）,D为K左子树；

⑧根据⑦，观测（2）知I）无左子树；

⑨观测（1）,A为D右子树:

⑩观测(2),IE分别为A左右子树；

OCJF的右子树自行观测判断。

dbd

4.二叉树与树互相转换；

◎树转化成二叉树：

规则：树日勺最左孩子变成二叉树左子树,该左孩子时兄弟变成二叉树左子树的右子树

(金夕•.⑥6

©O©©(^-©Q)(6©

®0(H)@©

⑻(b)(C)(d)

注：原树中B为A最左孩子，C,D为B兄弟,变成二叉树后C成为B右子树，D成为C

右子树。

◎二叉树转化成树

5.求哈夫曼树和给出编码、带权途径长度计算。

习题6.26假设用于通信日勺电文仅由8个字母构成，字母在电文中出现的频率分别

为0.07,0.19,0.02,0.06,0.32,0.21,0.10。试为这8个字母设计哈夫曼编码,并求

带权途径长度

设这8个结点为A、B、C、D、E、F、G、H,其对应日勺权为7、19、2、6、32、3、21、10。

①目前未用权：7、】9、2、6、

32、3、21、10,选出2、3构造

出5。

⑵目前未用权：7、19、6、32、

21、10、5,选出5、6构造出

Ho

▲编码：树时左分支为0,右分支为1。

得到哈夫曼编码为A:1101B:01C:lllllD:1110E:10F:11110G:00H:H00

带权途径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100=2.61

▲注：该公式为：A途径长*A权+B途径长*B权+-+H途径长*H权，由于设H勺权值是

本来的I100倍，因此成果除以100o

第七章

1.邻接矩阵、邻接表存储构造及其特性;

(＞有向图，无向图

•G(b)G?注：以有向图G1为

P1010-

■0110'

10101例■的途径用1，否则

0000

Gl.arcs=G2.arcs=01011

0001

101000)

.1000.

JO1100.

图7.8图的邻接矩阵

注：以有向图G1为例

标号0123

00110

I0000

20001

31000

第0行值为I的是1、2,因此有

(a)G］的邻接表；(b)Gz的邻接表；(c)Gi的逆邻接表

2.求最小生成树(Prim、Kruskal)；

①从VI开始，找到最小边

(VI,V3)；

②寻找与VI、V3有关联的最小

边，找到(V3,V6)；

③寻找与VI、V3、V6有关联日勺最

小边，找到(V6,V4)；

④寻找与VI、V3、V6、V4有关联

◎克鲁斯卡尔(Kruskal)(避圈法)：以边为基础

措施简介：依次寻找权最小边，防止生成•种圈，所有点联通时生成最小树。

3.拓扑排序：

环节：（1）在有向图中选一种没有前驱的顶点且输出之。

（2）从图中删除该顶点和所有以它为尾的弧。®

®@

:

(e)

V4w

注：拓扑排序不唯一。

4.求最短途径过程(Dijkstra、Floyd)o

◎迪杰斯特拉(Dijkstra)

习题7.11试运用Dijkstra算法求题7.11图中从顶点a到其他各顶点间H勺最短途径,

出执行算法过程中各步状态。

求解过程:

S

终点«

bcde▲g

Dist(终点集)

15212

K=1h»c)

(a,b)(a,c)(a,d)

1512106

K=2{a.c.f}

(a,b)(a,d)(ace)(a,c»f)

15111016

K=3{a,c»f»e}

(a,b)(add)(a,c»e)(a.c*f,g)

151116

K=4{a,c,f,e,d}

(a,b)(8,d)(a*cJ«g)

1514

K=5(a,c,f,e,d,g!

(a,b)(a,c»f,d,g)

15

K=6{a,c,f,e,d,g,b}

.(a,b)

K=1时，找a能直接抵达日勺点，有b,c,d,(a,c)权最小，(a,c)为a到c最短途径,

将c放如终点集S；

K=2时，找a能直接抵达的I点，或通过(a,c)能抵达的点，(a,c,f)权最小，(a,c,f)

为a到fH勺最短途径，将f放入终点集S；

K=3时，找a能直接抵达日勺点，或通过(a,c)能抵达的点,或通过(a,c,f)能抵达日勺

点，

(a,c,e)权最小，(a,c,e)为a到e最短途径，将e放入终点集S；

K=4时,找a能直接抵达的J点，或通过(a,c)能抵达的点,或通过(a,c,f)能抵达的

点，或通过(a,c,e)能抵达的点，(a,c,f,d)为a到d最短途径，将d放入终点集S：

k5时，找a能直接抵达的点，或通过(a,c)能抵达的点，或通过(a,c,f)能抵达的

点，或通过(a,c,e)能抵达的点，或通过(a,c,f,d)能抵达的J点，(a,c,f,d,g)权最小，为a

到g最短途径，将g放入终点集S：

K=6时，只剩余(a,b),(a,b)为a到b最短途径，将b放入终点集S。

◎弗洛伊德(Floyd)

-0411-

602

.3oo0.

(b)

图7.36带权有向图

<a)有向网G，(b)邻接矩阵

D(-i)D(o>D⑴D(2)

D

012012012012

004110411046046

1602602602502

23oo0370370370

p(-l)p(0)P(1)p(2)

P

01201Z012012

0ABACABACABABCABABC

1BABCBABCBABCBCABC

2CACACABCACABCACAB

图7.37图7.36中有向图的各对顶点间的最短路径及其路径长度

注:D(l)[i][j]是从Vi到Vj的中间顶点的序号不不小于1H勺最短途径的长度；

D(k)是从Vi到七的中间顶点的序号不不小于k的最短途径的长度；D(n-l)[i][j]

就是从Vi到Vj的最短途径的长度。

D(-1)栏中，Vi-Vj不容许有转折点。直接填邻接矩阵。

D(0)栏中，Vi-Vj只容许通过V0转折，或者不转折。通过V0转折权值不不小于原权

值，就把原权值替代掉。

D(l)栏中，Vi-Vj只容许通过VO、VI转折，或者不转折。假如转折后权值不不小于原权

值，替代。

D(2)栏中，Vj-Vj容许通过V0、VI、V2转折，或者不转折，假如转折后权值不不小于原

权值，替代。此时p(2)中就是各点间的J最短途径。

第九章

1.如卜.所有查找成功平均杳找长度

2.次序查找；折半查找；

◎次序查找：从表中最终•种记录开始，逐•进行比较。

▲平均查找长度

等概率时,平均查找长度ASL=(n+l)/2

不等概率时，ASL=nPl+(n-l)P2+…+2Pn-l+Pn

◎折半查找：

指针low和high分别指示待查元素所在范围的下界和上界，mid=(low+high)/2,

假如要找时值不小于S[mid],则让mid=(mid+1+high)/2,继续比较；

假如要找口勺值不不小于SMid],则让mid=(low+mid-1)/2,继续比较。

▲平均查找长度

等概率条件下，ASL=(n+l)-l

当n>50时，有近似成果ASL=(n+l)-l

3.二叉排序树U勺插入(建立)、删除、平衡过程；

◎二叉排序树建立

(1)若它的左子树不空，则左子树上所有结点的值均不不小于它U勺根结点的值；

(2)若它的右子树不空，则右子树上所有结点的值均不小于它口勺根结点的值；

(3)它的左、右子树也分别为二叉排序树。

习取9.9@已知如下所示长度为12的表

(Jan*Feb.Mar♦Apr♦MayJune»July.Aug.Sep»Oct»Nov,Dec)

(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后

的二叉排序树,并求其在等概率的情况下杳找成功的平均查找长度.

(1)求得的二叉排序树如下图所示，在等概率情况下查找成功的平均查找长度为

ASL^=上(1X1+2X2+3X3+4X3+5X2+6X1)=条

▲注：中序遍历二叉排序树，得到从小到大序列

根据字母的先后确定大小

①插入Jan；②F不不小于J,Feb成为Jan左子树：③M不小于J,Mar成为Jan右子

树；④Apr不不小于Jan,且Apr不不小于Feb,Apr成为Feb左子树；⑤May不小于Jan,

且May不小于Mar,May成为Mar右子树；⑦June不小于Jan,且June不不小于Mar,

June成为Mar左子树。剩余的I略。

◎二叉排序树删除O

3种状况：

(D*p为叶子节点，直接删除。

(2)*p只有一种孩子*chiId只需将*chiId和*pU勺双亲直接连接后，即可

删去*P。

(3)*p有两个孩子

MJ*P的直接前驱或直接后继替代*P,然后删除它的直接前驱或直接

后继。

◎平衡一叉树：树上任何节点的左右于树深度差都不超过1

▲插入节点P后不平衡，找到离P近来的不平衡点，根据二叉排序树的建立进行调

整。

插入Aug时,Feb左右子树深度差超过1不平衡

插入Oct时,近来不平衡点为May。由于Sep>Oct>May,因此Ocl作为双亲

Jan

(3)＞一^x

^Nov

二f^June^)(^May^\(^SepT

(

变化后的(3)

插入Nov时,Jan不平衡。把Jan左转,Mar时左子树变成Jan右子树。

Tune^)^May^X^Sept^)

)(^July^)(^Nov^)

最终平衡树

4.哈希表构造、冲突处理措施:除留余数法、线性探测或链地址法。

◎构造：

除留余数法:H(key)=keyMODp,p<=m

◎冲突处理:

线性探测法：Hi=(H(key)+)Modmi=1,2,•••,k(k<=m-l)

链地址法：将所有关键字为同义词日勺记录存储在同一线性链表中。

例题：已知一种线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计

算散列地址,并散列存储在散列表A［0..6］中,采用线性探测措施处理冲突。

①38；38%7=3,查找次数为地址：。］23456

(2)25：25%7=4,查找次数为1。|一|一||一|

③74：74%7=4,与25冲突，次数：131124

(4+1)%7=5,查找次数为2。

等概率成功查找II勺平均查找长度为:

④63：63%7=0,查找次数为1.

(1+3+1+1+2+4)/6=2

©52：52%7=3,与38冲突,

例9-3已知一组关键字为(19.14.23,01,68,20,84,27,55,11.10,79)

则按哈希函数H(.key^keyMOD13和链地址法处理冲突构造所得的哈希表如图9.26

所示.

A

A

A

A

A

A

TH111A

A

图9.26链地址法处理冲突时的哈希表

第十章

1.简朴排序(直接插入、选择、冒泡)的过程；

◎直接插入(略)

◎选择排序

基本思想：依次在序列中选出最小的记录R[k],将它与第1个记录R[l]互换。

模式：for(i=0;i<10;i++)

forG=i;j<10;j++);

。置泡排序：

基本思想：依次比较相邻H勺两个数，将小数放在前面，大数放在背面。

模式：for(i=0;i<n;i++)

for(j=0;j<n-i-l;j++);

2.先进排序(希尔、迅速、堆、归并、基数)过程；

◎希尔排序：

基本思想：先取一种不不小于n的整数dl作为第一种增量，所有距离为dl的倍数的

记录放在同一种组中，先在各组内进行直接插入排序；然后，取第二个增量d2<dl反复上