2006北大cs题目
计算机软件基础
part1:数据结构，80分
一:填空
序列:3，5，9，18，37，66， 98，102，问用二分查找
找5和6分别要查几次。（序列中所用数字与原题不符）
只记住这一道。
二:简答
1。画出用带压缩的union-find算法查结点b311后的形状。
下图为一个有两颗树的森林:左树只有一个a结点；
bmn为bm的第n个孩子。
a b
b1 b2 b3 b4
b21 b31
b311 b312
b3111
2。在(a, b, c, d)中加括号，问可以表示出多少个不同的广义表。
要求不能有多余括号。
((a), (b), (c), (d))内层的四对儿括号为多余括号。
三:辩析
题目中给出了一个图，是个有两颗树的森林。
首先要写出print算法作用于所给森林后的生成序列。
然后问这个算法是否能遍历整个森林，
如果可以的话，就什么都不干吧，好像是；（记不清了，-_-）
如果不可以，在这个算法的基础上给出一个新的算法，
使之可以遍历整个森林。
print(treenode* rt) {
if (rt == null)
return;
visit(rt);
for (node = rt.leftmostchild(); node != null; node = node->rightsibling())
print(node);
}
四:算法填空（15分，5个空，每空3分）:
floyd算法。
for (i = 0; i < g.vnum(); i++)
for (e e = g.fisrte(v); g.ise(e); e = nexte(e)) {
空缺一
g[i][g.tov(e)].pre = i;
}
if(d[i][v].length==-∞ || d[v][j]==-∞)
空缺二
else if (d[i][j].length == -∞)
空缺三
else if (空缺四)
空缺五
五:算法设计（好像是10分）:
设a，b是长为n的数表，已经按照非降顺序排好。
如果将这2n个数全体排序，处于第n个位置的数
称为中位数。设计一个最坏情况下时间复杂度为
o(logn)的算法求a和b的中位数。
第一问:描述算法的设计思想。
第二问:证明算法的时间复杂度。
注:这是本学期数据结构课的一道作业题（hw9.1）
选自《学习指导》习题7.12
part2:操作系统，70分
倒数第五题:
叙述中断处理过程，以及操作系统是如何支持这一过程的。
倒数第四题:
1。叙述快表的工作原理，以及特点，作用
2。叙述工作集模型的特点，以及该模型给程序员带来的影响。
倒数第三题:
设计一个支持多目录的文件系统，要求可以快速检索，
给出详细的设计方案。
倒数第二题:
1。采用最高响应比优先算法进行作业调度，
求开始时间，结束时间和周转时间。
job1 8:00 70
job2 8:20？ 20
job3 ？ 30？
job4 ？ 40？
job5 9:00？ 10
2。现有如下访盘序列（磁道号）:
10？，20？，30？。。。164，184，198。
当前磁头在173道，给出用最短寻道时间优先算法和扫描算法
的磁头移动序列和移动总量。
倒数第一题:pv操作（14分）
场景:看病。
三个病椅，十个等椅，三个医生。
病人来了以后，若病椅有空闲，直接去看病；
若病椅满，而等椅有空闲，坐在等椅上等待；
若病椅和等椅均满，则离开。
若无病人看病，医生等待。
给出医生和病人的程序，正确实现互斥和同步。
