首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意
admin
2017-04-28
102
问题
输入一整数数组{5,7,6,9,1 1,10,8},该整数序列为图2—2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法,判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。要求:
根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法实现如下: int rdfs (ADJLIST g,int vi) { int i,count, yes; yes=0; count=1; stack s; for(int i=0; i<n; i++)visited[i] =0;//初始化访问标记数组 push (vi,s) ; visited [vi]=i; //初始化 while ( ! empty (s) &&yes—=0) { int w=top (s) ; p=g[w],firstarc; while(p !=NULL&&visited[p—>adj data]) { p=p—>next; if (p==NULL) pop (s); else { w=p—>adjdata; visited [w]=1; count++; push (w, s) ; } } } if(count==n)//n为该有向图中的结点数 yes=1; return yes; break; } //在二叉排序树中右子树的结点值大于根结点的值 int j=i; for(;j<length—1;j++) { if (sequence[j]<root) return false; } //判断左子树是不是二叉排序树 bool left=true; if (i>0) left=verifySquenceOfBST((squence,i), //判断右子树是不是二叉排序树 bool right=true; if (i<length—1} right=verifySquenceofBSlf squence+i,length—i—1); return (left&&right), }
解析
转载请注明原文地址:https://kaotiyun.com/show/2XRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
荷马时代的社会管理制度和经济生活。
概述日本古代文化的发展情况。
简述公元前8世纪至公元前6世纪希腊海外殖民的背景、范围及影响。
1951年底到1952年春,中国共产党在党政机构工作人员中开展运动的内容是()。
元朝农业取得了巨大的成就,出现的第一部从全国范围内对农业进行研究的农书是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
对图B-2进行拓扑排序,可以得到不同的拓扑序列的个数是____。
随机试题
小路,今年15岁,初中毕业考上了职业中专。由于父母离异,法院将其判给了爸爸。但是爸爸很快为小路找了继母,继母对小路并不好,不让爸爸给小路筹集学费。而小路的生母由于一直没有一个很好的工作,也没钱供小路上学。小路的学费问题严重困扰着小路。问题:针对小路目
“三突出”创作原则
在控制过程中,管理者按照标准对资源配置、工作成果等进行监测的阶段是
Zeta电位降低产生:微生物作用可使乳剂:
HPMCP可作为片剂的辅料使用正确的是
市级商服中心()。
1989年联合国通过了一部关于儿童权益问题的法规,法规中明确指出:18岁以下的任何人都是积极和创造的权利主体,拥有包括生存、发展和充分参与社会、文化、教育、生活以及他们个人成长与福利所必需的活动权利,这部法规是()
持之以恒的精神固然可贵,但如果我们所坚持、所固守的是_______甚至错误的,那坚持到底的结果只能是一错再错。人生允许_______,敢于放弃不切实际的理想,也是一种生存智慧。依次填入画横线部分最恰当的一项是()。
请在【答题】菜单下选择【进入考生文件夹】命令,并按照题目要求完成下面的操作。注意:以下的文件必须保存在考生文件夹下。在考生文件夹下打开工作簿Excel.xlsx,按照要求完成下列操作并以该文件名(Excel.xlsx)保存工作簿。某公司拟对其产品季度
A、It’salmosttimeforlunch.B、Onlyafewstrawberrieswillbeeatenatlunch.C、Therearejustenoughstrawberriesforlunch.
最新回复
(
0
)