一、填空
1、hash（杂凑）技术广泛应用于查周过程，选择hash函数的主要标准是_____________________和__________________。
2、在AOV网中，存在环意味着_____________________________。这是____________的。对程序的数据流图来说，它表明存在_________________。
3、遍历图的过程实质上是_______________________。breath_firstsearch遍历图的时间复杂度_______________depth_firstsearch遍历图的时间复杂度，两者不同之处在于_________________________，反映在数据结构上的差别是____________________。
4、prim（普里姆）算法适用于求_____________的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_________________的网的最小生成树。

二、作图
1、用普里姆算法和克鲁斯卡尔算法分别构造下面网络的最小生成树。
2、画出左图二叉树的后序线索二叉树表示法。

三、算法题：
1、设指针p指着双向链表中的结点k，指针f指着将要插入的新结点x，x要插在结点k之后，写出有关指针需要修改的步骤。
2、用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25，平均查找长度是多少？
3、设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表`带权路径长度值并比较两种方案的优缺点。
4、如果在1000000个记录中找出2个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？

程序设计部分

四、写出下面程序的输出结果
1、 program csdge01(output);
var a,b,c: intger;
fuction tq( var x,y: intger ; z:integer): integer;
begin z:=x*3; x:=z+1; y:=x+z; tq:=y-1
end;
begin
a:=1; b:=1; c:=1;
writeln (tq ( a,b,c)):6, a:6, b:6, c:6)
end.
2、 program csdge02(output);
var p1,p2,p3:^ intger;
begin
new(p1); p1^:=5;
new(p3); p3^:=p1^*3; new(p2);
p2^:=3; p1^:=p2^+p3^; p2:=p3;
p3^:=p1-p2^; p2^:= (p1^*4+p2^) div (p3^ mod 4);
writeln (p1^:6, p2^:6, p3^:6)
end.
3 、 program csdge03(output);
var a,b,c: intger;
procedure p1(var x:integer);
function f2 (y:integer): integer ;
procedure p3( var z:integer );
begin z:z+2; b:=3*z
end;
begin p3(c); f2 :=y+c end;
begin x:=f2(b) end;
begin
a:=2 ; b:=1; c:=3; p1(a);
writeln ('a=', a:4 , ' b=' , b:4, ' c=', c:4)
end..
4、 program csdege04(output);
const n=2 ;
var s:array[1..n] of char ;
procedure al(k: integer);
var ch:char ; i: integer ;
begin
for ch:='a' to 'c' do
begin s[k]:=ch;
if k=n then
begin
for i:=1 to k do
write(s[i]:1); write (' ')
end
else al(k+1) end
end;
begin al (1) ; writeln end.

五、填空
1、[程序说明]如下程序读入字符序列，直至读入全部26个大写英文字母时停止，输出下列内容：
（1）读入字符总数；
（2）各大写字母首次输入时读入字符顺序号（从1开始计数）；
（3）首次读入的5个大写字母出现字数；
program csdge05(input,output );
var c: char ; n,m:integer ;
s,sl:_____________________________;
p,g:array['a'..'z'] of integer ;
begin
s:=_________________; sl:=[] ; n:=0;________________________;
for c:='a' to 'z' do
begin g[c] :=0 ;
p[c] :=0; end;
repea t read(c) ;________________;
if _____________ then
begin
s:=s_[c]; p[c] :=n;
if m<5 then
begin ___________; m:=m+1 end
end;
if ____________________ then g[c]+1
unti l ________________; writeln;
writeln (n,'character counted');
for c:='a' to 'z' do
begin write (c, p[c]:8);
if g[c] <>0 t hen write (g[c]:8); writeln
end
end.
2、[程序说明]如下程序实现带插入的树检索：给定一系列整数，输出每个整数出现的次数。为此，从空树开始，在树中检索每一个整数，如果找到，其出现次数加1，否则就作为一个新结点插入。
program csdge06(input,output );
type ref=^word;
word =record
key :integer;
count:integer;
left ,right: ref
end;
var root: ref; k :integer;
procedure printtree(w:ref; l:integer);
var i :integer;
begin if w<>nil then
---------------------
begin printtree(left,l+1);
for i:=1 to l do write(' ');
writeln (key); ---------------------- end
end;
procedure search(x:integer; var p:ref);
begin
if p=nil then
begin -------------;
with p^ do
begin key:=x; count:=1;
left =nil ; right= nil end end
else
if x< p^.key then search(x,p^.left) else ----------------
then search (x,p^.right) else -----------------
end
begin
----------------------
while not eof (input ) do
begin read(k) ; search(k,root) end;
printtree(root,0)
end.

六、在5*5格的棋盘上（如下图所示），找出一种方案。使得从1点出发，按日字跳马，可以不重复地跳经所有方格。要求用递归方法求解。
（1）详细描述你的算法；
（2）编写完整的pascal程序.