数据结构第二次作业答案C语言07Word下载.doc
《数据结构第二次作业答案C语言07Word下载.doc》由会员分享，可在线阅读，更多相关《数据结构第二次作业答案C语言07Word下载.doc（6页珍藏版）》请在冰点文库上搜索。
（）6.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为____b____个结点最佳。
a.10b.25c.6d.625
（）7.下列排序算法中时间复杂度不受数据初始状态影响，恒为O（n2）的是____c______。
a、堆排序b、起泡排序c、直接选择排序d、快速排序
（）8.已知数据表中的每个元素距其最终位置不远，则采用____b___排序算法最省时间。
a.堆排序b.插入排序c.快速排序d.直接选择排序
（）9.假设图的顶点数=n,边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为____b_____。
a.O（n2）b.O（n+e）c.O（n*e）d.O（n3）
（）10.一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为____a_____。
a.2b.1c.0d.不确定
二.填空作图简答题（共62分）：
51
15
30
43
9
21
1.依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。
2.有一组关键码序列{40，20，60，15，50，45，95，10，75}，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。
答案：
第1趟：
40，20，10，15，50，45，95，60，75
第2趟：
15，20，10，40，50，45，95，60，75
第3趟：
10，15，20，40，45，50，60，75，95
3.对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。
20
10
40
1216
50
28
4.用Prim算法求下图的最小生成树,若从顶点0出发，请将算法中的辅助数组closedge的变化过程填入下表。
1
2
3
4
5
6
7
8
辅助数组closedge
所选边
选出第1条边
adjvex
lowcost
选出第2条边
选出第3条边
选出第4条边
选出第5条边
选出第6条边
选出第7条边
5.假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。
请画出该森林的带双亲的孩子链表示。
6.已知9个结点的值分别为1～9，请将各结点的值填入下面二叉排序树中：
7.用堆排序算法（“最大堆”排序算法）对关键字{70，33，79，67，46，24，30，40}进行排序，请先建“最大堆”，然后输出一个堆顶元素,并调整成堆：
初始状态{40，33，24，67，46，79，30，70}
所建大顶堆{79，70，40，67，46，24，30，33}或{79，70，67，46，40，24，30，33}
输出一个堆顶元素后调整的结果{70，67，40，33，46，24，30，79}或{70，46，67，33，40，24，30，79}
8.如下图已知哈希表为空，哈希函数为H（Key）=KeyMOD11,冲突解决方法分别用线性探测再散列和二次探测再散列。
填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下所要求的平均查找长度。
（1）线性探测再散列
012345678910
14
37
25
16
（2）二次探测再散列
线性探测再散列查找不成功时的平均查找长度=____21/11_;
二次探测再散列查找成功时的平均查找长度=___6/4=3/2=1.5_;
9.用快速排序对下列关键字进行排序（图示）,基准元素取第一个元素。
7033796746243040
写出两趟排序的结果。
第一趟排序之后:
{40，33，67，46，24，30}70{79}或{40，33，30，67，46，24}70{79};
第二趟排序之后:
{30，33，24}40{67，46}70，79或{24，33，30}40{46，67}70，79;
若基准元素按“三者取中”的原则取，则两趟排序的结果是：
{40，33，46，24，30}67{79，70}或{33，40，30，24，46}67，{70，79};
{30，33，24}40{46}67，70，79或{24，30}33{40，46}67，70，79;
10.已知一字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。
a：
1；
b：
5；
c：
4；
d：
3；
e：
2；
a
e
d
b
c
11.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。
10
A
B
C
D
H
E
F
G
27
AE=10;
AF=17;
AB=19;
AG=25;
AC=26;
AD=27;
AH=28
三.程序填空（18分）
1.下面是仅给出了部分操作的二叉树类的定义和实现。
试在程序的每一划线部分填入一条语句或表达式，完成计算度为1的结点个数的操作countNodes1（）。
typedefstructBinNode{
intdata;
structBinNode*leftchild,*rightchild;
}BinNode,*BinTree;
voidInitBinTree（BinTree&
root）//初始化二叉树root
{
root=Null;
}
voidDestroyBinTree（BinTree&
root）//销毁二叉树root
if（root==NULL）return;
DestroyBinTree（root->
leftchild）;
DestroyBinTree（root->
rightchild）;
free（root）;
intcountNodes1（BinTree&
root）//计算二叉树root中度为1的结点数
{
if（①_root!
=NULL_____________________）{
if（root->
leftchild!
=NULL&
&
root->
rightchild!
=NULL）
___②_____return__countNodes1（root->
leftchild）+countNodes1（root->
rightchild）__;
elseif（root->
leftchild==NULL&
__③__root->
=NULL_________）
__④__return__1+countNodes1（root->
rightchild）______;
elseif（root->
⑤root->
rightchild==NULL_____）
__⑥_return__countNodes1（root->
leftchild）+1______________;
return0;
2.下面是起泡排序算法的实现。
试在程序的每一划线部分填入一条语句或表达式，以使该算法在发现数据有序时能及时停止。
voidBubbleSort（intdatalist[],intsize）//要排序的数据存放在数组datalist[]中，元素个数=size
intexchange,i,j,temp;
i=1;
exchange=1;
while（i<
size&
___⑧_exchange______）
{
_____⑨____exchange=0;
_____
for（j=size-1;
j>
=i;
j--）
if（datalist[j-1]>
datalist[j]）
temp=datalist[j-1];
datalist[j-1]=datalist[j];
datalist[j]=temp;
____⑩___exchange=1_______;
i++;
}
升级会员 