一 填空
1 hash（杂凑）技术广泛应用于查周过程，选择hash函数的主要标准是---------------------和------------------。
2 在 AOV网 中，存在环意味着-----------------------------。这是------------的。对程序的数据流图来说，它表明存在-----------------。
3 遍历图的过程实质上是-----------------------。breath-first search遍历图的时间复杂度---------------depth-first search遍历图的时间复杂度，两者不同之处在于-------------------------，反映在数据结构上的差别是--------------------。
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程序.
