数据结构第六章习题课
- 格式：doc
- 大小：67.50 KB
- 文档页数：10
下载文档原格式
合集下载
数据结构 第六章 图 练习题及答案详细解析
图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。
【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。
《数据结构(C语言版 第2版)》(严蔚敏 著)第六章练习题答案
《数据结构（C语言版第2版）》（严蔚敏著）第六章练习题答案第6章图1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A．1/2B．1C．2D．4答案：C（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1/2B．1C．2D．4答案：B解释：有向图所有顶点入度之和等于所有顶点出度之和。
（3）具有n个顶点的有向图最多有（）条边。
A．n B．n(n-1)C．n(n+1)D．n2答案：B解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。
A．n B．2(n-1)C．n/2D．n2答案：B所谓连通图一定是无向图,有向的叫做强连通图连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素（5）G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A．7B．8C．9D．10答案：C解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。
A．非连通B．连通C．强连通D．有向答案：B解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。
（7）下面（）算法适合构造一个稠密图G的最小生成树。
A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法答案：A解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。
（8）用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。
A．栈 B.队列 C.树D．图答案：B解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
数据结构课后习题及解析第六章
第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
数据结构第六章图练习题及答案详细解析（精华版）
数据结构第六章图练习题及答案详细解析（精华版）第一篇：数据结构第六章图练习题及答案详细解析(精华版) 图1.填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵ 任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。
【免费下载】数据结构 第6章习题答案
4 5 3 (3)
（注：合并值应排在叶子值之后）
1
2
（注：原题为选择题：Ａ．32
Ｂ．33
Ｃ．34
Ｄ．15）
三、单项选择题（每小题 1 分，共 11 分）
（ C ）1． 不含任何结点的空树
。
（Ａ）是一棵树;
（Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树;
（Ｄ）既不是树也不是二叉树
答：以前的标答是 B，因为那时树的定义是 n≥1
空指针。 （正确。用二叉链表存储包含 n 个结点的二叉树，结点共有 2n 个链域。由于二叉树中，除根结点外，每 一个结点有且仅有一个双亲，所以只有 n-1 个结点的链域存放指向非空子女结点的指针，还有 n+1 个空指 针。）即有后继链接的指针仅 n-1 个。 （ √ ）10. 〖01 年考研题〗具有 12 个结点的完全二叉树有 5 个度为 2 的结点。
，而 N 的右子女是它在原树里对应结点的 D 。
供选择的答案
A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构
B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟
C～D： ①最左子结点
② 最右子结点 ③ 最邻近的右兄弟
④ 最邻近的左兄弟
⑤ 最左的兄弟 ⑥ 最右的兄弟
答案：A=
B=
C=
D＝
答案：ABCDE＝2，1，1，3
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术关，系电，力根保通据护过生高管产中线工资敷艺料设高试技中卷术资配，料置不试技仅卷术可要是以求指解，机决对组吊电在顶气进层设行配备继置进电不行保规空护范载高与中带资负料荷试下卷高总问中体题资配，料置而试时且卷，可调需保控要障试在各验最类；大管对限路设度习备内题进来到行确位调保。整机在使组管其高路在中敷正资设常料过工试程况卷中下安，与全要过，加度并强工且看作尽护下可关都能于可地管以缩路正小高常故中工障资作高料；中试对资卷于料连继试接电卷管保破口护坏处进范理行围高整，中核或资对者料定对试值某卷，些弯审异扁核常度与高固校中定对资盒图料位纸试置，.卷编保工写护况复层进杂防行设腐自备跨动与接处装地理置线，高弯尤中曲其资半要料径避试标免卷高错调等误试，高方要中案求资，技料编术试5写交卷、重底保电要。护气设管装设备线置备4高敷动调、中设作试电资技，高气料术并中课3试中且资件、卷包拒料中管试含绝试调路验线动卷试敷方槽作技设案、，术技以管来术及架避系等免统多不启项必动方要方式高案，中；为资对解料整决试套高卷启中突动语然过文停程电机中气。高课因中件此资中，料管电试壁力卷薄高电、中气接资设口料备不试进严卷行等保调问护试题装工，置作合调并理试且利技进用术行管，过线要关敷求运设电行技力高术保中。护资线装料缆置试敷做卷设到技原准术则确指：灵导在活。分。对线对于盒于调处差试，动过当保程不护中同装高电置中压高资回中料路资试交料卷叉试技时卷术，调问应试题采技，用术作金是为属指调隔发试板电人进机员行一，隔变需开压要处器在理组事；在前同发掌一生握线内图槽部纸内故资，障料强时、电，设回需备路要制须进造同行厂时外家切部出断电具习源高题高中电中资源资料，料试线试卷缆卷试敷切验设除报完从告毕而与，采相要用关进高技行中术检资资查料料和试，检卷并测主且处要了理保解。护现装场置设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。
数据结构第六章习题章
• 假设二叉树采用二叉链表存储结构，设计一个非 递归算法求二叉树的高度。 • int Depth (BiTree T ){ // 返回二叉树的深度 • if ( !T ) depthval = 0; • else { • depthLeft = Depth( T->lchild ); • depthRight= Depth( T->rchild ); • depthval = 1 + (depthLeft > depthRight ? • depthLeft : depthRight); • } • return depthval; • }
第六章
习题
• 1、对下图所示二叉树分别按前序﹑中序﹑ 后序遍历，给出相应的结点序列，同时给 二叉树加上中序线索。
• 2、从概念上讲，树，森林和二叉树是三种 不同的数据结构，将树，森林转化为二叉 树的基本目的是什么，并指出树和二叉树 的主要区别。
• 3. 对于图6.29给出的树，指出树中的根结 点、叶结点和分支结点。并指出各个结点 的度数层数。
• if(p->lchild!=NULL) • { rear=(rear+1)%Maxsize； //左孩子入队 • qu[rear]=p->lchild; level[rear]=m+1;//子女层次加1 • }
• • • • • • • if(p->rchild!=NULL) { rear=(rear+1)%Maxsize； //右孩子入队 qu[rear]=p->rchild; level[rear]=m+1;//子女层次加1 } } return max; }
• 8. 请按先根、后根和中根序遍历下图所示 的二叉树，列出遍历所得的结点序列。 9. 请将下图所示的二叉树转换成对应的森 林，并按先序和中序遍历森林，将遍历结 果与上题结果对照比较。
数据结构第6章习题答案
第6章树和二叉树习题解答一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。
用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。
）即有后继链接的指针仅n-1个。
（√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。
2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
数据结构(C++版)课后作业6-8章附答案
数据结构(C++版)课后作业6-8章附答案-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII第6 章图课后习题讲解1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列（8）如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路2. 选择题⑵n个顶点的强连通图至少有（）条边，其形状是（）。
A n B n+1 C n-1 D n×(n-1) E 无回路F 有回路G 环状H 树状【解答】A，G⑶含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。
A 1 B n/2 C n-1 D n【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。
（4）最小生成树指的是（）。
A 由连通网所得到的边数最少的生成树B 由连通网所得到的顶点数相对较少的生成树C 连通网中所有生成树中权值之和为最小的生成树D 连通网的极小连通子图【解答】C（5）下面关于工程计划的AOE网的叙述中，不正确的是（）A 关键活动不按期完成就会影响整个工程的完成时间B 任何一个关键活动提前完成，那么整个工程将会提前完成C 所有的关键活动都提前完成，那么整个工程将会提前完成D 某些关键活动若提前完成，那么整个工程将会提前完【解答】B 【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。
数据结构（C++版）课后作业6-8章附答案
数据结构（C++版）课后作业6-8章附答案第6 章图课后习题讲解1. 填空题⑴设⽆向图G中顶点数为n，则图G⾄少有（）条边，⾄多有（）条边；若G为有向图，则⾄少有（）条边，⾄多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷⾮空的，⽽边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵任何连通图的连通分量只有⼀个，即是（）。
【解答】其⾃⾝⑶图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表⑸已知⼀个有向图的邻接矩阵表⽰，计算第j个顶点的⼊度的⽅法是（）。
【解答】求第j列的所有元素之和⑹有向图G⽤邻接矩阵A[n][n]存储，其第i⾏的所有元素之和等于顶点i的（）。
【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所⽤到的数据结构是（）；图的⼴度优先遍历类似于树的（）遍历，它所⽤到的数据结构是（）。
【解答】前序，栈，层序，队列（8）如果⼀个有向图不存在（），则该图的全部顶点可以排列成⼀个拓扑序列。
【解答】回路2. 选择题⑵n个顶点的强连通图⾄少有（）条边，其形状是（）。
A n B n+1 C n-1 D n×(n-1) E ⽆回路 F 有回路G 环状H 树状【解答】A，G⑶含n 个顶点的连通图中的任意⼀条简单路径，其长度不可能超过（）。
A 1 B n/2 C n-1 D n【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。
（4）最⼩⽣成树指的是（）。
A 由连通⽹所得到的边数最少的⽣成树 B 由连通⽹所得到的顶点数相对较少的⽣成树 C 连通⽹中所有⽣成树中权值之和为最⼩的⽣成树 D 连通⽹的极⼩连通⼦图【解答】C（5）下⾯关于⼯程计划的AOE⽹的叙述中，不正确的是（）A 关键活动不按期完成就会影响整个⼯程的完成时间B 任何⼀个关键活动提前完成，那么整个⼯程将会提前完成C 所有的关键活动都提前完成，那么整个⼯程将会提前完成D 某些关键活动若提前完成，那么整个⼯程将会提前完【解答】B 【分析】AOE⽹中的关键路径可能不⽌⼀条，如果某⼀个关键活动提前完成，还不能提前整个⼯程，⽽必须同时提⾼在⼏条关键路径上的关键活动。
数据结构(C语言版)第6章练习 清华大学出版社
第六章数据结构作业第六章树选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A．5 B．6 C．7 D．84. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．具有10个叶结点的二叉树中有（）个度为2的结点，A．8 B．9 C．10 D．ll7．一棵完全二叉树上有1001个结点，其中叶子结点的个数为（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 有n个叶子的哈夫曼树的结点总数为（）。
A．不确定 B．2n C．2n+1 D．2n-19. 一棵具有 n个结点的完全二叉树的树高度（深度）是（）A．⎣logn⎦+1 B．logn+1 C．⎣logn⎦ D．logn-110．深度为h的满m叉树的第k层有（）个结点。
(1=<k=<h)A．m k-1 B．m k-1 C．m h-1 D．m h-111．在一棵高度为k的满二叉树中，结点总数为（）A．2k-1 B．2k C．2k-1 D．⎣log2k⎦+112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1、下图所示的4棵二叉树中，不是完全二叉树的是（）2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。
A 、正确B 、错误C 、不一定3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。
A 、acbedB 、decabC 、deabcD 、cedba4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。
A 、前序B 、中序C 、后序D 、层次序5、深度为5的二叉树至多有（）个结点。
A 、16B 、32C 、31D 、106、在一个非空二叉树的中序遍历序列中，根结点的右边（）。
A 、只有右子树上的所有结点B 、只有右子树上的部分结点C 、只有左子树上的部分结点D 、只有左子树上的所有结点7、树最适合用来表示（）。
A 、有序数据元素B 、无序数据元素C 、元素之间具有分支层次关系的数据D 、元素之间无联系的数据。
8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A 、不发生改变B 、发生改变C 、不能确定D 、以上都不对9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。
A 、二叉链表B 、广义表存储结构C 、三叉链表D 、顺序存储结构10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。
A 、n=m+hB 、h+m=2nC 、m=h-1D 、n=2h -111、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。
A 、n 在m 右方B 、n 是m 祖先C 、n 在m 左方D 、n 是m 子孙12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，ABC D其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 13.设有一表示算术表达式的二叉树（见右图），它所表示的算术表达式是（）A. A*B+C/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G14.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③B ．②③④C ．②④D ．①④15.设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定16．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A ．9B ．11C ．15D ．不确定17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A ． 250B ．500C ．254D ．505E ．以上答案都不对18. 一个具有1025个结点的二叉树的高h 为（）A ．11B ．10C ．11至1025之间D ．10至1024之间19．深度为h 的满m 叉树的第k 层有（）个结点。
(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -120.利用二叉链表存储树，则根结点的右指针是（）。
A ．指向最左孩子B ．指向最右孩子C ．空D ．非空21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A ．前序B ．中序C ．后序D ．按层次23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点25.线索二叉树是一种（）结构。
A．逻辑B．逻辑和存储C．物理D．线性26．n个结点的线索二叉树上含有的线索数为（）A．2n B．n－l C．n＋l D．n27．下面几个符号串编码集合中，不是前缀编码的是（）。
A．{0,10,110,1111} B．{11,10,001,101,0001}C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}28.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）A．A[2i](2i=<n) B. A[2i+1](2i+1=< n) C．A[i/2] D．无法确定29、高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。
30、在什么样的情况下，等长编码是最优的前缀码?答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。
31.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边。
已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用图表示出此树，并回答下列问题：(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?答：这是测试我们对树的基本概念的掌握情况。
a是根结点；mndfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟，g,h是f的兄弟；b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。
32、试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。
答：(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。
(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。
(3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。
(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。
33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。
现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
解：A/ \BC/ \ \D E F/ \ /GHI\J34、对下图所示的森林：(1)求各树的前序序列和后序序列；(2)求森林的前序序列和后序序列；(3)将此森林转换为相应的二叉树；(4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?解：(1) (a)的前序序列：ABCDEF 后序序列：BDEFCA(b)的前序序列：GHIJK 后序序列：IJKHG(c)的前序序列：LMPQRNO 后序序列：QRPMNOL(2) 此森林的前序序列：ABCDEFGHIJKLMPQRNO此森林的后序序列：BDEFCAIJKHGQRPMNOL(3)略(4)略35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。
答：⎣n/2⎦36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1),则该二叉树对应的树林包括(2)棵树。
答：(1)EACBDGF （2）237．具有n个结点的满二叉树，其叶结点的个数是______。
答：(n+1)/2设内部节点数为a，叶节点数为b，明显有a+b=n (1)，非空满二叉树中所有节点的出度正好等于入度，每个内部节点出度为2，叶节点出度为0，所有节点的出度和为2a；根节点入度为0，其他节点的入度为1，所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)。
由(1)(2)得b=(n+1)/2，a=(n-1)/2。
另外可得b=a+1，也就是说，非空满二叉树的叶节点数正好比内部节点数多1。
38．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y 的右子树高度是31，x是y的左孩子。
则确定x的后继最多需经过______中间结点（不含后继及x本身）答：31（x的后继是经x的双亲y的右子树中最左下的叶结点）39．有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)，字符c的编码是(2)。
答：(1)80 (2)001（不唯一）40．下面是求二叉树高度的类C写的递归算法，试补充完整。
[说明]二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。
height(p){if ((1)){if(p->lchild==null) lh=(2); else lh=(3);if(p->rchild==null) rh=(4); else rh=(5);if (lh>rh) hi=(6)；else hi=(7);}else hi=(8);return hi;}//答：(1)p (2)0 (3)height(p->lchild) (4)0(5)height(p->rchild) (6)lh+1 (7)rh+1 (8)041．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？答：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。
42．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。