首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
admin
2009-02-15
57
问题
阅读下列函数说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
下列关于Word文本编辑的叙述中,不正确的是(33)。
黑屏是微机显示器常见的故障现象。发生黑屏时需要检查的项目不包括(27)________________。
在使用计算机的过程中应增强的安全意识中不包括________________。
要使Word能自动提醒英文单词的字母拼写是否正确,应设置Word的(47)选项功能。
下列关于应用Word软件新建文档第一次存盘时的叙述,正确的是______。
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
(1)是固化在主板ROM内的程序,为计算机提供最底层、最直接的硬件访问和控制。
下列选项中,衡量数据校验人员业务水平的主要指标是(20)。
下图是某国多年来统计的出生人数和死亡人数曲线图。从图中看出,该国从________________年以后,死亡人数超过了出生人数,出现了人口危机。
/etc/dhcpd.conf文件中的配置语句:hostCIU_DHCP{hardwareethemet52.54.AB.3B.B6.45fixed-address192.168.1.15;}表示的是什么意思?当配置文件配置好以后,还
随机试题
肺结核的主要传播途径是
心脏右前斜位摄影,吞服钡剂的目的是为了观察
患儿,男,2岁。因发热、头痛半天入院。查体:患儿精神差,有恶心、呕吐现象。脑脊液检查为:压力高,外观浑浊,白细胞高,以中性粒细胞为主,蛋白升高,糖和氯化物下降。该患儿的致病菌可能是
男,30岁。外伤后急性失血约1000ml,给予手术止血,并输注平衡盐溶液和羟乙基淀粉。术后查体:P95次/分,BP100/60mmHg,Hb80g/L。此时应采取的治疗措施是
皮肤接触有机磷农药者,可用的洗涤溶液为:
(2005年)设a,b都是向量,下列说法正确的是()。
甲、乙、丙三人各自出资10万元、6万元、4万元设立普通合伙企业。因经营管理不善,对丁负债10万元,丙遂提出退伙,并拿出1万元由甲、乙代为偿还对丁的债务。如合伙企业财产不能清偿丁的债务,根据合伙企业法律制度的规定,下列表述中,正确的有()。
(2018年)2016年6月6日,甲与乙签订委托合同,委托乙出租自有房屋一套并代收租金,委托期间为2016年6月6日至2018年7月31日。2016年7月4日,甲向乙出具了授权委托书,载明乙有权代理甲处理房屋出租及租金收取事宜,代理期间为2016年7月4日
以下关于中国政党制度的表述不正确的是()。
阅读下文,完成下列5题。。约言之,藏书的①当能铸冶治学的风气,影响学风,②学术思想的活跃,学术思想的活跃又进一步③学风,并给著述提供津梁。战国时期学术的百家争鸣的出现,无疑与图书事业的发展有千丝万缕的联系。。梁代萧绎出任荆州称帝江陵,,招致饱学之
最新回复
(
0
)