北京理工大学1998年硕士研究生入学考试试题:软件基础（含离散数学与操作系统）
总号：62 分号：09-03一九九八年研究生入学考试
软件基础（含离散数学与操作系统）试题
参加
[url=http://dankao.kaoyantj.com]单独考试[/url]
考生答题：一、二、三、五、六、七、八并在九、十中任选一题
参加统考考生答题：一、二、四、五、六、七、八，并在九、十中任选一题
一、选择题（每小题只选择一个答案）（20分）
1．命题公式(P? Q)ú (Q? P)在 种真值指派下为真。
a)1 b)2 c)3 d)4
2．仅用命题变元P和联结词，最多可写出 个不等价的公式。
a)1 b)2 c)3 d)4
3．公式$ X(P(X)ˉ Q(X))
a)被$ XP(X)ˉ $ XQ(X)蕴含
b)蕴含$ XP(X)ˉ $ XQ(X)
c)被" XP(X)ˉ " XQ(X)蕴含
d)蕴含" XP(X)ˉ " XQ(X)
4．解释I如下：在解释I下，公式 的真值为真。
a)" X$ YP(X,Y) b)$ X" YP(X,Y)
c)" X" YP(X,Y) d)? $ X$ YP(X,Y)
5．不是公式" X(F(X,Y)? G(X,Y))前束范式的为 。
a)" X$ Y(F(X,U)? G(X,Y)) b) " X$ U(F(X,Y)? G(X,U))
c) " X$ Y(F(X,Y)? G(X,Y)) d) " U$ Y(F(U,Y)? G(U,Y))
6．设A={a,b,c},B={b,c,d,e},C={b,c}，则(Aè B)? C为 。
a){a,b} b){b,c} c){a,d,e} d){a,b,c}
7．整数集合Z上的<关系的自反装包是 关系。
a)= b)1 c)< d)3
8．集合A有n个元素，则A上共有 个既对称又反对称的关系。
a)0 b)2n c)n2 d)2n
9．集合{1,2,3}上共有 个等价关系。
a)3 b)4 c)5 d)6
10．集合{1,2,3}到{1,2}共有 个满射。
a)3 b)6 c)9 d)12
11．群<N12 12>共有 个生成元。
a)2 b)4 c)6 d)8
12．设N为自然数集合，<N,*>在 运算下不构成代数系统。
a)X*Y=X Y-2XY b)X*Y=X Y
c)X*Y=X?Y d)X*Y=|X| |Y|
其中， ，-，分别为普通乘法，加法和减法。
13．实数集R上的两个二元运算*和D 分别定义为：
，则 是<R,*>到<R,D >的同构映射。
a){<X,X9>|X? R} b) {<X,X3>|X? R}
c) {<X,>|X? R} d) {<X,>|X? R}
14．若二元运算*有两上左零元，则*一定 。
a)不满足交换律 b)满足交换律
c)不满足结合律 d)满足结合律
15．在布尔格<A,|>中，A={X|X是5的整数倍且是210的正因}，|为整除关系。则30的补元为 。
a)15 b)30 c)35 d)70
16． 5阶无向完全图的边数为 。
a)5 b)10 c)15 d)20
17． 6阶非同构的无向树共有 棵树。
a)4 b)5 c)6 d)7
18．三阶无向完全图K3共有 个互不同构的字图。
a)6 b)7 c)8 d)9
19．下列命题中， 是正确的。
a)欧拉图是汉密尔顿图
b)汉密尔顿图是欧拉图
c)平面图是树 d)树是平面图
20．带权为10，15，20，25，30撮优树的权为 。
a)100 b)225 c)400 d)625
二、（10分）
求命题公式(P? Q)ù R的主析取范式及成假赋值。
三、（10分）
在实数集合上定义二元运算X*Y=XY-2X-2Y 6
1．验证*是否满足交换律和结合律；
2．求*的幺元和零元；
3．对任何实数X，求其逆元。
四、（10分）
已知R1，R2均为大空集合A上的等价关系。
试证：（1）R1? R2是上A的等价关系。
（2）对
五、（10分）
G=<V,E>，其中V={1,2,3,4,5},E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}
（1）求G的邻接矩阵和可达矩阵；
（2）当不考虑边的方向时，G作为无向图是否是欧拉图和哈密尔顿图？为什么？
六、回答下列问题（20分）
1．当一个进程被中断时，其断点保存在什么地方？该断点地址是相对地址还是绝对地址？为什么？
2．解决大作业和小内存的矛盾有哪些途径？简述其实现思想。
3．以DOS和UNIX为例，说明它们的构造文件系统形式各有什么特色？
4．某进程被唤醒后立即投入运行，我们就说这个系统采用的是剥夺式调度方式，对吗？为什么？
5．OS的基本特征有哪些，这些特征在OS的哪部分策略被处理？
七、（10分）
设备管理中为什么要引入缓冲？缓冲队列的管理策略通常有几种方法？如何实现？有什么好处？就你知道的某类OS，说明缓冲的设置方法。
八、（5分）
使用系统共享资源最简单的方法是FCFS。在采用优先级调度的系统中，若优先级高的进程等待优先级低的进程正占有的系统资源。系统中就绪队列如下图，图中数字为进程优先数。
队头
当前正占有系统资源的进程优先数为5，优先数为1进程正等待这些资源。请设计一个算法，使高优先级进程尽可能快地得到资源后运行，而不是长期等待在阻塞队列等待就绪队列中进程依次运行完。
九、（15分）
请求页式管理中涉及哪些数据结构？各包含哪些字段？各有什么作用？叙述如何使用这些表格实现一条不在内存指令：MOV2372，Ro（将Ro内容送2372单元）的实现过程。请先为该指令设置页表项内容。
十、（15分）
一个采用SPOOLING技术的系统，由输入进程1，用户进程P和输出进程O组成，如下图所示：
这些缓冲是以磁盘为存储介质，且输入与输出所需的页面数随进程的速度而浮动，但输入缓冲与输出缓冲应满足资源限制条件：
i ()<max max是系统缓冲区最大个数
各进程的运行情况说明如下：
1）只要盘上有空间，且有供输入的数据，输入进程1就一直向盘上提供输入。
2）只要盘上有可用输入数据，进程P就消耗它，并将处理结果记盘（盘上保证有空间使用，否则等待）。
3）只要盘上有输出数据，进程O就消耗它。
请考虑：①此系统在什么情况下会发生死锁？
②考虑一个附加资源限制条件，使其既能防止死锁，又能满足上述的输入与输出所需的缓冲数随进程速度而浮动。
③给出三者之间相互制约关系，用P/V操作给出1和P之间的同步算法。
页:
[1]