2004年研究生数据结构试题(70分)
一、已知一棵中序线索二叉树的结点结构为:
leftltagdatartagright
其中:data域的类型为int。
ltag=0,那么left域中存放的是该结点的左儿子结点的地址。
ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结点的地址。
rtag=0,那么right域中存放的是该结点的右儿子结点的地址。
rtag=1,那么right域中存放的是该结点的按中序周游次序的后继结点地址。
现已知该中序线索树中,按照中序遍历次序的第一个结点的地址为first,以及某一整数值为key。请写一个函数,输出结点的data之值为key的结点,并仍保持中序线索树的性质不变。注意:不准使用递归,额外空间不得大于O(1)。(本题25分)
二、已知一棵二叉树是以二叉链表的形式存储的,且结点的数据场的类型为int。现已知该二叉树的根结点的地址为root。请写一个非递归的函数(使用的额外空间不得大于O(1)),给出按后序遍历次序的第一个结点的数据场之值。(本题10分)
三、已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:(本题10分。)
structnode{intdata;//结点的数据场。
structnode*left;//给出结点的左儿子的地址。
structnode*right;//给出结点的右儿子的地址。
};
请在1、2二题的[]处进行填空,完成题目要求的功能。注意,每空只能填一个语句,多填为0分。
1、求出以T为根的二叉树或子树的结点个数。
intsize(structnode*T){
if([])return0;
else[];
}
2、求出以T为根的二叉树或子树的高度。注:高度定义为树的总的层次数。
intheight(structnode*T){
if(T==NULL)[];
else[];
}
四、设结点个数为n,请问采用堆排序法进行排序,其时间复杂性是多少?请以大O形式给出,并给出证明。(本题10分)
五、填空:(本题15分)
1、在二叉排序树上成功地找到一个结点,在平均情况下的时间复杂性是[],在最坏情况下的时间复杂性是[]。
设结点个数为n,以大O形式给出时间复杂性。
2、在二叉平衡排序树上成功地找到一个结点,在平均情况下的时间复杂性是[],在最坏情况下的时间复杂性是[]。
设结点个数为n,以大O形式给出时间复杂性。
3、设工作区的容量为W,则置换选择排序法所得到的初始归并段长度的期望值为[]。
4、设主串和模式的字符个数分别为m和n,则在最坏情况下,KMP算法的时间复杂性为[]。
上海交通大学2004年考研真题-数据结构试题
本站小编 FreeKaoyan/2018-01-22
相关话题/考研真题 上海交通大学 试题 数据结构
上海交通大学2005年考研真题-电子系复试题(高频+通原)
笔试一个钟头,高频和通信原理各90分,高频全是问答,通信原理全是填空,所以你不需要都看得很深,但一定要看得全面。高频的题目我记得是:1、不同种类伞端震荡器的优缺点;2、好像是同步检波什么的;3、丙类功放Re对工作状态的影响;4、AM,FM,PM的数学表达式什么的。还有两道想不起来了。我是上午面试,第 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2004年考研真题-数据结构入学试题答案
2004年研究生数据结构试题(70分) 一、已知一棵中序线索二叉树的结点结构为: leftltagdatartagright 其中:data域的类型为int。 ltag=0,那么left域中存放的是该结点的左儿子结点的地址。 ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-法学考研试题汇总回忆版
民商法两题论述 1。我国民商法典理论体系存在的争议和你的观点!20分 2.我们商法的现状及其走向(考生可加副标题)30分 法理学 法律原则在法律适用和法律制定中的作用!30 诉讼法学试题 感谢东方神犬提供 刑事诉讼法: 一、概念比较 1、一般侦查羁押期限与特殊侦查羁押期限 2、诉讼参与人与其他诉讼 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-法理学(不全)
法理学法律原则在法律适用和法律制定中的作用!30 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-民商法
上海交通大学试题感谢ZLXSDX提供民商法两题论述1。我国民商法典理论体系存在的争议和你的观点!20分2.我们商法的现状及其走向(考生可加副标题)30分 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-法学综合考研试题回忆版
民商法两题论述 1。我国民商法典理论体系存在的争议和你的观点!20分 2.我们商法的现状及其走向(考生可加副标题)30分 法理学 法律原则在法律适用和法律制定中的作用!30 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-微观经济学考试大纲
微观经济学考试大纲序论:经济学基础知识内容:经济学的含义,经济学家的思维方式,经济学的发展历程。第一章:需求与供给理论内容:需求的概念,需求函数,需求的变化与需求量的变化,供给的概念,供给函数,供给的变化与供给量的变化,市场均衡,需求价格弹性,需求收入弹性,需求交叉弹性,供给价格弹性,需求、供给在经 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-诉讼法学
诉讼法学试题感谢东方神犬提供刑事诉讼法:一、概念比较1、一般侦查羁押期限与特殊侦查羁押期限2、诉讼参与人与其他诉讼参与人3、回避的理由和回避的范围4、强制措施与强制性措施5、原始证据与传来证据二、简答(略)三、论述论我国刑事诉讼中检察监督的原则民事诉讼法部分一、名词解释1、执行竟合……………………… ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-刑法学(不全)
刑法学试卷 一、名词解释 1、特殊防卫 2、共同正犯 二、简要的回答问题 ……………… 三、案例分析 ………………………… ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2005年考研真题-宪法学
宪法学试卷一、名词解释1、宪法的解释2、人民代表大会制度………………………………二、简答1、论述宪法的保障制度刑法学试卷一、名词解释1、特殊防卫2、共同正犯二、简要的回答问题………………三、案例分析………………………… ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2002年考研真题-管理学春
一、简答题1.评价组织文化的标准2.理性决策的内在缺陷3.群体的成长过程4.跨国公司所经历的阶段5.组织生存所面临的环境6.计算题:经济批量订货的计算7.反馈的类型8.跨国公司面临的机遇和挑战9.评价直接控制的标准二、问答和论述题1.有关公司的价值目标,企业界和实业界存在许多争议,怎样看待?2.9. ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学2002年考研真题-管理学秋
上海交通大学2002年管理学[秋]考研试题1.领导的构成要素2.说明职能结构与矩阵结构的冲突3.系统阐述TQM对管理研究的重要性4.阐述明茨伯格的角色理论5.战略管理的步骤6.为什么孔茨单独将人事管理列为一个单独的管理职能?7.什么是直接控制,它有什么值得怀疑的前提假设?8.高效团队主要有什么特征? ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学1997年考研真题-自动控制原理历年试题标准答案
专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学1997年考研真题-控制理论基础
专业课考研经验 本站小编 FreeKaoyan 2018-01-22上海交通大学1998年考研真题-自动控制原理历年试题标准答案
专业课考研经验 本站小编 FreeKaoyan 2018-01-22