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

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

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

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

    对！....看来我还很渺小....
    Run the algorithm on the two new arrays.
    这道题10分，这句话值5分吧

    btw：考试时，我这道题做了1个多小时，当时急得满头大汗。我一直在寻找while中mid,right,left的关系，却从未想过用递归。而且因为这道题，我的整个考试时间全乱了，后面的os部分写的飞快，最后也没有检查....其实今年就两道难题——还有os那道作业题，我记得题目说“CPU可以抢占”，不知道是当时太紧张看错了还是确实如此，如果CPU可以抢占，那么最高相应比就需要列很多方程，也会产生抖动——除此之外，都是中等或以下的题，可是今年能考130左右的很少，估计都是背着两道题折腾的吧。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/22 12:53:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第12楼
    发贴心情 
    能回忆一下那道OS题吗？@_@

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/22 13:14:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第13楼
    发贴心情 
    那道题大概有10个作业，现在已经无法回忆，但是我回忆的题干大概如下：
    以北大教材66页表3-3为例：
    有4个作业，分别为：

    作业    进入时间    估计运行时间(分钟)

    JOB1    8:00        120

    JOB2    8:50        30

    JOB3    9:00        10

    JOB4    9:50        20

    系统采用最高响应比优先（HRN）调度算法，采用多道程序设计思想，CPU可以抢占，问执行结果。
    我对这道题型的回忆就是这样，最主要的问题就是CPU可以抢占

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/22 21:45:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第14楼
    发贴心情 
    作业调度不同于进程调度，作业一旦调入系统，在执行完之前是不会被换出的。抢占只是针对进程而言的吧？


    [此贴子已经被作者于2006-5-22 22:34:35编辑过]

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/22 21:49:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第15楼
    发贴心情 
    本题说采用多道程序设计，意思是说一个作业一旦收容后，如果满足调度算法，就立刻进入内存，然后就主要是进程在内存中的调度了。整个过程按HRN算法进行。在进程的执行过程中，不涉及与外存的交换，一个进程只有被全部执行完后才被转入输出井中。

    这里对收容一词作一点解释：北大的教材对收容的观点是作业的提交过程所需的时间是可以忽略不计的，一个作业到达时间即表示其被收容完毕的时间，处于收容态的某个作业一旦满足调度算法，就可以被调度，即一个作业被不被调度只于其是否被收容有关。（而其他教材，如清华的教材对收容的理解为：一批作业中的最后一个到达后之前的作业才全部收容完毕，即调度算法与所有作业的到达时间都有关系。这两种思想在做题时有时候会得到完全不同的答案）

    对本题，就是说一个作业被调度取决于它到达的时间和是否满足调度算法。可以认为到达的作业都在输入井中，可以随时被调度。

    以下是引用Logician在2006-5-22 21:49:00的发言：
    作业调度不同于进程调度，作业一旦调入系统，在执行完之前是不会被换出的。抢占只是针对进程而言的吧？





    [此贴子已经被作者于2006-5-23 14:45:33编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/23 10:59:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第16楼
    发贴心情 
    不好意思许久没来了
    下面那个算法思想就是我说的……
    一开始取i=j=n/2，另设一个变量dist存储步长值,初始时dist为n/4,然后每次循环dist/=2，当A[i]<B[j]时，i+=dist，j-=dist。算法结束时dist==1或A[i]==B[j]。
    应该是这样……

    我也看了下那本习题集，就是这题，花了我15分钟哦

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/27 10:36:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第17楼
    发贴心情 
    应该可以用非递归吧……
    看看这个程序：
    int find_pivot(int *A,int *B,int n){
     int pa,pb;
     pa=pb=n/2;

     int dist=n/4;

     while(dist>1){

      if(A[pa]==B[pb]){
       return A[pa];
      }

      if(A[pa]<B[pb]){
       pa+=dist;
       pb-=dist;
      }else{
       pa-=dist;
       pb+=dist;
      }

      dist/=2;
     }
     return A[pa];
    }//在vc6.0下编译通过。
    可惜还有点小缺憾，不过可以用引用返回两个中值（即A、B中值不等的情况）

    望高人指教！！

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/27 11:04:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第18楼
    发贴心情 
    以下是引用Supremgoooo在2006-5-23 10:59:00的发言：
    本题说采用多道程序设计，意思是说一个作业一旦收容后，如果满足调度算法，就立刻进入内存，然后就主要是进程在内存中的调度了。整个过程按HRN算法进行。在进程的执行过程中，不涉及与外存的交换，一个进程只有被全部执行完后才被转入输出井中。

    这里对收容一词作一点解释：北大的教材对收容的观点是作业的提交过程所需的时间是可以忽略不计的，一个作业到达时间即表示其被收容完毕的时间，处于收容态的某个作业一旦满足调度算法，就可以被调度，即一个作业被不被调度只于其是否被收容有关。（而其他教材，如清华的教材对收容的理解为：一批作业中的最后一个到达后之前的作业才全部收容完毕，即调度算法与所有作业的到达时间都有关系。这两种思想在做题时有时候会得到完全不同的答案）

    对本题，就是说一个作业被调度取决于它到达的时间和是否满足调度算法。可以认为到达的作业都在输入井中，可以随时被调度。

    [quote]以下是引用Logician在2006-5-22 21:49:00的发言：
    作业调度不同于进程调度，作业一旦调入系统，在执行完之前是不会被换出的。抢占只是针对进程而言的吧？

      
      
    [/quote]
    那道题是有一个两道的批处理操作系统，作业调度采用最高相应比调度算法，进程调
    度采用基于优先数的抢占式调度算法，有如下的作业序列：
    作业     进入时间  估计运行时间   优先数
    JOB1      10：00      40分钟        5
    JOB2      10：20      30分钟        3
    JOB3      10：30      50分钟        4
    JOB4      10：50      20分钟        6
    其中优先数数值越小优先级越高。
    （i）列出所有作业进入内存时间及运行结束时间
    （ii）计算作业平均周转时间和带权平均周转时间

    呵呵这题不难的，但要搞清楚作业调度和进程调度的不同。
    还有就是“几道”程序调度，比如这一题，如果限于2道，那么job3到来后还是无法进入内存，只有等，而当job2进入内存后，由于其priority高，便抢占了job1的cpu，job1阻塞（但仍在内存！）
    好像就是这样……


    [此贴子已经被作者于2006-5-23 14:45:33编辑过]


    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/27 11:14:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第19楼
    发贴心情 
    嗯。了解。谢谢！：）

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/27 12:07:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第20楼
    发贴心情 
    强！

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

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

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

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