厦门大学2001研究生入学考试数据结构试题

厦门大学2001研究生入学考试数据结构试题

厦门大学2001研究生入学考试数据结构试题
厦门大学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^.tag=0时)
f(L)= f(L^Link)+ f(L^sublist) （当L^.tag=1时）
故求广义表GL的各数据域值之和的递归函数如下：
Function f(L:glist):integer;
  begin
if L=Nil
  then f:=0
  else
    if L^.tag=0
     then f:=1+f(L^.link)
     else f:=f(L^.link)+f(L^.sublist)
  end;

三、解答题（本题12分）
已知连通图如下：

给出本图的邻接表。
若从顶点B出发对该图进行遍历，在问题1的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列。
写出按深度优先搜索的递归程序。
答案：1、该图的邻接表为

2、若从顶点B出发对该图进行遍历，由建立的邻接表得到本图的深度优先搜索和广度优先搜索的顶点序列分别为：
B、A、D、C、E、F；
B、A、C、E、D、F；
3、深度优先搜索的递归程序为：
#define Maxsize 100
typedef struct rcnode
{
int adjvex;
struct arcnode *node;
infotype info;
}Arcnode;
  typedef struct vnode
{
telemtype data;
arcnode *firstarc;
}vnode,adjlist[Maxsize];
typedef struct
{
adjlist ver;
int vexnum,arcnum;
int kind;
}algraph;

void dfstraverse(algraph G)
/*深度优先搜索队无向图G的递归算法*/
｛
int visited[maxsize];
for(v=0;v<G.vexnum;i++)
visited[v]=0;
for(v=0;v<G.vexnum;i++)
  if(!visited[v])
DFS(G,v,visited);
｝

void DFS(algraph G,int v,int visited[])
/*从第V个顶点出发递归的深度优先遍历图G*/
｛
visited[v]=1;
printf(G.ver[v]-->data);
for(w=first_Adjv(G,v);w;w=next_Adj(G,v,w))
if (!visited[w])
  DFS(G,w);/*对V的尚未访问的邻接结点递归调用DFS*/
｝
四、解答题（本题8分）
判断下列两个序列是否为堆，若不是，按照对序列建立堆的思想把他调整为堆，用图表示建堆的过程。
1．（1、5、7、20、18、8、8、40）
2．（18、9、5、8、4、17、21、6）

答案：根据堆的定义，序列1为堆，序列2不是堆。

好象不是吧！对不对啊？？