资源描述：
《2014河科大离散数学考研真题试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、河南科技大学2014年硕士研究生入学考试试题答案及评分标准考试科目代码：652考试科目名称：离散数学一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的备选项中只有一个是符合题目要求的，错选、多选或未选均无分。1-5：ADBDC6-10：CDBAB11-15：ADABB二、填空题(本大题共10小题，每小题2分，共20分)1.或2.13.P真值为1，Q的真值为04.5.R={<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<5,6>}6.7.{,
2、,,,}IA8.β，γ9.10.三、计算题(本大题共5小题，每小题8分，共40分)1．利用主析取范式，求公式的类型。(注：重言式、矛盾式或可满足式)解：(6分)它无成真赋值，所以为矛盾式。(2分)2．给定解释I：D={2，3}，L（x,y）为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0，求在解释I下的真值。解：(2分)(2分)(2分)(2分)第6页（共6页）3．设是模12的整数加群，求G的生成元和所有子群解：(1)，小于12且与12互质的数是1,5,
3、7,11；所以，G的生成元是1,5,7,11(2分)(2)12的正因子有1,2,3,4,6,12，则的子群有：1阶子群(1分)2阶子群(1分)3阶子群(1分)4阶子群(1分)6阶子群(1分)12阶子群(1分)4．求下图的邻接矩阵和可达矩阵。解：(1)求邻接矩阵(4分)(2)求可达矩阵(1分)(1分)(1分)所以可达矩阵(1分)第6页（共6页）5.如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算其总造价。 解：(1)用K
4、ruskal算法求产生的最优树。算法为：(3分)结果如图：(3分)(2)树权C(T)=23+1+4+9+3+17=57即为总造价。(2分)四、证明题(本大题共3小题，每小题10分，共30分)1．设论域D={a,b,c}，求证：。证明：第6页（共6页）(3分)(3分)(3分)(1分)第6页（共6页）第6页（共6页）2．设R是A上一个二元关系，试证明：若R是A上一个等价关系，则S也是A上的一个等价关系。证明：（1）S自反的(3分)，由R自反，，（2）S对称的(3分)（3）S传递的(3分)由（1）、（2）、（3）
5、得；S是等价关系。(1分)3.设是一代数系统，*是R上二元运算，，，则0是幺元且是独异点。证明：[幺]，即(3分)[乘]，由于+，·在R封闭。所以，即*在R上封闭。(3分)[半群](3分)因此，〈R，*〉是独异点。(1分)五、应用题(本大题共2小题，每小题15分，共30分)1．假设英文字母a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。解：(1)根据权数构造最优二叉树：
6、(5分)第6页（共6页）(2)传输它们的最佳前缀码如上图所示，(5分)a—011；e—111；h—10；n—110；p—0101；r—000；w—0100；y—001(3)happynewyear的编码信息为：(5分)10011010101010011101110100001111011000附：最优二叉树求解过程如下：2．设集合A={a,b,c,d}上关系R={,,,}，请写出R的关系矩阵MR和关系图GR，并用矩阵运算求出R的传递闭包t(R)。解：(1)R的关系矩阵
7、MR(4分)第6页（共6页）(2)R的关系图GR(4分)(3)用矩阵运算求R的传递闭包t(R)(1分)(1分)(1分)(1分)所以，t(R)={,,,,,,,,}(3分)第6页（共6页）
