北京理工大学2000年硕士研究生入学考试试题软件基础(含离散数学与操作系统)

2023-01-23 23:56:13 文档大全网 [ 字体：小中大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《北京理工大学2000年硕士研究生入学考试试题软件基础(含离散数学与操作系统)》，欢迎阅读！
北京理工大学,离散,考试试题,入学,硕士
科目编号：545 科目名称：软件基础（含离散数学与操作系统）分号：009-03 请统考考生答：一、二、三、四、六、七、八、九

请单独考生答：一、二、三、四、五、六、七、八、九与十两题任选一题一、选择题（每小题只选一个答案）（20分） 1．在连结词ù ，ú ，，? ，? 中，满足结合律的有（）个。 a)2; b)3 c)4 d)5 2．下列命题公式中，（）与Pù （Pú Q）不等价： a)Pú （Pù Q） b)（PQ）Q c)（P? Q）? Q d)（P? Q）? Q

3．E：我学英语；J：我学日语；G：我学德语，则在英、日、德三种语言中公式

（Eù ? Jù ? G）ú （? Eù Jù ? G）ú （? Eù ? Jù G）ú （? Eù ? Jù ? G）表示（） a)至少学一种 b)至多学一种 c)至少学两种 d)至多学两种 4．下列推理定律中，（）不正确。 a)QT Pú Q b)QT P? Q

c)? Qù (P? Q)T P d)? (P? Q)T ù Q

5．L(x,y):x<y，当客体域为（）时，公式(" x)($ y)L(y,x)不是有效的。 a)自然数集 b)整数集 c)有理数集 d)实数集

6．公式(" x)P(x)? ( " x)Q(x)的前束范式为（） a)( " x)( " y)(P(x)? Q(y)) b)( " x)($ y) (P(x)? Q(y)) c) ($ x)(" y) (P(x)? Q(y)) d) ($ x) ($ y) (P(x)? Q(y)) 7．(" x) (P(x)? Q)? （）

a)((" x)P(x)? Q)ù (Q? (" x)P(x)) b) ((" x)P(x)? Q)ù (Q? ($ x)P(x)) c) (($ x)P(x)? Q)ù (Q? (" x)P(x)) d) (($ x)P(x)? Q)ù (Q? (" x)P(x))

8．下列集合运算中（）对? 满足分配律： a)è b)? c)- d)?

9．A，B是集合，P(A), P(B)为其幂集，且A? B=f ，则P(A)? P(B)= ； a) f b){ f } c){{ f }} d){ f {f }}

10．A，B是集合，以下各式除（）之外，均与Aê B等价： a)A? Bí B b)Aè B=B c)A? B=A d)A′ Bí B2 11．R是集合A上的自反关系，则（）： a)R·Rí R b)Rí R·R c)R? Rc=lA d)R·Rc=lA

12．集合A中有n个元素，则A上共有（）个既对称又反对称的关系： a)0 b)2 c)n2 d)2n

13．R是可传递的二元关系，则在R? Rc，Rè Rc，R－Rc，Rc－R中，有（）个一定是可传递的： a)1 b)2 c)3 d)4

14．函数f:R? R，其中R为实数集合，下列四个命题中（）为真。 a)f(x)=5是单射的 b)f(x)=5是满射的

c)f(x)=5是双射的 d)a),b),c)都不真

15．集合A到B共有64个不同的函数，则B中元素个数不可能是（）。 a)4 b)8 c)16 d)4

16．含有三条边的K4非同构的子图，有（）个。 a)1 b)2 c)3 d)4

17．二部图K2，3是（）。

a)欧拉图 b)哈密顿图 c)非平面图 d)平面图 18．5阶无向完全图的边数为（）。 a)5 b)10 c)15 d)20

19．6阶非同构的无向树共有（）。 a)4 b)5 c)6 d)7 20．下列命题中，（）是正确的。 a)欧拉图的子图一定是欧拉图 b)哈密顿图的子图一定是哈密顿图 c)平面图的子图一定是平面图 d)树的子图一定是树二、（10）

用真值表法求(P- Q)? (Pù ? (Qú ? R))的主合取范式和成真指派。三、（10分）

已知一组权2,3,5,7,11,13,17,19,23,29,31,37。试求相应的最优二元树和最优三元树。四、（10分）

（一）已知A={1,2,3,4,5}和R={<1,2>,<3,4>} 1．试求A上的关系R'，使a)R'等价；b)Rí R; c)对任何A上的等价关系R''，若Rí R''，则R'í R''；

2．对上面的R'，试求A/R'。

（二）已知V=<Z7,x7>，其中Z7={1,2,3,4,5,6},x7为模7乘法。试找出群V的3阶子群H，计算H关于Z7元素的左倍集并给出相应的。五（10分）

（一）试构造下面的推理证明（用P,T或CP规则）前提：A? (Bù C),? Bú D,(H? ? E)? ? D,B? (Aù ? G)。结论：B? E。

（二）R是集合A上自反和传递的关系，试证R·R=R。六、填空（10分）

1．实时系统应具有两个基本特性：（）和（）。

2．在操作系统的存储管理中，存储共享既可以节省主存空间，又可以（）。 3．活动头磁盘的访问时间包括（）、（）和（）。 4（）存储管理方案可解决小内存运行大作业。

5．在UNIX系统中，当进程要读写一个已打开文件时，它依次要访问的数据结构是：（）、（）和（）。七、解释下列术语：（10分） 1．设备独立性 2．虚拟设备

3．程序局部性原理