若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：

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

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

(1)

(2)

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

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

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

(1)

(2)

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

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

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

(1)

(2)

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

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

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

(1)

(2)

四、算法阅读题(本大题共4小题，每小题5分，共20分)

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

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;

            }

          }

        }

     }

(1)

(2)

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

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;

(1)

(2)

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

typedef struct {

&n