[分享]2002年《算法与数据结构》复习

ilikenba

2002年《算法与数据结构》复习

第一讲 表

一、 基本概念

表、栈、队列和串的概念及其特征

*表的特征：表中元素具有同一数据类型；表是由有限个元素组成的有限序列；表中元素之间的逻辑关系是一种邻接关系（前驱和后继），因此表结构是一种线性结构，即线性表；作为抽象数据类型，表支持9种基本运算。

二、 表和串9种基本运算

*表的9种运算Insert(x, p, l), Locate(x, l), Retrieve(p, l), Delete(p, l), Next(p, l), Previous(p,l), Makenull(l), First(l), Printlist(l)

*END(l)的含义

*会利用上述基本运算实现表的其它运算例如教材P41例子

*串的9种运算及会利用其实现串的其它运算

三、 表、栈、队列和串的实现方法

*表的数组实现和指针实现各自的特点

*循环链表的特点

*常用的栈运算：EMPTY（S），其为一个函数，当S为空时，其值为true, 否则其值为false

两栈共享操作；会利用栈设计算法

*常用的队列运算：EMPTY（S），其为一个函数，当S为空时，其值为true, 否则其值为false；队列为空为满的条件；会利用队列设计算法

*串的实现各种方法的特点（串的数组实现、串的指针实现、串的块链实现和串的堆结构）

*朴素的模式匹配算法的数组实现和指针实现及实例执行过程

*前缀函数Л（q）的计算及KMP算法进行模式匹配时每一趟的匹配过程。

四、 习题

1、 利用表的9种基本运算实现将两个有序表合成一个有序表；

2、 设多项式P（x）用单链表存储，链表中的每个单元由3个域构成，它们分别存放多项式P（x）中一个项的系数、指数和指向下一单元的指针。设计一算法用于求P(x)的微商。

3、 计算模式串‘ababababca’的前缀函数Л。

4、 利用串的9种基本运算实现把串s=’(xyz)*’转换为串t=’(x+y)*z’

5、 设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。

解答

1、 procedure merge(var l1,l2,l3:list);

var p,q,r:position;

begin

p:=first(l1);

q:=first(l2);

r:=first(l3);

while (p<>end(l1)) and (q<>end(l2)) do

begin

if retrieve(p,l1)<retrieve(q,l2) then

begin

insert(retrieve(p,l1),r,l3);

p:=next(p,l1)

end

else

begin

insert(retrieve(q,l2),r,l3);

p:=next(q,l2)

end;

r:=next(r,l3)

end;

while p<>end(l1) do

begin

insert(retrieve(p,l1),r,l3);

p:=next(p,l1)

r:=next(r,l3)

end;

while q<>end(l2) do

begin

insert(retrieve(q,l2),r,l3);

q:=next(q,l1)

r:=next(r,l3)

end;

end;

2、 Type

celltype=record

coef:integer;

exp:integer;

next:^celltype

end;

list:celltype;

position:celltype;

procedure dif(var l:list);

var

q:position;

begin

q:=l;

while q^.next<>nil do

begin

q:=q^.next;

if q^.exp>0 then

begin

q^.coef:=(q^.coef)*(q^.exp);

q^.exp:=q^.exp-1;

End

Else

Delete(q)

End

End;

3、 Л（q）=max{l|0≤l<q且t[1..l]是t[1..q]后缀}

1	2	3	4	5	6	7	8	9	10
a	b	a	b	a	b	a	b	c	A
0	0	1	2	3	4	5	6	0	1

4、 t=concat(rep(sub(s,1,5),’y’,’+’),

rep(sub(s,6,1),’*’,’*y’))

s=concat(rep(sub(t,1,5),’+’,’y’),

rep(sub(t,6,2),’*y’,’*’))

5、 function judge(l:list):integer;

var p:position;

s:stack;

I:integer;

begin

p:=l^.next;I:=1;

while p<>nil do

begin

s^.top:=s^.top+1;

s^.data[s^.top]:=p^.data

p:=p^.next

end;

p:=l^.next;

while p<>nil do

if (p^.data=s^.data[s^.top]) then

begin

p:=p^.next;

s^.top:=s^.top-1;

end

else

begin

I:=0;

P:=nil

End;

Return(I)

End;

五、 思考题

1、 对表A=（a₁,a₂,…a_n）,采用数组实现，则在等概率的前题下，平均每插入一个元素需要移动的元素个数为多少？若元素插入在a_i与a_i+1之间（ ）的概率为 ，则平均插入一个元素所要移动的元素个数又是多少？

2、 用链接方式实现将两个有序表合并成一个有序表；

3、 试写出在双向链表L中的插入操作算法，算法中插入位置的获取可直接引入getnodep(L,x),其中参数L为双向链表，X为要插入的数据，要求算法中含有双向链表L的结构描述。

4、 写出和下列递归过程等价的非递归过程。

Procedure test(var sum:integer);

Var a:integer;

Begin

Read(a);

If a=0 then sum:=1

Else begin

Test(sum);

Sum:=sum*a

End;

Write(sum)

End.

5.证明：有n个数顺序（依次）进栈，出栈序列的数目为

6．已知3个字符串分别为s=’ab…abcaabcbca…a’,

s1=’caaba’,s2=’aca…a’,利用所学字符串基本运算法的函数得到结果串为：s3=’caabcbca…aca…a’。要求写出得到上述结果s所用的函数及执行过程。

参考解答：1.n/2,(2n+1)/3;

2.Type pointer=^node ;

Node=record

Data:datatype;//integer

Next:pointer

End;

Procedure combine(var L1,L2:pointer);

Var p,q:pointer;

Begin

New(q);

Q^.next:=nil;

P=q;

While (L1<>nil) and (L2<>nil) do

If L1^.data>=L2^.data

Then begin

P^.next:=L1;

P:=p^.next;

L1:=L1^.next

End

Else begin

P^.next:=L2;

P:=p^.next;

L2:=L2^.next

End;

If l1=nil then p^.next:=l2;

If l2=nil then p^.next:=l1;

End;

3.Type link=^node;

node=record

data:datatype;

pre,next:link;

end

procedure insert(var L:link;x:datatype);

var p,q:link;

begin

p:=getnodep(l,x);

new(q);

q^.data:=x;

q^.next:=p^.next;

p^.next:=q;

q^.next^.pre:=q;

q^.pre:=p;

end.

4.pocedure test;

var stack:array[1…maxsize] of integer;

top,sum,a:integer;

begin

top:=0;

sum:=1;

read(a);

while a<>0 do

begin

top:=top+1;

stack[top]:=a;

read(a);

end

write(sum);

while top<>0 do

begin

sum:=sum*stack[top];

top:=top-1;

write(sum);

end

end.

5．假设对二叉树的N个结点1到N加以编号，且令其前序序列为1，2，…,N，则不同的二叉树所得的中序序列不同，因此，不同形态的二叉树的数目恰好是前序序列均为1，2，…N的二叉树所能得到的中序序列的数目，而中序遍历的过程实质上是一个结点进栈和出栈的过程。

6．i1=index(1,s,s1)

i2=index(1,s,s2)

s4=substr(s,i1,length(s)-i1+1)

s5=substr(s,i2,length(s)-i2+1)

s3=concat(s4,s5)

第二讲 树

一、 树、二叉树的基本概念

*树与二叉树的区别

*二叉树的性质

*二叉树的计数B_n=

*近似满二叉树与满二叉树的概念和性质

思考题：叶子数为124的近似满二叉树的结点数为多少？

二、 会将表达式改写成前缀和后缀表达式

会画前缀和后缀表达式对应的二叉树

三、 树的表示（父亲数组表示法、儿子链表表示法、左儿子右兄弟表示法）

四、 树的遍历（递归与非递归算法）及基本运算

五、 二叉树的实现（顺序存储实现与链式存储实现）

六、 森林与二叉树的转换

七、 二叉树的线索化的作用、会画线索链表及相关的操作算法（例中序遍历算法、寻找前驱结点和后继结点算法等）

八、 习题

1、 写出中缀表达式A-（B+C/D）*E的后缀形式。

2、 高为H的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为多少？至多为多少？

3、 已知某字符串中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用{0，1}进行前缀编码，问该字符串的编码至少有多少位？

4、 已知深度为H的二叉树以一数组A[1：2^H-1]作为其存储结构。请写一算法，求该二叉树中叶子节点的个数。

5、 已知一棵二叉树的先序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树的算法。

九、 证明

1、 任一棵有n个结点的二叉树，已知它有m个叶子结点。证明：度为2的结点有m-1个，其他结点是度为1的结点。

解答:

1、 ABCD/+E*-

2、 2H-1，2^H-1

3、 98

4、 function leafcount(A,H):integer;

var I,len,count:integer;

begin

len:=2^H-1;

count:=0;

for I:=1 to len do

if A[I]<>0 then

if I*2>len then count:=count+1

else if a[I*2+1]=0 and A[I*2]=0 then

count:=count+1;

return(count);

end

5、 算法思想：可以依次从先序遍历中取出结点，每取出一个结点就与中序遍历序列中的各结点进行比较，当相等时，中序遍历序列就分成以该结点为根的两棵子树，左部分为左子树，右部分为右子树，直到取完先序遍历序列中的所有结点，则该二叉树构造完毕。可以用一个数组A存放先序遍历序列，A中的元素类型为字符类型，用数组B存放中序遍历序列，B中的元素类型为一个记录，包含lchild,rchild,ch三个域，其类型分别为整型和字符型，同时利用一个类型为stack的栈S。

Procedure binatree(A,B);

Var

A:array[1..N] of char;

Node=record

Lchild,rchild:integer;

Ch:char

End;

B:array[1..n] of node;

I,j,k:integer;

S:stack;

Begin

S^.top:=0;

For I:=1 to n do

Begin

J:=1;

While B[j].ch<>A[I] do

J:=j+1;

If s^.top=0 then

Begin

S^.top:=s^.top+1;

S^.data[s^.top]:=j;//入栈

End

Else//建立左子树

If (j<s^.data[s^.top]) then

Begin

B[s^.data[s^.top]].lchild:=j;

S^.top:=s^.top+1;

S^.data[s^.top]:=j

End

Else

Begin

While ((j>s^.data[s^.top]) and (s^.top<>0) do

Begin

K:=s^.data[s^.top];

S^.top:=s^.top-1;

End

B[k].rchild:=j;

S^.top:=s^.top+1;

S^.data[s^.top]:=j

End

End

End;

证明题

1、 设二叉树中度为1和2的结点数为n1和n2，总的结点数为n,则

n=n1+n2+m (1)

再由二叉树中的分支数得知：除根结点之外，其余结点都有一个分支进入，设B为分支数，

则有：n=B+1 (2)

而B又可以由度为1的结点数与度为2的结点数得：

B=1*n1+2*n2 (3)

从而由（1）、（2）、（3）得n2=m-1

十、思考题

1、 若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中含有多少棵树？

2、 假设先序遍历某棵树的结点序列为SACEFBDGHIJK，后序遍历该棵的结点序列为CFEABHGIKJDS，要求画出这棵树。

3、 简述后序线索树的不足之处。

4、 如果两棵二叉树的结构相同，并且结点中的数值相等，则称这两棵二叉树相等。试设计一算法用于判断两二叉树是否相等。

5、 教材第四章习题4-8和4-9；

参考答案：

1、设森林中有M棵树，每棵树具有的顶点数为 ,则 ，

，从而得M=N-K

4、Type nodeptr=^node;

node=record

infchar;

left,right:nodeptr;

end;

element=record

t1:nodeptr;

t2:nodeptr;

end;

function equal(p,q:nodeptr):Boolean;

var ok,sempty:Boolean;

x:element;

begin

makenull(s);

ok:=true;

repeat

while (p<>nil) and (q<>nil) and ok do

if p^.info=q^.info then

begin

X.t1:=p;

x.t2:=q;

push(s,x);

p:=p^.left;

q:=q^.left

end

else ok:=false;

if p<>nil or q<>nil then ok:=false;

sempty:=empty(s);

if ok and not empty then

begin

pop(s,x);

p:=x.t1;

q:=x.t2;

p:=p^.right;

q:=q^.right;

end

until not ok or sempty;

if not empty(s) then makenull(s);

equal:=ok;

end;

第三讲 图

一、 图的基本概念

*G=（V，E），集合V，E的基本要求

*完全图的边和顶点的关系(有向图和无向图)

*顶点度的计算(有向图和无向图)

*顶点数、边与顶点度的关系

上式表明任意一个图其所有顶点的度之和为偶数

*图的子图的计数

*图的路径和连通性概念(有向图和无向图)

*最小生成树的定义

*回路的概念

二、 图的表示及其应用

*邻接矩阵表示法（邻接矩阵与边数的关系）

*邻接表表示法（邻接表与边数的关系、逆邻接表及建立邻接表的算法）

三、 图的遍历

*图的深度优先遍历（DFS算法思想及算法时间复杂性）

（利用DFS算法思想设计相关的算法）

*图的广度优先遍历（BFS算法思想及算法时间复杂性）

四、 最少生成树

*Prim算法的实例执行过程、时间复杂性及适用场所

*Kruskal算法的实例执行过程、时间复杂性及适用场所

五、 最短路径

*Dijkstra算法的实例执行过程

*Floyd算法的实例执行过程及应用

六、 习题

1、 求有向图的强连通分量（极大连通子图）

2、 判断一个图是否有回路的方法。

解答：（拓朴排序即在拓朴排序中若输出之后余下的顶点均有前驱；计算G的边数e，若e≥n，则可判定G中是否有回路；计算G的顶点度D，若D≥2，则G中必有回路）。

3、 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路。若存在，则以顶点序列的方式输出该回路。//dfs算法的应用

解答：procedure findcircle;

var v:integer;

begin

for v:=1 to n do visited[v]:=false;

p:=0;

found:=false;

for v:=1 to n do dfs(v);

end;

procedure dfs(v:integer);

begin

if found then return;

p:=p+1;

vex[p]:=v;

if visited[v] then begin

found:=true;

display();

end

else begin

visited[v]:=true;

for I:=1 to n do

if matrix[v,i]>0 then dfs(i);

end;

p:=p-1;

visited[v]:=false;

end;

4、 给定图的存储结构，写出从某点出发的深度优先遍历和深度优先遍历序列。

5、 给定N个村庄之间的交通图，若村庄I和村庄J之间有道路，则将顶点I和顶点J用边连结，边上的权W（I，J）表示这条道路的长度。现在要从这N个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试设计一个算法解决上述问题。

解答：算法思想：建立图的邻接矩阵；用FLOYD算法计算每对顶点间的最短路径；找出从每一顶点出发到其余各顶点的最短路径中最长的路径；在这N条最长路径中找出最短的一条，则它的出发点即为所求。

Procedure example(n:integer; C:cost;var A:cost);

Begin//计算每对顶点间最短路径

For I:=1 to N do

For j:=1 to N do

A[I,j]:=c[I,j];

For k:=1 to n do

For I:=1 to n do

For j:=1 to n do

If a[I,k]:+a[k,j]<a[I,j]

Then a[I,j]:=a[I,k]+a[k,j];

K:=1;

M:=maxint;

For j:=1 to N do

Begin

S:=0;

For j:=1 to N do

If a[I,j]>s then s:=a[I,j];

If s<m then begin

M:=s;k:=I

End

End

End;

6、 证明：设G为具有n个顶点的无向连通图，证明所有具有n-1条边n个顶点的无向连通图是树图。

解答：（反证法）设G是连通的但不是树图，则G中必有回路，因而我们至少可以从某个回路中去掉某一条边且仍然保证G是连通的，则G将变成含有n个顶点且最多只有n-2条连的连通图，这显然是错误的，这与G为具有n个顶点的无向连通图，则G至少有n-1条边结论相矛盾。（归纳法）

7、 对于n个顶点的无向图，采用邻接矩阵表示，回答下列有关问题：

（1） 图中有多少条边？

（2） 任意两个顶点I和j是否有边相连？

（3） 任意一个顶点的度是多少？

解答：（1）图中边数等于邻接矩阵的非零元素个数之和的一半（2）I,j间有边相连的条件是A[I,j]<>0,且A[j,I]<>0（3）顶点i的度为第i行中非零元素的个数.

第四讲 集合(1)

一、 基本概念

*字典（有序字典）

*优先队列

*并查集

*平衡树

*二叉搜索树

*堆树（优先级树）

二、 字典实现

*字典的数组实现与表的数组实现的异同点。

*字典的散列表实现（开散列表和闭散列表）

*开散列表实现的基本思想及其运算

*闭散列表实现的基本思想及其运算（线性重新散列技术与二次散列技术）

三、 有序字典实现

*有序字典的数组实现（二分搜索）：算法、时间复杂性及实例执行过程

*有序字典的二叉搜索树实现（MEMBER及INSERT算法）

四、 优先队列

*优先队列与队列的区别

*优先队列基本运算

*堆的数组实现

五、 平衡树（AVL树）

*引入AVL树的意义及查找时间分析

*建AVL树的实例实行过程

*LL、LR、RR、RL型平衡旋转的指针修改操作

*B-树的定义（2-3树）及具体实例执行插入与删除过程

六、 习题

1、已知序列17，31，13，11，20，35，25，8，4，11，24，40，27，请画出该序列的二叉搜索树，并分别给出下列操作后的二叉树：

（1） 插入数据9；

（2） 删除结点17；

（3） 再删除结点13

2、假设有N个关键字互为同义词，若用线性探测法把N个关键字存入散列表中，至少要进行多少次探测？

解：N*（N+1）/2

3、对于给定AVL树，依次插入关键字为6和10的两个结点，请分别画出依次插入后的AVL树。

4、已知一棵3阶B-树如图，

（1） 画出插入18的3阶B-树；

（2） 画出在插入18后的3阶B-树中删除78后的3阶B-树。

5、设二叉搜索树的存储结构为：

type tree=^node;

node=record

key:keytype;

size:integer;

lchild,rchild,parent:tree;

end;

一个结点X^的size域的值是以该结点为根的子树中的总数（包括X^本身），例如，图示中X^所指结点的size值为4。设树高为H，试写一时间为O（H）的算法RANK（T：TREE；X：NODE），求X所指结点是树T中的第几个最小元素。（例X所指结点是树T中第11个最小元素）

解答：

function rank(t:tree;x:^node):integer;

begin

if x^.lchild=nil then r:=1

else r:=x^.lchild^.size+1;

y:=x;

while y<>t do

begin

if y=y^.parent^.rchild then

if y^.parent^.lchild=nil then r:=r+1

else r:=r+y^.parent^.lchild^.size+1;

y:=y^.parent;

end;

end

6、设散列表表长m=4，散列函数为h(k)=k mod 11，表中已有4个记录，如果用二次探测再散列技术处理冲突，关键字为49的记录的存储地址是多少？

0 1 2 3 4 5 6 7 8 9 10 11 12 13

15

38

61

84

解答：

散列函数序列为：h(x),h₁(x),h₂(x),…,h_2I-1(x),h_2i(x),….

h_2I-1(x)=( h(x)+i²) mod B

h_2i(x)= ( h(x)-i²) mod B (1≤i≤(B-1)/2)

h(49)=5, h₁(x)=6,h₂(x)=4, h₃(x)=9

第四讲 排序与选择（2）

一、 快速排序算法

*快速排序算法的基本思想

*快速排序算法（PARTION）及其算例执行过程

二、 堆排序算法

*堆排序算法的基本思想

*堆排序算法及算例

三、 计数排序、桶排序和基数排序的算法思想

四、 中位数的概念及寻找中位数的算法思想

五、习题讲解说

1、 对键值集合，{72，73，71，23，94，16，05，68}对应的二叉树进行建堆。

2、 已知关键字序列（K₁，K₂,…,k_n-1）已是堆，试写一算法将（K₁，K₂,…,k_n-1，Kn）调整为堆。

**例子

1、 设散列表表长m=4，散列函数为h(k)=k mod 11，表中已有4个记录，如果用二次探测再散列技术处理冲突，关键字为49的记录的存储地址是多少？

0 1 2 3 4 5 6 7 8 9 10 11 12 13

15

38

61

84

2设有一组关键字（17，13，14，153，29，35），需插入到表长为12的散列表中，请回答以下问题：

（1） 设计一个合适该散列表的散列函数；

（2） 用设计的散列函数将上述关键字插入到散列表中，画出其结构，并指出用线探测解决冲突时构造散列表的加载因子为多少？

3、对键值集合，{72，73，71，23，94，16，05，68}对应的二叉树进行建堆。

4、计数排序算法

解答

1、 散列函数序列为：h(x),h₁(x),h₂(x),…,h_2I-1(x),h_2i(x),….

h_2I-1(x)=( h(x)+i²) mod B

h_2i(x)= ( h(x)-i²) mod B (1≤i≤(B-1)/2)

h(49)=5, h₁(x)=6,h₂(x)=4, h₃(x)=9

2、（1）由于散列表表长为12，则可选不超过表长的最大素数11作为除留余数法的模，则可得其散列函数为h(k)=k mod 11.

(2)若用线性探测法解决冲突，则可构造出散列表如下：

0 1 2 3 4 5 6 7 8 9 10

13

14

35

17

29

此时，其加载因子为α=6/12=0.5

4、算法思想：对给定的输入序列中的每一个元素x,确定该序列中的键值小于x的元素的个数。本算法的关键问题是要确定序列中元素的上界m.

数据结构：A，B，C为数组，分别存放输入、输出的数据元素和元素的计数。

procedure count_sort(var a,b:array[1..n] of recordtype);

var I,j:integer;

c:array[1..m] of integer;

begin

for I:=1 to m do c[I]:=0;

for j:=1 to n do c[A[j].key]:=C[A[j].key]+1;

for I:=1 to m do c[I]:=c[I]+c[I-1];

for j:=n downto 1 do

begin

B[C[A[j].key]]:=A[j];

C[A[j].key]:=c[A[j].key]-1

End

End

A

3

6

4

1

3

4

1

4

C 1 2 3 4 5 6

2

0

2

3

0

1

C 1 2 3 4 5 6

2

2

4

7

7

8

B 1 2 3 4 5 6 7 8

4

//比4小的数有7个//

C 1 2 3 4 5 6

2

2

4

6

7

8

B 1 2 3 4 5 6 7 8

1

4

//比1小的数有2个//

C 1 2 3 4 5 6

1

2

4

6

7

8

B 1 2 3 4 5 6 7 8

1

1

3

3

4

4

4

6

算法时间为O（n+m），当m=O(n), 算法时间为O（n），线性时间

陈国龙

7893219（O），cgl@fzu.edu.cn;

cglh@pub3.fz.fj.cn

3223179(小灵通)

lynnyan

搞那么多白痴呀

欣然

[em06]

bayern

~~~~~~~~~~~~~~~~~~~

欢殇一笑

咋是这样啊

暗夜№☆修罗

有值得一看的理由。。。。。。。。。。。

warriorIverson

好贴啊。必须收藏

空木葬花

非常感谢楼主的福利！

wy617958197

谢谢楼主分享

pen960223