全国自考（数据结构）模拟试卷2

35． 下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的一填上正确的语句。

int dlink_symmetry(dlklist s)

  {j=true;

    p=s—＞next;

    q=s—＞prior;

    while(p!=q)&(______)

      if(p—＞data=q—＞data)

         { (______);

        (______);

         }

      else

           j=false;

       return(j);

  }

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

int locate_iklist(1klist head,datatype x)

  /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/

    { p=head;j=O;

      while(______){p=p—＞next;j++;}

      if(p—＞data==x)return(j);

      else{return(0);

    }

36． 若输入12000个不同的整数，其值介于0和19999之间，采用散列表存储这些数，散列函数为h(k)=k/2，请设计实现的算法。

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

Bfs(GraphTp g,int v)

    { QueptrTp Q;

    ArcNodeTp*P;

    InitQueue(&Q);

    printf("%"”,v);

    visited[v]=1;

    ______

    while(!EmptyQueue(Q))

    {______;

    p=g.adjlist[v].firstarc;

    while(p! =NULL)

    { if(! visited[p—＞adjvex])

    { printf("%"”,p—＞adjvex);

      visited[p—＞adjvex]=1);

      EnQueue(&Q，p—＞adjvex);

    }

    ______;

    }

   }

  }

32． 以下运算实现在循环队上取队头，请在______处用适当的语句予以填充。

int GetHead(CycqueueTp sq,DataType*x)

       { if(sq.rear==______return(0);

          else{*x=sq.data[______];

               return(1);

              }

       }

31． 请画出二叉树的五种基本形态。

30． 已知散列函数为H(K)=K mod 12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

28． 以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。

29． 假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

其中front和rear分别是队头和队尾指针。

求：循环队列中元素的个数?

27． 用单链表给出B(x)的存储表示。