全国自考（数据结构）模拟试卷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． 查找表按其所包括的运算的不同分为______查找表和______查找表。

24． 在具有n个单元的循环队列中，队满时共有______个元素。

23． 在线性表的顺序存储中，假设每个结点所占用的存储空间为c，且第一个单元的存储地址则是该结点的存储地址，设开始结点a₁的存储地址是LOC(a₁)，则结点a₁存储地址LOC(a₁)可以通过下式得到______。

20． 数组0[1……n]表示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为______。

22． 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______。

21． 一般来说，数组中的元素具有______的数据类型，并且数组元素的下标的上界和下界都是______的。

19． 在二叉排序树中，其左子树中任何一个结点的关键字一定______其右子树的各结点的关键字。

18． 对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为______，如果k不在表中，则需要进行______次比较后才能确定查找失败。

17． 设有两个串p和q，求q在p中首次出现的位置的运算叫______。

16． 对于一个具有n个结点的单链表，在已知p结点后插入一个新结点的事件的时间复杂性为______，在给定值为x的结点后插入一个新结点的时间复杂性为______。

14． 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )

15． 在下面的排序方法中，属于不稳定的排序方法的是( )

13． 在一非空二叉树的中序遍历序列中，根结点的右边( )

11． 线索二叉树是一种( )结构。

12． 排序的重要目的是为了以后对已排序的数据元素进行( )

10． 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( )

9． 设散列函数为H(k)=k mod7，一组关键码为23,14,9,6,30,12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为(  )

7． 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。

8． 在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为( )

4． 非空的单循环链表L的尾结点P↑，满足( )

5． 在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )

6． 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )

3． 带头结点的单链表head为空的判断条件是( )

2． 一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )

1． 对文件进行直接存取的是根据( )