中大数据结构(C)其次次作业答案

本文格式为Word版，下载可任意编辑——中大数据结构(C)其次次作业答案数据结构其次次作业答案

学号：姓名：评分：.一.单项选择题(20分)

()1.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是____b____的二叉树。

a.空或只有一个结点b.高度等于其结点数（空树高度为0）c.任一结点无左孩子d.任一结点无右孩子

()2.设图的顶点数=n,边数=e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间繁杂

度为_____b____。

a.O(n*e)b.O(n2)c.O(n+e)d.O(n3)

()3.一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为

____b_____。

a、0b、1c、2d、不确定()4.下面程序段的时间繁杂度是____d_____。

i=1;while(i0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级

为_____b______。

a.O(n)b.O(log2n)c.O(nlog2n)d.O(n2)

()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分）：1.依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。

3030302143214399219215143154315433030301

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

1040

2812163050

4.用Prim算法求下图的最小生成树,若从顶点0出发，请将算法中的辅助数组closedge的变化过

程填入下表。

16053

选出第1条边3122587

辅助数组closedge647486557

adjvex

5

6701234所选边2

lowcostadjvex选出第2条边lowcostadjvex选出第3条边lowcostadjvex选出第4条边lowcostadjvex选出第5条边lowcostadjvex选出第6条边lowcostadjvex选出第7条边lowcost

5.假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。请画出该

森林的带双亲的孩子链表示。

6.已知9个结点的值分别为1～9，请将各结点的值填入下面二叉排序树中：

5193647827.用堆排序算法(“最大堆〞排序算法)对关键字{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}

3

8.如下图已知哈希表为空，哈希函数为H（Key）=KeyMOD11,冲突解决方法分别用线性探测

再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的状况，并求等概率状况下所要求的平均查找长度。

（1）线性探测再散列

01234567891014372516（2）二次探测再散列

01234567891025143716

线性探测再散列查找不成功时的平均查找长度=____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；dbbcdc

aeae

11.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。

4

27A109E20B37F889C6G13D1HAE=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}

voidDestroyBinTree(BinTree

DestroyBinTree(root->leftchild);DestroyBinTree(root->rightchild);free(root);}

intcountNodes1(BinTreeelseif(root->leftchild==NULLelseif(root->leftchild!=NULL}

return0;}

5

92.下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算

法在发现数据有序时能及时中止。

voidBubbleSort(intdatalist[],intsize)//要排序的数据存放在数组datalist[]中，元素个数=size{

intexchange,i,j,temp;i=1;

exchange=1;

while(i=i;j--)

if(datalist[j-1]>datalist[j])

{

temp=datalist[j-1];datalist[j-1]=datalist[j];datalist[j]=temp;

____⑩___exchange=1_______;}

i++;}}

6

2.下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算

法在发现数据有序时能及时中止。

voidBubbleSort(intdatalist[],intsize)//要排序的数据存放在数组datalist[]中，元素个数=size{

intexchange,i,j,temp;i=1;