新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     >>计算机科学论坛<<     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [讨论]07DS真题辨析第三道 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 17618 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [讨论]07DS真题辨析第三道 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     okdavinci 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(Java考了96分!)
      文章：111
      积分：480
      门派：XML.ORG.CN
      注册：2007/3/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给okdavinci发送一个短消息 把okdavinci加入好友 查看okdavinci的个人资料 搜索okdavinci在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看okdavinci的博客第31楼
    发贴心情 

    2：为什么“B树一个结点”只能存储在“一个磁盘块”中？

    记得课本好像有说一般是这样的处理的。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/1 12:33:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第32楼
    发贴心情 
    以下是引用vonwenhui在2008-1-1 10:58:00的发言：
    还是不明白填空(3)的路径压缩问题

    只是重量权衡合并规则得出的答案我理解,但再加上路径压缩后,怎么确定哪一步的合并需要压缩?

    请指点,谢谢


    这个规律我不知道怎么用语言表达,语文有点烂...
    我就拿这道题说一下好了..
    说一下(4,14)这个地方吧,因为这个地方用了路径压缩,在(4,14)之前,4的位置应该是:
    (0(3(4))) (用嵌套括号表示法,其他的分支省略)
    14应该是(12(14))
    然后到(4,14)
    我们发现4不是根结点,那么就把在查找4的根结点的路径上的每一个结点的父结点都设成根结点0,也就是把4和3的父结点都设成0,这样就产生了路径压缩,就是课本P153算法里的那个递归调用语句,你按着递归调用走一下就知道了.
    然后是(7,0)那里,7的的根结点是6,0的根结点就是0,这样就直接把6的父结点设为0,这里没有用路径压缩,因为0本来就是根,不用再找根了.

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/1 12:57:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第33楼
    发贴心情 
    以下是引用lionx在2007-12-21 20:45:00的发言：
    对于tree_compare()那题，只要将楼主答案的2)改为
    if (p!=null || q!= null)    return false;
    if (aQueue.Empty())     return true;  //楼主的答案只要加上此句就行

    其实在上面的while(p && q)中，已经保证了运行到2)时p或q至少有一个为null，因此2)中只要p或q有一个不是null 的就说明两树结构不一样。
    其次，在2)下面出队操作前必须判定队是否为空（否则取空队会抛出异常），而队为空时说明所有结点都判断完成（由广度周游可知），而由于aQueue/bQueue两队同时进出队，只要判断一个即可。

    改后的程序我测试过了，没什么问题。

    算法辨析题第9行加完if(parent==null)...后，好像还要把第10-13行用else括起来吧。



    我是觉得万一俩都是空然后跳出循环怎么办?所以就加了那样一句
    行~既然修改后没问题的话,就这样加吧~不过我现在修改不了楼主那张帖子...
    谢谢你们:)

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/1 13:03:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第34楼
    发贴心情 
    以下是引用okdavinci在2008-1-1 12:33:00的发言：
    2：为什么“B树一个结点”只能存储在“一个磁盘块”中？

    记得课本好像有说一般是这样的处理的。



    课本哪里?

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/1 13:05:00
     
     vonwenhui 美女呀，离线，快来找我吧！
      
      
      等级：大一(高数修炼中)
      文章：26
      积分：154
      门派：XML.ORG.CN
      注册：2007/4/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给vonwenhui发送一个短消息 把vonwenhui加入好友 查看vonwenhui的个人资料 搜索vonwenhui在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看vonwenhui的博客第35楼
    发贴心情 
    以下是引用蝶影在2008-1-1 12:57:00的发言：
    [quote]以下是引用vonwenhui在2008-1-1 10:58:00的发言：
    还是不明白填空(3)的路径压缩问题

      只是重量权衡合并规则得出的答案我理解,但再加上路径压缩后,怎么确定哪一步的合并需要压缩?

      请指点,谢谢
    [/quote]

    这个规律我不知道怎么用语言表达,语文有点烂...
    我就拿这道题说一下好了..
    说一下(4,14)这个地方吧,因为这个地方用了路径压缩,在(4,14)之前,4的位置应该是:
    (0(3(4))) (用嵌套括号表示法,其他的分支省略)
    14应该是(12(14))
    然后到(4,14)
    我们发现4不是根结点,那么就把在查找4的根结点的路径上的每一个结点的父结点都设成根结点0,也就是把4和3的父结点都设成0,这样就产生了路径压缩,就是课本P153算法里的那个递归调用语句,你按着递归调用走一下就知道了.
    然后是(7,0)那里,7的的根结点是6,0的根结点就是0,这样就直接把6的父结点设为0,这里没有用路径压缩,因为0本来就是根,不用再找根了.


    我明白了,你说得很清楚,多谢多谢

    ----------------------------------------------
    一只小动物。。。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/1 14:02:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第36楼
    发贴心情 
    以下是引用okdavinci在2007-10-23 18:03:00的发言：
    第一问应该是一个节点是一个磁盘块的大小。并且一个节点包含
    m-1 关键码 ，每个占4字节 ,一共4*(m-1)字节
    m-1个指向磁盘块的首地址的指针，每个占8个字节 ，一共8*(m-1)字节
    m个指向子节点的指针一共为8m字节
    所以 4*(m-1)+8*(m-1)+8m=2048
    =>m=103，
    所以最多有103阶
    第二问：albani 的答案还要：
    把四层所有的关键码个数相加为n，然后再乘以2048为最多可以索引的数据文件的大小（因为是稀疏索引）


    这怎么会乘2048呢？应该是（1+103+103^2+103^3）*102*128吧

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/8 11:36:00
     
     蝶影 美女呀，离线，快来找我吧！狮子座1985-8-1
      
      
      威望：1
      等级：大四(总算啃完XML规范了)
      文章：183
      积分：1291
      门派：IEEE.ORG.CN
      注册：2006/5/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给蝶影发送一个短消息 把蝶影加入好友 查看蝶影的个人资料 搜索蝶影在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给蝶影 引用回复这个贴子 回复这个贴子 查看蝶影的博客第37楼
    发贴心情 
    以下是引用applestar在2007-12-19 14:35:00的发言：
    第三小问最多次数还应该考虑把同一层的所有索引结点放入内层可以放入第一第二层，第三层
    第四层各放一个，然后考虑到主数据区找所需数据1+103+1+1+1=107次。12m可容纳6K块（假设稀疏索引）


    我觉得你的答案是认为B树索引还在外存
    之前的人的答案都假定B树前两层已经在内存里了，所以才会那样计算
    考试的时候最好写明假定的情况

    ----------------------------------------------
    不许偷懒~!

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/8 11:45:00
     
     wulin007 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：25
      积分：151
      门派：XML.ORG.CN
      注册：2007/4/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wulin007发送一个短消息 把wulin007加入好友 查看wulin007的个人资料 搜索wulin007在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看wulin007的博客第38楼
    发贴心情 
    以下是引用蝶影在2008-1-8 11:36:00的发言：
    [quote]以下是引用okdavinci在2007-10-23 18:03:00的发言：
    第一问应该是一个节点是一个磁盘块的大小。并且一个节点包含
      m-1 关键码 ，每个占4字节 ,一共4*(m-1)字节
      m-1个指向磁盘块的首地址的指针，每个占8个字节 ，一共8*(m-1)字节
      m个指向子节点的指针一共为8m字节
      所以 4*(m-1)+8*(m-1)+8m=2048
      =>m=103，
      所以最多有103阶
      第二问：albani 的答案还要：
      把四层所有的关键码个数相加为n，然后再乘以2048为最多可以索引的数据文件的大小（因为是稀疏索引）

    [/quote]

    这怎么会乘2048呢？应该是（1+103+103^2+103^3）*102*128吧



    ×128和我的答案一样！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/10 23:20:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/2 16:02:50

    本主题贴数38，分页： [1] [2] [3] [4]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 109.375ms