X
跨考考研 搜一搜
跨考考研
跨考考研
跨考考研
跨考考研
数据结构第六章应用题及答案[9]_跨考网
跨考考研2011-11-25
来源跨考网整理
跨考考研

1.设T是具有n个内结点的扩充二叉树,I是它的内路径长度,E是它的外路径长度。

  (1)试利用归纳法证明E=I+2n, n>=0.5)

  (2)利用(1)的结果试说明:成功查找的平均比较次数s与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1 清华大学 1998 四、 (10)

  【参考答案】

  (1)设n=1,则e=0+2*1=2(只有一个根结点时,有两个外部结点),公式成立。

  设有n个结点时,公式成立,即

  En=In+2n (1)

  现在要证明,当有n+1个结点时公式成立。

  增加一个内部结点,设路径长度为l,则

  In+1=In+l (2)

  该内部结点,其实是从一个外部结点变来的,即这时相当于也增加了一个外部结点(原外部结点变成内部结点时,增加两个外部结点),则

  En+1=En+l+2 (3)

  由(1)和(2),则(3)推导为

  En+1=In+2n+l+2=In+1-l+2n+l+2

  =In+1+2(n+1

  故命题成立

  (2)成功查找的平均比较次数s=I/n

  不成功查找的平均比较次数u=E-n/n+1=I+n/n+1

  由以上二式,有s=1+1/n*u-1

  

  2.一棵非空的有向树中恰有一个顶点入度为0, 其它顶点入度为1,但一个恰有一个顶点入度为0,其它顶点入度为1的有向图却不一定是一棵有向树,请举例说明。【中科院计算所 1999 三、1 5分)】

  【参考答案】

  该有向图只有一个顶点入度为0,其余顶点入度均为1,它不是有向树。

查看更多

  2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!

点击右侧咨询或直接前往了解更多

考研院校专业选择和考研复习计划
2023备考学习 2023线上线下随时学习 34所自划线院校考研复试分数线汇总
2022考研复试最全信息整理 全国各招生院校考研复试分数线汇总
2023全日制封闭训练 全国各招生院校考研调剂信息汇总
2023考研先知 考研考试科目有哪些? 如何正确看待考研分数线?
不同院校相同专业如何选择更适合自己的 从就业说考研如何择专业?
手把手教你如何选专业? 高校研究生教育各学科门类排行榜

当前位置: 首页> 频道> 考研报名> 正文
考研报名相关栏目
跨考考研
考研热点
推荐阅读
推荐课程
跨考考研
2022全年魔鬼集训营二期
跨考考研开班时间:2021.4.20
在线咨询跨考考研
跨考考研
2022大三抢先学
跨考考研开班时间:每月20日
在线咨询跨考考研
Copyright©2008-2020 北京尚学硕博教育咨询有限公司
公司地址:北京市西城区宣武门庄胜广场中央办公楼南翼19层
客服电话:400-833-2220
跨考考研