电大数据结构(本)形考作业3-阶段性学习测验3答案

答案地址

点击查看答案

一、单项选择题(每小题2分,共32分)

题目1

假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为( )。

选择一项:
A. 15
B. 17
C. 16
D. 47
题目2

二叉树第k层上最多有( )个结点。

选择一项:
A. 2k-1
B. 2k-1
C. 2k
D. 2k-1
题目3

设某一二叉树先序遍历为abdec,中序遍历为dbeac,则该二叉树后序遍历的顺序是( )。

选择一项:
A. abedc
B. abdec
C. debca
D. debac
题目4

将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为( )。

选择一项:
A. 36
B. 35
C. 33
D. 34
题目5

如果将给定的一组数据作为叶子数值,所构造出的二叉树的带权路径长度最小,则该树称为( )。

选择一项:
A. 二叉树
B. 平衡二叉树
C. 哈夫曼树
D. 完全二叉树
题目6

在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为( )。

选择一项:
A. 5
B. 4
C. 7
D. 6
题目7

在一棵度具有5层的满二叉树中结点总数为( )。

选择一项:
A. 16
B. 32
C. 31
D. 33
题目8

利用n个值作为叶结点的权生成的哈夫曼树中共包含有( )个结点。

选择一项:
A. 2*n
B. n
C. 2*n-1
D. n+1
题目9

利用3、6、8、12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子结点中的最长带权路径长度为( )。

选择一项:
A. 30
B. 12
C. 18
D. 16
题目10

在一棵树中,( )没有前驱结点。

选择一项:
A. 树根结点
B. 叶结点
C. 分支结点
D. 空结点
题目11

设一棵有n个叶结点的二叉树,除叶结点外每个结点度数都为2,则该树共有( )个结点。

选择一项:
A. 2n-1
B. 2n+1
C. 2n+2
D. 2n
题目12

在一个图G中,所有顶点的度数之和等于所有边数之和的( )倍。

选择一项:
A. 2
B. 1/2
C. 1
D. 4
题目13

邻接表是图的一种( )。

选择一项:
A. 散列存储结构
B. 索引存储结构
C. 顺序存储结构
D. 链式存储结构
题目14

如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是( )。

选择一项:
A. 有回路
B. 完全图
C. 一棵树
D. 连通图
题目15

图的深度优先遍历算法类似于二叉树的( )遍历。

选择一项:
A. 先序
B. 后序
C. 中序
D. 层次
题目16

已知下图所示的一个图,若从顶点V1出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为( )。

选择一项:
A. V1V3V6V7V2V4V5V8
B. V1V2V4V8V5V3V6V7
C. V1V2V4V8V3V5V6V7
D. V1V2V4V5V8V3V6V7

二、填空题 (每小题1分,共20分)

题目17

结点的度是指结点所拥有的回答

题目18

树的度是指回答

题目19

度大于0的结点称作__________________或__________________。

题目20

度等于0的结点称作__________________或__________________。

题目21

在一棵树中,每个结点的_______________或者说每个结点的_______________称为该结点的_______________,简称为孩子。

题目22

从根结点到该结点所经分支上的所有结点称为该结点的回答

题目23

树的深度或高度是指回答

题目24

具有n个结点的完全二叉树的深度是_____________。

题目25

先序遍历二叉树的的操作定义为;若二叉树为空,则为空操作,否则进行如下操作,访问二叉树的回答
;先序遍历二叉树的回答
,先序遍历二叉树的回答

题目26

中序遍历二叉树的的操作定义为;若二叉树为空,则为空操作,否则进行如下操作,中序遍历二叉树的回答
;访问而叉树的回答
,中序遍历二叉树的回答

题目27

后序遍历二叉树的的操作定义为;若二叉树为空,则为空操作,否则进行如下操作,后序遍历二叉树的回答
;后序遍历二叉树的回答
,访问而叉树的回答

题目28

将树中结点赋上一个有着某种意义的实数,称此实数为该结点的回答

题目29

树的带权路径长度为树中所有叶子结点的回答

题目30

哈夫曼树又称为回答
,它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL回答

题目31

若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树,则其带权路径长度是回答

题目32

具有m个叶子结点的哈夫曼树共有回答
结点。

题目33

图的遍历是从图的某一顶点出发,按照一定的搜索方法对图中回答
各做回答
访问的过程。

题目34

图的深度优先搜索遍历类似于树的回答
遍历。

题目35

图的广度优先搜索类似于树的回答
遍历。

题目36

图常用的两种存储结构是_____________和_____________。

三、综合题(每小题8分,共40分)

题目37

写出如下图所示的二叉树的先序、中序和后序遍历序列。

题目38

已知某二叉树的先序遍历结果是: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,请画出这棵二叉树,并写出该二叉树后续遍历的结果。

题目39

假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成,它们出现的频率分别是:10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求:

(1)设计一棵哈夫曼树;

(2)计算其带权路径长度WPL;

(3)写出每个字符的哈夫曼编码。

题目40

请根据以下带权有向图G

(1)给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列;

(2)给出G的一个拓扑序列;

(3)给出从结点v1到结点v8的最短路径。

题目41

已知无向图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)写出每个顶点的度。

四、程序填空题(每空2分,共8分)

题目42

以下是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。

void Inorder (struct BTreeNode *BT)

{

if(BT!=NULL){

回答
;

回答
;

Inorder(BT->right);}

}

题目43

以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。

void Inorder (struct BTreeNode *BT)

{

if(BT!=NULL){

回答
;

Inorder(BT->right);

回答
;}

}

答案地址

点击查看答案