全国自考（数据结构）模拟试卷10
一、1.单项选择题
0. 如图所示二叉树的中序遍历序列是( )
A．a b c d g e f
B．d f e b a g c
C．d b a e f c g
D．d e f b a g c
1. 长度为12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )
A．35/12
B．37/12
C．39/12
D．43/12
2. 采用分治法进行排序的方法是( )
A．快速排序
B．插入排序
C．堆排序
D．希尔排序
3. 下面四种内排序方法中，要求内存容量最大的是( )
A．插入排序
B．选择排序
C．快速排序
D．归并排序
4. 设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量少( )个。
A．k+1
B．2k
C．2k-1
D．2k+1
5. 串是一种特殊的线性表，其特殊性体现在( )
A．可顺序存储
B．数据元素是一个字符
C．可链接存储
D．数据元素可以是多个字符
6. 一个长度为10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为( )
A．25/10
B．27/10
C．29/10
D．31/10
7. 从一个包含2000个结点的散列表A[1..2000]中查找结点的平均比较次数( )从一个包含200个结点的散列表B[1..200]中查找结点的平均比较次数。
A．大于
B．小于
C．等于
D．不确定
8. 深度为k的二叉树，所含叶子的个数最多为( )
A．2K
B．K
C．2K-1
D．2K-1
9. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A．5
B．6
C．7
D．8
10. 对一棵非空二叉树进行中序遍历，则根结点的左边( )
A．只有左子树上的所有结点
B．只有右子树上的所有结点
C．只有左子树上的部分结点
D．只有右子树上的部分结点
11. 索引非顺序文件是指( )
A．主文件无序，索引表有序
B．主文件有序，索引表无序
C．主文件有序，索引表有序
D．主文件无序，索引表无序
12. 由权值为4,2,8,7的四个叶子构成一棵哈夫曼树之后，此树的带权路径的长度为( )
A．21
B．42
C．40
D．44
13. 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。
A．先根
B．中根
C．后根
D．层次
14. 将含100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的结点的双亲的编号为( )
A．34
B．35
C．36
D．无法确定
二、2.填空题
0. 从树的根结点到树中的其余结点之间的路径______惟一的。
1. 一个字符串相等的充要条件是______和______。
2. 性结构中，______决定了它的遍历路线只有一条。
3. 带有一个头结点的单链表head为空的条件是______。
4. 散列文件关键在于选择好的______和______方法。
5. ISAM文件采用______索引结构，而VSAM文件采用______索引结构。
6. 已知广义表A=((a,b,c)，(d,e,f))，则运算head(head(tail(tail(A))))=______。
7. 具有N个顶点的无向完全图的边为______，具有N个顶点无向完全图的弧为______。
8. 设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是：______。
9. 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为______个。
三、3.解答题
0. 设某文件有14个记录，其关键字分别为{25,75,125,93,241,203,19,198,121,173,218，80，214，329}。桶的容量M=3，此时采用除留余数法构造散列函数，且散列函数为h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作。
1. 对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。
2. 已知：S="XYZ*+" T="(X+Z)*Y"，试利用串的各种基本运算将S转换为T。
3. 令s=‘aaab’，t=‘abcabaa’，u=‘abcaabbabcabaacbacba’，分别求出它们的next值。
四、4.算法阅读题
0. 以下运算实现在循环队上的入队列，请在______处用适当的语句予以填充。
int EnCycQueue(CycquetaeTp*sq,DataType x)
{ if((sq—＞rear+1)%maxsize==______)
{error("队满");return(0);)
else{______;
______;
return(1);
}
}
1. 以下程序段采用先根遍历方法求二叉树的叶子数，请在______处填充适当的语句。
void countleaf(bitreptr t,int*count)/*根指针为t，假定叶子数count的初值为0*/
{ if(t!=NULL)
{ if((t—＞lchild==NULL)&&(t—＞rchild==NULL))______;
countleaf(1—＞lehild,count);
______;
}
}
2. 以下为冒泡排序的算法。请分析算法，并在______处用适当的语句予以填充。
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;
}
}
3. 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的三元组a.data的次序进行转置(快速转置)，请在______处用适当的语句予以填充。
Fast_Trans_Sparmat(SpMatrixTp a,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;
______;
}
}
}
五、5.算法设计题
0. 对一个有t个非零值元素的m×n矩阵，用B[0..t,1..3]的数组来表示，其中第0行的三个元素分别是m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素A[i][j]的位置，并考虑若修改其元素值须用多少时间?(设B中第1列原行号是递增的)
