电大资源网《数据结构（本）》形成性考核册作业3答案
最近更新：2020-04-14
【数据结构】形考作业三：答案
（本部分作业覆盖教材第6-7章的内容）
一、单项选择题
1．B 2．B 3．D 4．C 5．B 6．A 7．A 8．C 9．A 10. D
11. A 12．C 13．C 14．B 15．B 16．C 17．B 18．C 19．A 20．B
21．D 22．B 23. B 24. B 25. C 26. A 27．A 28．C
二、填空题
1．子树树木或后继结点数
2．树中所有结点的度的最大值
3．分支结点 非终端结点
4．叶子结点 终端结点
5．子树的根 后继结点 孩子结点
6．祖先
7．树中结点的最大层数
8．
9．根结点 左子树 右子树
10．左子树 根结点 右子树
11．左子树 右子树 根结点
12．权
13．带权路径长度之和
14．最优二叉树 最小的二叉树
15．69
16．
17．多对多
18．所有顶点 一次
19．先序
20．按层次
21．n2
22．邻接矩阵 邻接表
23．2(n-1)
24．n-1
25．栈
三、综合题
1．写出如下图所示的二叉树的先序、中序和后序遍历序列。
答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…..，这样划分一直进行到树叶结点。
(1)先序为“根左右”，先序序列为：fdbacegihl
(2)中序为“左根右”，中序序列为：abcdefghij
(3)后序为“左右根”，后序序列为：acbedhjigf
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，请画出这棵二叉树，并写出该该二叉树后续遍历的结果。
（1）二叉树图形表示如下：
（2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。
3．答
⑴ 已知深度为k的二叉树最多有2k-1个结点(K≥1)，
29-1<892< 210-1，故树的高度为10
⑵ 对于完全二叉树来说，度为1的结点只能是0或1
因为n=n0+n1+n2和n0=n2+1
得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错
设n1=1，892=n0+1+n2=2n2+2
得n2 =445→ n0=n2+1=446
叶子结点数为446。
⑶ 由⑵得单支结点数为1
⑷ 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点 即为最后一个非终端结点，
序号为892/2=446。
4．
（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树
（2）中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树
（3）先序和后序序列相同的二叉树为空树或仅有一个结点
5．
（1）哈夫曼树如图B-4所示。
图B-4
（2）其带权路径长度WPL值为270。
（3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01
6．答
（1）深度优先遍历：v1,v2,v3,v8,v5,v7,v4,v6
广度优先遍历：v1,v2,v4,v6,v3,v5,v7,v8
(2) G的拓扑序列为：v1,v2,v4,v6,v5,v5,v3,v5,v7,v8
(3)最短路径为：v1,v2,v5,v7,v8
7．
① g1的图示和图g1的邻接表如下图所示。
图G
② 图G的邻接矩阵如下图所示：
图G的邻接矩阵 图G的邻接表
③ V1、V2、V3、V4、V5的度分别为：2，3，2，3，2
四、程序分析题
1. (1) return c1+1
(2) NodeLevel(BT->right,X)
(3) (c2>=1) return c2+1
2．(1)for(j=0; j<n; j++)
(2) dfstree(GA,j,n);
五、算法设计题
1．写一个将一棵二叉树复制给另一棵二叉树的算法。
define NULL 0
typedef struct btnode
{
elemtype data;
struct btnode *lchild, *rchild;
}bitnode, *bitree;
bitree *CopyTree( bitnode *p )
{
/*复制一棵二叉树*/
bitnode *t;
if ( p!=NULL )
{
t=(bitnode *)malloc (sizeof (bitnode));
t->data=p->data;
t->lchild=CopyTree(p->lchild);
t->rchild=CopyTree(p->rchild);
return(t);
}
else
return(NULL);
}/*CopyTree*/
2.
int BTreeLeafCount(struct BTreeNode* BT)
{
if(BT==NULL) return 0;
else if(BT->left==NULL && BT->right==NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}
六、完成：实验3――栈、队列、递归程序设计
实验4——图的存储方式和应用
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。
