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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [原创]北大06年试卷中的编程题（凭印象） ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 77225 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [原创]北大06年试卷中的编程题（凭印象） 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

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

    二分查找有O(logn)的时间效率，因为它避开了近一半的内容。对于这道排序来说，哪怕数组中就剩了1个数，也要先看一下它是几，所以任何一个单元都是不能不看的（个人认为），于是得出结论：下限至少是O（n），即看一遍

    基于比较的排序算法上面已经给出了时间下限，若这道题有解，肯定不是基于比较的排序

    不基于比较的排序比较适于这题的是桶排序，时间复杂为O（n+3）=.O(n)

    看起来不像是出错了，而只有不看一些单元才能满足条件，但是究竟满足什么样条件的单元可以不看呢？？我感觉题目少条件，例如n=3时，若0，1，2都出现1次，则第三个单元是可以不看的。一般的情况就不知道了。。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 14:38:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第42楼
    发贴心情 
    这个答案如何：因为A,B两数组皆已经排好序，很容易知道median[A]和median[B],比较之。
    case1:median[A]>=median[B],去掉A的后半部分和B的前半部分，因为A的后半部分>=median[A]>=median[B]>=B的前半部分，整个序列的median肯定不在这被去掉的元素中。
    case2:median[A]<median[B],去掉A的前班部分和B的后半部分，与case1中同样的道理。
    这样算法规模N->N/2，每次规模减半。
    所以算法复杂度是log(N)

    这是《算法导论》上的课后习题，我当时看了就想出这么个算法。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/29 22:16:00
     
     淘客 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究C++)
      文章：33
      积分：211
      门派：XML.ORG.CN
      注册：2006/4/3

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

      领教领教！
        我看到这道题是一点思路都没有，汗颜。。。。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/30 21:08:00
     
     jingmouren 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：15
      积分：175
      门派：XML.ORG.CN
      注册：2006/4/5

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给jingmouren发送一个短消息 把jingmouren加入好友 查看jingmouren的个人资料 搜索jingmouren在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看jingmouren的博客第44楼
    发贴心情 
    设A，B 是长为n 的数表，已经按照非降顺序排好。如果将这2n 个数全体排序，处于第n 个位置的数称为中位数。设计一个最坏情况下O(logn)时间的算法求A 和B 的中位数。
    1．描述算法的设计思想；
    2．证明算法的时间复杂性。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/31 10:27:00
     
     freeask 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：13
      积分：114
      门派：XML.ORG.CN
      注册：2006/8/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给freeask发送一个短消息 把freeask加入好友 查看freeask的个人资料 搜索freeask在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看freeask的博客第45楼
    发贴心情 
    牛人》》》》》》》！！！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/3 11:30:00
     
     NeverExist 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：3
      积分：71
      门派：XML.ORG.CN
      注册：2006/2/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给NeverExist发送一个短消息 把NeverExist加入好友 查看NeverExist的个人资料 搜索NeverExist在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看NeverExist的博客第46楼
    发贴心情 
    hehe ,遇上数组要求logn的算法，直接就想到二分了~
    这个题很经典，很多地方都出现过，挺好想出来的~
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/6 17:59:00
     
     Szeus 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：24
      积分：180
      门派：XML.ORG.CN
      注册：2007/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Szeus发送一个短消息 把Szeus加入好友 查看Szeus的个人资料 搜索Szeus在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Szeus的博客第47楼
    发贴心情 
    不错，学习中
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/11/26 17:00:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/17 19:36:59

    本主题贴数47，分页：[1] ... [2] [3] [4] [5]

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