int adjvex;//邻接点域

     int weight;//边的权值

     struct node *next;//链指针域

    } EdgeNode;//边表结点结构描述

    typedef struct {

      char vertex;//顶点域

      EdgeNode * firstedge;//边表头指针

    } VertexNode ;//顶点表结点结构描述

    typedef struct {

    VertexNode adjlist[MaxNum];//邻接表

    int n,e;//图中当前的顶点数和边数

    } ALGraph;//邻接表结构描述

下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。

void convertM(MGraph *G1,ALGraph *G2)

{

 int i,j;

 EdgeNode * p;

 G2->n=G1->n;

 G2->e=G1->e;

 for(i=0;i<G1->n;i++)

 {

   G2->adjlist[i].vertex=G1->vexs[i];

   G2->adjlist[i].firstedge=   (1)     ;

  }

for (i=0;i<G1->n;i++)

     for (j=0;j<G1->n;j++)

          if(G1->edges[i][j]<INFINITY)

          {

            p=(EdgeNode *) malloc(sizeof(EdgeNode));

            p->weight=   (2)   ;

            p->adjvex=j;

            p->next=G2->adjlist[i].firstedge;

                (3)     ;

          }

}

(1)

(2)

(3)

33.阅读下列算法，并回答下列问题：

(1)该算法采用何种策略进行排序?

(2)算法中R[n+1]的作用是什么?

Typedef struct {

   KeyType key;

   infoType otherinfo;

} nodeType;

typedef nodeType SqList［MAXLEN］;

void sort(SqList R,int n)

{

  //n小于MAXLEN-1

  int k;i;

  for(k=n-1;k>=1;k--)

    if(R[k].key>R[k+1].key)

    {

     R[n+1]=R[k];

     for(i=k+1;R[i].key<R[n+1].key;i++)

       R[i-1]=R[i];

      R[i-1]=R[n+1];

    }

}

五、算法设计题(本题共10分)

34.假设二叉树T采用如下定义的存储结构：

   typedef struct node {

     DataType data;

     struct node *lchild,*rchild,*parent;

   }PBinTree;

   其中，结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针。

全国2001年10月高等教育自学考试

数据结构试题

课程代码：02331

第一部分  选择题(30分)

一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（   ）

   A．计算机程序                   B．解决问题的计算方法

   C．排序算法