2021年数据结构本形成性考核作业.doc

数据构造（本）课程作业
作业3
（本某些作业覆盖教材第6-7章内容）

一、单项选取题
1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。
A．15 B．16 C．17 D．47
2．二叉树第k层上最多有（ ）个结点。
A．2k B．2k-1
C．2k-1 D．2k-1
3．二叉树深度为k，则二叉树最多有（ ）个结点。
A．2k B．2k-1
C．2k-1 D．2k-1
4. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历顺序是（ ）。
A．abdec B．debac C．debca D．abedc
5．将具有150个结点完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为69结点双亲结点编号为（ ）。
A．33 B．34 C．35 D．36
6．如果将给定一组数据作为叶子数值，所构造出二叉树带权途径长度最小，则该树称为（ ）。
A．哈夫曼树 B．平衡二叉树
C．二叉树 D．完全二叉树
7．下列关于二叉树说法对的是（ ）。
A．二叉树中度为0结点个数等于度为2结点个数加1
B．二叉树中结点个数必不不大于0
C．完全二叉树中，任何一种结点度，或者为0或者为2
D．二叉树度是2
8．在一棵度为3树中，度为3结点个数为2，度为2结点个数为1，则度为0结点个数为（ ）。
A．4 B．5 C．6 D．7
9．在一棵度具备5层满二叉树中结点总数为（ ）。
A．31 B．32 C．33 D．16
10. 运用n个值作为叶结点权生成哈夫曼树中共包具有( )个结点。
A. n B. n+1 C. 2*n D. 2*n-1
11. 运用3、6、8、12这四个值作为叶子结点权，生成一棵哈夫曼树，该树中所有叶子最长带权途径长度为( )。
A. 18 B. 16 C. 12 D. 30
12．在一棵树中，（ ）没有前驱结点。
A．分支结点 B．叶结点 C．树根结点 D．空结点

13．在一棵二叉树中，若编号为i结点存在右孩子，则右孩子顺序编号为（ ）。
A．2i B．2i-1 D．2i+1 C．2i+2
14．设一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。
A．n B．n-1 C．n+1 D．2n
15．设一棵有n个叶结点二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。
A．2n B．2n-1 C．2n+1 D．2n+2
16．在一种图G中，所有顶点度数之和等于所有边数之和（ ）倍。
A．1/2 B．1 C．2 D．4
17．在一种有向图中，所有顶点入度之和等于所有顶点出度之和（ ）倍。
A．1/2 B．2 C．1 D．4
18．一种具备n个顶点无向完全图包括（ ）条边。
A．n（n-1） B．n（n+1） C． n（n-1）/2 D． n（n+1）/2
19．一种具备n个顶点有向完全图包括（ ）条边。
A．n（n-1） B．n（n+1） C． n（n-1）/2 D． n（n+1）/2
20．对于具备n个顶点图，若采用邻接矩阵表达，则该矩阵大小为（ ）。
A．n B．n2 C．n-1 D．（n-1）2
21．对于一种具备n个顶点和e条边无向图，若采用邻接表表达，则所有顶点邻接表中结点总数为（ ）。
A．n B．e C．2n D．2e
22．在有向图邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。
A．入边 B． 出边
C．入边和出边 D． 不是入边也不是出边
23．邻接表是图一种（ ）。
A．顺序存储构造 B．链式存储构造
C．索引存储构造 D．散列存储构造
24．如果从无向图任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A．完全图 B．连通图 C．有回路 D．一棵树
25．下列关于图遍历说法不对的是（ ）。
A．连通图深度优先搜索是一种递归过程
B．图广度优先搜索中邻接点寻找具备“先进先出”特性
C．非连通图不能用深度优先搜索法
D．图遍历规定每一顶点仅被访问一次
26．无向图邻接矩阵是一种（ ）。
A．对称矩阵 B． 零矩阵 C．上三角矩阵 D．对角矩阵
27．图深度优先遍历算法类似于二叉树（ ）遍历。
A．先序 B． 中序 C．后序 D．层次

28．已知下图所示一种图，若从顶点V1出发，按深度优先搜索法进行遍历，则也许得到一种顶点序列为（ ）。
A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8

V6
V7
V1
V2
V3
V8
V4
V5

二、填空题
1．结点度是指结点所拥有 。
2．树度是指 。
3．度不不大于0结点称作 或 。
4．度等于0结点称作 或 。
5．在一棵树中，每个结点 或者说每个结点 称为该结点 ，简称为孩子。
6．从根结点到该结点所经分支上所有结点称为该结点 。
7．树深度或高度是指 。
8．具备n个结点完全二叉树深度是 。
9．先序遍历二叉树操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树 ；先序遍历二叉树 ，先序遍历二叉树
。
10．中序遍历二叉树操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树 ；访问而叉树 ，中序遍历二叉树
。
11．后序遍历二叉树操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树 ；后序遍历二叉树 ，访问而叉树
。
12．将树中结点赋上一种有着某种意义实数，称此实数为该结点 。
13．树带权途径长度为树中所有叶子结点 。
14．哈夫曼树又称为 ，它是n个带权叶子结点构成所有二叉树中带权途径长度WPL 。
15．若以4，5，6，7，8作为叶子结点权值构造哈夫曼树，则其带权途径长度是 。
16．具备m个叶子结点哈夫曼树共有 结点。
17．在图中，任何两个数据元素之间都也许存在关系，因而图数据元素之间是一种
关系。
18．图遍历是从图某一顶点出发，按照一定搜索办法对图中 各做
访问过程。
19．图深度优先搜索遍历类似于树 遍历。
20．图广度优先搜索类似于树 遍历。
21．具备n个顶点有向图邻接矩阵，其元素个数为 。
22．图惯用两种存储构造是 和 。
23．在有n个顶点有向图中，每个顶点度最大可达 。
24．在一种带权图中，两顶点之间最段途径最多通过 条边。
25．为了实现图深度优先搜索遍历，其非递归算法中需要使用一种辅助数据构造为 。

三、综合题
1．写出如下图所示二叉树先序、中序和后序遍历序列。
a
j
f
g
h
i
d
c
e
b

2．已知某二叉树先序遍历成果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它中序遍历成果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历成果。

3．已知一棵完全二叉树共有892个结点，求
⑴ 树高度
⑵ 叶子结点数
⑶ 单支结点数
⑷ 最后一种非终端结点序号

4．给出满足下列条件所有二叉树。
（1）先序和中序相似
（2）中序和后序相似
（3）先序和后序相似

5．假设通信用报文由9个字母A、B、C、D、E、F、G、H和I构成，它们浮现频率分别是：10、20、5、15、8、2、3、7和30。请请用这9个字母浮现频率作为权值求：
（1）设计一棵哈夫曼树；
（2）计算其带权途径长度WPL；
（3）写出每个字符哈夫曼编码。

6．请依照如下带权有向图G
（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得结点序列；
（2）给出G一种拓扑序列；
（3）给出从结点v1到结点v8最短途径。

7．已知无向图G描述如下：
G=（V，E）
V={V1，V2，V3，V4，V5}
E={（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）}
（1）画出G图示；
（2）然后给出G邻接矩阵和邻接表；
（3）写出每个顶点度。

四、程序填空题
1. 下面函数功能是返回二叉树BT中值为X结点所在层号，请在划有横线地方填写适当内容。
int NodeLevel(struct BinTreeNode* BT，char X)
{
if(BT==NULL) return 0； /*空树层号为0*/
else if(BT->data==X) return 1； /*根结点层号为1*/
/*向子树中查找X结点*/
else {
int c1=NodeLevel(BT->left,X);
if(c1>=1) ___(1)___________；
int c2=______(2)________ __；
if ___(3)__________________；
//若树中不存在X结点则返回0
else return 0;
}
}

2. 下面函数功能是按照图深度优先搜索遍历办法，输出得到该图生成树中各条边，请在划有横线地方填写适当内容。

void dfstree(adjmatrix GA，int i，int n)
{
int j;
visited[i]=1；
(1)
if(GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j])
{
printf("(%d,%d)%d,",i,j,GA[i][j]);
(2)
}
}

五、算法设计题
1．写一种将一棵二叉树复制给另一棵二叉树算法。

2．依照下面函数声明编写出求一棵二叉树中叶子结点总数算法，该总数值由函数返回。假定参数BT初始指向二叉树根结点。
int BTreeLeafCount(struct BTreeNode* BT);

六、完毕：实验3――栈、队列、递归程序设计
实验4——图存储方式和应用
依照实验规定（见教材P203）认真完毕本实验，并提交实验报告。