-- 作者：carlos_zjm
-- 发布时间：12/1/2008 1:37:00 PM
--
在别的网上找的，呵呵，大家参考下 08年北大真题 计算机软件基础
一。填空题 共15分。
1.散列表。散列函数home=key%13.散列表有13项，冲突解决方法双散列，
probe函数为p(key,i)=(key%13+i*key%11)%13. 依次将以下几个关键码插入散列表
，。。。。（记不住了）画出散列表插入后的状态，并计算等概率查找这几个关键
码时的ASL。
2.一系统存储管理采用虚拟页式存储管理方案，一程序共有10个内存块，拥有6个缓冲
区，一个缓冲区可缓存一块，缓冲区淘汰算法为LRU，缓冲区采用链接结构，尾缓冲
区的指针可以重用，假定此程序内存块调用顺序依次为。。。。（记不住了），则
最后缓冲区链上留下的页块依次为什么，在此过程中对缓冲区共写入多少次。
3.5阶4层B树，最多可以索引多少个关键码，最少呢？
二。辨析 20分。
1.红黑树是具有下面一些性质的数据结构：
(列出红黑树的五个性质）
请回答以下问题：
（1）颜色有什么作用？
（2）n个内部结点的红黑树，请估算高度最大为多少，并给出证明。
2.按字典序依次插入以下关键词
RAT OX TIGER RABBIT DRAGON SNAKE HORSE GOAT MONKEY ROOSTER DOG
PIG
组成AVL树。
（1）画出这颗AVL树。
（2）不考虑AVL树对高度的平衡，将此树看作半伸展树，画出查找一次PIG后此半伸
展树的形态。
三。程序改错（10分）
1.以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。
void reverse(char *s)
{ int len=strlen(s);
char *dest=new char[len];
int i=0;
while(len--!=0)
{
.....
}
printf(...);
return 0;
}
四。程序填空。（10分）
1.有n个非零实数，如今要使之排成前半部分为小于零的后半部分为大于零的数组，
复杂度为O(n),填空下列程序，每个空有零或一或多句语句空缺。
void sort(Record Array,int n)
{int i=0,j=n-1;
while(i<j)
{ while(______)
i++;
while(______)
j--;
if(i>j)
break;
else ______
}
}
五 。算法设计。
1.。。。。。图的ADT。。。。。。
要求判断一个图的MST是不是惟一的，提供一个函数int Kruskal(Graph G)可以直接
调用，返回MST权值。要求写出函数bool uniqueKruskal(Graph G)，如果无向连通
图只有惟一一颗MST，则返回TRUE，否则返回FALSE。要求写出算法思想和程序实现
2.一个UNIX文件系统的文件结构如下图，要求（1）设计合适的数据结构，（2）写出一
个程序，返回如右图的输入，注意顺序及文件名后的数字。
/usr* (1)
/allen* (2)
hw.c （7）
course.ppt （5）
/mark* (8)
hw.c （3）
/etc* (4)
hw.c （2）
work.c （1）
course.ppt（11）
_______________________________________
要求的输出
hw.c (7)
course.ppt(5)
allen* (14)
hw.c (3)
mark* (11)
hw.c (2)
work.c (1)
course.ppt (11)
etc* (18)
操作系统部分
一.简答题&计算题 （15分）
1.中断有哪几种类型，对每一种举相应实例说明。
2.计算题。三个进程P1,P2,P3,如在无并发的环境中依次执行，三个进程分别需要的
CPU计算和IO时间分别为:
P1 40msCPU 40msIO 40msCPU
P2 40msCPU 120msIO 80msCPU
P3 20msCPU 40msIO 40msCPU
二。论述题。（40分）
1.线程的实现机制主要有哪几种，详细说明并分别写出优缺点。
2.请设计一个页面存储机制，详细说明其硬件部分和软件部分并说明你是如何考虑这
个系统的效率问题的。
三。PV操作题 （15分）ǎ
一个无红绿灯的十字路口可以从四个方向来车，每个方向的车在通过这个十字路
口前都会先在自己方向的停车线上停一下然后按从每个方向的车到达停车线的先
后严格顺序通过十字路口，用PV操作实现这一机制，有以下要求：
1.说明你的设计思想。
2.信号量及其他变量的定义和初值。
3.写出程序。
4.证明不会出现死锁。 计算机数学基础 一。高数部分（60分）
1. f(x)有连续的二阶导数，f(a)不等于0，求lim|x->a ( 1/(f(x-a)-f(a))-1/(f'(a))
2. f(x)在[a,b]上连续且f(a)=f(b)=0,f'(a)f'(b)>0,证明在(a,b)上必有一点u,使
f(u)=0.
3. 不定积分∫(1-lnx)/(x-lnx)^2dx
4. f(0)=0且f'(0)=1 f(x)有连续的导数，求lim|x->0 ∫（上限x,下限0) tf(x^2-t^2)
dx)/x^4
5. f(x)在0附近可导且导数大于0，证明无穷级数f(1/n)发散，无穷级数
（-1）^nf(1/n)收敛。
二。离散数学部分（90分）
1.运用集合演算法化简 （A∩（BUC））∩（A-（BUC））
2.一个集合A={1,2,3,4}.A上的二元关系R={<1,2>,<1,3>,<2,3>,<4,3>}，写出此二元
关系的哈斯图并写出包含R的等价关系所表示的商集。
3.证明可数集A，B的并集也是可数集。
4. 5，6，7，阶自补图是否存在，说明理由。
5.正多面体共有几个，证明之。
6.一个竞赛图可以既是欧拉图，又是哈密顿图吗？为什么。
7.一个集合{a,b,c}上的二元运算*的运算表为：
*_ a b c
______________
a| b b b
|
b| b b b
|
c| b b b
写出该集合上的所有一一变换，并说明哪些是集合上的自同构。
8.p是任意一个素数，Sp为对称群。证明：
（1）Sp恰有(p-1)!个p阶元。
（2）Sp中恰有(p-2)!个p阶子群。
9.无零因子环R中有一个非零元满足x^2=x,证明这个元即是R中的单位元。
|