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

34． 对一个有t个非零值元素的m×n矩阵，用B[0..t,1..3]的数组来表示，其中第0行的三个元素分别是m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素A[i][j]的位置，并考虑若修改其元素值须用多少时间?(设B中第1列原行号是递增的)

33． 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的三元组a.data的次序进行转置(快速转置)，请在______处用适当的语句予以填充。

Fast_Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b)

    { (*b)．mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;

      if(a.tu)

  {for(col)=1;______col++)unm[col]=0

    for(t=1;t＜=a.tu;t++)num[a.data[t].j]++;

    cpot[1]=1;

    for(col=2;col＜=a.nu;col++)cpot[col]=______;

    for(p=1;p＜=a.tu;p++)

      { col=a.data[p].j;

        q=cpot[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． 以下为冒泡排序的算法。请分析算法，并在______处用适当的语句予以填充。

void bubblesort(int n,list r) /*fiag为特征位，定义为布尔型*/

  {for(i=1;i＜=______，i++)

       {______;

         for(j=1;j＜=______;j++)

           if(r[j+1].key＜r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=P;}

         if(flag)return;

       }

  }

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

int EnCycQueue(CycquetaeTp*sq,DataType x)

        { if((sq—＞rear+1)%maxsize==______)

               {error("队满");return(0);)

          else{______;

               ______;

          return(1);

          }

       }

31． 以下程序段采用先根遍历方法求二叉树的叶子数，请在______处填充适当的语句。

void countleaf(bitreptr t,int*count)/*根指针为t，假定叶子数count的初值为0*/

       { if(t!=NULL)

          { if((t—＞lchild==NULL)&&(t—＞rchild==NULL))______;

             countleaf(1—＞lehild,count);

          ______;

          }

       }

28． 已知：S='XYZ*+' T='(X+Z)*Y'，试利用串的各种基本运算将S转换为T。

29． 令s=‘aaab’，t=‘abcabaa’，u=‘abcaabbabcabaacbacba’，分别求出它们的next值。

27． 对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。

26． 设某文件有14个记录，其关键字分别为{25,75,125,93,241,203,19,198,121,173,218，80，214，329}。桶的容量M=3，此时采用除留余数法构造散列函数，且散列函数为h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作。

25． 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为______个。

23． 具有N个顶点的无向完全图的边为______，具有N个顶点无向完全图的弧为______。

24． 设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是：______。

21． ISAM文件采用______索引结构，而VSAM文件采用______索引结构。

22． 已知广义表A=((a,b,c)，(d,e,f))，则运算head(head(tail(tail(A))))=______。

20． 散列文件关键在于选择好的______和______方法。

19． 带有一个头结点的单链表head为空的条件是______。

18． 在线性结构中，______决定了它的遍历路线只有一条。

16． 从树的根结点到树中的其余结点之间的路径______惟一的。

17． 一个字符串相等的充要条件是______和______。

15． 将含100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的结点的双亲的编号为( )

13． 由权值为4,2,8,7的四个叶子构成一棵哈夫曼树之后，此树的带权路径的长度为( )

14． 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。

11． 对一棵非空二叉树进行中序遍历，则根结点的左边( )

12． 索引非顺序文件是指( )

9． 深度为k的二叉树，所含叶子的个数最多为( )

10． 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

8． 从一个包含2000个结点的散列表A[1..2000]中查找结点的平均比较次数( )从一个包含200个结点的散列表B[1..200]中查找结点的平均比较次数。

7． 一个长度为10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为( )

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

5． 设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量少( )个。

4． 下面四种内排序方法中，要求内存容量最大的是( )

2． 长度为12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )

3． 采用分治法进行排序的方法是( )

1． 如图所示二叉树的中序遍历序列是(  )