数据结构自考2009年1月真题及答案解析

假设以带头结点的单链表表示线性表，单链表的类型定义如下：

typedef int DataType;

typedef struct node {

     DataType data;

     struct node * next;

} LinkNode, * LinkList;

编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：

void f34(LinkList head) ;

设有向图邻接表定义如下：

typedef struct {

     VertexNode adjlist[ MaxVertexNum ] ;

     int n，e; //图的当前顶点数和弧数

}ALGraph; //邻接表类型

其中顶点表结点VertexNode边表结点EdgeNode结构为：

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

(1)已知某有向图存储在如图所示的邻接表G中，写出执行f32(&G)的输出;

(2)简述算法f32的功能。

int visited[ MaxNum ];

void DFS(ALGraph * G, int i) {

EdgeNode * p;

    visited [ i ] = TRUE ;

   if (G - >adjlist[ i]. firstedge = = NULL)

   printf( "% c ", G - >adjlist[ i]. vertex);

else {

   p = G - >adjlist[ i]. firstedge;

    while (p ! = NULL) {

      if ( ! visited[p ->adjvex] )

      DFS( G, p - >adjvex) ;

      p = p->next;

       }

  }

 }

  void f32 ( ALGraph * G) {

   int i;

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

           visited [ i ] = FALSE ;

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

           if ( ! visited[i] ) DFS(G, i) ;

}

下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。

#define MAXLEN 100

  typedef int KeyType;

    typedef struct {

  KeyType key;

  InfoType otherinfo;

   } NodeType ;

  typedef NodeType SqList[ MAXLEN ];

   void f33 ( SqList R, int n)

  { int i,j,k;

  NodeType t;

  i =0;

  j =n-l;

  while (i< j) {

  for ( (1) )

  if (R[k].key >R[k +l].key) {

  t = R[k];

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

 R[k +1] = t;}

  j--;

  for (k =j; k >i; k -- )

  if ( (2) ) {

  t = R[k];

  R[k] = R[k-1];

  R[k-1] = t;

}

 (3) ;

}

}

假设以二叉链表表示二叉树，其类型定义如下：

typedef struct node {

 DataType data;

 struct node * lchild, * rchild;       //左右孩子指针

} * BinTree ;

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

(1)已知以T为根指针的二叉树如图所示，写出执行f31(T)之后的返回值;

(2)简述算法f31的功能。

int f31 ( BinTree T)

{ int d;

     if ( ! T) return 0;

       d = f31 ( T - >lchild) + f31 ( T - >rchild) ;

     if (T - >lchild && T - >rchild)

   return d + 1 ;

else

  return d;

已知3阶B—树如图所示，

(1)画出将关键字6插入之后的B—树;

(2)画出在(1)所得树中插入关键字2之后的B—树。

假设以带头结点的单链表表示线性表，单链表的类型定义如下：

typedef int DataType;

typedef struct node {

        DataType data;

        struct node * next;

} LinkNode, * LinkList;

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

(1)已知初始链表如图所示，画出执行f30(head)之后的链表;

                                        题 30图

(2)简述算法f30的功能。

void f30( LinkList head)

{ LinkList p,r, s;if (head - >next) {

          r = head - >next;

          p = r->next;

         r - >next = NULL;

         while (p) {

             s =p;

                 p = p->next;

                if ( s - >data% 2 = = 0) {

                  s - >next = head - >next;

                  head - >next = s;

                   } else {

                     s - >next = r - >next;

                     r->next = s;

                      r =s;

               }

        }

      }

 }

假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。

要求：

(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值);

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。

(1)写出排序过程中前两趟的划分结果;

(2)快速排序是否是稳定的排序方法?

假设有一个形如

的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，

请回答下列问题：

(1)B数组的体积至少是多少?

(2)若存储在B[0]中，存储在B[k]中，则k值为多少?

VSAM文件的实现依赖于操作系统中的_________存取方法的功能。