22． 在串的链式存储结构中，有一个串S1="ejidc"，我们假设存储时结点的大小为1，并设指针占有4个字节，则链串的存储密度为______，又假设串S2="abcdefg"在存储时我们设定结点的大小为4，指针占有4个字节，则此链串的存储密度为______。

34． 设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。

32． 以下为单链表的插入运算，分析算法，请在______处填上正确的语句。

oid insert_lklist(lklist head,datatypex,int i)

  /*在表head的第i个位置上插入一个以x为值的新结点*/

  {p=find_lklist(head,i-1);

    if(p==NULL)error("不存在第i个位置");

    else{s=______;s—＞data=x;

         s—＞next=______;

         p—＞next=s;

        }

  }

33． 根据文字说明，请在以下______处填充适当的语句。 采用静态链表作存储结构，设置一个大小为2n-1的数组，令数组的每个元素由四个域组成：wt是结点的权值；lehild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：

typedef struet

  { float wt;   /*权值*/

     int parent,lchild rchild;   /*指针域*/

  }node;

  typedef node hftree[2*n-1];

  在这种存储结构上的哈夫曼算法可描述如下：

  void huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/

  {int i,j,x,y;

    float m,n;

    for(i=0;i＜2*k-1;i++)

    { T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;

      if(______)T[i].wt=W[i];

           else T[i].wt=0

    }

  for(i=0;i＜k-1;i++)

     { x=0;y=0;m=maxint;n=maxint;

       for(j=0;j＜k-i,j++)

         if(T[j].wt＜m)&&(T[j].parent==-1){n=m;y=___;m=___;x=j;}

             else if(T[j].wt＜n)&&(T[j].parent==-1)){n=T[j].wt;y=j;)

  }

      T[x].parent=______;T[y].parent=______;

      T[k+i].wt=______;

      T[k+i].lchild=______;T[k+i].rchild=______;

  }

30． 以下为单链表的建表算法，分析算法，请在______处填上正确的语句。

lklist create_1klistl()

  /*通过调用intiate_lklist和insetr_lklist算法实现的建表算法。假定$是结束标志*/

  {ininiate_lklist(head);

       i=1;

       scanf("%",&x);

       while(x!=$)

         {______;

          ______;

          scanf("%f",&x);

         }

       return(head);

  }

  该建表算法的时间复杂性约等于______，其量级为______。

31． 以下是图的深度优先搜索算法，请在______处填充适当的语句。

Dfs(GraphTp g,int v)

  {ArcNodeTp*P;

    printf("%",v);

    visited[v]=1;

    p=______;

    while(p!=NULL)

    {if(!______)Dfs(g,p—＞adjvex);

    p=______;

    }

  }

28． 在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?

29． 已知有如右图所示的一棵树，请将其转化成二叉树。

27． 假设一棵具有12个结点的二叉树的存储结构如下图所示，其中left和right分别表示此结点左、右孩子的序号，data表示此结点的数据，根结点为编号为4的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题：

(1)写出前序遍历、中序遍历和后序遍历此二叉树时的遍历序列。

(2)求出此树的高度并分析叶结点的个数。

(3)结点E的双亲及子孙分别是什么?

26． 已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264)，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。

25． 由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为______。