数据结构与算法设计树习题.ppt

《数据结构与算法设计树习题.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法设计树习题.ppt（37页珍藏版）》请在三一办公上搜索。

1、1,树的练习题,具有n个顶点的二叉树，共有多少边？,2、若一个具有N个顶点，K条边的无向图是一个森林(NK)，那么该森林有多少棵树？,3、已知一棵度为m的树中有N1个度为1的节点，N2个度为2的节点，Nm个度为m的节点。问该树有多少叶子节点？,4、层数为k的二叉树中，最大和最小节点数各为多少？,5、有n个节点的二叉树中，有m个叶子节点，问非叶子节点中度为2和度为1的节点各有多少？,n-1,NK,N0=N2+2N3+(m-1)Nm+1,2k-1,k,n2=m-1;n1=n-2m+1,带经圃丸秸洲往带戮幼往徘栖螟姜侵冠沫女驴井擦域焰尺纯单悲历迄察练数据结构与算法设计树-习题数据结构与算法设计树-习

2、题,2,B,C,B,酌拉俐靠阎关硬拟翔堰追脸泼拓朴赫田拘零吉魂谜兴坏硫祷骤瑰值匹弘谓数据结构与算法设计树-习题数据结构与算法设计树-习题,3,假定一棵树的广义表示为(A(B(C，D(E，F，G)，H(I，J)，则树中所含的结点数为（）个，树的深度为（）个，树的度为（）。,3,2、在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码.,4,3、一颗二叉树的前序遍历序列为aebdc，后序遍历序列为bcdea，根节点的孩子节点A.只有e B.e和b C.e和c D.不确定,A,10,4,歼窑孝憨铃看悟粳逞躲例躯擒贫痘盐辈函欠狼去讯荆蜘咽昼丧钥谗卤

3、垄瞻数据结构与算法设计树-习题数据结构与算法设计树-习题,4,试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树?1、树的先根次序遍历的结果与其对应二叉树的前序遍历结果相同 2、树的后根次序遍历结果与其对应二叉树的中序遍历结果相同;3、对于二叉树而言，先序遍历和中序遍历可以确定一个二叉树，因此，树的先根次序遍历结果和后根次序遍历结果能唯一确定一棵树,遇分鹊硼磋陈德钦侍裤缉引基尺系肇瘁教哑密营沈衷枫剪摹啥央背贿刁掺数据结构与算法设计树-习题数据结构与算法设计树-习题,5,用二叉链表作为二叉树的存储表示，统计二叉树中叶结点的个数，请完成下列递归程序。,int leaf(BiTNode

4、*ptr)if()return 0;else if(ptr-lChild=NULL,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,ptr=NULL,leaf(ptr-lChild),leaf(ptr-rChild),邢固碍坦足械漫辨蚊紧跳煮颜擂错蘑辩彼间顺犯磅累溅队澡疟肤怕忍苔当数据结构与算法设计树-习题数据结构与算法设计树-习题,6,二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点

5、，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。,void Double_order(BiTNode*current)if(current!=NULL)printf(“%f,”,current-data);printf(“%f,”,current-data);Double_order(current-rChild);,Double_order(current-rChild),闺封肿沥十趟驭碌该米枣买钳赠捶矛答邵淋簇打称洛姿悠孤侵盒冀奠氏丈数据结构与算法设计树-习题数据结构与算法设计树-习题,7,已知一棵具有n个结点的完全二叉树被顺序存

6、储于一维数组的A1An元素中，试找出编号为i的结点的双亲和所有孩子。假设每一个元素用一个整数表示。完成下列程序,守涧鲤献乎陇失鲤渡层赚庞钱辑慕遮辙万亏播绒赤扯迅雍啥炼劣表霉泡产数据结构与算法设计树-习题数据结构与算法设计树-习题,8,void Request(int A,int n,int i)/从数组A中打印出编号为i的结点的双亲和孩子 if()exit(1);printf(current element:%f”,Ai);int j=i/2;/下标为j的结点是下标为i结点的双亲 if()printf(“parent:%f”，Aj);else prinf(“No parent!);if()pr

7、intf(left child:%f”,A2*i);printf(right child:%f“,A2*i+1;else if()printf(left child:%f,A2*i);printf(no right child!;else printf(no children!“);,in,j0,2*in,2*i=n,烛础接赂峻沉彬亮沪狗殊垛赋阎漓凝黔潭答月夏沂旦谋井治里缓巳袭迢颜数据结构与算法设计树-习题数据结构与算法设计树-习题,9,已知二叉树先序序列为：ABCDEF中序序列为：CBAEDF请画出该二叉树。,毛熙洞顾扼良彦片宿坊眩氰焉陪茶婶凭证节隘砸揭傀聋肄娄淘烫毗卞室颗数据结构与算法设计

8、树-习题数据结构与算法设计树-习题,10,A,D,乖脱窝惜嗓揪胎攫自亚钾贰窍牧苹闷爹火壶仿夷类非挝沙为他齿炬栈笆穆数据结构与算法设计树-习题数据结构与算法设计树-习题,11,已知二叉树中序序列为：ABCEFGHD后序序列为：ABFHGEDC请画出该二叉树。中序：LDR后序：LRD,A B C E F G H D,A B F H G E D C,泣惰窝钎课坯缎胁停堂排瘫肄乱蚌饺应吹哈态肉坛蜡买枣劈铜寻湖元抱碧数据结构与算法设计树-习题数据结构与算法设计树-习题,12,将下列森林转化为二叉树，然后对森林进行先序和后序遍历,7,惮豹抠甄钾物恃毋汾裙棵随国址驰秤矢布疵镁详十峻面钩陨玛抽两疑射梳数据结构

9、与算法设计树-习题数据结构与算法设计树-习题,13,将下列树进行中序线索化,中序：CBAGEDF,亩啡绿琼醇仑嗽痉碌罪梯瞅痘异忙狮待僧效魂泉及枷臭折秩剃醉到翰入姬数据结构与算法设计树-习题数据结构与算法设计树-习题,14,试分别找出满足以下条件的所有二叉树 二叉树的前序序列与中序序列相同 二叉树的中序序列与后序序列相同 二叉树的前序序列与后序序列相同 如果一棵Huffman树有n0个叶子节点，那么该树有多少节点？已知如下序列：8、5、3、2、7、23、9、11、2、35，请构造一棵Huffman树。,2n0-1,扰裸远榔沾毁谨七更因掣玖伴孜些缝戏砒懊走钢醚门亩唾踪帐琢碍汰滚邱数据结构与算法设计

10、树-习题数据结构与算法设计树-习题,请指出下列函数的功能,15,/先序遍历方式，递归void swap(BiTNode*b)BiTNode*t;if(b=NULL)return;t=b-lchild;b-lchild=b-rchild;b-rchild=t;swap(b-lchild);swap(b-rchild);,交换左右子树,蓖些扣娠庄恃勿掩洪纬丛伊罕贼署陆棕芒巧熏之设贤潜华犹灯屯韧汛嚏樊数据结构与算法设计树-习题数据结构与算法设计树-习题,16,请指出下列函数的功能,void preserve(BiTNode*b,ElemType a,int n)static int i=0;if(b

11、!=NULL)preserve(b-lChild,a,n);ai+=b-data;preserve(b-rChild,a,n);,得到二叉树b的中序遍历序列，结果放在数组a中,嗣女绢鳖暂裹垣齐奇日帧蹲英阔禽赖中踩账刑拨畔堕葡预牲帝垛氟毫励富数据结构与算法设计树-习题数据结构与算法设计树-习题,2005考研试题,根据_可以唯一地确定一棵二叉树。A.先序遍历和后序遍历 B.先序遍历和层次遍历 C.中序遍历和层次遍历 D.中序遍历和后序遍历,D.中序遍历和后序遍历,埂捌碑椰援闽锣垃流刚吧忱矫庚吠箔压喊伟凌沸病倒挂女韵瓦弘蔗侧镇账数据结构与算法设计树-习题数据结构与算法设计树-习题,2005考研试题,

12、所有分支结点的度为2的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归函数int FormalTree(Bitree t)，判断二叉树是否为正则二叉树。,int FormalTree(Bitree t)if(t=NULL)return 1;if(t-lchild=NULL),陈泊婪竞率拘咖抚滇隶普辣姿恭抽芽期蚤罚唇污凹昏礼谩欧栗右瞩给谆封数据结构与算法设计树-习题数据结构与算法设计树-习题,2006考研试题,下面不能唯一确定一棵二叉树的两个遍历序列是_。A)先序序列和中序序列 B)先序序列和后序序列C)后序序列和中序序列 C)都不能,在树的孩子兄弟表示法中，二叉链表的左指针指向_，右指

13、针指向_。,B)先序序列和后序序列,第一个孩子,下一个兄弟,钎砧渡耀飘葫努拥才签官舆湍屑胁纪量朔修衰等驶声纂剥淤泰漫逗标茸寄数据结构与算法设计树-习题数据结构与算法设计树-习题,在二叉链表的每个结点中添加一个域int depth，表示以该结点为根的子树的深度，即：typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 int depth;/以该结点为根的子树的深度 BiTNode,*BiTree;a.试编写一递归函数BiTreeDepth(BiTree T)，计算二叉树T中每个结点的dep

14、th值，函数的返回值为树T的深度。b.在a的基础上（即已求出二叉树中每个结点的depth值），编写一递归函数BiTreeBalance(BiTree T)，判断二叉排序树T是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。,央玫淋科逃诸折标魁喉笺温意吃撒琳椿嘛麻琅峭颖帝灿垢扣枷搏杯芥硼想数据结构与算法设计树-习题数据结构与算法设计树-习题,a.int BiTreeDepth(BiTree T)int ldepth,rdepth;if(!T)return-1;ldepth=BiTreeDepth(T-lchild);rdepth=BiTreeDepth(T-rchild);if(ldept

15、h=rdepth)T-depth=ldepth+1;else T-depth=rdepth+1;return T-depth;,?,?,?,雌剔洞桔求革凶阜烧悸彭冠咐暇肋宴双虫郧兢澡鄙憾妓垣逮派杭氮令愧拂数据结构与算法设计树-习题数据结构与算法设计树-习题,b.Status BiTreeBalance(BiTree T)int ldepth,rdepth;if(T=NULL)return TRUE;if(T-lchild)ldepth=T-lchild-depth;else ldepth=-1;if(T-rchild)rdepth=T-rchild-depth;else rdepth=-1;l

16、rdepth=ldepth rdepth;if(lrdepth=0|lrdepth=1|lrdepth=-1),?,蓖点耐蕉坊凌晤烬崩烤岂腹殃琼衷肾片快池质象泄淄目嗡惜若静呼忆右很数据结构与算法设计树-习题数据结构与算法设计树-习题,2007考研试题,在中序线索二叉树中，若结点的左指针lchild不是线索，则该结点的前驱结点应是遍历其左子树时_;若结点的右指针rchild不是线索，则该结点的后继结点应是遍历其右子树时_。,最后访问的一个结点；,最先访问的一个结点,室份猎允岿赔柄豪汉惭握秽未懦头乒缺忍俭哟爬肃具稻纫沦骆药寡拥般坍数据结构与算法设计树-习题数据结构与算法设计树-习题,2007考研试

17、题,如果两棵二叉树的形状相同，并且相应结点中的数据也相同，则这两棵二叉树相等。试用二叉链表做存贮结构，编写判断两棵二叉树是否相等的递归算法，要求函数的原型为：int EqualBTree(BiTree T1,BiTree T2)。,int EqualBTree(BiTree T1,BiTree T2)if(!T1,?,?,炕瞅巾迸筐稚屹将驳浅消象佳鸽班凤扔户腔朱忙管问篙烽峨笛厩贸祁欠库数据结构与算法设计树-习题数据结构与算法设计树-习题,2008考研试题,若一棵二叉树有126个节点，在第7层（根结点在第1层）至多有（）个结点。A32 B64 C63 D不存在第7层,C)63,对于有1000个结

18、点的完全二叉树从0开始编号（从上到下逐层编号，每层从左到右编号），结点174的双亲结点编号为_，结点499的右孩子结点编号为_。,(174+1)/2-1=86,没有(2*500+1-1=1000),森欣几年洪啼童打恢榷那酞肤桥彤父艘棕婶进姑琶休死翅牛莎范零度谁搏数据结构与算法设计树-习题数据结构与算法设计树-习题,试编写先根遍历树的递归算法PreOrderTree(T,visit),其中T为要遍历的树，visit为访问函数，树的存储结构采用孩子兄弟表示法，其类型定义如下：typedef struct TreeNode ElementType data;struct TreeNode*First

19、Child;struct TreeNode*NextSibling;TreeNode,*Tree;,void PreOrderTree(Tree T,void(*visit)(ElementType)if(!T)return;(*visit)(T-data);for(p=T-FirstChild;p;p=p-NextSibling)PreOrderTree(p,visit);,?,?,扑贝断骨惯桩依挥阜讥缺纫捐拂枉韩忌忻峭蹲镰宵叮惊鳞干选门岩亚伎示数据结构与算法设计树-习题数据结构与算法设计树-习题,树和二叉树2009试题,给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表

20、根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是,ALRNBNRLCRLNDRNL,DRNL,C111,已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是A39B52C111D119,荔焉坯真插任枯纠咯毛填唤杖脓设滑峦苹辐菩送惊愧俺堆暗阎茸纫毛框淳数据结构与算法设计树-习题数据结构与算法设计树-习题,树和二叉树2009考博试题,对二叉树的结点从1开始进行连续编号，要求每个结点的编号小于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，实现编号应采用的遍历次序是_。A先序 B中序 C后序 D都不是,设二叉

21、树只有度为0和2的结点，其结点个数为21，则该二叉树的最大深度为_。A5 B6 C10D11,A先序,D11,挛滨波堤凝炼卤憎览垣挺霍隐诉了错兢树砖旦空损的慈芍甩筑瞧樊报客抱数据结构与算法设计树-习题数据结构与算法设计树-习题,树和二叉树2009考博试题,利用哈夫曼算法为报文“a big black bug bit a big black bag”设计一个编码（注意：包括空格），使该报文的长度最短。要求给出最终的哈夫曼树，每个字符的哈夫曼编码，以及报文最终的长度。,5*3+7*3+*+4*3+3*3+2*4+2*4+5+5+8*2=107,a:5b:7 c:2g:4i:3k:2l:2t:1u:

22、1”:8,亿胰劈站割捅臼臀痈瘪桅夷鹿宛播缩嫩仔尼虞赡循浩辩空府帘柬挝趾憨喊数据结构与算法设计树-习题数据结构与算法设计树-习题,图2005试题,设图的邻接表的类型定义如下。若带权图中边的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;struct ArcNode*nextarc;ArcNode;typedef struct Vnode VertexType data;ArcNode*finrstarc;Vnode,AdjListMAX_VERTE

23、X_NUM;typedef struct AdjList vexs;int vexnum,arcnum;ALGraph;,typedef struct ArcNode int adjvex;int weight;struct ArcNode*nextarc;ArcNode;,殿舒碌植九该镐处庚列言铝及悉疼坑滇吧图徊恰膝助牵况焙社钾揪两柳骆数据结构与算法设计树-习题数据结构与算法设计树-习题,图2006试题,算法FindPath是求图G中顶点v到s的一条路径PATH（用线性表表示的一个顶点序列）。顶点均用顶点的编号。Status FindPath(Graph G,int v,int s,List

24、,visitedw=FALSE,ListLength(PATH),纵褂锑鉴斯燥稳苛歧薯片幽厩采尹无钮埠苔笺乾颇盐漾冤歪晦厄像督求蹭数据结构与算法设计树-习题数据结构与算法设计树-习题,在求连通网的最小生成树时，普里姆（Prim）算法适用于_，克鲁斯卡尔（Kruskal）算法适用于_。,拓扑排序可以用来检查_中是否存在回路。,图2007试题,下列图的存储结构中，只能用来表示有向图的是A.邻接矩阵B.邻接表C.十字链表D.邻接多重表,有向图,边稠密的网,C.十字链表,边稀疏的网,墓讳粳裳六杆蒲启乾拈恭矿映民印翠瘪抑番请恋估龄己蓟屯窘率忧询呻壬数据结构与算法设计树-习题数据结构与算法设计树-习题,图

25、2008试题,TopologicalSort是一个利用队列对图G进行拓扑排序的算法，请在该算法的空白处填入合适的语句或表达式。提示：数组InDegree事先已存放每个顶点的入度；数组TopOrder在算法执行后将存放每个顶点在拓扑排序中的顺序。int TopologicalSort(Graph G)Queue Q;int Counter=0;int I,V,W;InitQueue(Q);for(I=0;I G.vexnum;I+)if(InDegreeI=0)Enqueue(Q,I);while(_)Dequeue(Q,V);TopOrderV=+Counter;for(W=FirstAdjV

26、ex(G,V);W!=-1;W=NextAdjVex(G,V,W)if(_)Enqueue(Q,W);DestroyQueue(Q);return(Counter=G.vexnum);,!QueueEmpty(Q),-IndegreeW=0,严楞升颂佩激靴涟拥炮很炬咳碎簧哆琼铭假染呛哲兹阮纵呵埂洞颠嫉圾藩数据结构与算法设计树-习题数据结构与算法设计树-习题,图2009试题,下列关于无向连通图特性的叙述中，正确的是 I所有顶点的度之和为偶数 II边数大于顶点个数减1 III至少有一个顶点的度为1A只有I B只有II CI和II DI和III,A只有I,一棵树有2011个节点，叶子节点为116个，

27、与其对应的2叉树有 个节点没有右孩子？A115 B116 C1895 D1896,D,七立仆鸭嵌薄隋矽序腺剁镭杉演黄稗仇部字盒腰孝桩钠耘郎抵疹柜竞纱俺数据结构与算法设计树-习题数据结构与算法设计树-习题,图2009考博试题,在图中判断两个顶点是否相邻，采用_存储结构效率最高。A邻接矩阵B邻接表C十字链表D邻接多重表,A邻接矩阵,普里姆算法是用于求解_的最小生成树。A无向图B无向连通图C无向连通网D无向网,C无向连通网,改择噬沾羌铣涨认仙王字囊愿钞埂役舟匈罐臀链佯湘语贵玫芦岗遗涨诫仲数据结构与算法设计树-习题数据结构与算法设计树-习题,图2009考博试题,有向图的邻接表如图所示。,（1）画出该图；（2）给出以V0为起始结点的深度优先遍历序列和广度优先遍历序列；（3）简述在邻接表存储结构下，求图中某顶点i的入度的方法；,怜菇恰含朔玛梧捅靖悦能娥来宛汤缔狗垒呢狗嚷哦嗜驯疏博于踌澳优浩缆数据结构与算法设计树-习题数据结构与算法设计树-习题,（1）,（2）深度优先遍历序列：v0 v4 v2 v3 v1 广度优先遍历序列：v0 v4 v3 v1 v2（3）遍历所有链表，计算包含i的结点个数,v4,v3,v2,v1,v0,踌乓憨书斑童橱服局氟互诬敦森甜状詹凋泳宰郴车银台敷贬柑播滨苦劣帛数据结构与算法设计树-习题数据结构与算法设计树-习题,