数据结构形考作业3.doc
文本预览下载声明
一、单项选择题（每小题2分，共32分）
题目1
假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）。
选择一项：
A. 17
B. 16
C. 15
D. 47
题目2
二叉树第k层上最多有（ ）个结点。
选择一项：
A. 2k
B. 2k-1
C. 2k-1
D. 2k-1
题目3
设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。
选择一项：
A. debac
B. abdec
C. abedc
D. debca
题目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. 7
B. 6
C. 5
D. 4
题目7
在一棵度具有5层的满二叉树中结点总数为（ ）。
选择一项：
A. 31
B. 32
C. 16
D. 33
题目8
利用n个值作为叶结点的权生成的哈夫曼树中共包含有（ ）个结点。
选择一项：
A. 2*n
B. n
C. 2*n-1
D. n+1
题目9
利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（ ）。
选择一项：
A. 16
B. 18
C. 12
D. 30
题目10
在一棵树中，（ ）没有前驱结点。
选择一项：
A. 树根结点
B. 分支结点
C. 空结点
D. 叶结点
题目11
设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ ）个结点。
选择一项：
A. 2n-1
B. 2n+1
C. 2n
D. 2n+2
题目12
在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。
选择一项：
A. 4
B. 2
C. 1/2
D. 1
题目13
邻接表是图的一种（ ）。
选择一项：
A. 链式存储结构
B. 散列存储结构
C. 索引存储结构
D. 顺序存储结构
题目14
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
选择一项：
A. 有回路
B. 一棵树
C. 完全图
D. 连通图
题目15
图的深度优先遍历算法类似于二叉树的（ ）遍历。
选择一项：
A. 先序
B. 层次
C. 后序
D. 中序
题目16
已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
选择一项：
A. V1V2V4V5V8V3V6V7
B. V1V2V4V8V3V5V6V7
C. V1V2V4V8V5V3V6V7
D. V1V3V6V7V2V4V5V8
二、填空题 （每小题1分，共20分）
题目17
结点的度是指结点所拥有的子树树木或后继结点数。
题目18
树的度是指树中所有结点的度的最大值。
题目19
度大于0的结点称作__________________或__________________。
分支结点、非终端结点
题目20
满分1.00
度等于0的结点称作__________________或__________________。
叶子结点、非终端结点
题目21
在一棵树中，每个结点的_______________或者说每个结点的_______________称为该结点的_______________，简称为孩子。
子树的根、后继结点、孩子结点
题目22
从根结点到该结点所经分支上的所有结点称为该结点的祖先。
题目23
树的深度或高度是指树中结点的最大层数。
题目24
具有n个结点的完全二叉树的深度是_____________。
[log2n]+1
题目25
先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结点；先序遍历二叉树的左子树，先序遍历二叉树的右子树。
题目26
中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左子树；访问而叉树的根结点，中序遍历二叉树的右子树。
题目27
后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左子树；后序遍历二叉树的右子树，访问而叉树的根结点。
题目28
将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权。
题目29
显示全部