首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
admin
2009-02-15
80
问题
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。
【说明】
函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag,Top是栈顶指针。
【函数】
void print( BinTreeNode * t; DateType &x) {
stack ST; int i, top; top = 0;//置空栈
while(t! = NULL &&t-> data!= x || top!=0)
{ while(t!= NULL && t-> data!=x)
{
/*寻找值为x的结点*/
(1);
ST[top]. ptr = t;
ST[top]. tag = 0;
(2);
}
if(t!= Null && t -> data == x) { /*找到值为x的结点*/
for(i=1;(3);i ++)
printf("%d" ,ST[top]. ptr ->data);
else {
while((4))
top--;
if(top>0)
{
ST[top]. tag = 1;
(5);
}
}
}
选项
答案
(1)top++ (2)t=t->leftChild (3)i=top (4)top>0 && ST[top].tag=1 (5)t=ST[top].ptr->rightChild
解析
这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是:先扫描根结点的所有左结点并入栈;当找到一个结点的值为x,则输入出栈里存放的数据,这些数据就是该结点所有祖先结点;然后判断栈顶元素的右子树是否已经被后序遍历过,如果是,或者右子树为空,将栈顶元素退栈,该子树已经全部后序遍历过;如果不是,则对栈顶结点的右子树进行后序遍历,此时应把栈顶结点的右子树的相结点放入栈中。再重复上述过程,直至遍历过树中所有结点。
(1)、(2)空年在循环就是扫描根结点的所有左结点并入栈,根据程序中的栈的定义,栈空时top=0,因此在入栈时,先将栈顶指针加1,因此(1)空处应填写“top++”或其等价形式,(2)空是取当前结点的左子树的根结点,因此应填写“t=t->leftChild”。
(3)空所在循环是处理找到值为x的结点,那么该结点的所有祖先结点都存放在栈中,栈中的栈底是二叉树的根,而栈顶元素是该结点的父结点,因此,(3)空处应填写“i=top”。
(4)空所在循环是判断栈顶元素的右子树是否已经被后序遍历过,如果是,或者右子树为空,将栈顶元素退栈,这里要填写判断条件。 tag=0表示左子树,tag=1表示右子树,因此,(4)空处应填写“top> 0&&ST [top].tag=1”。
(5)空所在语句块是处理栈顶元素的右子树没有被后序遍历情况,则将右子树入栈,因此(5)空处应填写“t=ST[top].ptr->rightChild”。
转载请注明原文地址:https://kaotiyun.com/show/NbjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
文件abc.docx______。
某一个PPT文档共有8张幻灯片,现选中第4张幻灯片,改变幻灯片背景设置后,单击“应用”按钮,则______。
以下关于Excel单元格操作的叙述,(52)是错误的。
以下关于数据处理的叙述中,不正确的是(1)________________。
________________是按照科学的城市发展理念,利用新一代信息技术,通过人、物、城市功能系统之间的无缝连接与协同联动,实现自感知、自适应、自优化,形成安全、便捷、高效、绿色的城市形态。
下面无助于加强计算机安全的措施是(19)。
在浏览网页时,当鼠标指针移至某些文字或某些图片时,会出现手形状,通常是由于网页在这个地方做了(17)。
为什么一般处理“震荡波”病毒时,首先要把被侵入的计算机系统从网络上断开?在计算机系统发现病毒并清除以后,在未接入网络之前,从安全方面考虑,若需重新安装操作系统,通常需要执行以下几项主要工作后,方可接入网络。请给出下列工作的合理顺序。A.安装操作
随机试题
投资者对房地产内部,使用功能的变动(例如,在公寓内设置自助洗衣房提供洗衣服务等),体现了投资者对房地产投资()的重视。
“备案号”栏应填()“保费”栏()
张小姐有了一定积蓄,想买一些外汇产品,但她对外汇产品不甚了解,于是向理财规划师进行咨询。外汇汇率具有双向表示的特点:它既可以用本币表示外币价格,又可以用外币表示本币价格。目前,除了英国,欧盟,美国,澳大利亚,新西兰等之外,世界上绝大多数国家,包括中国在
期货交易所向会员收取的保证金属于()所有。
关于建筑安装业应纳营业税代理审查的说法,正确的有()。
学生没有智力障碍,但在阅读、写作或数学方面仍然存在困难。针对此类学习有困难的学生,可采用的正确教学策略有()。
依据《行政处罚法》规定,限制人身自由的行政处罚应由()。
对清朝平定“三藩叛乱”的评价有误的一项是()。
FactorsInfluencingMarriageThecommonviewinsocialscienceofloverelationshipsisnotthatoppositesattracteachother
Singapore(新加坡)isthenameofanislandonthesouthofMalaya.Itisalsothenameofthecityonthesouthsideofthisisland.
最新回复
(
0
)