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

一、1.单项选择题

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

A．归并排序
B．插入排序
C．快速排序
D．选择排序

1. 散列表的目的是(  )

A．插入
B．删除
C．快速查找
D．排序

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

A．front:=front+1
B．front:=(front+1)mod m
C．rear:=(rear+1)mod m
D．front:=(front+1)mod(m+1)

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

A．n-i
B．n-i+1
C．n-i-1
D．i

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

A．每个元素都有一个直接前趋和直接后继
B．线性表中至少要有一个元素
C．表中诸元素的排列顺序必须是由小到大或由大到小的
D．除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继

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

A．V₁ V₅ V₃ V₄ V₂ V₆ V₇
B．V₁ V₅ V₃ V₄ V₂ V₇ V₆
C．V₁ V₇ V₂ V₆ V₄ V₅ V₃
D．V₁ V₂ V₄ V₇ V₆ V₅ V₃

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

A．奇数
B．偶数
C．素数
D．充分大的数

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

A．大于
B．小于
C．等于
D．无法确定

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

A．(N-1)×(N-1)
B．N×N
C．(N+1)×(N+1)
D．不确定

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

A．O(nlogn)
B．O(n²)
C．O(n³)
D．都不对

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

A．Top—＞next=s;
B．s—＞next=Top—＞next;Top—＞next=s;
C．s—＞next=Top;top=s;
D．s—＞next=Top; Top=Top—＞next;

11. 树最适合用来表示(  )

A．有序数据元素
B．无序数据元素
C．元素之间具有分支层次关系的数据
D．元素之间无联系的数据

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

A．G"为G的子图
B．G"为G的连通分量
C．G"为G的极小连通子图且V"=V
D．G"是G的一个无环子图

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

A．二叉链表
B．广义表
C．三叉链表
D．顺序

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

A．插入排序
B．选择排序
C．快速排序
D．归并排序

二、2.填空题

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

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

2. 散列函数的作用是：______。

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

4. 树的结点数目至少为______，二叉树的结点数目至少为______。

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

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

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

8. 设有两个散列函数H1(k)=k mod 13和H2(k)=k mod 11+1，散列表为T[0…12]，用双重散列解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量，假定在某一时刻表T的状态为
  
  下一个被插入的关键码是42，其插入的位置是：______。

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

三、3.解答题

0. 对于散列文件来说，其存储单位是什么?对于一个能存储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，请给出该散列文件的表示方法。

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

2. 假设在树中，如果结点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)树的度数是多少?

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

四、4.算法阅读题

0. 以下算法实现若开散列表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]=______;  /*前插法链入新结点*/
    }
  }

1. 以下运算实现在链队上的出队列，请在______处用适当的语句予以填充。
  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);
      }
  }

2. 以下运算实现在链栈上的进栈，请在______处用适当的语句予以填充。
  void Push(LStackTp*ls,DataType x)
   { LStackTp*p;p=malloc(sizeof(LStackTp));
    ______;
    p—＞next=ls;
    ______;
  }

3. 以下将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++;}
  }
  此算法的执行时间为______。

五、5.算法设计题

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