厦门大学1999年考研程序设计试题
一填空1hash（杂凑）技术广泛应用于查周过程，选择hash函数的主要标准是---------------------和------------------。
2在AOV网中，存在环意味着-----------------------------。这是------------的。对程序的数据流图来说，它表明存在-----------------。
3遍历图的过程实质上是-----------------------。breath-firstsearch遍历图的时间复杂度---------------depth-firstsearch遍历图的时间复杂度，两者不同之处在于-------------------------，反映在数据结构上的差别是--------------------。
4prim（普里姆）算法适用于求-------------的网的最小生成树；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个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？共计多少次？
程序设计部分
四写出下面程序的输出结果
1programcsdge01(output);
vara,b,c:intger;
fuctiontq(varx,y:intger;z:integer):integer;
beginz:=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.
2programcsdge02(output);
varp1,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^mod4);
writeln(p1^:6,p2^:6,p3^:6)
end.
3programcsdge03(output);
vara,b,c:intger;
procedurep1(varx:integer);
functionf2(y:integer):integer;
procedurep3(varz:integer);
beginz:z 2;b:=3*z
end;
beginp3(c);f2:=y cend;
beginx:=f2(b)end;
begin
a:=2;b:=1;c:=3;p1(a);
writeln(’a=’,a:4,’b=’,b:4,’c=’,c:4)
end..
4programcsdege04(output);
constn=2;
vars:array[1..n]ofchar;
procedureal(k:integer);
varch:char;i:integer;
begin
forch:=’a’to’c’do
begins[k]:=ch;
ifk=nthen
begin
fori:=1tokdo
write(s[i]:1);write(’’)
end
elseal(k 1)end
end;
beginal(1);writelnend.
五填空
1[程序说明]如下程序读入字符序列，直至读入全部26个大写英文字母时停止，输出下列内容：
（1）读入字符总数；
（2）各大写字母首次输入时读入字符顺序号（从1开始计数）；
（3）首次读入的5个大写字母出现字数；
programcsdge05(input,output);
varc:char;n,m:integer;
s,sl:-----------------------------;
p,g:array[’a’..’z’]ofinteger;
begin
s:=-----------------;sl:=[];n:=0;------------------------;
forc:=’a’to’z’do
beging[c]:=0;
p[c]:=0;end;
repeatread(c);----------------;
if-------------then
begin
s:=s-[c];p[c]:=n;
ifm<5then
begin-----------;m:=m 1end
end;
if--------------------theng[c] 1
until----------------;writeln;
writeln(n,’charactercounted’);
forc:=’a’to’z’do
beginwrite(c,p[c]:8);
ifg[c]<>0thenwrite(g[c]:8);writeln
end
end.
2[程序说明]如下程序实现带插入的树检索：给定一系列整数，输出每个整数出现的次数。为此，从空树开始，在树中检索每一个整数，如果找到，其出现次数加1，否则就作为一个新结点插入。
programcsdge06(input,output);
typeref=^word;
word=record
key:integer;
count:integer;
left,right:ref
end;
varroot:ref;k:integer;
procedureprinttree(w:ref;l:integer);
vari:integer;
beginifw<>nilthen
---------------------
beginprinttree(left,l 1);
fori:=1toldowrite(’’);
writeln(key);----------------------end
end;
proceduresearch(x:integer;varp:ref);
begin
ifp=nilthen
begin-------------;
withp^do
beginkey:=x;count:=1;
left=nil;right=nilendend
else
ifx<p^.keythensearch(x,p^.left)else----------------
thensearch(x,p^.right)else-----------------
end
begin
----------------------
whilenoteof(input)do
beginread(k);search(k,root)end;
printtree(root,0)
end.
六在5*5格的棋盘上（如下图所示），找出一种方案。使得从1点出发，按日字跳马，可以不重复地跳经所有方格。要求用递归方法求解。
（1）详细描述你的算法；（2）编写完整的pascal程序.
ab10
ac12
ae15
bc7
bd5
bf6
ce12
cf8
df6
ef10
页:
[1]