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

33． 以下将a_h，…a_m，和a_m+1…a_n，两个有序序列(它们相应的关键字值满足K_h≤K_m，K_m+1≤…K_n，)合并成一个有序序列R_h，…，R_n，(使其关键字值满足K_h，'≤…≤K_n，')。请分析算法，并在______上填充适当的语句。

void merge(list a,list R,int h,int m,int n)

  {i=h;k=h;j=m+1;

    while((i＜m)&&(j＜=n))

    { if(a[i].key<=a[i].key){R[k]=______;______;}

      else{R[k]=______;______;}

    k++;

    }

    while(i＜=______){R[k]=a[i];i++;k++;)

    while(j＜=______){R[k]=a[j];j++;k++;}

  }

  此算法的执行时间为______。

34． 有两个磁盘文件A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件C中。

31． 以下运算实现在链队上的出队列，请在______处用适当的语句予以填充。

int OutQueue(QueptrTp*lq,DataType*x)

    { LqueueTp*s;

      if(1q—＞front==lq—＞rear){error("队空");return(0);}

      else{ s=(lq—＞front)—＞next;

            ______=s—＞data;

            (lq—＞front)—＞next______;

            if(s—＞next==NULL)lq—＞rear=lq—＞front;

            free(s);

            return(1);

          }

  }

32． 以下运算实现在链栈上的进栈，请在______处用适当的语句予以填充。

void Push(LStackTp*ls,DataType x)

    { LStackTp*p;p=malloc(sizeof(LStackTp));

      ______;

      p—＞next=ls;

      ______;

  }

30． 以下算法实现若开散列表HP中无键值为K的结点，则插入一个这样的结点。请分析程序，并在______上填充合适的语句。

void insert_openhash(keytype K,openhash HP)

  { if(research_openhash(K,HP)==NULL)

       { i=H(K);

         q=malloc(size);q—＞key=______;   /*生成新结点*/

         ______=HP[i];HP[i]=______;   /*前插法链入新结点*/

       }

  }

29． 对于如图所示的二叉树，请画出其顺序存储结构图。

28． 假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为{(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c))，请用树形结构画出此树，并回答下面的问题。

(1)哪个是根结点?

(2)哪些是叶结点?

(3)哪个是g的双亲?

(4)哪些是g的祖先?

(5)哪些是g的孩子?

(6)哪些是e的子孙?

(7)哪些是e的兄弟?

(8)树的深度是多少?

(9)树的度数是多少?

27． 已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。

26． 对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法。

25． 无向图的邻接矩阵是______，并且主对角线上的元素的值为______。

24． 设有两个散列函数H1(k)=k mod 13和H2(k)=k mod 11+1，散列表为T[0…12]，用双重散列解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量，假定在某一时刻表T的状态为

下一个被插入的关键码是42，其插入的位置是：______。

21． 在结点数目相同的二叉树中，______的路径长度最短。

23． 对于数组，通常具有的基本操作有______种，它们分别是______。

22． 从一个顺序存储的循环队列中删除一个元素时，应该______。

19． 内部排序的方法可以分为五类：______、______、______、______、______。

20． 树的结点数目至少为______，二叉树的结点数目至少为______。

18． 散列函数的作用是：______。

17． 假设在线索二叉树中，结点的标志域的值为0时，表示其指针域是指向孩子的指针，当结点的标志域为1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是______。

16． 对快速排序来讲，其最好情况下的时间复杂度是______，其最坏情况下的时间复杂度是______。

14． 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。

15． 下面四种排序方法中，平均查找长度最小的是( )

12． 树最适合用来表示( )

13． 设有一个无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下面不正确的说法是( )

11． 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )

10． 快速排序在最坏情况下的时间复杂度是( )

9． 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )

7． 在Hash函数H(k)=k MOD m中，一般来讲，m应取( )

8． 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。

6． 在下图中，从顶点V₁出发，按广度优选遍历图的顶点序列是(  )

5． 线性表L=(a₁，a₂，…，a₁，a_n)，下列说法正确的是( )

3． 设数组data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )

2． 散列表的目的是( )

4． 在一个长度为n的顺序表(顺序存储的线性表)中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动( )个元素。

1． 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。