离散结构
2007-a
一、填空（每空2分，共30分）
1、设P：2+2=4，Q：3是奇数 xujie将命题“2+2=4，当且仅当3是奇数”符号化__(1)___，其真值为__(2)___。 2、在公式中，自由出现的变元为___(3)____。
3、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素__(4)___，若关系R具有对称性，当且仅当关系矩阵是__(5)___。 4、若关系，则关系一定具有__(6)___性。
5、有向图的连通性可分为弱连通、强连通、__(7)___。
6、前缀表达式 + * 2 / 8 4 3 的值是__(8)___。
7、设G是完全二元树，G有15个顶点，其中有8个叶子，则波诺波黑猩猩G有__(9)___条边，G的总度数是__(10)___。
8、十进制3位数的数字中恰好有一个8和一个9，共有__(11)___个这样的3位数。
9、设集合，上的运算定义为：
则代数系统中单位元是__(12)___，的左逆元是__(13)___，无左逆元的元素是__(14)___。
10、设是由元素生成的循环，且的阶为4，则集合=__(15)___。
二、选择题（每题2分，共30分）
A、地球上的人真多
B、把门关上
C、下午有会吗？
D、
2、一个公式在等价意义下，下面哪个写法是唯一的_____。
A、析取范式 B、合取范式 C、主析取范式 D、以上都不唯一
3、设命题公式，则G是_____。
A、永真式 B、矛盾式 C、可满足式 D、以上都不是
4、设I是如下一个解释，，其中，为真，，为假，则在解释I下取真值的公式是______
A、 B、 C、 D、
5、下列哪个表达式错误_____。。
A、
B、
C、
D、
6、设R，S是集合上的两个关系，其中，，则S是R的____闭包。
A、自反 B、反对称 C、对称 D、传递
7、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_____。
A、 B、 C、 D、的对称闭包
8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的_____。
A、下界 B、上界 C、最小上界 D、以上都不对
9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。
A、1，2，2，3，4，5
B、2，3，3，4，4，5
C、1，1，1，2，3
D、2，3，3，4，5，6
10、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_____条边后使之成为树。
A、10 B、5 C、3 D、2
11、在下列关于图论的命题中，正确的是_____。
A、哈密顿图一定是欧拉图
B、无向完全图都是欧拉图
C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出
D、哈密顿图是平面图
12、下面编码_____不是前缀码。
A、11，00，10，01
B、01，11，011，1001
C、101，11，001，011，010
D、010，11，011，1011，1001，10101
13、5阶非同构的无向树有_____棵。
A、1 B、2 C、3 D、4
14、由0、1、2、3这四个数字能构成_____个3位数
血清铁蛋白
A、64 B、48 C、24 D、18
15、在下列选项中，不是的是_____。
A、，为有理数，+为加法运算
B、，为非零实数集，为乘法运算
C、全体实对称矩阵集合，对于矩阵的加法运算靖州县
D、，为有理数，*为乘法运算
三、计算题（5分+5分+8分，共18分）
，，，，，
，，，，
试求出连接5个城市的且造价最低的铁路网
2、构造前序遍历为a，b，f，c，g，h，i，d，e，j，k，p的有序树，其中a有4个子结点，c有3个子结点，j有2个子结点，b和e都有一个子结点，所有其它结点都是树叶。
34、设集合，A上的关于等价关系R的商集=，试求：
（1）等价关系R
（2）写出关系矩阵
（3）画出关系图
（4）写出R的传递闭包
四、证明题（5分+5分+6分，共16分）
1、设R是A上的等价关系，S是B上的等价关系，且A和B非空，关系T满足：
且，证明T是上的等价关系。
2、设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则或，其中k为正整数。
3、若是，，定义G中的运算“”为：，对
证明为。
五、应用题（6分）
的意义如下：p：张是大学生，q：张心情愉快，r：张唱歌
试用日常语言说明下列复合命题：
(1)
(2)
(3)
2007-b
一、填空（每空2分，共30分）
1、表达式中谓词的个体域是{}，将其中的量词消去，写成与之等价的命题公式为__(1)__。
2、设R是集合A上的二元关系，如果关系R同时具有__(2)__、__(3)__和传递，则称R是A上的偏序关系。
3、已知集合上的二元关系，，则=__(4)__，经济社会体制比较=__(5)__。
4、若有限集关系职来职往第66期刘璐具有自反性，则其对应的关系矩阵主对角元素全为__(6)__。
5、若某个简单图不是欧拉图但具有欧拉通路，则图中顶点度数为奇数的顶点个数一定为__(7)__。
6、设是图，如果G是__(8)__并且__(9)__则G是树。
7、一个无向图的欧拉回路要求经过图中__(10)__一次且仅一次，哈密顿回路要求经过图中__(11)__一次且仅一次。
8、树是平面图，它有__(12)__个面。
9、在、半、独异点中，__(13)__满足消去律。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议