习题答案(1)

1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（ ）。

A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DE 参考答案：D

3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。

A．250 B．500 C．254 D．505 E．以上答案都不对 参考答案：E

8．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A．4 B．5 C．6 D．7 参考答案：C

10．具有10个叶结点的二叉树中有（ ）个度为2的结点。

A．8 B．9 C．10 D．11 参考答案：B

53．由3个结点可以构造出（ ）种不同的二叉树。

A．2 B．3 C．4 D．5 参考答案：D

47．引入二叉线索树的目的是（ ）。

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

19．将如下由三棵树组成的森林转换为二叉树。 D G A J H I E B C L M K N O F 参考答案：

P A

B D E G C

H F I KO J L M

P N

O

反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化成树的结果不一样）

21．设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。 参考答案：

A

B D

F C E

G I

H

27．设二叉树T的存储结构如下：

1 2 3 4 5 6 7 8 9 10 Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 9 7 B 4 5 A 0 8 C 0 0 E 0 10 G 0 1 I 0 其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T的值为6，试：(1)画出二叉树的逻辑结构；(2)写出按前序、中序、后序遍历该二叉树所得到的结点序列；(3)画出二叉树的后序线索树。 参考答案：

前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

31．假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。 参考答案：

各字母编码如下：c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。

33．设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：(1)树T的最大深度和最小可能深度分别是多少？(2)树T中共有多少非叶结点？(3)若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 参考答案：

(1)最大深度6，最小深度4； (2)非叶结点数5；

(3)哈夫曼树见下图，其带权路径长度wpl=51。

34．一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，问：(1)第ｉ层上有多少个结点？(2)编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？(3)编号为ｐ的结点的双亲结点（若存在）的编号是多少？ 参考答案： (1)ki?1个

(2)（１＋（ｐ－１）＊ｋ）＋ｉ (3)??p?k?2?（ｐ≠１） 】 ?k??

2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 参考答案：

本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表

达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。

int Precede(char optr1, char optr2)

// 比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1 {switch(optr1)

{case‘+’:case‘-’:if(optr2==‘+’||optr2==‘-’)return(0);else return(-1); case‘*’:case‘/’:if(optr1==‘*’||optr2==‘/’)return(0);else return(1);

} }

void InorderExp (BiTree bt)

//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名 {int bracket; if(bt)

{if(bt->lchild!=null)

{bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优先级

if(bracket==1) printf(‘(’);

InorderExp(bt->lchild); //输出左子女表示的算术表达式 if(bracket==1)printf(‘)’); //加上右括号 }

printf(bt->data); //输出根结点

if(bt->rchild!=null) //输出右子树表示的算术表达式 {bracket=Precede(bt->data,bt->rchild->data)

if (bracket==1)printf(“(”); //右子女级别低，加括号 InorderExp (bt->rchild); if(bracket==1)printf(“)”); } }

}//结束Inorder Exp

4．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 参考答案：

方法一：BiTree Creat(ElemType A[],int i)

//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树

{BiTree tree;

if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];

if(2*i>n) tree->lchild=null;else tree->lchild=Creat(A,2*i);

if(2*i+1>n) tree->rchild=null;else tree->rchild=Creat(A,2*i+1); }

return (tree); }//Creat 初始调用时i=1。

图的部分习题答案

5．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1） 参考答案：D

15．设图如右所示，，在下面的5个序列中，符合深度优先遍历的序列

有（ ）个。

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个 参考答案：D

21．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,, ,,,,}，G的拓扑序列是（ ）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7

参考答案：A 24．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。

A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径 参考答案：D

26．关键路径是事件结点网络中（ ）。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 参考答案：A

37．设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。

参考答案：

本文来源：https://www.bwwdw.com/article/a3pp.html