1998年中科院计算机技术研究所硕士生入学试题（离散数学）
1．（10分）证明：若（A－B）U（B－A）＝C，则A包含于（B－C）U（C－B）的充要
条件是A交B交C＝空。
2．（12分）找出只有6个元素的所有不同构的群。
3．（14分）R1和R2为X上的两个关系，且R1*R2＝Ix（恒同关系）
（1）若X为有限集合，证明：存在X上双射F1和F2，使得F1*F2＝Ix且aR1b〈＝＝〉
b＝F1（a），cR2d〈＝＝〉d＝F2（c）。
（2）若X为无限集合，举例说明（1）的结论不成立。
4．（10分）令A分别为下列各式：
（1）（（p－＞q）＜－＞（v否p并q））并（p交r交否p）
（2）（p并q－＞q并r）－>（q－>r）
（3）p<－>p交（q并否q并r）
（4）（p－>否q）交（r并q）
（5）否p<－>（p交（p并q））
从下列备选答案中选择正确的答案：（1）A是重言式（2）否A是重言式（3）A和否A都不是
重言式．
5．（8分）求公式否（（p－>否q）－>r）的主析取范式和主合取范式．
6（12分）将命题"并非E1中的每个数都小于或等于E2中的每个数"按以下要求的形式
表达出来：
（1）出现全称量词，不出现存在量词；
（2）出现存在量词，不出现全称量词．
7．（14分）
（1）写出下图的关联矩阵和邻接矩阵；
（2）说明如何从关联矩阵中判断一结点为割点，一边为割边．
8．（10分）若图G的着色数（或称做顶色数）x（G）＝k，则G中至少有k（k－1）/2条边．
9．（10分）证明：一连通图的任两条最长通路（也称轨）有公共交点．
1）在答卷纸上画出此单纯型表，并在所有空格中填上适当的数（其中可含参数a，b）。
2）判断以下四种情况在什么时候成立，并简要说明理由。
（1）此解为最优解？请写出相应的基解和目标函数值。
（2）此解为最优解，此规划又有无穷多最优解？
（3）此规划有无界解？
（4）此解不是最优解，且能用单纯型法得到一下一个基解。
十、（12分）某地区有三个煤矿，专供四个城镇之用。已知各煤矿与各城镇之间的运输费用矩阵如下（单位：元/吨）：。已知三个煤矿的产量分别为25000吨，18000吨，17000吨；四个城镇的需求量分别为12000吨，15000吨，18000吨，24000吨。若不能满足需求，各城市的最低需求分别为8000吨，10000吨，12000吨，15000吨。
（1）试建立使本地区四城镇煤炭运费最小的线性规划模型。
（2）写出此线性规划的对偶规划。
以上是：1998年中科院计算机技术研究所硕士生入学试题（离散数学），希望对考生有所帮助。
最新评论（共0条）评论一句
Copyright©2007–2021 www.100xuexi.com All rights reserved 圣才学习网 版权所有
全国热线：400-900-8858（09:00-22:00），18001260133（09:00-22:00）
增值电信业务经营许可证 出版物经营许可证 网络文化经营许可证 广播电视节目制作经营许可证
