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=（a1,a2,…an）,采用数组实现，则在等概率的前题下，平均每插入一个元素需要移动的元素个数为多少？若元素插入在ai与ai+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)
第二讲 树
一、 树、二叉树的基本概念
*树与二叉树的区别
*二叉树的性质
*二叉树的计数Bn=
*近似满二叉树与满二叉树的概念和性质
思考题：叶子数为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：2H-1]作为其存储结构。请写一算法，求该二叉树中叶子节点的个数。
5、 已知一棵二叉树的先序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树的算法。
九、 证明
1、 任一棵有n个结点的二叉树，已知它有m个叶子结点。证明：度为2的结点有m-1个，其他结点是度为1的结点。
解答:
1、 ABCD/+E*-
2、 2H-1，2H-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棵树，每棵树具有的顶点数为
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),h1(x),h2(x),…,h2I-1(x),h2i(x),….
h2I-1(x)=( h(x)+i2) mod B
h2i(x)= ( h(x)-i2) mod B (1≤i≤(B-1)/2)
h(49)=5, h1(x)=6,h2(x)=4, h3(x)=9
第四讲 排序与选择（2）
一、 快速排序算法
*快速排序算法的基本思想
*快速排序算法（PARTION）及其算例执行过程
二、 堆排序算法
*堆排序算法的基本思想
*堆排序算法及算例
三、 计数排序、桶排序和基数排序的算法思想
四、 中位数的概念及寻找中位数的算法思想
五、习题讲解说
1、 对键值集合，{72，73，71，23，94，16，05，68}对应的二叉树进行建堆。
2、 已知关键字序列（K1，K2,…,kn-1）已是堆，试写一算法将（K1，K2,…,kn-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),h1(x),h2(x),…,h2I-1(x),h2i(x),….
h2I-1(x)=( h(x)+i2) mod B
h2i(x)= ( h(x)-i2) mod B (1≤i≤(B-1)/2)
h(49)=5, h1(x)=6,h2(x)=4, h3(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;
3223179(小灵通)
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |