厦门大学2001年研究生入学考试.doc

厦门大学2001年研究生入学考试
数据结构试题(部分、附答案)
一、程序阅读题(本题10分)
下面的算法为读入一段正文,统计所出现的字符,并计算它们出现的频数。每遇到一个字符,就从链表的根到链头扫描链表,如果在链表中该字符被找到,它的频数就增加1,否则就插入该字符的一个节点到表头,相应频数为1。当输入字符为”#”时,程序结束。请在空白处填入适当的内容。
Program list(input,output);
Type ref=^word;
Word=record
Key: char;
Cont: integer;
Next: ref;
end;
var k:char;
Sentinel, root: ref;
Procedure search ([1])
var w:ref;
Begin
w:=root;
sentinel^key:=x;
while w^.key<>x do
[2];
if [3]
then w^count:=w^.count+1
else
begin
w:=root;
[4];
with root^ do
begin
key:=x;count:=1;next:=w
end
end
End;
Procedure display(w:ref);
begin
while w<>sentinel do
begin
writeln(w^.key,w^.count);
w:=w^.next;
end
End;
Begin
new(sentinel);
with sentinel^ do
begin
key:='#';
count:=0;
next:=nil
end;
root:=sentinel;
while k<>'#' do
begin
search(k,root);
read(k);
end;
display [5];
End.
答案:[1]:x:char,var root:ref
[2]:w:=w^.next
[3]:w^.key:=x
[4]:new(root)
[5]:(root)
二、算法题(本题9分)
广义表GL=(a1,a2,……an),其中ak(k=1,2,3…..n)或是单个数据元素(原子),或仍然是一个广义表。给定如下有关广义表的类型定义:
type
tagtype=0..1;
glist=^gnode;
link:glist;case tag:tagtyoe of
0(data:integer);
1(sublist:glist);
end;
编写一个过程或函数计算一个广义表的所有元素节点数据之和,例如对广义表(3(2,4),(6,3))数据与之和为23。
答案:可以看出,该存储结构为首尾存储结构,求广义表GL=(a1,a2,….an)的各数据域值之和本质上就是遍历广义表并对遍历的数据域求和。这里可采用递归程序来实现。对给定指向的广义表GL=(a1,a2,
……an)的指针L,广义表GL的各数据域值之和f(L)为
f(L)=0 (当L为空时)
f(L)=1+ f(L^Link) (当L