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

35． 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

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

lklist create_iklist2()   /*直接实现的建表算法。*/

     { head=malloc(size);

       p=head;

       scanf("%",&x);

       while(X!='$')

       { q=malloc(size);

         q—＞data=x;

         p—＞next=q;

         ______;

         scanf("%",&x);

       }

         ______;

         return(head);

       }

  此算法的量级为______。

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

void delete_lklist(1klist head,int i)

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

      if(______)

        { q=______;

          p—＞next=q—＞next;

          free(q);

        }

    else error("不存在第i个结点")

  }

33． 以下为顺序表的定位运算，分析算法，请在______处用正确的语句予以填充。

int locate_sqlist(sqlist L,datatype X)

  /*在顺序表L中查找第一个值等于X的结点。若找到回传该结点序号；否则回传0*/{______；

  while((i≤L.last)&&(L.data[i-1]!=x))i++;

  if(______)return(i);

  else return(0);

  }

31． 以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在______上填充合适的语句。

int search_closehash(keyt,ype K,closehashHL)

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

    i=d;

    while(HL[i].key!=K&&(i!=d-1)i=______;)/*未成功且未查遍整个HL时继

                                                 续扫描*/

    if(______)return(i);   /*查找成功*/

    else return(-1);       /*查找失败*/

  }

判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。

(1,5,7,25,21,8,8,42)

30． (3,9,5,8,4,17,21,6)

27． 已知有一关键字序列为{97,86,53,108,72,34,215,146,11,68}，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

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

26． 已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

25． 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为______，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为______。

22． 在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的______加上排在aij前面的元素所占用的单元数。

23． ______查找法的平均查找长度与元素个数n无关。

24． 在计算机软件系统中，有两种处理字符串长度的方法：一种是采用______，第二种是设置______。

20． 文件的记录均存放在数据集中，数据集中的一个结点称为______，它是一个______操作的基本单位。

21． 设线性表L=(a₁，a₂，…，a_n)(n＞2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b，若检索不成功，则s和b的数量关系是______。

19． 若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的______个结点。

18． 对磁带上的顺序文件进行更新某个记录时，必须______整个文件。而在顺序文件的最后添加新的记录时，则不必______整个文件。

16． 在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的______。它通常采用______结构来组织。

17． 数组A[1..10，-2..6，2..8]以行优先顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5,0,7]的存储地址为______。

15． 假设有一个数组，它的行号从0到8，列号从0到10，数组中每个元素所占的存储空间为3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。

14． 线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )

13． 串是一种特殊的线性表，其特殊性体现在( )

12． 如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 ( )

11． 带头结点的单链表Head为空的判定条件是( )

10． 堆是一个键值序列(k₁，k₂，k…，k₁…，k₀)，对i=1，2…，[n/2]，满足( )

8． 链栈与顺序栈相比，有一个比较明显的优点即( )

9． 串是任意有限个( )

7． 如果T₂是由有序树T转换而来的二叉树，那么T中结点的后序就是T₂中结点的( )

6． 设数组A[0,m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是( )

4． 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )

5． 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( )

2． 对广义表((a)，(b))进行下面的操作head(head((a)，(b)))后的结果是( )

3． 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是 ( )

1． 堆排序的最坏时间复杂度为( )