首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
admin
2009-02-15
65
问题
阅读下列函数说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
I/0设备表示(16)________________。
鼠标指针的形状取决于它所在的位置以及与其他屏幕元素的相互关系。在文字处理的文本区域,指针就像(),指向当前待插入字符的位置。
为支持各级管理决策,信息处理部门提供的数据不能过于简化,也不能过于繁琐,不要提供大量不相关的数据。这是信息处理的()要求。
在Windows系统的资源管理器中,文件和文件夹可以采用多种形式显示,但不能以(40)形式显示。
在Word2010中,要对设定好纸张大小的文档进行每页行数和每行字数调整,可通过页面设置对话框中的()命令进行设置。
计算机使用了一段时间后,系统磁盘空间不足,系统启动时间变长,系统响应延迟,应用程序运行缓慢,此时,需要对系统进行优化。(28)________________不属于系统优化工作。
程序员一般用(7)软件编写和修改程序。
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。说明某公司内部有一个采用TCP/IP作为传输协议的100BASE-TX局域网,包括1台服务器和20台客户机,通过一台16端口的交换机与一台8端口共享集线器级连,其网络结构如图11所
阅读以下说明,回答问题1至问题4。【说明】某校园网络拓扑结构如图4-1所示。
请根据图2-13网页的显示效果,解释该ASP程序中用下画线标出的语句的含义,即填写(1)、(3)、(4)、(6)、(10)空缺处的解释内容。在index.asp文档中使用了<styletype="text/css">语句。其中,CSS是指(10),
随机试题
阻击式防御战略要求当对手的进攻发生后,针对这种进攻的性质、特点和方向采取相应对策,维持原有竞争地位和经营水平。()
某公司拥有一生产设备,原值为80000元,现已使用3年,尚可使用5年,使用期满无残值。该设备采用直线法计提折旧,已累计提取折旧30000元.使用该设备,每年获得销售收入90000元,每年需支付使用费用11000元。若现在出售该设备,售价预计为40
领导权变理论中的路径一目标理论提出的假设认为,当任务不明或压力过大时,能产生更高满意度的领导方式是()
男性,42岁,因左上腹饱胀感伴发热、齿龈出血1个月入院。体检发现,患者呈中度贫血貌,全身皮肤散在出血点,脾是巨脾,血常规白细胞210×109/L,红细胞248×1012/L,血红蛋白70g/L,血小板50×109/L,骨髓象原粒细胞25%,中晚幼粒细胞增多
下列何项不是郁证的临床特点
肝性脑病诱因是()。
2012年6月A施工单位中标一项传输设备安装工程,建筑安装工程费为100万元,其中材料费为30万元,建设单位提供的施工费为建筑安装工程费扣除材料费的80%,最终合同价款为56.84万元,其中施工费为56万元,安全生产费用为0.84万元,合同工期为2012年
反映论是一切唯物主义的认识论的一个基本观点,认为认识是对世界的反映,坚持从物到感觉和思想的认识路线。()
下列权利中,属于物权的是()。
Asmanycollegegraduatesarescramblingtofindjobs,oneofthemostimportantthingsforgraduatestounderstandisthatyou’
最新回复
(
0
)