离散数学试题与答案试卷一。
1．设 （n：自然数集，e+ 正偶数） 则。
2．a，b，c表示三个集合，文图中阴影部分的集合表达式为
3．设p，q 的真值为0，r，s的真值为1，则。
的真值。4．公式的主合取范式为。
5．若解释i的论域d仅包含一个元素，则在i下真值为。
6．设a=，a上关系图为。
则 r27．设a=，其上偏序关系r的哈斯图为。
则 r8．图的补图为。
9．设a= ，a上二元运算如下：
那么代数系统的幺元是有逆元的元素为它们的逆元分别为。
10．下图所示的偏序集中，是格的为。
1、下列是真命题的有（ ）
a． ；b．； c． ；d． 。
2、下列集合中相等的有（ ）
a．；b．；c．；d． 。
3、设a=，则a上的二元关系有（ ）个。
a． 23 ； b． 32 ； c． ；d． 。
4、设r，s是集合a上的关系，则下列说法正确的是（ ）
a．若r，s 是自反的， 则是自反的；
b．若r，s 是反自反的， 则是反自反的；
c．若r，s 是对称的， 则是对称的；
d．若r，s 是传递的， 则是传递的。
5、设a=，p（a）（a的幂集）上规定二元系如下。
则p（a）/ r=（
a．a ；b．p(a) ；c．}，
d．，，6、设a=，，则a上包含关系“”的哈斯图为（ ）
7、下列函数是双射的为（ ）
a．f : ie , f (x) =2x ； b．f : nnn, f (n) =
c．f : ri , f (x) =x] ；d．f :in, f (x) =x |
注：i—整数集，e—偶数集， n—自然数集，r—实数集）
8、图中从v1到v3长度为3 的通路有（ ）条。
a． 0； b． 1； c． 2； d． 3。
9、下图中既不是eular图，也不是hamilton图的图是（ ）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。
a．1； b．2； c．3； d．4 。
1、 r是集合x上的一个自反关系，求证：r是对称和传递的，当且仅当。
a, b> 和在r中有<.b , c>在r中。（8分）
2、 f和g都是群到< g2, *的同态映射，证明是的一个子群。其中c= (8分)
3、 g= (v| =v，|e|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则， 由此证明彼得森图（peterson）图是非平面图。（11分）
用cp规则证明下题（每小题 8分）
1、设集合a=上的关系r=用矩阵运算求出r的传递闭包t (r)。 9分）
2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （分）
试卷一答案：
一、填空 20% （每小题2分）
；6、；7、 ia ；8、
9、a ；a , b , c ,d ；a , d , c , d ；10、c;
二、选择 20% （每小题 2分）
三、证明 26%
1、 证：” 若由r对称性知，由r传递性得
” 若，有任意 ，因若所以r是对称的。
若， 则即r是传递的。
2、 证，有 ，又。
< c , 是 < g1 , 的子群。
3、 证：设g有r个面，则，即 。而故即得 。（8分）
彼得森图为，这样不成立，所以彼得森图非平面图。（3分）
二、 逻辑推演 16%
1、 证明：
p（附加前提）
t①i p
t②③i t④i
t⑤i p
t⑥⑦i cp
2、证明 p（附加前提）
us① p
us③ t②④i
ug⑤ cp
三、 计算 18%
1、 解：，
t (r)=
2、 解： 用库斯克（kruskal）算法求产生的最优树。算法略。结果如图：
树权c(t)=23+1+4+9+3+17=57即为总造价。
1、设g为9阶无向图，每个结点度数不是5就是6，则g中至少有个5度结点。
2、n阶完全图，kn的点数x (kn
3、有向图中从v1到v2长度为2的通路有条。
4、设[r，+，是代数系统，如果①[r，+]是交换群 ②[r，·]是半群
③ 则称[r，+，为环。
5、设是代数系统，则满足幂等律，即对有。
1、 下面四组数能构成无向简单图的度数列的有。
a、（2，2，2，2，2b、（1，1，2，2，3）；
c、（1，1，2，2，2d、（0，1，3，3，3）。
2、 下图中是哈密顿图的为。
3、 如果一个有向图d是强连通图，则d是欧拉图，这个命题的真值为（ ）
a、真； b、假。
4、 下列偏序集（ ）能构成格。
5、 设，*为普通乘法，则[s，*]是（）。
a、代数系统； b、半群； c、群； d、都不是。
1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。
2、（8%）若图g中恰有两个奇数度顶点，则这两个顶点是连通的。
3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。
4、（10%）证明循环群的同态像必是循环群。
5、（12%）设是布尔代数，定义运算*为，求证[b，*]是阿贝尔群。
1、在二叉树中。
1） 求带权为2，3，5，7，8的最优二叉树t。（5分）
2） 求t对应的二元前缀码。（5分）
2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在d点）。
答案：1、 6；2、n；4、+对·分配且·对+分配均成立；5、。
1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集v=，设，无向图g=（v，e）
现证g中至少有两个结点度数相同。
事实上，（1）若g中孤立点个数大于等于2，结论成立。
2） 若g中有一个孤立点，则g中的至少有3个顶点，既不考虑孤立点。设g中每个结点度数均大于等于1，又因为g为简单图，所以每个顶点度数都小于等于n-1，由于g中n顶点其度数取值只能是1，2，…，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。
2、（8分）证：设g中两个奇数度结点分别为u，v。若 u，v不连通则至少有两个连通分支g1、g2，使得u，v分别属于g1和g2。
于是g1与g2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。
3（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8
由图论基本定理知：，而，所以必有，即每个面用3条边围成。
4（10分） 证：设循环群[a，·]的生成元为a，同态映射为f，同态像为[f（a），*于是都有。
对n=1有。
n=2, 有。
2023年西安电子科技大学考研复试 离散
离散数学试题与答案试卷一。1 设 n 自然数集，e 正偶数 则。2 a，b，c表示三个集合，文图中阴影部分的集合表达式为 3 设p，q 的真值为0，r，s的真值为1，则。的真值。4 公式的主合取范式为。5 若解释i的论域d仅包含一个元素，则在i下真值为。6 设a a上关系图为。则 r27 设a 其上...
2023年西安电子科技大学考研复试 微机原理真题
微型计算机原理及接 术 试题。一。单项选择题。1.8086cpu芯片的外部引线中，数据线的条数为 6条 8条 16条 20条。2.8088cpu上ready信号为下面哪种信号有效？上升边下降边 高电平低电平。3.8088cpu中的cs寄存器是一个多少位的寄存器？8位 16位 24位 32位。4.当8...
西安电子科技大学考研复试 数据库
a 数据定义功能 b 数据管理功能 c 数据操纵功能 d 数据控制功能。11.通过指针链接来表示和实现实体之间联系的模型是 a 关系模型b 层次模型 c 网状模型d 层次和网状模型。12.数据的正确 有效和相容称之为数据的 a 安全性 b 一致性 c 独立性 d 完整性。13.对关系模型叙述错误的是...