习题答案(1)
更新时间:2024-04-24 20:13:01 阅读量: 综合文库 文档下载
- 题目答案软件推荐度:
- 相关推荐
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.一棵深度为H的满k叉树有如下性质:第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。若按层次顺序从1开始对全部结点编号,问:(1)第i层上有多少个结点?(2)编号为p的结点的第i个孩子结点(若存在)的编号是多少?(3)编号为p的结点的双亲结点(若存在)的编号是多少? 参考答案: (1)ki?1个
(2)(1+(p-1)*k)+i (3)??p?k?2?(p≠1) 】 ?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 B.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={
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中有弧
26.关键路径是事件结点网络中( )。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路 参考答案:A
37.设有无向网如下,写出其邻接矩阵,并在此基础上按普里姆算法求最小生成树。
参考答案:
正在阅读:
习题答案(1)04-24
消防应急预案演练总结04-21
教资作文万能开头结尾汇总08-01
简历怎么写12-11
传统文化教育02-19
高中英语选修7单词表05-02
金子般十句话——每天看一遍,好处大无边!08-02
成长的烦恼作文800字02-05
摄影作品分析08-26
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 习题
- 答案
- 说课
- 231062 北交《城市轨道交通牵引电气化概论》在线作业一 15秋答案
- 葡萄籽提取物产品的开发建设可行性研究报告
- 平凡的极致 衡水中学
- 西理工编译原理试题集1-7
- 2016年上海高三二模汇编-文言文阅读一(附答案)
- 第4章 结构型模式实训
- 纺织后整理复习题
- 2017年上半年湖南省建筑工程C证安全员试题
- 四语-王联丽-祁黄羊(第二课时教学设计)
- 4 上 生命与健康 计划 2018年新版 地质出版社
- 小学德育工作总结2016
- 关于参评省综合实践成果、校本课程成果奖的通知(排版)
- 商品期货逼仓案例分析(近20年国内外案例)
- 培智美工第2册
- 如何打造高绩效团队一
- 观课报告
- 沥青混凝土路面压实施工技术控制论文
- 人美版《美术》5年级下册19课 - 昨天、今天和明天
- 大学物理2期末考试试卷