Exam 版 (精华区)

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


2002年研究生入学试题数据结构答案（仅供参考）
一、填空：
1. n-1
2. 5
3. n/2  n-1
4. 16
5. 25 26
6. 2n-1 
7. 顺序 有序 
8. O(nlog2n) O(dn)
9. 2e
10. n+1
二、单项选择：
1. C 2. B 3. B 4. B 5. A G 6. D 7. B 
三、判断
1. 错误  2. 正确 3.正确 4. 正确 5. 错误 6. 正确 7. 正确 8. 正确
9. 正确 10. 错误
四、简答：
1.







2. 稳定分类是指如果在分类之前存在关系A[i].key=A[j].key，1<=i<j<=n 经分类处理之
后，A[i]和A[j]原来的数据分别被移到A[i1]和A[j1]，并且i1，j1满足关系1<= i1< j1<=
n我们称这种分类是稳定的。（例子可任意选取）
3. 拓扑分类是指利用先广搜索算法，将无环路有向图的每个顶点排列成一个线性序列，使
当从结点i到结点j存在一条边，则在线性序列中，将i排在j的前边。
五、 






六、
(1)           (2)          (3) 






(4)           (5)






七、
邻接表的抽象数据型如下所示：
      data firstarc  adjrex next

                  ……







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

void create (ADJLIST g,int a[n][n])
{
   int i,j;
   for(i=0;i<n;i++)
   {
      g[i].data=i;
      g[i].firstarc=NULL;
   }

  for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         if(a[i][j]==1)
         {
            p=new node;
            p->adjvex=j;
            p->next=g[i].firstarc;
            g[i].firstarc=p;
         }
}
八、
int n0,n1,n2;

void count(BTREE *b)
{
   if(b!=NULL)
   {
      if((b->lchild==NULL)&&(b->rchild==NULL)) n0++;
      if((b->lchild==NULL)&&(b->rchild!=NULL)) n1++;
      if((b->lchild!=NULL)&&(b->rchild==NULL)) n1++;
      if((b->lchild!=NULL)&&(b->rchild!=NULL)) n2++;
    
      count(b->lchild);
      count(b->rchild);
   }
}

九、
int count(ADJLIST g)
{
   int m=0;
   for(i=0;i<n;i++)
      visited[i]=0;
   for(i=0;i<n;i++)
      if(visited[i]=0)
      {
         dfs(g,i);
         m++;
      }
      return m;
}

void dfs(ADJLIST g,int t)
{
   visited[i]=1;
   p=g[v].firstarc;
   while(p!=NULL)
   {
      w=p->data;
      if(visited[i]=0)
         dfs(g,w);
      p=p->next;
   }
}


十、
void move(int A[n])
{
   x=A[0]; i=0; j=n-1;
   while(i<j)
   {
      while((A[j]%2==1)&&(i<j)) j--;
      if(i<j)
      {
         A[i]=A[j];
         i++;
      }
      while((A[j]%2==0)&&(i<j)) j++;
      if(i<j)
      {
         A[j]=A[i];
         i--;
      }
      A[i]=x;
   }
}


十一、
void push(int a[m],element x)
{
   if(top==r+1)
      if(f==0)
         error("上溢");
     else
      {
         for(i=0;i<r-f;i++)
            a[i]=a[i+1];
        top--;
        a[top]=x;
      }
   else
   {
      top--;
      a[top]=x;
   }
}

void enqueue(int a[m],element x)
{
   if(top==r+1)
      if(f==0)
         error("上溢");
     else
      {
         for(i=0;i<r-f;i++)
            a[i]=a[i+1];
        r++;
        a[r]=x;
      }
   else
   {
      r++;
      a[r]=x;
   }


--

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