首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
阅读下列函数说明和C代码,将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点,并打印该结点所有祖先结点。在此算法中,假设值为x的结点不多于一个。此
admin
2009-02-15
59
问题
阅读下列函数说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
面向社会服务的信息系统突发安全事件时所采取的技术措施中一般不包括(62)________________。
如果表A和表B中有公共字段,且该字段在表B中称为主键,则该字段在表A中称为________________。
点击F.DOC文档窗口的“最小化”按钮后,则______。
在Windows系统的资源管理器中,文件和文件夹可以采用多种形式显示,但不能以(40)形式显示。
___________接口是目前微机上最流行的I/O接口,具有支持热插拔、连接灵活、独立供电等优点,可以连接常见的鼠标、键盘、打印机、扫描仪、摄像头、充电器、闪存盘、MP3机、手机、数码相机、移动硬盘、外置光驱、Modem等几乎所有的外部设备。
假设100个数据的平均值为82.31,其中有10个数据又发生了如下增减变化:+3.52,+2.87,-4.13,+5.34,-2.87,+2.50,-3.52,+4.23,-5.04,+0.10,则新的平均值变为(26)。
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
为了调查某学校3000名学生的身高,抽取了100名学生进行身高测量,以下叙述中正确的是(23)。
阅读以下说明,回答问题1至问题4。【说明】某校园网络拓扑结构如图4-1所示。
阅读下列说明,根据网页显示的效果图,回答问题1至问题7。【说明】以下是用ASP实现了一个网络收藏夹网页,用于保存用户感兴趣的Web网页地址。用IE打开网页文件“index.asp”后的效果如图5-1所示。程序中使用的Access数据表结构如表5-1所示。
随机试题
下列属于缔约过失行为的有()
情绪是一种反映形式,其中介为()
实验设计的四个基本原则是
患者;女,18岁。因牙龈肿痛,服用消炎止痛片,引发全身丘疹、红斑、风团,锨热作痒,伴恶寒发热,舌苔薄黄,脉浮数。诊断为药疹,治疗应首选( )。
下列属于雌激素生理作用的有()。
扩散指数(DIt)的取值范围是()。
下列中国特殊风味菜中,属于素菜名肴的是()。
矫正社会工作者小王在帮助罪犯小张时,发现小张行为冲动,缺乏同情心,对人抱有敌意,不关心人,喜欢古怪不平常的事,不顾安危,喜欢恶作剧,适应环境不良,对小王的引导非常敏感且抱有很强的戒心,这里体现了小张身上具有自卑消沉的心理特征。()
麦哲伦
关于四级服务回顾机制,说法错误的是()。
最新回复
(
0
)