武汉科技大学2006年数据结构考研试题答案

一、
void c1_1(Linklist A, Linklist B, Linklist &C)
{
        LNode *pa=A->next, *pb=B->next,*pc,*s,*r;
        C=( LNode*)malloc(sizeof(LNode));
        C->next=null;
        r=C;
        while(pa)
        {
                s=( LNode*)malloc(sizeof(LNode));
                s->data=pa->data;s->next=null;
                r->next=s;r=s;
                pa=pa->next;
}
while(pb)
{
        pc=C->next;
        while(pc&&pb->data!=pc->data)
                pc=pc->next;
        if(pc==null)
        {
                s=( LNode*)malloc(sizeof(LNode));
                s->data=pb->data;s->next=null;
                r->next=s;
                r=s;
}
        pb=pb-next;
}
}
void c1_2(Linklist A, Linklist B, Linklist &C)
{
        LNode *pa=A->next, *pb, *s,*r;
        C=( LNode*)malloc(sizeof(LNode));
        C->next=null;
        r=C;
        while(pa)
        {        pb=B->next;
                while(pb&&pb->data!=pa->data)
                        pb=pb->next;
        if(pb==null)
        {
                s=( LNode*)malloc(sizeof(LNode));
                s->data=pa->data;s->next=null;
                r->next=s;
                r=s;
}
        pa=pa-next;
}
}

int ListLength(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
   int i=0;
   LinkList p=L->next; /* p指向第一个结点 */
   while(p) /* 没到表尾 */
   {
     i++;
     p=p->next;
   }
   return i;
}
二、
Typedef struct Lnode{
        ElemType data;
        char sex;
        floar stature;
        struct LNode *next;
}LNode,*Linklist;
void DisCreat(LinkedList A)
{
LinkedList B,C;
LNode *p,*r,*b1,*b2,*c1,*c2;
B=C=null;
p=A; ∥p为工作指针。
while(p)
{r=p->next; ∥暂存p的后继。
if (p->sex==’M’)∥男生放入B表。
{if(B==null){p->next=null;B=p;}
else{b1=null;b2=B;
                while(b2&&p->stature>b2->stature)
{b1=b2;b2=b2->next;}
p->next=b2; b1->next=p;}
                }
else∥女生放入C表
{if(C==null){p->next=null;C=p;}
else{c1=null;c2=C;
                while(c2&&p->stature>c2->stature)
{c1=c2;c2=c2->next;}
p->next=c2; c1->next=p;}
        }
p=r;∥p指向新的待处理结点。
}
三、
采用输出受限的双端队列
void Train_Rearrange(char *train)
//这里用字符串train表示火车，’P’表示硬座，’H’表示硬卧，’S’表示软卧。
{
   r=train;
   InitDQueue(Q);
   while(*r)
   {
      if(*r=‘P’)
      {
         不入队列，直接输出；
      }
      else if(*r=‘S’)
      {
         EnDQueue(Q, *r, 0);//从头端入队
      }
      else
      {
         EnDQueue(Q, *r, 1);//从尾端入队
}
r++;
   }//while
   while(!DQueueEmpty(Q))
   {
      DeDQueue(Q);//从头端出队
   }//while
}//Train_Rearrange
四、
(1)
void compress (int A[n][n], int B[ ], int n)
{//将三对角矩阵A[0..n-1, 0..n-1]三条对角线上的元素逐行存放于数组B中
K=0;
for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      if (A[j]!=0) B[k++]= A[j];
}
(2) 已知k求i、j时，则下标的对应关系是：
i = (k+1)/3
j = k-2i
void uncompress (int B[ ], int A[n][n], int n)
{//由数组B[0..3n-3]确定三对角矩阵A[0..n-1, 0..n-1]
for (i=0; i<n; i++)
    for (j=0; j<n; j++)
A[j] =0;
  for(k=0; k<=3*n-3; k++)
    { i=(k+1)/3;
     j=k-2*i;
    A[j]=B[k];
    }
}
(3)
void TransMatrix(int B[ ], int C[ ],int n)
{
        C[0]=B[0];
        For(k=1;k<n;k++)
        {        C[k+1]=B[k];
                k++;
                C[k-1]=B[k];
                k++;
                C[k]=A[k];
        }
}
五、
用二叉树表示该大家族，可以用根结点表示父或母（祖先），根结点的左子女表示配偶，配偶的右子女表示子女。这种二叉树可以看成类似树的孩子兄弟链表表示法；根结点是父或母，根无右子女，左子女表示配偶，配偶的右子女（右子女的右子女等）均可看成兄弟姐妹（即父母的所有子女），这些结点又可成为新的双亲。首先递归查找某家族成员结点，若查找成功，要么其左子女是配偶，配偶的右子女及右子女的右子女等均为父母的子女，要么其右子女及右子女的右子女等均为父母的子女。
BiTree Search(BiTree t,ElemType parent)//在二叉树上查找值为parent的结点
{if(t==null) return (null);            //二叉树上无parent结点
else if(t->data==parent) return(t);   //查找成功
p=Search(t->lchild, parent); p=Search(t->rchild, parent); }
}//结束Search
void PrintSons(BiTree t,ElemType p)//在二叉树上查找结点值为p的所有的子女
{p=Serach(t,p);                     //在二叉树t上查找父结点p
if(p!=null)                        //存在父结点
{
if(p->lchild!=null){q=p->lchild; q=q->rchild;}
//先指向其配偶结点，再找到第一个子女
else q=p->rchild;
   while(q!=null) {printf(q->data); q=q->rchild;} //输出所有子女
     }
}//结束PrintSons
六、
该题可用求每对顶点间最短路径的FLOYD算法求解。求出每一顶点到其它顶点的最短路径。在每个顶点到其它顶点的最短路径中，选出最长的一条。因为有n个顶点，所以有n条,在这n条最长路径中找出最短一条，它的出发点为所求。
void Signal(AdjMatrix w,int n)
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (w[k]+w[k][j]<w[j]) w[j]=w[k]+w[k][j];
m=MAXINT; //设定m为机器内最大整数。
for (i=1;i<=n;i++) //求最长路径中最短的一条。
{s=0;
for (j=1;j<=n;j++) //求从某地区i（1<=i<=n）到其它地区的最长路径。
if (w[j]>s) s=w[j];
if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。
Printf(“供应站应建在%d地区\n”,i);
}//for
}
七、
void FindInDegree(ALGraph G,int indegree[])
{ /* 求顶点的入度*/
   int i;
   ArcNode *p;
   for(i=0;i<G.vexnum;i++)
     indegree=0; /* 赋初值 */
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices.firstarc;
     while(p)
     {
       indegree[p->adjvex]++;
       p=p->nextarc;
     }
   }
}
typedef int SElemType; /* 栈类型 */
Status TopologicalSort(ALGraph G)
{ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。*/
   int i,k,count,indegree[MAX_VERTEX_NUM],term;
   SqStack S1,S2;
   ArcNode *p;
   FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */
   InitStack(&S1); /* 初始化栈 */
InitStack(&S2);
   for(i=0;i<G.vexnum;++i) /* 建零入度顶点栈S */
     if(!indegree)
       Push(&S1,i); /* 入度为0者进栈 */
   count=0; /* 对输出顶点计数 */
        term=1;//学期
   while(!StackEmpty(S1))
   { /* 栈不空 */
     while(!StackEmpty(S1))
{Pop(&S,&i); Push(&S2,i)}
         if (!StackEmpty(S2))
{ printf("第%d个学期的课程有：",term);
StackTraverse(S2,print);
term++;
}
while(!StackEmpty(S2))
{
     ++count;
     for(p=G.vertices.firstarc;p;p=p->nextarc)
     { /* 对i号顶点的每个邻接点的入度减1 */
       k=p->adjvex;
       if(!(--indegree[k])) /* 若入度减为0,则入栈 */
         Push(&S1,k);
}
}
   }
   if(count<G.vexnum) return ERROR;
   else  return OK;
}
八、
该问题类似于五叉路口交通灯的设计，采用无向图的数据结构，将每个项目视为顶点，凡是一个运动员同时报名参加的项目，表示不能在同一单位时间进行，则用边连接发生冲突的顶点，然后进行染色分析。
//判断图g中的第i个结点是否与所有已着色为count的结点都不相邻
bool isnotadjacent(ALGraph& g, int i, int count)
{
    EdgeNode* p=g.vertices.firstedge ;  //p指向邻接表第i个结点的链表头
    while(p){
        if(g.vertices [p->adjvex].color ==count)
            return false;
        p=p->nextedge;
    }
    return true;
}

//判断图g是否已全部着色
bool isallcolored(ALGraph& g)
{
    for(int i=0;i<g.vexnum;i++)
        if(g.vertices.color==0)
            return false;
    return true;
}

//依图中结点的度数从大到小的顺序给图着色,返回着色数
int color(ALGraph& g)
{
    int i;
    int count=0;  //记录着色数
    while(!isallcolored(g))
    {
        count++;
        for(i=0;i<g.vexnum;i++)
            if(g.vertices.color==0){
                g.vertices.color=count;
                break;
            }  //先找到第一个未着色的结点进行着色
        for(i++;i<g.vexnum;i++){
            //如果第i个结点尚未着色并且该结点与刚着色为count的结点
            //都不相邻,则将该结点着色为count
            if(g.vertices.color==0 && isnotadjacent(g,i,count))
                g.vertices .color=count;
        }//for
    }//while
    return count;