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

35． 设计一个用链表表示的直接选择排序算法。

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

int Pop(LStackTp*is,DataType*x)

    { LStackTp*P;

      if(1s!=NULL)

           { p=ls;

              *x=______;

              ls=ls—＞next;

              ______;

              return(1);

            } else return(0);

  }

34． 分析下面程序段的时间复杂度______。

j=1; 

while(j＜=n)  

{j=j*2; 

}

30． 假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。 (1)队列为空(即没有任何元素进入)； (2)A，B，C入队； (3)A出队； (4)B，C出队，此时队列为空。

31． 以下运算实现在循环队上判队空，请在______处用适当的语句予以填充。

int EmptyCycQueue(CycqcleueTp sq)

       { if(______)retum(1);

         else return(0);

       }

32． 以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在______上填充合适的语句。

int binsearch(sqtable R,keytype K)

  {low=l;hig=R.n;/*置查找区间初值。low，hig分别标记查找区间的下、上界*/

      while(low＜=hig)

       { mid=(low+hig)/2;

         switch

           { case K==R.item[i].key:return(mid);   /*找到，返回位置mid*/

             case K＜R.item[i].key:______;break;/*缩小区间*/

             case K＞R.item[i].key:______;break;/*缩小区间*/

           }

       }

     return(0); /*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/

  }

29． 进行多项式相加，采用哪一种表示方法处理较为简单?

多项式A(x)=a_nXⁿ+a_n-1X^n-1+…+a₁X+a₀的线性表表示法有下列两种可能的形式：

A=(n,a_n,a_n-1，…，a₁，a₀) 

A=(m，1_m-1，b_m-1，1_m-2，b_m-2，…，1₀，b₀)

其中：m为非零项的个数，1_i，b_i分别为非零项的指数和系数。试分析：

两种表示方法对存储空间的需要情况；

27． 已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。

26． 试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。

24． 查找表中主关键字指的是______，次关键字指的是______。

23． VSAM文件既可以在______中进行顺序存取，又可以从最高层的索引出发，进行按钮______的随机存取。

25． 若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左右子树皆非空的结点个数为______。

21． 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和______。

22． 在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是______，对于无向图来说是______。

18． 记录的______结构是数据在物理存储器上的存储方式。

19． 有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是______。

20． 在B—树上进行删除操作分为两个步骤，即：______和______。

17． 严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是______的线性表。

16． 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

(1)删除P结点的语句序列是______；

(2)删除尾元结点的语句是______。

  aP—＞next=P—＞next—＞next   b P=P—＞next—＞next

  cwhile(P—＞next!=Q)P=P—＞next

  dwhile(P—＞next!—＞next!=Q)P=P—＞next

  ewhile(P—＞next!—＞next!=NULL)P=P—＞next

  fQ=P     g Q=P—＞next

  hP=L     i L=L—＞next

  jfree(Q)

14． 在一棵具有5层的满二叉树中，结点总数为( )个。

15． 在线索化二叉树中，结点T↑没有左子树的充要条件是( )

13． 在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )

12． 设栈S和队列Q的初始状态为空，元素e₁、e₂、e₃、e₄、e₅和e₆依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序是e₂、e₃、e₄、e₅、e₆、e₁，则栈S的容量至少应该是( )

11． 任何一个带权的无向连通图的最小生成树( )

9． 若已知一个栈的输入序列为1,2,3…,n，其输出序列为P₁，P₂，…，P_n。若P₁=n，则P₁为( )

10． 用数组A[0..N-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为( )

7． 具有12个记录的序列，采用冒泡排序最少的比较次数是( )

8． 若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行( )次比较。

4． 设矩阵A(a_ij,1≤i,j≤i0)的元素满足：

6． 如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用( )查找方法。

5． 循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是( )

2． 在循环双链表的p所指结点之后插入s所指结点的操作是( )

3． 在下面的程序中，语句S的执行次数为(  ) 

for(i=1;i＜=n-1;i++) 

{for(j=n;j＞=i;j--)

{S;

}

1． 索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的( )