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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → DS 疑问？？？ ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 14061 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： DS 疑问？？？ 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

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

    以下是引用computerlover在2006-11-7 11:27:00的发言：


    06年真题数据结构最后一题也说的不明不白的，　处于第n个位置的数为中位数，那么在2n个数中，只有一个中位数，那又怎么求Ａ和Ｂ的中位数？
      


    这道题，我想题目意思是说：当用A和B来重新组合成一个“非降序”数组时候，
    求出这个新数组的中位数吧！否则，分别求出A和B的中位数，不就是重复了吗？

    我的算法：
    先对A和B进行归并到新数组C中，大小是2n。此时，C便有序。
    直接在C选出中间的数值，即C[n]。

    在这个归并的程序中，算法只是一个循环即可，所以复杂度为O(n).

    可是-----什么是最坏的情况呢？有怎么算出来O(logn)呢？
    这一点，我困惑。
    请大侠指点

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/15 8:29:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第12楼
    发贴心情 
    以下是引用teng_t1986在2006-11-9 19:06:00的发言：

    6次，根节点1个关键码，第二层31*2=62个关键码，第三层32*31*2以此类推，
    第n层有2*(32^（n-2）)*31个关键码，完全树
    不难算出从第一层到最后一层，一共有5层，最后一层不满，但得算上，
    于是：
    在B树上要有5次访外，但别忘了B树的叶子是指向磁盘文件的，于是查找给定关键字一共需6次访外。


    拜谢teng_t1986哦。

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/15 8:32:00
     
     mxf3306 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：112
      积分：823
      门派：XML.ORG.CN
      注册：2006/7/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mxf3306发送一个短消息 把mxf3306加入好友 查看mxf3306的个人资料 搜索mxf3306在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看mxf3306的博客第13楼
    发贴心情 
    以下是引用teng_t1986在2006-11-9 19:06:00的发言：
    [quote]以下是引用borlong在2006-10-30 19:23:00的发言：
    64阶B树中，若B树包含的关键码个数是64K(64*1024)，B树的节点均
      放在磁盘里，每次只能从磁盘往内存中读入一个节点，查找一个给定
      关键字的纪录是，最多需要进行（ ）次访外操作。

      ---------------------
      请大侠给点思路，行吗？拜谢啦！
    [/quote]

    6次，根节点1个关键码，第二层31*2=62个关键码，第三层32*31*2以此类推，
    第n层有2*(32^（n-2）)*31个关键码，完全树
    不难算出从第一层到最后一层，一共有5层，最后一层不满，但得算上，
    于是：
    在B树上要有5次访外，但别忘了B树的叶子是指向磁盘文件的，于是查找给定关键字一共需6次访外。


    指出一点: B树中是不会存在最后一层不满的情况的。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/15 16:54:00
     
     DavidPotter 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了6.5分!)
      文章：150
      积分：852
      门派：Lilybbs.net
      注册：2006/3/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给DavidPotter发送一个短消息 把DavidPotter加入好友 查看DavidPotter的个人资料 搜索DavidPotter在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给DavidPotter 引用回复这个贴子 回复这个贴子 查看DavidPotter的博客第14楼
    发贴心情 
    对于加括号，我想你在草稿纸上画画，可能就知道了。注意用一下递归的思想。 如4个分成3+1的时候就可以通过3个的结果来了。
    中位数以前应该有人讲过了。我的思想就是分治法。 每次可以消除n/2^i个元素。这样消除其实是和折半查找分析是一样的。故可以达到logn

    ----------------------------------------------
    Don‘t try so hard, the best things come when you least expect them to.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/18 12:50:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第15楼
    发贴心情 
    以下是引用borlong在2006-11-15 8:32:00的发言：

      6次，根节点1个关键码，第二层31*2=62个关键码，第三层32*31*2以此类推，
      第n层有2*(32^（n-2）)*31个关键码，完全树
      不难算出从第一层到最后一层，一共有5层，最后一层不满，但得算上，
      于是：
      在B树上要有5次访外，但别忘了B树的叶子是指向磁盘文件的，于是查找给定关键字一共需6次访外。


    dear teng_t1986,您 所说的不难算出，是怎么个算法，是把根节点 加上 第二层上的节点
    再加上 第三层的节点 等等 之和 小于或等于 64k 吗？ 还是按照你的算法 只要最后一层节点数目 小于或等于 64k 呢？

    请赐教！！
    我正在迷雾中啊！

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/19 16:00:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第16楼
    发贴心情 
    以下是引用DavidPotter在2006-11-18 12:50:00的发言：
    对于加括号，我想你在草稿纸上画画，可能就知道了。注意用一下递归的思想。 如4个分成3+1的时候就可以通过3个的结果来了。
    中位数以前应该有人讲过了。我的思想就是分治法。 每次可以消除n/2^i个元素。这样消除其实是和折半查找分析是一样的。故可以达到logn

    中位数！ 是中间位置的元素（只考虑位置）。还是 元素的大小（只考虑大小）位于中间数啊？

    如果考虑位置，不就是O（n）,如果后者，当然是O(logn)啦。

    然而 教材中推导分治法的复杂度有些复杂！
    那么在考试中，如果要分析这个复杂度，也要在考试卷上写出这些过程吗？
    这个问题，请大侠们赐教啊！！！！

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/19 16:09:00
     
     DavidPotter 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了6.5分!)
      文章：150
      积分：852
      门派：Lilybbs.net
      注册：2006/3/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给DavidPotter发送一个短消息 把DavidPotter加入好友 查看DavidPotter的个人资料 搜索DavidPotter在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给DavidPotter 引用回复这个贴子 回复这个贴子 查看DavidPotter的博客第17楼
    发贴心情 
    当然是位置了，这也有问题么？

    ----------------------------------------------
    Don‘t try so hard, the best things come when you least expect them to.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/20 18:02:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第18楼
    发贴心情 
    以下是引用DavidPotter在2006-11-20 18:02:00的发言：
    当然是位置了，这也有问题么？

    位置????
    那么复杂度不就是O(n),因为直接计算不就行啦！
    至于O(logn)又是怎么理解的呢？？？

    大家，新年快乐啊！！！！

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

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

    本主题贴数18，分页： [1] [2]

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