计算机科学论坛--[原创]北大06年试卷中的编程题（凭印象）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

Logician你是斑竹吧？我很想要一份pkucs06的考题（我07考），可惜现在没有权限访问你们的ftp server……，可以传一份到我的邮箱terran_lucker@sohu.com吗？谢谢你啊！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

06年没有官方的完整题（北大还开始没有卖今年的真题）。
版上有一些今年考过的研友发的回忆题和解答，如：http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=33097

附件里是其它研友整理出来的专业课试题：

今年的“数学基础”试题我没有见到过系统的回忆和整理。

再等两、三个月，应该北大就会开始卖了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

下下来了，谢谢你啊！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不客气。：）
有空多发点原创啊。^_^

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不对。。想法不错

以下是引用teng_t1986在2006-5-27 11:04:00的发言：
应该可以用非递归吧……
看看这个程序：
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中值不等的情况）

望高人指教！！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用teng_t1986在2006-5-27 11:14:00的发言：
[quote]以下是引用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编辑过]

[/quote]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Supremgoooo在2006-5-28 16:49:00的发言：
不对。。想法不错

哪儿错了啊？望指出。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

假如while不执行，一般不对；
假如while执行，那么在没有执行if（相等）的情况下，有两种跳出的情况，而这两种情况不一定总是a被返回吧。
本想修改一下，但我的vc又坏了，你先自己改一下吧！

[此贴子已经被作者于2006-5-28 17:32:56编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Supremgoooo在2006-5-28 17:12:00的发言：
假如while不执行，一般不对；
假如while执行，那么在没有执行if（相等）的情况下，有两种跳出的情况，而这两种情况不一定总是a被返回吧。
本想修改一下，但我的vc又坏了，你先自己改一下吧！

[此贴子已经被作者于2006-5-28 17:32:56编辑过]

对……我dist变量用的太草率了，边界没处理好……sigh，谢谢高人！
突然发现：在n<4的情况下恐怕要另行考虑（n==4是可以把while循环条件改为dist>=1），也就是要考虑n=2、n=3两种情况，对不起我太草率了……
莫非要硬性的加两行判断语句？n=2、3两种情况下似乎我的算法不适用呀……


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	94.238ms