28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

    (1)画出该图的图形；

   （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

29．已知一个散列表如下图所示：

      0   1    2    3    4   5    6    7   8   9    10   11   12

其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：

      h_i=(h(key)+ *h1(key))%m    =0,1,…，m－1

其中

    h1(key)=key%11+1

回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

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

30．下列算法的功能是比较两个链串的大小，其返回值为：

               comstr(s₁,s₂)=    

请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2)

{//s1和s2为两个链串的头指针

   while(s1&&s2){

      if(s1－>date<s2－>date)return－1；

      if(s1－>date>s2－>date)return1；

          ①    ；

          ②    ；

       }    

       if(  ③   )return－1；

       if(  ④   )return1；

            ⑤   ；

     }

①

②

③

④

⑤

31．阅读下面的算法

       LinkList mynote(LinkList L)

       {//L是不带头结点的单链表的头指针

             if(L&&L->next){

                  q=L；L=L－>next；p=L；

        S1：       while(p－>next) p=p－>next；

        S2：       p－>next=q；q－>next=NULL；

              }

              return  L；

            }

    请回答下列问题：

   （1）说明语句S1的功能；

 &