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

34． 采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。

33． 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在______处用适当的语句予以填充。

Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b)

  {(*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu

    if(a.tu)

      { q=1;

         for(col=1;______;col++)

         for(p=1;p＜=a.tu;p++)

          if(______)==col)

           { (*b).data[q].i=a.data[p].j;

             (*b).data[q].j=a.data[p].i;

             (*b).data[q].v=a.data[p].v;

             ______;

           }

      }

  } 

32． 以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在______上填充合适的语句。

pointer research_openhash(keytypeK,openhash HP)

  {i=H(K);   /*计算K的散列地址*/

    p=HP[i];   /*i的同义词子表表头指针传给P*/

    while(______)p=p—＞next; /*未达到表尾且未找到时，继续扫描*/

    ______;

  } 

30． INITIATE()的功能是建立一个空表。请在______处填上正确的语句。

lklist initiate_lklist()  /*建立一空表*/ 

{______;

______;

return(t);

}

31． 以下运算实现在顺序栈上的退栈，请在______处用适当的语句予以填充。

int Pop(SqStackTp*sq,DataType*x)

     { if(sq—＞top==0){error("下溢");return(0);)

        else{*x=______;

                ______;

                return(1);

     }

  } 

27． 对于如下一个有序的关键字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为18的关键字，则经过几次比较之后能查找成功?

29． 已知数据序列为{12,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

28． 已知有一关键字序列为{505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。

26． 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点v_i表示)。

25． 查找表按其所包括的运算的不同分为______查找表和______查找表。