全国自考（数据结构）模拟试卷7
一、1.单项选择题
0. 设有一个用线性探测法解决冲突得到的散列表：
散列函数为H(k)=Kmod 11 若要查找元素14，探测的次数(比较的次数)是
A．8
B．9
C．3
D．6
1. 如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点 ( )
A．先根
B．中根
C．后根
D．层次
2. 对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A．O
B．1
C．2
D．不存在这样的二叉树
3. 含N个顶点的连通图中的任意一条简单路径，其长度不可能超过( )
A．1
B．N/2
C．N-1
D．N
4. 顺序存储结构 ( )
A．仅适合于静态查找表的存储
B．仅适合干动态查找表的存储
C．既适合静态又适合动态查找表的存储
D．既不适合静态又不适合动态查找表的存储
5. 已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是( )
A．将该元素所在的存储单元清空
B．将该元素用一个特殊的元素替代
C．将与该元素有相同Hash地址的后继元素顺次前移一个位置
D．用与该无素有相同Hash地址的最后插入表中的元素替代
6. 邻接表存储结构下图的广度优先遍历算法结构类似于树的( )
A．先根遍历
B．后根遍历
C．按层遍历
D．先序遍历
7. 下列说法中正确的是( )
A．二叉树中任何一个结点的度都为2
B．二叉树的度为2
C．任何一棵二叉树中至少有一个结点的度为2
D．一棵二叉树的度可以小于2
8. 已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为( )
A．ACFKBDG
B．GDBFKCA
C．KCFAGDB
D．ABCDFKG
9. 用二分查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为( )
A．O(n2)
B．O(nlog2n)
C．O(n)
D．O(log2n)
10. 与其他查找方法相比，哈希查找法的特点是( )
A．通过关键字比较进行查找
B．通过关键字计算记录存储地址进行查找
C．通过关键字计算记录存储地址，并进行一定的比较进行查找
D．通过关键字记录数据进行查找
11. 下列说法正确的是( )
A．树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B．树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C．树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D．树的后根遍历序列与其对应的二叉树的后根遍历序列相同
12. 设串s1="ABCDEFG"，s2="PQRST"，函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的con(subs(s1，2，len(s2))，subs(s1，len(s2)，2)的结果串是( )
A．BCDEF
B．BCDEFG
C．BCPQRST
D．BCDEFEF
13. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )
A．2h
B．2h-1
C．2h-1
D．2h+1-1
14. 顺序查找法适用于存储结构为( )的线性表。
A．散列存储
B．压缩存储
C．顺序存储或链接存储
D．索引存储
二、2.填空题
0. 拓扑排序指的是找一个有向图的______的过程。
1. 存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用______和进行查找。
2. 在______遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
3. 设N阶方阵A中的任一元素aij(1≤i，j≤N)，当i=j或i+1=j时，aij≠0，否则aij=0，
若将A按如下方式映象到一维数组S中
通过计算公式______可随机地从S中取出A中任一元素aij。
4. 在双向链表中，每个结点含有两个指针域，一个指向其______结点，另一个指向______结点。
5. 栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表______和______运算的限定不一样。
6. 在串的链式存储结构中，有一个串S1="ejidc"，我们假设存储时结点的大小为1，并设指针占有4个字节，则链串的存储密度为______，又假设串S2="abcdefg"在存储时我们设定结点的大小为4，指针占有4个字节，则此链串的存储密度为______。
7. 给定一个具有n个元素的向量，建立一个有序单链表的时间复杂度是______。
8. 稀疏矩阵一般的压缩存储方法有2种，它们分别是______和______。
9. 由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为______。
三、3.解答题
0. 已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264)，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。
1. 假设一棵具有12个结点的二叉树的存储结构如下图所示，其中left和right分别表示此结点左、右孩子的序号，data表示此结点的数据，根结点为编号为4的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题：
(1)写出前序遍历、中序遍历和后序遍历此二叉树时的遍历序列。
(2)求出此树的高度并分析叶结点的个数。
(3)结点E的双亲及子孙分别是什么?
2. 在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?
3. 已知有如右图所示的一棵树，请将其转化成二叉树。
四、4.算法阅读题
0. 以下为单链表的建表算法，分析算法，请在______处填上正确的语句。
lklist create_1klistl()
/*通过调用intiate_lklist和insetr_lklist算法实现的建表算法。假定$是结束标志*/
{ ininiate_lklist(head);
i=1;
scanf("%",&x);
while(x!=$)
{______;
______;
scanf("%f",&x);
}
return(head);
}
该建表算法的时间复杂性约等于______，其量级为______。
1. 以下是图的深度优先搜索算法，请在______处填充适当的语句。
Dfs(GraphTp g,int v)
{ ArcNodeTp*P;
printf("%",v);
visited[v]=1;
p=______;
while(p!=NULL)
{if(!______)Dfs(g,p—＞adjvex);
p=______;
}
}
2. 以下为单链表的插入运算，分析算法，请在______处填上正确的语句。
void insert_lklist(lklist head,datatype x,int i)
/*在表head的第i个位置上插入一个以x为值的新结点*/
{ p=find_lklist(head,i-1);
if(p==NULL)error("不存在第i个位置");
else{s=______;s—＞data=x;
s—＞next=______;
p—＞next=s;
}
}
3. 根据文字说明，请在以下______处填充适当的语句。
采用静态链表作存储结构，设置一个大小为2n-1的数组，令数组的每个元素由四个域组成：wt是结点的权值；lehild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：
typedef struet
{ float wt; /*权值*/
int parent,lchild rchild; /*指针域*/
}node;
typedef node hftree[2*n-1];
在这种存储结构上的哈夫曼算法可描述如下：
void huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/
{ int i,j,x,y;
float m,n;
for(i=0;i＜2*k-1;i++)
{ T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;
if(______)T[i].wt=W[i];
else T[i].wt=0
}
for(i=0;i＜k-1;i++)
{ x=0;y=0;m=maxint;n=maxint;
for(j=0;j＜k-i,j++)
if(T[j].wt＜m)&&(T[j].parent==-1){n=m;y=___;m=___;x=j;}
else if(T[j].wt＜n)&&(T[j].parent==-1)){n=T[j].wt;y=j;)
}
T[x].parent=______;T[y].parent=______;
T[k+i].wt=______;
T[k+i].lchild=______;T[k+i].rchild=______;
}
五、5.算法设计题
0. 设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。
