昆明理工大学2007年硕士研究生招生入学考试试题
(A卷)
考试科目代码： 607 考试科目名称 ： 离散数学 试题适用招生专业 ： 计算机软件与理论
考生答题须知
1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做
在本试题册上无效。请考生务必在答题纸上写清题号。
2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。 4． 答题时不准使用涂改液等具有明显标记的涂改用品。
一、选择题（每个选择2分，共40分） 1、 设P表示“明天下雨”，Q表示“明天下雪”，R表示“我去学校”，则命题“当且仅当明天不下雪并且不下雨时我才去学校”符号化为（ ）。 (a)PQR (b)PQR (c)PQR (d) PQR 2、命题公式“（P∧（P→Q））→Q”是（ ）。 (a)矛盾式 (b) 蕴涵式 (c) 重言式 (d) 等价式 3、谓词公式“x(P(x)yR(x))Q(x)”中量词x的辖域是（ ）。 (a)x(P(x)yR(x)) (b)P(x) (c)(P(x)yR(x)) (d) P(x),R(x)) 4、给定下列两组前提： （1）P→R，┓Q→P，┓R （2）┓PR，Q，R→（Q→S） 则（1）的有效结论为（ ），（2）的有效结论为（ ）。 (a)Q (b)┓P (c)R→S (d)P→S 。 5、下面哪个公式不是谓词公式（ ）(a)P (b)P(x)∨Q(x)→P(x) (c)x(R(x)∧R(x,y)) (d)x(R(x)→P(x,y)) 6、设A={{1，2，3}，{4，5}，{6，7，8}}下面各式中哪个是错误的（ ）。 (a) A (b) {6，7，8}A (c) {{4，5}}A (d) {1，2，3}A 7、设S表示内存中的系统区的集合，C表示内存中的公共作业区的集合，A1 ,A2 ,A3分别表示三个用户专用作业区的集合，则“第一个用户不能访问的内存区域”表示为（ ）。 (a) S∪┓A1 (b) S∪A2∪A3 (c)S∪C (d) S∪C∪A2∪A3 第 1 页 共 3 页
昆明理工大学2007年硕士研究生招生入学考试试题 8、集合A上的函数f：“„ 是取 „ 的平方”为A→A的（ ）。 单射函数 (b) 满射函数 ( c) 双射函数 (d) 只是一个函数 。 9、集合A={0,b},B={1,b,3},则A∪B的恒等关系为（ ）(a) {<0,0>,<1,1>,,<3,3>} (b) {<0,0>,<1,1>,<3,3>} (c) {<1,1>,,<3,3>} (d) {<0,1>,<1,b>,,<3,0>} 10、设集合A有4个元素，则A上的不同的等价关系的个数为（ ）。 (a)11 (b)14 (c)15 (d)17 11、集合A上的等价关系R，决定了A上的一个划分，该划分就是（ ）。 (a) 商集A/R (b) 差集A-R (c) 交集A∩R (d) 并集A∪R 12、0和自然数全体所构成的集合中的最小元为（ ）。 (a)负数 (b)最小的正数 (c) 1 (d) 0 13、设f：a称b为母亲，g：b称c为父亲，则gοf为（ ）。 (a) a称c为祖父 (b) a称c为外祖父 (c) a称c为祖母 (d) a称c为外祖母 14、仅由一个孤立点组成的图称为（ ）。 (a)零图 (b)平凡图 (c)多重图 (d)子图 15、设|V|= n (n >1)，G = 是强连通图，当且仅当（ ）。 (a) G中至少有一条路 (b) G中有通过每个结点至少有一条的路 (c) G中至少有一条回路 (d) G中有通过每个结点至少有一条的回路 16、设G是具有k个连通分支的平面图，若G中有n个结点，m条边，r个面，则必有（ ）。 (a) n-m+r=2 (b) n-m+r=k (c) n-m+r=k-1 (d) n-m+r=k+1 17、一棵树有2个2度结点，1个3度结点，3个4度结点，则该树的1度结点数为 （ ）。 (a) 7 （b）8 （c）9 （d）10 18、n阶图G中有m条边，每个顶点的度数不是k就是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则 Nk为（ ）。 (a) n/2 (b) n * k (c) n(k+1)-2m (d) n(k+1)- m 19、在自然数集N上，下列哪种运算是可结合的( )。 (a) a*b = a - b (b) a*b = max (a, b) (c) a*b = a+2b (d) a*b = |a - b| 二、填空题（每题3分，共30分） 1、设L(x): x是运动员，J (x): x是教练，A(x，y)：x敬佩y。则命题“所有的运动员都敬佩某些教练”符号化为 。 2、由n个命题变元可以组成 个不等价的命题公式。 3、对谓词公式x (P →Q (x))R(a)，其中P：2>1，Q (x)：x≤3，R (x) >5，a=5则当个体域为：{-2，3，6}时，其真值是 。 4、命题公式是谓词公式的 。 5、集合A={,a,{a}}的幂集P(A)= 。 6、设集合A={0，1，2}，P(A)上的一个二元关系“x是y的一个真子集”具有反第 2 页 共 3 页 自反性、 性和 性。 7、若集合A上的关系R具 ，则称R是A上的一个偏序关系。 8、在有8个结点的图中（存在不存在） 结点总度数为45的图，因为 。 9、由Huffman算法求带权1，3，3，5，5，3，50，20的最优二元树T的树权W（T）= 。 10、设Z为整数集合，+为普通加法，则代数系统< Z, +> 中，Z对+的幺元为 ，Z对+的零元为 _，对任意x∈Z，其x = 。 三、计算题(共35分) 1、 用等值演算方法求给定命题公式的主析取范式，并写出成真赋值。 （P∨（Q∧R）→（P∧Q∧R） （8分） 2、求谓词公式x A(x, y)→y B (y) →x D(x,y) 的前束范式。（7分） 3、设X={a,b,c,d}, R是X上的二元关系：R ={,,,, , }，试求①R的关系矩阵，②求出R 3，③用矩阵的方法求出关系R的传递闭包。 （10分） 4、 设A={1, 2,„„,9},R是A×A上的一个二元关系，对于任意的 a,b,c,d∈A，若a+d=b+c且R。则R是等价关系，求[<2,5>]的等价类。 （3分） 5、对如下运算 a + b×c – d – e÷f构造一棵二元树，并求出该树的三种遍历。（7分） 四、 证明题(共45分) 1、构造下述推理的证明： 对IT业的好事就是对国家的好事；对国家的好事就是对你的好事。你去买一台电脑是对IT业的好事。 （12分） 2、设A，B为任意的集合，证明 P(A∩B)= P(A)∩P(B)。 （10分） 3、设R是A的一个二元关系，并设 S = {〈a，b〉| 对某个c使〈a，c〉∈R 且〈a，b〉∈R } 证明如果R是等价关系，则S也是等价关系。 （9分） 4、证明：非平凡的无向连通图G是树当且仅当G的每一条边都是割边。（8分） 5、设 为一个代数系统，其中*是一个二元运算，使任意的 a,b∈A，有a*b=a 。 （1） 证明 * 运算是可结合的； （2） 说明 * 运算是否是可交换的。 (6分) -1第 3 页 共 3 页
