Exam 版 (精华区)

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


2001年研究生入学试题数据结构答案(仅供参考)
一、填空:
1.O(1) O(n)
2.5 3
3. 完全 退化的单链树
4.i-1
5.O(n2)
二、选择填空:
1.(1) 2.(3) 3.(3) 4.(3) 5.(4) 
三、回答下列问题:
1. 数据结构是指数据元素之间抽象的相互关系,并不涉及数据元素的具体内容。而数据类
型指的是具体数据所属的类型,两者概念不同。
2. 当用数组表示排队时,我们把数组看成一个环形,即令数组中第一个元素紧跟在其最末
一个单元之后,就行成了一个循环队列。
3. 在二元树的左右链表示法中,用线索取代原来的^链。当lchild为空时,令其指向按中
根遍历时的前导结点;当rchild为空时,令其指向按中根遍历时的后继结点。这样形成的
二元树称为线索二元树。
4. 指从任一结点开始,沿着箭头所指方向,依次访问每个结点且只访问一次的过程。
5. 索引文件是在主文件之外再建立一个指示关键字与其物理记录之间的对应关系的表,这
种表称为索引表。索引表与主文件共同构成索引文件。顺序存放的索引文件,称为索引顺
序文件。
四、
(1)      (2)               (3)  






(4)







将此图顺时针旋转45度即所求

五、
  BOOL judge (List &L)
{   POSITION p,q;
   BOOL a=TURE;
   p=FIRST(L); q=p->next;
   while ((p->next!=NULL)&&(a=ture))
   {   if (p->element>q->element) 
      {   p=q;
         q=p->next;
      }
      else
         a=FALSE;
   }
   return a;
}
六、
(1) 是堆 
(2) 不是堆,成堆过程为:
  a.                  b.









c.                  d.













七、 
-1   0   …………   Maxsize-1   maxsize
typedef struct 
{
   elementtype STACK[maxsize];
   int top[2];
} dqstype s;  //定义抽象数据型
void initialize(dqstype s) //初始化
{
   s->top[0]=-1;
   s->top[1]=maxsize;
}

int PUSH (dqstype s,int i,elementtype x) //i为控制器,i=0时对S1操作,i=1时对S2操

{
   if(s->top[0]==s->top[1]-1)
   {   prinft("栈满");
      return 0;
   }
   if((i!=0)&&(i!=1))
   {   prinft("参数出错");
      return 0;
   }
   if(I==0) //对S1操作
   {   s->top[i]++;
      s->stack[s->top[i]]=x;
   }
   else  //对S2操作
   {   s->top[i]--;
      s->stack[s->top[i]]=x;
   }
   return 1;
}

int POP(dqstype s) 
{
   if(s->top[0]==s->top[1]-1)
   {   prinft("栈满");
      return 0;
   }
   if((i!=0)&&(i!=1))
   {   prinft("参数出错");
      return 0;
   }
   if(i==0) s->top[i]--;
   else   s->top[i]++;
   return 1;
}
八、
             a: 1011
                 b: 111
                 c: 1010
                 d: 110
                 e: 0
                 f: 100
九、
邻接表的抽象数据型如下所示:
      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; int yes=0; 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)
         {   if(w==vj) yes=1;
            visited[w]=1;
            ENQUEUE(w,Q);
         }
         else p=p->next;
      }
   }
   return yes;
}
法二:深度优先遍历(使用栈)
int rdfs(ADJLIST g,int vi,vj)
{  int i; int yes=0; 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;
            if(w==vj) yes==1;
            visited[w]=1;
            PUSH(w,S);
         }
      }
   }
   return yes;
}


--

※ 来源:.哈工大紫丁香 bbs.hit.edu.cn [FROM: 210.46.77.132]
[百宝箱] [返回首页] [上级目录] [根目录] [返回顶部] [刷新] [返回]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:3.264毫秒