58章习题答案.docx

58章习题答案.docx

《58章习题答案.docx》由会员分享，可在线阅读，更多相关《58章习题答案.docx（29页珍藏版）》请在冰点文库上搜索。

58章习题答案

一、名词解释

1、二叉树：

2、哈夫曼树：

3、小根堆：

4、最小生成树

5、拓扑排序

6、二叉搜索树

7、出度：

8、权

二、填空

1、二叉树的度为：

2，当深度h=4时，其满二叉树的结点树为：

15。

2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为通用数据（ElemType）类型。

如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的左指针域（left）和右指针域（right）。

3.一棵二叉树的广义表表示是A（B（C,D）），则对其的中序遍历结果是CBDA。

4．对一棵完全二叉树的各结点从1开始编号，并按此编号把它顺序存储到一维数组a中，即将根结点编号为1并存储到a[1]中，其余类推，则a[i]元素的左孩子（如果有的话）元素为a[2*i]，右孩子（如果有的话）元素为a[2*i+1]，双亲元素（如果有的话）为a[i/2]。

5.一个大根堆中，值最大的结点是根结点。

6、同一棵树中的数据元素必须是同质（或同类型）的。

7、一个广义表形式的二叉树A（B,C（，D））

此二叉树的深度为3

8、二叉搜索树是指树上所有右结点均大于根结点，同时左右子树又各是一棵排序二叉树。

9、哈夫曼树是指此树的带权路径长度（WPL）最小。

10、图由非空顶点集和边集所组成。

无向图某个顶点的度是以该顶点为端点的边的数目。

11．一个有n个顶点的连通图的最小生成树的边数为n-1。

12、对有向图来说，出度是指某个顶点出边的数目。

13、在计算机中若采用索引查找，索引表中的每个索引项应至少包含索引值域和子表开始位置域两个域。

14、在散列查找中，多个关键字求出的散列地址相同时，若散列地址已被占用，这种现象被称之为冲突。

15、在选择排序方法时，在最坏或平均情况下元素移动次数越多，则说明该方法的时间复杂性越大（越差）。

三、选择题

1、一棵三叉树的结点个数为10，则它的最小深度为？

，最大深度为？

，正确的是（B）。

A．5和8B.3和10C.1和10D．2和7

2.一棵深度为h的二叉树最多有（D）个结点。

A．2h+1B．2h-1C．2h+1D．2h-1

3.一棵二叉树的第i层最多有（D）个结点。

A．2i+1B．2i-1C．2i+1D．2i-1

4、在计算机领域，磁盘上的目录结构就是一棵树，对于这种数据结构，在查找时采用哪种方法较好？

（B）

A．顺序查找B.二分查找C.索引查找D.散列查找

A．1B.2C.3D.4

5、如果有一棵完全二叉树上的结点数是9，那么这棵二叉树的最大深度是（C）

A．2B．3C．4D．5

6、下列算法是二叉树的（A）。

voidPreorder（structBTreeNode*BT）

{if（BT!

=NULL）{

printf（"%c",BT->data）;

Preorder（BT->left）;

Preorder（BT->right）;

}

}

A．前序遍历算法B．中序遍历算法

C．后序遍历算法D．按层遍历算法

7、二叉搜索树的特点是（B）。

A．后序遍历有序B．按层遍历有序

C．前序遍历有序D．中序遍历有序

8、哈夫曼编码是（B）

A．等长编码B．无前缀编码

C．有前缀编码D．最短编码

9、根据大根堆排序，其排序结果为（B）。

A．无序B．升序

C．降序D．逆序

10．一个图的边集形如：

E（G）={（0,1）,（0,2）,（1,4）,…},这是一个（A）。

A．无向无权图B．有向无权图

C．无向带权图D．有向带权图

11．一个图的边集形如：

E（G）={<0,1>,<0,2>,<1,4>,…},这是一个（B）。

A．无向无权图B．有向无权图

C．无向带权图D．有向带权图

12．一个图的边集形如：

E（G）={<0,1>2,<0,2>3,<1,4>5,…},这是一个（D）。

A．无向无权图B．有向无权图

C．无向带权图D．有向带权图

13．一个图的边集形如：

E（G）={（0,1）2,（0,2）3,（1,4）5,…},这是一个（C）。

A．无向无权图B．有向无权图

C．无向带权图D．有向带权图

14.一个无向带权图的邻接矩阵是一个（B）。

A．对角矩阵B．对称矩阵

C．非对称矩阵D．行、列数不等的矩阵

15．对一个有向图作拓扑排序，结果总有若干顶点不能进入序列，这说明（D）。

A．图中一定没有回路B．图中可能有回路

C．图中顶点顺序不对D．图中一定有回路

16.以下查找算法是（A）算法。

intSeqsch（structElemTypeA[],intn,KeyTypeK）

{inti;

A[n].key=K;

for（i=0;;i++）

if（A[i].key==K）break;

if（i

elsereturn-1;

}

A．顺序查找B．索引查找

C．二分查找D．散列查找

17.以上Seqsch（）算法中returni;的含义是（C）。

A．查到的数据B．查到的数据的地址

C．查到的数据的下标D．查到的数据的位置

18．如果采用h（K）=K%13计算散列地址，则元素64的初始散列地址为（B）。

A．8B．12C．13D．14

19．对有序表进行二分查找，算法的时间复杂度为（B）。

A．O

（1）B．O（log2n）C．O（n）D．O（n2）

20．以下排序算法是（D）算法。

voidBubbleSort（structElemTypeA[],intn）

{structElemTypex;

inti,j,flag;

for（i=1;i<=n-1;i++）{

flag=0;

for（j=n-1;j>=i;j--）

if（A[j].stn

x=A[j];A[j]=A[j-1];A[j-1]=x;

flag=1;

}

if（flag==0）return;

}

}

A．直接插入排序B．直接选择排序

C．快速排序D．气泡排序

四、判断对错，说明原因

1、二叉树上所有结点的度都为2.

□对■错

原因：

只有左右子树都有的结点度为2，单支结点的度为1，叶子结点度为0.

2、有向图中某顶点的度为该顶点的相邻顶点的边数。

□对■错

原因：

有向图应分为出度和入度。

3、最小生成树中所有边之和是生成树中边之和最小的。

■对□错

原因：

由最小生成树的定义可知。

4、拓扑排序具有唯一性。

□对■错

原因：

拓扑排序不具有唯一性

5、顺序查找算法的最好时间复杂度为O（n）。

□对■错

原因：

顺序查找算法的最好时间复杂度为O

（1）。

6、堆排序的时间复杂度为log2n。

□对■错

原因：

堆排序的时间复杂度为nlog2n。

五、有一棵树，以广义表表示：

A（B（D（，G））,C（E（H），F（I）））。

要求：

1、以图形表示法如下：

2、此树的深度是：

4。

3、写出前序遍历的结果：

ABDGCEHFI、中序遍历的结果：

DGBAHECIF、后序遍历的结果：

GDBHEIFCA。

4、画出链接存储方式。

5、如果以D结点为根（不考虑其他结点），开始代入求深度的算法，写出递归过程。

六、用数组A[8]={12,4,7,3,5,34,11,22}

要求1：

建立二叉搜索树；

要求2：

并再次插入28结点；

要求3：

之后删除12结点；

要求4：

之后删除34结点。

画出对应二叉树图形。

要求1：

要求2：

要求3：

要求4：

七、

要求1：

利用已有完全二叉树建初始堆（大根堆）：

答1：

要求2：

插入55之后调整堆。

要求3：

删除堆顶元素。

八-1、有6个权值分别为3,4,6,8,9,12的结点，试：

要求1：

按左小右大规则画出哈夫曼树的图形。

要求2：

求该哈夫曼树的WPL。

WPL=4*（3+4）+3*6+2*（8+9+12）=104。

要求3：

按左‘0’右‘1’的规则进行哈夫曼编码。

结点权值

编码

3

1

1

1

0

4

1

1

1

1

6

1

1

0

8

0

0

9

0

1

12

1

0

八-2、有7个权值分别为3,4,6,8,9,12,14的结点，试：

要求1：

按左小右大规则画出哈夫曼树的图形。

要求2：

求该哈夫曼树的WPL。

WPL=4*（3+4）+3*（6+8+9）+2*（12+14）=149。

要求3：

按左‘0’右‘1’的规则进行哈夫曼编码。

结点权值

编码

3

0

1

1

0

4

0

1

1

1

6

0

1

0

8

1

1

0

9

1

1

1

12

0

0

14

1

0

九-1、有一个带权无向图G如下

要求1：

写出顶点数组和邻接矩阵中缺失行。

要求2：

利用普里姆算法求出图的最小生成树（不要求编写算法），画出对应的图形，填写最小生成树生成过程中顶点集U、最小生成树的边集TE、以及LW的变化过程。

根据最小生成树填写边集数组CT的内容。

要求3：

利用可卢斯卡尔生成最小生成树，并写出生成过程中最小生成树的顶点集、边集的变化过程。

答1：

顶点数组：

0

1

2

3

4

5

6

7

邻接矩阵：

01234567

00927∞∞∞∞

1

22∞04∞∞∞10

3

4∞12∞16012∞∞

5

6∞∞∞11∞809

7

答2：

（0）第0次

U＝{0}

TE={}

LW={（0,1）9,（0,2）2,（0,3）7,（0,4）∞,（0,5）∞,（0,6）∞,（0,7）∞}

（1）第1次

U＝{0,2}

TE={（0,2）2}

LW={（0,1）9,（2,3）4,（0,4）∞,（0,5）∞,（0,6）∞,（2,7）10}

（2）第2次

U＝{0,2，3}

TE={（0,2）2,（2,3）4}

LW={（0,1）9,（3,4）16,（0,5）∞,（3,6）11,（2,7）10}

（3）第3次

U＝{0,2，3,1}

TE={（0,2）2,（2,3）4,（0,1）9}

LW={（1,4）12,（2,5）6,（3,6）11,（2,7）10}

（4）第4次

U＝{0,4，1，3，2,5}

TE={（0,2）2,（2,3）4,（0,1）9,（2,5）6}

LW={（1,4）12,（5,6）8,（2,7）10}

（5）第5次

U＝{0,4，1，3，2,5,6}

TE={（0,2）2,（2,3）4,（0,1）9,（2,5）6,（5,6）8}

LW={（1,4）12,（6,7）9}

（6）第6次

U＝{0,4，1，3，2,5,6,7}

TE={（0,2）2,（2,3）4,（0,1）9,（2,5）6,（5,6）8,（6,7）9}

LW={（1,4）12}

（7）第7次

U＝{0,4，1，3，2,5,6,7,4}

TE={（0,2）2,（2,3）4,（0,1）9,（2,5）6,（5,6）8,（6,7）9,（1,4）12}

LW={}

CT

0

1

2

3

4

5

6

fromvex

0

2

0

1

5

6

1

endvex

2

3

1

5

6

7

4

weight

2

4

9

6

8

9

12

九-2、有一个带权无向图G如下

0

228

1154

216

5195

243

要求1：

写出顶点数组和邻接矩阵中缺失行。

要求2：

利用普里姆算法求出图的最小生成树（不要求编写算法），画出对应的图形，填写最小生成树生成过程中顶点集U、最小生成树的边集TE、以及LW的变化过程。

根据最小生成树填写边集数组CT的内容。

要求3：

利用可卢斯卡尔生成最小生成树，并写出生成过程中最小生成树的顶点集、边集的变化过程。

答1：

顶点数组：

0

0

1

1

2

2

3

3

4

4

5

5

邻接矩阵：

012345

0022∞∞8∞

12205215∞

2∞504∞∞

3∞24019∞

4815∞19016

5∞∞∞∞160

答2：

（0）第0次

U＝{0}

TE={}

LW={（0,1）22,（0,2）∞,（0,3）∞,（0,4）8,（0,5）∞}

0

228

14

5

23

（1）第1次

U＝{0,4}

TE={（0,4）8}

LW={（0,2）∞,（4,3）19,（4,1）15,（4,5）16}

0

8

1154

16

195

23

（2）第2次

U＝{0,4，1}

TE={（0,4}8,（4,1）15}

LW={（1,3）2,（1,2）5,（4,5）16}

0

8

1154

216

55

23

（3）第3次

U＝{0,4，1，3}

TE={（0,4}8,（4,1）15，（1,3）2,}

LW={（1,2）5，（（3，2）4）,（4,5）16}

0

8

1154

216

5

243

（4）第4次

U＝{0,4，1，3，2}

TE={（0,4}8,（4,1）15，（1,3）2，（1,2）5，（3，2）4}

LW={（4,5）16}

0

8

1154

216

5

243

（4）第5次

U＝{0,4，1，2，3，5}

TE={（0,4}8,（4,1）15，（1,3）2，（1,2）5,（3，2）4，（4,5）16}

LW={}

0

8

1154

216

5

243

CT

0

1

2

3

4

fromvex

0

4

1

3

4

endvex

4

1

3

2

5

weight

8

15

2

4

16

十-1、有向无权图如下

要求1：

给出顶点数组和邻接表。

要求2：

分别给出小优先和大优先的拓扑排序过程。

答2：

小优先拓扑序列：

023*******

大优先拓扑序列：

3502716849

十-2、一个AOV网如图所示，

要求1：

画出其顶点数组和邻接表；

要求2：

分别按小优先和大优先画出其拓扑排序过程。

答1：

Λ

顶点数组：

0

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

邻接表：

答2-1：

小优先拓扑序列：

021*******

答2-2：

大优先拓扑序列：

2603857491

十一-1、分析以下算法：

intBinsch（structElemTypeA[],intn,KeyTypeK）

{intlow=0,high=n-1;

while（low<=high）{

intmid=（low+high）/2;

if（K==A[mid].key）returnmid;

elseif（K

elselow=mid+1;

}

return-1;

}

要求分析以下问题：

1、算法功能？

2、算法返回？

3、算法有无健壮性？

若有，是哪（些）语句？

4、算法的关键语句是哪（些）语句？

5、算法的时间复杂度大O（）？

十一-2、分析以下算法：

intSeqsch1（structElemTypeA[],KeyTypeK,intn）

{

inti;

A[n].key=K;

for（i=0;;i++）

if（A[i].key==K）//A

break;

if（i

returni;//B

elsereturn-1;//C

}

1、该算法是哪种查找算法？

顺序查找。

2、填写算法中标注A、B、C处.语句缺失的部分

十一-3、voidInsertSort（structElemTypeA[],intn）

{

inti,j;

structElemTypex;

for（i=1;i<=n-1;i++）

{

x=A[i];

for（j=i-1;j>=0;j--）

if（x.stn

A[j+1]=A[j];

else

break;

A[j+1]=x;

}

}

要求分析以下问题：

1、算法功能？

2、算法返回？

3、算法有无健壮性？

若有，是哪（些）语句？

4、算法的关键语句是哪（些）语句？

5、算法的时间复杂度大O（）？

十一-4、分析以下算法：

voidBubbleSort（structElemTypeA[],intn）

{structElemTypex;

inti,j,flag;

for（i=1;i<=n-1;i++）{

flag=0;

for（j=n-1;j>=i;j--）

if（A[j].stn

x=A[j];

A[j]=A[j-1];//A

A[j-1]=x;//B

flag=1;//C

}

if（flag==0）return;

}

}

1、该算法是哪种排序算法？

气泡。

2、填写算法中标注A、B、C处.语句缺失的部分

十二-1、算法设计及程序实现：

对数据进行查找，数据源自编，数据结构自定，查找方法自定。

要求1：

根据自定的数据结构进行定义，并组织数据。

要求2：

根据数据特点自选查找方法，编写算法。

要求3：

编写程序，实现以上数据的查找算法。

十二-2、算法设计及程序实现

对数据进行排序，数据源自编，数据结构自定，排序方法自定。

要求1：

根据自定的数据结构进行定义，并组织数据。

要求2：

根据数据特点自选排序方法，编写算法。

要求3：

编写程序，实现以上数据的排序算法。