习题答案1分析Word下载.docx
- 文档编号:7723657
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:14
- 大小:196.16KB
习题答案1分析Word下载.docx
《习题答案1分析Word下载.docx》由会员分享,可在线阅读,更多相关《习题答案1分析Word下载.docx(14页珍藏版)》请在冰点文库上搜索。
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.一棵深度为H的满k叉树有如下性质:
第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。
若按层次顺序从1开始对全部结点编号,问:
(1)第i层上有多少个结点?
(2)编号为p的结点的第i个孩子结点(若存在)的编号是多少?
(3)编号为p的结点的双亲结点(若存在)的编号是多少?
(1)
个
(2)(1+(p-1)*k)+i
(3)
(p≠1)】
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*nB.n(n+1)C.n/2D.n*(n-1)
答:
当月球运行到地球和太阳的中间,如果月球挡住了太阳射向地球的光,便发生日食。
13、1663年,英国科学家罗伯特.胡克用自制的复合显微镜观察一块软木薄片的结构,发现它们看上去像一间间长方形的小房间,就把它命名为细胞。
15.设图如右所示,
,在下面的5个序列中,符合深度优先遍历的序列有()个。
17、近年来,我国积极推广“无车日”活动,以节约能源和保护环境。
科学家也正在研制太阳能汽车和燃料电池汽车,减少对空气的污染。
aebdfcacfdebaedfcbaefdcbaefdbc
1、放大镜为什么能放大物体的图像呢?
我们注意到它的特点了吗?
(P3)A.5个B.4个C.3个D.2个
19、细胞也是生物最基本的功能单位,生物的呼吸、消化、排泄、生长、发育、繁殖、遗传等生命活动都是通过细胞进行的。
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的拓扑序列是()。
20、在水中生活着许我微生物,常见的有草履虫、变形虫、喇叭虫、眼虫、团藻等。
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
13、以太阳为中心,包括围绕它转动的八大行星(包括围绕行星转动的卫星)、矮行星、小天体(包括小行星、流星、彗星等)组成的天体系统叫做太阳系。
A
24.在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是()。
5、月球在圆缺变化过程中出现的各种形状叫作月相。
月相变化是由于月球公转而发生的。
它其实是人们从地球上看到的月球被太阳照亮的部分。
A.G中有弧<
Vi,Vj>
B.G中有一条从Vi到Vj的路径
硫酸铜溶液的颜色逐渐变浅,取出铁钉后,发现浸入硫酸铜溶液中的那部分变红了。
C.G中没有弧<
Vi,Vj>
D.G中有一条从Vj到Vi的路径
在铁制品表面涂上油漆或菜油,用完铁制品后擦干放在干燥的地方等。
26.关键路径是事件结点网络中()。
A.从源点到汇点的最长路径B.从源点到汇点的最短路径
C.最长回路D.最短回路
37.设有无向网如下,写出其邻接矩阵,并在此基础上按普里姆算法求最小生成树。
邻接矩阵:
最小生成树:
38.试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。
每次输出一个入度为0的顶点。
abcdefg、abcdfeg、abcfdeg。
39.设有向网如下,用弗洛伊德算法求图中各对顶点间的最短路径。
35.设有AOE网如下,试求关键路径。
关键路径1:
v1→v2→v5→v7
关键路径2:
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*/++
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 答案 分析