您的位置:自考365 > 复习指导 > 历年试题 > 北大“数据结构”上机考试题(04年11月18)

北大“数据结构”上机考试题(04年11月18)

2006-06-20 14:36  北京自考热线 【 】【我要纠错

  1、求拓朴排序后结果及用矩阵表示……输入形式为:n  1  2  1 3 ……(就是上机练习题上的哪个题,不过多加了一个用矩阵表示)……

  2、输入一串整数,以相反次序输出

  第1题我做的答案是这样的,第2题太简单就不用了。

  //有的未加判断,矩阵输出及拓扑排序

#include <stdio.h>
#include <malloc.h>
#include <iostream.h>
#define MAX 100

typedef struct {
int arcs[MAX][MAX];
int vexnum;
}Mgraph;

void input(Mgraph *mgraph,int i,int *count1)
{
int a,b,c1=0;
for(int j=0;j<i;j++)
  for(int k=0;k<i;k++)
   mgraph->arcs[j][k]=0;
  while(1){
   printf("输入(i j),(-1 -1)结束:");
   scanf("%d%d",&a,&b);
   if(a==-1 && b==-1)
    break;
   else
   {
    mgraph->arcs[a][b]=1;continue;
   }
  }
  for (int k=0;k<i;k++){
   int c=0;
   for(int m=0;m<i;m++){
    if(mgraph->arcs[m][k]==1)
     c++;
   }
    count1[k]=c;
  }
  printf("\n矩阵为:\n");
  for(int l=0;l<i;l++)
   for(int m=0;m<i;m++){
     printf("%3d",mgraph->arcs[l][m]);
     c1=c1+1;
     if(c1==i){
      printf("\n");
      c1=0;
     }
   }
}

//拓扑排序
void topsort(Mgraph * mgraph,int i,int *count){
int a,b,c=0,s=-1;
for(a=0;a<i;a++){
  if(count[a]==0){
   count[a]=s;
   s=a;
  }
}
while(s!=-1){
  printf("V(%d)  ",s);
  c++;
  a=s;
  s=count[a];
  for(b=0;b<i;b++){
   if(mgraph->arcs[a][b]){
    count[b]--;
    if (count[b]==0){
     count[b]=s;
     s=b;
    }

   }

  }
}
}

void main(){
Mgraph mgraph;
int i;
printf("输入顶点个数:");
scanf("%d",&i);
int count1[MAX];
input(&mgraph,i,count1);
topsort(&mgraph,i,count1);

}

本文转载链接:北大“数据结构”上机考试题(04年11月18)

分享到:
  • 站内搜索
  • 课程搜索
  • 试题搜索

热门搜索:教材 报名 查分 免考 考试计划