习题答案1分析Word文件下载.docx
《习题答案1分析Word文件下载.docx》由会员分享，可在线阅读，更多相关《习题答案1分析Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。
21．设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。
27．设二叉树T的存储结构如下：
12345678910
Lchild
0
2
3
7
5
8
10
1
Data
J
H
F
D
B
A
C
E
G
I
Rchild
9
4
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:
0110c2:
10c3:
0010c4:
0111c5:
000c6:
010c7:
11c8:
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）
个
（2）（１＋（ｐ－１）＊ｋ）＋ｉ
（3）
（ｐ≠１）】
2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。
本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表达式还原成原表达式。
二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树表示中消除了括号。
将中序序列加上括号就恢复原貌。
当根结点运算符优先级高于左子树（或右子树）根结点运算符时，就需要加括号。
intPrecede（charoptr1,charoptr2）
//比较运算符级别高低，optr1级别高于optr2时返回1，相等时返回0，低于时返回-1
{switch（optr1）
{case‘+’:
case‘-’:
if（optr2==‘+’||optr2==‘-’）return（0）;
elsereturn（-1）;
case‘*’:
case‘/’:
if（optr1==‘*’||optr2==‘/’）return（0）;
elsereturn
（1）;
}
voidInorderExp（BiTreebt）
//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名
{intbracket;
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->
rchild->
data）
if（bracket==1）printf（“（”）;
//右子女级别低，加括号
InorderExp（bt->
rchild）;
if（bracket==1）printf（“）”）;
}}
}//结束InorderExp
4．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。
方法一：
BiTreeCreat（ElemTypeA[],inti）
//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树
{BiTreetree;
if（i<
=n）{tree=（BiTree）malloc（sizeof（BiNode））;
tree->
data=A[i];
if（2*i>
n）tree->
lchild=null;
elsetree->
lchild=Creat（A,2*i）;
if（2*i+1>
rchild=null;
rchild=Creat（A,2*i+1）;
}
return（tree）;
}//Creat
初始调用时i=1。
图的部分习题答案
5．n个结点的完全有向图含有边的数目（ ）。
A．n*nＢ．n（n+1）C．n／2D．n*（n-1）
15．设图如右所示，
，在下面的5个序列中，符合深度优先遍历的序列有（）个。
aebdfcacfdebaedfcbaefdcbaefdbc
A．5个B．4个C．3个D．2个
21．已知有向图G=（V,E），其中V={V1,V2,V3,V4,V5,V6,V7}，E={<
V1,V2>
<
V1,V3>
V1,V4>
V2,V5>
<
V3,V5>
V3,V6>
V4,V6>
V5,V7>
V6,V7>
}，G的拓扑序列是（）。
A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7
A
24．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。
A．G中有弧<
Vi，Vj>
B．G中有一条从Vi到Vj的路径
C．G中没有弧<
Vi,Vj>
D．G中有一条从Vj到Vi的路径
26．关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长回路D．最短回路
37．设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。
邻接矩阵：
最小生成树：
38．试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。
每次输出一个入度为０的顶点。
ａｂｃｄｅｆｇ、ａｂｃｄｆｅｇ、ａｂｃｆｄｅｇ。
39．设有向网如下，用弗洛伊德算法求图中各对顶点间的最短路径。
35．设有ＡＯＥ网如下，试求关键路径。
关键路径１：
v1→v2→v5→v7
关键路径２：
v1→v3→v6→v7
32．下图是带权的有向图G的邻接表表示法，求：
（1）以结点V1出发深度遍历图G所得的结点序列；
（2）以结点V1出发广度遍历图G所得的结点序列；
（3）从结点V1到结点V8的最短路径；
（4）从结点V1到结点V8的关键路径。
（1）V1,V2,V3,V8,V5,V7,V4,V6；
（2）V1,V2,V4,V6,V3,V5,V7,V8；
（3）V1到V8最短路径56，路径为V1----V2----V5----V7----V8；
（4）V1到V8的关键路径是V1----V6----V5----V3----V8，长97。
29．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。
顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。
34．对图示的AOE网络，计算各活动弧的e（ai）和l（ai）的函数值，各事件（顶点）的ve（Vj）和vl（Vj）的函数值，列出各条关键路径。
7．有向图的邻接表存储如下，要求：
（1）画出其邻接矩阵存储；
（2）写出图的所有强连通分量；
（3）写出顶点a到顶点i的全部简单路径。
（1）略。
（注：
邻接矩阵下标按字母升序:
abcdefghi）
（2）强连通分量：
（a），（d），（h），（b，e，i，f，c，g）
（3）顶点a到顶点i的简单路径：
（a->
b->
e->
i），（a->
c->
g->
i）。
数组
20．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40
23．将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A．198B．195C．197D．196
25．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A．60B．66C．18000D．33
26．算术表达式a+b*（c+d/e）转为后缀表达式后为（）。
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++
升级会员 