数据结构第三次作业(12.6).pdf

难度系数及复杂系数说明：

难度系数从易到难分别为：N1、N2、N3、N4、N5

复杂系数从简到繁分别为：F1、F2、F3、F4、F5

数据结构第三阶段作业

第6章树和二叉树

6.1单项选择题

1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。（N2F1）

A.正确B.错误

2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为B个。

（N2F1）

A．15B．16C．17D．47

3.按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。（N2F1）

A.3B.4C.5D.6

4.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。（N3F1）

A.5B.6C.30D.32

5.深度为5的二叉树至多有__C__个结点。（N2F1）

A.16B.32C.31D.10

6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_

_A__。（N3F1）

A.2hB.2h-1C.2h+1D.h+1

7.对一个满二叉树，m个树叶，n个结点，深度为h，则_D___。（N3F1）

A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1

8.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。（N3F1）

A.不发生改变B.发生改变C.不能确定D.以上都不对

9.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C___。

（N3F1）

A.uwvtsB.vwutsC.wuvtsD.wutsv

6.2简答题

1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。（N2F3）

1

2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。（N3F2）

请画出该树。

3.以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其

带权路径长度。（N3F3）

4.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?（N3F2）

最大深度：h=N-k+1,最小深度：logkN+1

第7章图

7.1单项选择题

1．在一个图中，所有顶点的度数之和等于所有边数的__C__倍。（N3F1）

A.1/2B.1C.2D.4

2．任何一个无向连通图的最小生成树B。（N3F1）

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。（N3F1）

A.1/2B.1C.2D.4

4．一个有n个顶点的无向图最多有_C___条边。（N2F1）

A.nB.n(n-1)C.n(n-1)/2D.2n