一、单项选择题
1．设a = p(a)表示集合a的幂集，下列哪一个是错的？（
a． b． c． d．
2．设a=上的二元关系r = 则r具备性质（ ）
a．反对称的，传递的b．反对称的
c．反对称的， 自反的d．传递的。
3．集合a = b = 下列a到b的二元关系中，哪一个能构成函数？（ a． c．
4．下列命题中（ ）是正确的。
a．欧拉图的子图一定是欧拉图。
b．哈密顿图的子图一定是哈密顿图 。
c．平面图的子图一定是平面图。
d．树的子图一定是树。
5．设有向图d的邻接矩阵为。
则d中长度为3的通路总数有( )条。
a．9 b．10 c．11 d．12
二、填空题
1．公式的主析取范式为。
2．某班共有学生60人，其中有25人订杂志甲，26人订杂志乙，26人订杂志丙，11人订杂志甲和乙，9人订杂志甲和丙，8人订杂志乙和丙，还有8人未订任何杂志，则三种杂志都订的学生有人。
3．设a = r为a上的整除关系，则a的子集b = 的极大元为 ，极小元为 ，上界为下界为 。
4．设，则函数f是 （单射，满射还是双射）。
5．设集合a=上的的划分s =，则由划分s所确定的a上的等价关系r
6．用kruskal算法求得下图g的一棵最小生成树为。
7．设连通平面图g有4个面，9条边，则g有个结点。
三、解答题 ( 4×8 = 32分 )
1．将下列语句翻译成命题逻辑公式或谓词逻辑公式。
1)（4分）只有天下大雨，小明才乘公共汽车上学。
2)（4分）不是所有整数都是奇数。
2．设a = 上的二元关系r = 求r的关系矩阵，关系图。
3．设是a到 a 的满射，且，证明 。这里表示a 上的恒等映射。
4．画图：(1)一个既没有欧拉回路，又没有哈密尔顿回路的图；
（2）一个具有欧拉回路和哈密尔顿回路的图，并具体指出这两个回路。
5.用哈夫曼算法求带权为2,3,6，8,10,11的最优二元树并计算此最优树的权。
6. 设一棵树t有7片树叶，3个度数为3的结点，其余结点的度数均为4，求t的结点总数。
7.用二元有序完全树表示算术表达式。
并分别用波兰符号法和逆波兰符号法表示上述算术表达式。
四、证明题
1．用演绎法证明下述论断的正确性。
2. 设r是集合a上的一个具有传递和自反性质的关系，t是a上的关系，使得。
证明 t是a上的等价关系。
3.试证明：树是一个偶图。
4．用演绎法证明。
5．p335 27，28 这类题。一．二、
3． 10，12； 4，10； 没有； 2
4． 单射
三、1．解：（1）设p：天下大雨 q：小明乘公共汽车上学，则有2）设z（x）：x 是整数，e(x)：x是奇数。
2．解。3．略
4．略 5．解：
权 （ 定义10.3.7 ）
注：哈夫曼算法见书本（p292）算法10.3.6以及例10.3.9
6．解：设t有x个4度结点，则t的结点总数，边数。
由握手定理得。
解得。所以结点总数。
2）算式的波兰符号表示式为书上p295：先根次序遍历算法… 省去括号 ）
3）算式的逆波兰符号表示式为 （同上，用后根遍历，省去括号，规定… 即为… ）
四、1．证明：
2．证明：1）对任意的，由r是自反的，得，所以，即t是自反的。
2）对任意的，若，则，即有
从而，即t是对称的。
3）对任意的，若，则。且。即且
又因为r是传递的 ， 所以。
从而 ，所以t是传递的。
由（1）、（2）、（3）知t是等价关系。
3．试证明：树是一个偶图。（p334:18）
证：设 g= 是一棵树。任选， 定义 v 的两个子集如下：
. 现证明v1 中任二结点之间无边存在。若存在一条边 （u,v）, u,v , 由于树中任意两个结点之间仅存在唯一一条基本通路，故这条基本通路就是他们之间的短程线，设v0到u 的短程线为，则其长度为k+1,是偶数，因为（u,v），所以，v 是到 v 的一条通路，且该通路的长度k+2 为奇数，从而它不是基本通路， 故v必与某个相同，从而是g中的一条基本通路，这与g 是树矛盾。
4．用演绎法证明。
证明： 1p
2es，(1
3p4us，（3
5t，（46t，（5）（2
7） p8us，（76分）
9t，（8）（6） （7分）
10eg，（9）
5．在简单平面图g中，至少有一个度数小于等于5的结点。（p335:27）
或。5‘ 证明小于30条边的简单平面图g中至少有一个度数小于等于4的结点。（p335: 28 ）
试卷1 有答案
信息技术教师招聘考核试题含答案。一 选择题 60个 1 网页都是按照一种描述文档的标记规则编写而成的，这套标记规则叫做 c c html 2 basic语言属于 c c 高级语言。3 下列哪一个控件没有caption属性 a a textbox 4 在vb中，要想单击按钮 结束 时结束程序，可在该按...
离散试卷A答案
离散数学 a卷 2009 2010 1参 一 判断题 在下表相应位置，正确填a，错误填b。每题1分，共10分 二 填空题 将答案填于横线上。每空1分，共10分 1.p q 2.x q x t x 注 答案不唯一，此式的等值式如x q x t x 或x q x t x 等也对 3.x n x y n ...
离散试卷B答案
2009 2010年卷离散数学答案。一 判断题 每题 1 分，共 10 分 一 填空题 每题 1 分，共 10 分 1 m 2 qp 3 pq pq 45 重言式 6 7 p a p b q a q b 三 选择题 20分 1 c 2 3 4 5 6 7 8 9 10 四 简答题 35分 1 5分 ...