精品川大数据结构期终复习docWord文档格式.docx
《精品川大数据结构期终复习docWord文档格式.docx》由会员分享，可在线阅读，更多相关《精品川大数据结构期终复习docWord文档格式.docx（72页珍藏版）》请在冰点文库上搜索。
（
）o
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和顶点个数都有关
C）用邻接矩阵法存储图，占用的存储空间大小与图中顶点个数和边数都有关
D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关
（10）设有关键字序列Cq；
g,W,'
z；
'
a；
h,p,'
x；
h）,下面哪一个序列是从上述序列出
发建堆的结果？
A）匕,gV,d,p,q,乂,*zB）工g'
h；
q,h,p,*Nc）gm,q,xh,p,‘X；
h,hD）h,gm,p,'
a'
h,q,‘X；
r
二、（每小题4分，共8分）
已知一个6x5稀疏矩阵如下所示，试:
（1）写出它的三元组线性表；
（2）给岀三元组线性表的顺序存储表示。
三、（本题8分）
求网的最小生成树有哪些算法？
它们的时间复杂度分别下多少，各适用何种情况？
四、（每小题4分，共8分）
对于如下图所示的有向图采用邻接表存储结构，并且每个顶点邻接表屮的边结点都是按照终点序号从小到大的次序链接的，试写出：
（1）从顶点vl岀发进行深度优先搜索所得到的顶点序列；
（2）从顶点v2出发进行广度优先搜索所得到的顶点序列。
五、（本题8分）
已知一个图的顶点集V和边集E分别为：
V二{123,4,5,6,7};
E={<
2,1>
<
3,2>
3,6>
4,3>
4,5>
4,6>
5,1>
5,7>
6,1>
6,2>
6,5>
};
若釆用邻接表存储结构，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列（入度为零的顶点可采用栈或队列来进行存储）。
六、（本题8分）
对于序列{8,1&
6,16,29,28}，试写出堆顶元素最小的初始堆。
七、（本题8分）
一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。
试求出空格处的内容。
先序序列：
_B_F_ICEH_G
中序序列：
DKFIAEJC
后序序列：
—K_FBHJ_G_A
八、（每小恵2无共龄厂
设有序列：
w二{23,24,27,80,28},试给出：
（1）二叉排序树；
（2）哈夫曼树；
（3）平衡二叉树；
（4）对于增量d=2按降序执行一遍希尔排序的结果。
九、（本题9分）
有关键字序列{7,23,6,9,17,19,21,22,5},Hash函数为H（key）=key%5,采用链地址法处理冲突，试构造哈希表。
十、（本题15分）
假设二叉树屮每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
c
e
a
d
b
模拟试题
（一）参考答案
一、单项选择题
（1）B
（2）D（3）A（4）B（5）B
（6）C（7）A（8）C（9）B（10）B
二、（每小题4分，共8分）
（1）（（1,5,1）,（3,2,-1）,（4,5,-2）,（5,1,5）,（6,3,7））
（2）三元组线性表的顺序存储表示如下所示：
"
655'
151
32-1
45-2
515
627
求网的最小生成树可使用Prim算法，吋I'
可复杂度为O（n2）,此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O（eloge）,此算法适用于边较少的稀疏图。
（1）DFS：
vlv2v3v4v5
（2）BFS：
v2v3v4v5vl
用栈存储入度为零的顶点得到的拓扑排序为：
4365721
用队列存储入度为零的顶点得到的拓扑排序为：
4362517
所构造的堆如下图所示：
7.（本题8分）
在先序序列空格屮依次填ADKJ,
八、（每小题2分，共8分）
二叉排序树如下图所示：
（1）
屮序屮依次填BHG,后序屮依次填DIECo
（2）
哈夫曼树如下图所示:
（3）
（4）
九、（本题9分）
对于增量d=2按降序执行一遍希尔排序的结果：
28,80,27,24,23
哈希表如下图所示:
5|A
6IA
+0可+]22|八
23|A
Ma
+>
（本题15分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；
每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是
以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
具体算法实现如下：
〃文件路径幺:
examl\alg.h
template<
classElemType>
voidDisplayHelp（BinTreeNode<
ElemType>
*r,intlevel）
〃操作结果：
按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1
if（r!
=NULL）
//显示右子树
//显示新行
//确保在第level列显示结点
//显示结点
//显示左子树
{//空树不显式，只显式非空树
DisplayHelp<
（r->
rightChild,level+1）;
cout«
endl;
for（inti=0;
i<
level-I;
i++）
cout«
”
r->
data;
leflChild,level+1）;
I
voidDisplay（constBinaryTree<
&
bt）
//操作结果：
树状形式显示二叉树
//树状显示以bt.GetRoot（）为根的二叉树
//换行
{
（bt.GetRcx）t（）,1）;
模拟试题
（二）
1.单项选择题（每小题2分，共20分）
（1）设Huffman树的叶子结点数为m,则结点总数为（）。
A）2mB）2m-1
C）2m+lD）m+1
（2）若元素比b,c,d,e,f依次入栈，允许入栈、出栈操作交替进行。
但不允许连续三次进行出栈操作，贝怀可能得到的出栈序列是（）
D）afedcb
10个度为3的结点，1个度
A）dcebfaB）cbdaefC）dbcaef
（3）在一棵度为4的树T屮，若有20个度为4的结点,为2的结点，10个度为1的结点，则树T的叶节点个数是（
A）41
B）82C）113
D）122
⑷设有一个二维魏假设川0][0]存放位置在600（册A⑶⑶存放位置在67&
I0），
每个元素占一个空间，问用2］⑶（】0）存放在什么位置？
（脚注ao）表示用10进制表示,m>
3）（）。
A）658B）648C）633D）653
（5）下列关于二叉树遍历的叙述中，正确的是（）。
A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点
B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点
C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前
序最后一个结点
D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点
（6）k层二叉树的结点总数最多为（）。
A）2k-lB）2k+,C）2K-1
（7）对线性表进行二分法查找，其前提条件是（
A）
C）
线性表以链接方式存储,线性表以顺序方式存储,线性表以顺序方式存储,线性表以链接方式存储,
2k'
*
并且按关键字值排好序
并且按关键字值的检索频率排好序并且按关键字值排好序
并且按关键字值的检索频率排好序
（8）对n个记录进行堆排序，所需要的辅助存储空间为（）。
A）O（log2n）B）O（n）C）0
（1）D）
（9）对于线性表（7,34,77,25,64,49,20,14）进行散列存储时,二K%7作为散列函数，则散列函数值为为0的元素有（
A）1B）2C）
（10）下列关于数据结构的叙述中，正确的是（
）个。
3D）
数组是不同类型值的集合
递归算法的程序结构比迭代算法的程序结构更为精炼树是一种线性结构
用一维数组存储一棵完全二叉树是有效的存储方法
O（n2）若选用H（K）
二、（本题8分）
有5个元素，其入栈次序为：
A、B、C、D、E,在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？
三、（每小题4分，共8分）
已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示：
01001
10010
00011
01101
10110
（1）画出该图的图形；
（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写11!
相应的遍历序列。
四、（本题8分）
树有哪些遍历方法？
它们分别对应于把树转变为二叉树的哪些遍历方法？
将关键字序列（7、8、11、18、9、14,30）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组，散列函数为：
H（key）=（key*3）%m（m为表长）,处理冲突采用线性探测再散列法，要求装填（载）因子为0.7,请画出所构造的散列表；
计算查找成功的平均查找长度。
试列出如下图屮全部可能的拓扑排序序列。
请说明对一棵二叉树进行按照先遍左子树，后右子树的方式进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？
为什么？
八、（本题8分）
设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉排序树。
试画出表达式（a+b/c）*（d・"
f）的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。
以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。
模拟试题
（二）参考答案
一、单项选择题（每小题2分，共20分）
（1）B
（2）D（3）B（4）D（5）A
（6）A（7）C（8）C（9）D（10）D
按照栈的特点可知以元素C第一个出栈,D第二个出栈的次序有CDEBA、CDBAE和CDBEA3种。
【解答】
（1）该图的图形如下图所示:
（2）深度优先遍历序列为：
abdce；
广度优先遍历序列为：
abedco
树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。
由装载因子0.7,由于有7个数据元素，可得7/m=0.7,从而m=10,所以，构造的散列表为：
下标
1
2
3
4
5
6
7
8
9
关键字
30
14
11
18
•
比较次数
H（7）=（7*3）%10=1
H（8）=（8*3）%10=4
H（II）=（11*3）%10=3
H（18）=（18*3）%10=4
H（9）=（9*3）%10=7
H（14）=（14*3）%10=2
H（30）=（30*3）%10=2
（2）查找成功的ASL=（1+1+1+14-1+2+1）/7=8/7
全部可能的拓扑排序序列为：
1523634、152634、156234、561234、516234、512634、512364
二叉树任两个中叶结点必在某结点的左/右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的。
所以在三种遍历序列中叶结点的相对次序是不会发生改变的。
62
12
9.（本题9分）
表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序遍历、中序遍历及后序遍历序列。
二叉树表示如下图所示：
波兰式表示:
中缀表示：
a+b/c*d-e*f
逆波兰式表示：
abcZ+def*-*
十.（本题15分）
本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。
〃文件路径名:
exarn2\alg.h
longLeafCountHelp（BinTreeNocle<
*r）
按树状形式显示二叉树，level为层次数，可设根结点的层次数为1{
if（r==NULL）
（//空二叉树
return0:
〃空树返回0
elseif（r->
leftChild==NULL&
&
rightChild==NULL）
（//只有一个结点的树
return1;
//只有一个结点的树返回1
else
（//其他情况，叶子结点数为左右子树的叶子结点数之和
returnLeafCountHelp（r->
leftChild）+LeafCountHelp（r->
rightChild）;
longLeafCount（constBinjir）-Tree<
ElemType>
计算二叉树中叶子结点数目
returnLeafCountHelp（bt.GetR（x）t（））;
//调用辅助函数实现计算二叉树中叶子结点数H
}
模拟试题（三）
（1）对一组数据（2,12,16,88,5,10）进行排序，若前三趟排序结果如下第一趟：
2,12,16,5,
第二趟：
2,12,5,10,第三趟：
2,5,10,12,
则采用的排序方法可能是（
10,
16,
88
）。
A）起泡排序B）希尔排序C）归并排序D）基数排序
（2）在带有头结点的单链表HL中，要向表头插A—个由指针p指向的结点,则执行（
A）p->
next=HL->
HL->
next=pB）p->
next=HL;
HL=p
p=HLD）HL=p;
next=HL
（3）对线性表，在下列哪种情况下应当采用链表表示？
A）经常需要随机地存取元素B）经常需要进行插入和删除操作
C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变
（4）一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是（
A）231B）3210312D）123
（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序
（6）采用开放定址法处理散列表的冲突时，其平均查找长度（
A）低于链接法处理冲突
C）与链接法处理冲突相同
（7）若需要利用形参直接访问实参时，
A）值B）函数
B）高于链接法处理冲突
D）高于二分查找应将形参变量说明为（）参数。
C）指针D）引用
（8）为解决计算机与打印机Z间速度不匹配的问题，通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（
A）栈
B）队列
C）树
D）图
在稀疏矩阵的带行指针向量的链接存储中,
每个单链表中的结点都具有相同的
（）0
A）行号
B）列号
C）元素值D）非零元素个数
（9）快速排序在最坏情况下的时间复杂度为（）。
A）O（log2n）B）O（nlog2n）C）0（n）D）0（n）
（10）从二叉搜索树中查找一个元素吋，其吋间复杂度大致为（）。
A）O（n）B）0
（1）C）O（log2n）D）O（n2）
V二{1,2,3,4,5,6,7};
E={（1,2）3,（1,3）5,（1,4）8,（2,5）10,（2,3）6,（3,4）15,（3,5）12,（3,6）9,（4,6）4,（4,7）20,（5,6）18,（6,7）25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
请画出如下图所示的邻接矩阵和邻接表。
四、（每小题4分，共8分）
设有如下图所示的AOE网（其中vi（i=l,2,…，6）表示事件，有向边上的权值表示活动的天数）。
1设最短路径初始时仅包含初始顶点，令当前顶点U为初始顶点；
2选择离U最近且尚未在最短路径屮的一个顶点V,加入到最短路径中，修改当前顶点u=v；
3重复步骤②，直到U是目标顶点时为止。
请问上述方法能否求得最短路径？
若该方法可行，请证明之；
否则，请举例说明。
已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数：
H（key）=keyMOD
13,哈希地址空间为0〜12,请构造用链地址法处理冲突的哈希表，并求平均查找长度。
已知关键字序列{23,13,5,28,14,25},试构造二叉排序树。
编写一个算法求二又树的深度。
模拟试题（三）参考答案
（1）A
（2）A（3）B
（6）B（7）D（8）B
用克鲁斯卡尔算法得到的最小生成树为：
（1,2）3,（4,6）4,（1,3）5,
三、（本题8分）邻接矩阵：
（14）&
（25）10,
邻接表如下图所示:
（4）C
（9）D
（4,7）20
（5）B
（10）C
o
0111
101（）
1101
1010
四.（每小题4分，共8分）
（1）找出所有的关键路径有：
vlfv2—v3fv5fv6,以及vl—v4-*v6。
（2）v3事件的最早开始吋间是13。
五、（本题8分）
如下图所示的有向图，只有一个顶点的入度为0外，其他每个顶点的入度都为1,因为非连通，所以此图却不是有向树。
不对，例如序列｛3、3、4、2、1｝的“逆序元素”个数是2,2和1是“逆序元素”；
但是将第二个3和2交换后，成为｛3、2、4、3、1｝,此吋“逆序元素”个数是3,2、3和1是“逆序元素”。
然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、1｝的逆序对的个数是7,交换第二个3和2后，｛3、2、4、3、1｝的逆序对的个数是6。
七、（每小题4分，共8分）
该方法求得的路径不一定是最短路径。
例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A-B-C,事实上其最短路径为A-D-C。
4->
79A
八、（本题8分）
用链地址法处理冲突的哈希表如下图所示:
10
ASL=—（1*6+2*4+3*1+4*1）=1.7512
构造二叉排序树的过程如下图所示。
（b）
㉘
（f）
（c）
23
构造的二叉排序树如下图所示:
则二叉树的深度为左右子树深度的最大值
若二叉树为空，深度为0；
若二叉树不空,加1。
本题最简单算法是递归算法。
具体算法实现如下：
//文件路径名:
exam3\iilg.htemplate<
intDepthHelp（BinTreeNode<
求二叉树的深度
if（r==NULL）
{//空二叉树
return0;
//空二叉树的深度为0
{//非空二叉树
int1Depth=DepthHelp（r->
leftChild）;
//左子树的深度
intrDepth=DepthHelp（r->
//右子树的深度
return（（lDepth>
rDepth）?
IDepth:
升级会员 