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

ilikenba 发表于 2005-3-11 11:06

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是t后缀}
 
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=26>
1</TD>
<TD vAlign=top width=22>
2</TD>
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
5</TD>
<TD vAlign=top width=24>
6</TD>
<TD vAlign=top width=24>
7</TD>
<TD vAlign=top width=24>
8</TD>
<TD vAlign=top width=24>
9</TD>
<TD vAlign=top width=36>
10</TD></TR>
<TR >
<TD vAlign=top width=26>
a</TD>
<TD vAlign=top width=22>
b</TD>
<TD vAlign=top width=24>
a</TD>
<TD vAlign=top width=24>
b</TD>
<TD vAlign=top width=24>
a</TD>
<TD vAlign=top width=24>
b</TD>
<TD vAlign=top width=24>
a</TD>
<TD vAlign=top width=24>
b</TD>
<TD vAlign=top width=24>
c</TD>
<TD vAlign=top width=36>
A</TD></TR>
<TR >
<TD vAlign=top width=26>
0</TD>
<TD vAlign=top width=22>
0</TD>
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
2</TD>
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
5</TD>
<TD vAlign=top width=24>
6</TD>
<TD vAlign=top width=24>
0</TD>
<TD vAlign=top width=36>
1</TD></TR></TABLE>
 
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:=p^.data
 p:=p^.next
 end;
 p:=l^.next;
 while p<>nil do
 if (p^.data=s^.data) 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之间（<v:shapetype> <v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock aspectratio="t" v:ext="edit"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape>）的概率为<v:shape> <v:imagedata></v:imagedata></v:shape>，则平均插入一个元素所要移动的元素个数又是多少？
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个数顺序（依次）进栈，出栈序列的数目为
 <v:shape><v:imagedata></v:imagedata></v:shape>
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 of integer;
 top,sum,a:integer;
begin
 top:=0;
 sum:=1;
 read(a);
 while a<>0 do
 begin
 top:=top+1;
 stack:=a;
 read(a);
 end
 write(sum);
 while top<>0 do 
 begin
 sum:=sum*stack;
 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=<v:shape> <v:imagedata></v:imagedata></v:shape>
*近似满二叉树与满二叉树的概念和性质
思考题：叶子数为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作为其存储结构。请写一算法，求该二叉树中叶子节点的个数。
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<>0 then 
 if I*2>len then count:=count+1
 else if a=0 and A=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 of char;
 Node=record
 Lchild,rchild:integer;
 Ch:char
 End;
 B:array of node;
 I,j,k:integer;
S:stack;
Begin
S^.top:=0;
For I:=1 to n do
 Begin
 J:=1;
 While B.ch<>A do
 J:=j+1;
 If s^.top=0 then
 Begin
 S^.top:=s^.top+1;
 S^.data:=j;//入栈
 End
 Else//建立左子树
 If (j<s^.data) then
 Begin
 B].lchild:=j;
 S^.top:=s^.top+1;
 S^.data:=j
 End
 Else
 Begin
 While ((j>s^.data) and (s^.top<>0) do
 Begin
 K:=s^.data;
 S^.top:=s^.top-1;
 End
 B.rchild:=j;
 S^.top:=s^.top+1;
 S^.data:=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棵树，每棵树具有的顶点数为 <v:shape><v:imagedata></v:imagedata></v:shape>,则<v:shape> <v:imagedata></v:imagedata></v:shape>，
<v:shape><v:imagedata></v:imagedata></v:shape>，从而得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的基本要求
*完全图的边和顶点的关系(有向图和无向图)
*顶点度的计算(有向图和无向图)
*顶点数、边与顶点度的关系<v:shape> <v:imagedata></v:imagedata></v:shape>
上式表明任意一个图其所有顶点的度之和为偶数
*图的子图的计数
*图的路径和连通性概念(有向图和无向图)
*最小生成树的定义
*回路的概念
二、图的表示及其应用
*邻接矩阵表示法（邻接矩阵与边数的关系）
*邻接表表示法（邻接表与边数的关系、逆邻接表及建立邻接表的算法）
三、图的遍历
*图的深度优先遍历（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:=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:=v;
 if visited then begin
 found:=true;
 display();
 end
else begin
 visited:=true;
 for I:=1 to n do
 if matrix>0 then dfs(i);
 end;
p:=p-1;
visited:=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:=c;
For k:=1 to n do 
 For I:=1 to n do
 For j:=1 to n do
 If a:+a<a
 Then a:=a+a;
K:=1;
M:=maxint;
For j:=1 to N do 
 Begin
 S:=0;
 For j:=1 to N do 
 If a>s then s:=a;
 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<>0,且A<>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
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
15</TD>
<TD vAlign=top width=41>
38</TD>
<TD vAlign=top width=41>
61</TD>
<TD vAlign=top width=41>
84</TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD></TR></TABLE>
解答：
散列函数序列为：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
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
15</TD>
<TD vAlign=top width=41>
38</TD>
<TD vAlign=top width=41>
61</TD>
<TD vAlign=top width=41>
84</TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD>
<TD vAlign=top width=41>
 </TD></TR></TABLE>
 
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
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
13</TD>
<TD vAlign=top width=47>
14</TD>
<TD vAlign=top width=47>
35</TD>
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
17</TD>
<TD vAlign=top width=47>
29</TD>
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
 </TD>
<TD vAlign=top width=47>
 </TD></TR></TABLE>
 此时，其加载因子为α=6/12=0.5
4、算法思想：对给定的输入序列中的每一个元素x,确定该序列中的键值小于x的元素的个数。本算法的关键问题是要确定序列中元素的上界m.
数据结构：A，B，C为数组，分别存放输入、输出的数据元素和元素的计数。
 procedure count_sort(var a,b:array of recordtype);
var I,j:integer;
 c:array of integer;
 begin 
 for I:=1 to m do c:=0;
 for j:=1 to n do c.key]:=C.key]+1;
 for I:=1 to m do c:=c+c;
 for j:=n downto 1 do
 begin
 B.key]]:=A;
 C.key]:=c.key]-1
 End
 End
A
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
6</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
4</TD></TR></TABLE>
 
C 1 2 3 4 5 6
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=20>
2</TD>
<TD vAlign=top width=24>
0</TD>
<TD vAlign=top width=16>
2</TD>
<TD vAlign=top width=20>
3</TD>
<TD vAlign=top width=24>
0</TD>
<TD vAlign=top width=28>
1</TD></TR></TABLE>
 
C 1 2 3 4 5 6
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=20>
2</TD>
<TD vAlign=top width=24>
2</TD>
<TD vAlign=top width=16>
4</TD>
<TD vAlign=top width=20>
7</TD>
<TD vAlign=top width=24>
7</TD>
<TD vAlign=top width=28>
8</TD></TR></TABLE>
 
B 1 2 3 4 5 6 7 8
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
 </TD></TR></TABLE>
//比4小的数有7个//
 
C 1 2 3 4 5 6
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=20>
2</TD>
<TD vAlign=top width=24>
2</TD>
<TD vAlign=top width=16>
4</TD>
<TD vAlign=top width=24>
6</TD>
<TD vAlign=top width=24>
7</TD>
<TD vAlign=top width=36>
8</TD></TR></TABLE>
 
B 1 2 3 4 5 6 7 8
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
 </TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
 </TD></TR></TABLE>
//比1小的数有2个//
 
C 1 2 3 4 5 6
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=20>
2</TD>
<TD vAlign=top width=16>
4</TD>
<TD vAlign=top width=24>
6</TD>
<TD vAlign=top width=24>
7</TD>
<TD vAlign=top width=36>
8</TD></TR></TABLE>
 
B 1 2 3 4 5 6 7 8
<TABLE cellSpacing=0 cellPadding=0 border=1>

<TR >
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
1</TD>
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
3</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
4</TD>
<TD vAlign=top width=24>
6</TD></TR></TABLE>
 
算法时间为O（n+m），当m=O(n), 算法时间为O（n），线性时间
 
 
 
 
 
陈国龙
7893219（O），<a href="mailtcgl@fzu.edu.cn" target="_blank" >cgl@fzu.edu.cn</A>;
<a href="mailtcglh@pub3.fz.fj.cn" target="_blank" >cglh@pub3.fz.fj.cn</A>
3223179(小灵通)

lynnyan 发表于 2005-4-22 01:19

搞那么多白痴呀

欣然发表于 2005-11-19 15:57

bayern 发表于 2010-7-23 19:07

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

欢殇一笑 发表于 2013-11-6 18:32

咋是这样啊

暗夜№☆修罗 发表于 2013-11-20 12:45

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

warriorIverson 发表于 2014-1-18 09:16

好贴啊。必须收藏

空木葬花 发表于 2014-3-12 16:35

非常感谢楼主的福利！

wy617958197 发表于 2014-8-31 10:23

谢谢楼主分享

pen960223 发表于 2016-7-30 21:27

{:3_41:}{:3_41:}{:3_41:}{:3_41:}

页: [1] 2

数学建模社区-数学中国's Archiver

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