Exam 版 (精华区)

发信人: fenggao (kk), 信区: Exam
标  题: 2003年研究生入学试题数据结构答案（仅供参考）
发信站: 哈工大紫丁香 (Mon Dec 22 11:31:12 2003), 站内信件


2003年研究生入学试题数据结构答案（仅供参考）
一、填空：
1. 头指针
2. BFAWEH BFWAEH FBHAEW AFBWEH
3. K路归并、并行操作的缓冲处理、初始归并段
4. 最小
5. n-1 
6. 没有后继
二、单项选择与判断：
（一）1. A 2.D 3. D 4. A 
（二）5. 错误 6. 正确 7.正确 8.错误 9. 错误
三、简答题：
1. 堆与二元查找树均满足任一节点的元素值小于其左右儿子的值，但是若按中根顺序遍历
一颗二元查找树，将得到最终结果既递增顺序，而堆无此性质，需经过整理才得到最终结
果。
2. 用克鲁斯卡尔(Kruskal)算法较好。该算法假设G＝（V，E）是一个具有n个顶点的连通
图，T＝（V，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值
为空集。该算法的基本思想是：将G中的边按权值从小到大的顺序依次选取，若选取的边使
生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止，此时的T即为
最小生成树。
3. 算法思想：由于栈的特点是先进后出，为了模拟先进先出的队列，必须用两个栈，一个
栈（S1）用于插入元素，另一个栈（S2）用于删除元素，每次删除元素时应将前一个栈的
所有元素读出然后进入第二个栈中，这样才能达到模拟队列的效果。
四、
int DELETE (HASH F, keytype W)
{   int locate;    int yes=0;
   locate=h(W);
   if (locate!=-1) 
   {   if (F[locate].key=W) 
      {   F[locate].key=deleted;
         yes=1;
      }
      else
         ERROR("出错")；
   }
   return yes;
}
五、
设计思想：先对每个结点赋予一个层号， level域的最大值即为树的高度。
struct BTREE
{   
int LC;
   int RC;
   int LEVEL;
}; //树的抽象数据型
int level(BTREE T[maxsize])
{
   int i, count, LEVEL;
   count=LEVEL=-1;
  
   for(i=1;i<maxsize;i++)
   {
      if (T[i].LC>count) 
         count=T[i].LC;
      if (T[i].RC>count) 
         count=T[i].RC;
   } //得到这颗树共有多少个结点


   for(i=1;i<count;i++)
      T[i].level=0;

   T[1].LEVEL=1;
   for(i=1;i<count;i++)
   {
      if (T[i].LC!=0) 
         T[T[i].LC].level=T[i].level+1;
      if (T[i].RC!=0) 
         T[T[i].RC].level=T[i].level+1;
   }  //完成对每个结点赋予层号

  for(i=1;i<count;i++)
   {
      if (T[i].level>LEVEL) 
         LEVEL=T[i].level;
   } 
   return LEVEL; //返回树的高度
}

  
六、
设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图
是无环路的，那么该顶点到这些结点之间的路构成一个树，此树上的结点数应该等于该图
的结点数。若不等于（小于），则不存在这样的结点。因此，从任意结点开始，遍历此图
（先深、先广均可），若visited的结点数等于图的结点数，存在，否则不存在
设此有向图用邻接表表示，邻接表的抽象数据型如下所示：
      data firstarc  adjrex next

                  ……







struct node
{   int adjvex;
   node *next;
} //结点的型
struct g
{   vertexttype data;
   node *firstarc;
}typedef g ADJLIST; //邻接表的型

法一：广度优先遍历（使用队列）
int rbfs(ADJLIST g, int vi, vj)
{  int i, count ,yes; 
yes= 0; 
count =1；
QUEUE Q; 
   for(i=0;i<n;i++)
      visited[i]=0;
   ENQUEUE(vi,Q);
   visited[vi]=1; //初始化

   while(!EMPTY(Q)&&!yes)
   {   w=Q.front;
      p=g[w].firstarc;
      while((p!=NULL)&&!yes)
      {   w=p->adjdata;
         if(visited[w]=0)
         {   visited[w]=1;
        count++;
            ENQUEUE(w,Q);
         }
         else p=p->next;
      }
   }
if(count==V) //V为该有向图中结点总数
  yes＝1；
   return yes;
}
法二：深度优先遍历（使用栈）
int rdfs(ADJLIST g,int vi,vj)
{  int i, count ,yes; 
yes= 0; 
count =1；
STACK S;
   for(i=0;i<n;i++)
      visited[i]=0;
   PUSH(vi,S);
   visited[vi]=1; //初始化

   while(!EMPTY(S)&&(yes==0))
   {   w=TOP(S);
      p=g[w].firstarc;
      while((p!=NULL)&&visited[p->adjdata])
      {   p=p->next;
         if(p==NULL) POP(S);
         else 
         {   w=p->adjdata;
            visited[w]=1;
count++;
            PUSH(w,S);
         }
      }
   }
if(count==V) //V为该有向图中结点总数
  yes＝1；
   return yes;
}


--

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 210.46.77.132]