一、选择题（每小题只有一个正确答案，每题2分，共30分）
1、令A（x）:x是实数，B（x）:x是有理数，则命题：并非所有有理数都是实数。

符号化为：（）
A、x┐(A(x)∧B(x))
B、┐x(B(x)→A(x))
C、┐x(A(x)∧B(x))
D、┐x(B(x)∧┐A(x))
2、设A={{1，2，3}，{4，5}，{6，7，8}}，则下列选项正确的是（）
A、1∈A，
B、φ∈A
C、{1，2，3} A，
D、{{4，5}} A
3、设A、B为集合，A-B=φ，则有（）
A、B=φ
B、B≠φ
C、A B
D、B A
4、一个连通有向图，如果它的每个结点的出度均等于入度，那么它有一条（）。

A、基本回路
B、欧拉回路
C、欧拉通路
D、简单回路
5、一棵树有2个结点度数为2，2个结点度数为3，3个结点度数为4，则它的树叶数为（）
A、8
B、9
C、10
D、12
6、G是连通平面图，有5个顶点、6个面，则G的边数为（）
A、6
B、5
C、11
D、9
7、设A={1，2，3}，B={1，2，3，4，5}，C={2，3}，则（A∪B）+C=（）
A、{1，2}
B、{2，3}
C、{1，4，5}
D、{1，2，3}
8、下列命题中为假的是（）
A、{a，{b}}{{a，{b}}}
B、φP(∪{φ,{φ}})
C、{a}XaX
D、X∪Y=YX=φ
9、设解释T为：个体域为D={—2，3，6}，谓词A(x)：x 6，B(x)：x>5，则根据解释，公式x(A(x)∨B(x))的真值为（）
A、0
B、1
C、没有确定真值
10、一个教室公用一个电源，如果想接34盏灯，则至少需要4个插线孔的接线板（）个。

A、10
B、11
C、12
D、34
11、下列说法错误的是（）
A、n个结点m条边的有向树和无向树均满足：m=n－1.
B、树都是二部图。

C、有向树都是单侧连通的
D、有桥的图不是欧拉图
12、设A={a,b,c}，R是A上的关系，R={<a,b>，<a,c>，<c,a>}，那么R是（）
A、自反的
B、反自反的
C、对称的
D、反对称的
E、传递的
13、设图G是有5个顶点的连通图，总度数为18，则从G中删去（）边后使之变成树。

A、10
B、5
C、3
D、2
14、一个无向图G=<V，E>是二部图的充分必要条件是（）
A、G中没有回路
B、G中没有长度为奇数的回路
C、G中每个结点的度数均为偶数
D、G中每个结点的度数均为奇数
15、关系R是集合A上的关系，若R是自反性，对称性和传递性，则R是A上的（）关系。

A、相容关系
B、等价关系
C、偏序关系
D、全序关系
得分评卷人
二、填空题（每空2分，共30分）
1、若有向图D的基图是一棵树，则D称为。

2、设T是r元完全正则树，且为根树，根结点在第0层，则第i层上的结点数为。

3、图G是有7个结点，15条边的简单平面图，则G的每个面的次数为：。

4、命题公式p∨（p→q）的类型是。

5、能产生等长的前缀码的二叉树是。

6、设e是无向连通图G中的一条边，若e不在G的任何生成树中，则e是。

7、令p：他怕困难，q：他能战胜困难。

命题：“如果他不怕困难，那么他能战胜困难。

”的符号化形式为：。

8、已知公式A（p，q，r）的主析取范式为m0∨m2∨∨m7，m4∨m5则它的主合取范式为：
（用p，q，r表示）
9、如果一个有向图D是强连通的，则图D是欧拉图。

这个命题的真值为。

10、如果根树T除了树叶以外的每个结点都有两棵子树，则称T为。

11、n阶k-正则图G的边数m= 。

12、逻辑学是研究的科学。

13、n阶无向完全图kn中，当n 时，kn是哈密尔顿图。

14、设T为n（n≥2）个顶点，m条边的无向连通图G的生成树，若T无弦，则m和n的关系
为：。

15、对于具有K（K≥2）个连通分支的森林，恰巧加条新边能使所得图为树。

得分评卷人
三、计算题（共24分）
1、给出公式(p∨(┐q∧r))∧((┐s∨t)∧┐u)的根树表示。

（8分）
2、设有5个城市v1，v2，v3，v4，v5，任意两个城市之间铁路造价如下：（以百万元为单位）W（v1，v2）=12，W（v1，v3）=7，W（v1，v4）=4，W（v1，v5）=10，W（v2，v3）=4，W（v2，v4）=8，W（v2，v5）=6，W（v3，v4）=5，W（v3，v5）=10，W（v4，v5）=12，试画出连接5个城市的且造价最低的铁路网。

（要求写出解题思路）（8分）
3、求叶的权分别为2、
4、6、8、10、12、14的最优二叉树、权及对应的前缀码（8分）
得分评卷人
四、证明题（共16分）
1、证明：设T是二叉正则树，T有t片树叶，i个分支点，证明T是2t－1阶树。

（即T有2t－1个顶点）。

（8分）
2、公安局受理某单位发生的一桩案件，已获取如下事实：
（1）疑犯甲或疑犯乙至少有一人参与作案；
（2）若甲作案，则作案不在上班时间；
（3）若乙的证词正确，则大门还未上锁；
（4）若乙的证词不正确，则作案发生在上班时间；
（5）已证实大门上了锁。

试判断谁是作案人。

要求先将各命题进行符号化，并写出前提、结论及推理证明过程。

（8分）
参考答案：
一、选择题（每小题只有一个正确答案，每题2分，共30分）
题号123456789101112131415
答案B D C B C D C D B B C B B C B
二、填空题（每空2分，共30分）
1、有向树。

2、ri 。

3、3 。

4、重言式（永真式）。

5、完全二叉树。

6、环。

7、┐p→q。

8、(p∨q∨┐r)∧(p∨┐q∨┐r)∧(┐p∨┐q∨r) 。

9、0。

10、二叉树。

11、m=nk/2 。

12、思维的形式结构及规律。

13、n≥3。

14、m=n-1。

15、K-1 。

三、计算题（共24分）
画对图即得8分，画错不得分
2、设有5个城市v1，v2，v3，v4，v5，任意两个城市之间铁路造价如下：（以百万元为单位）W（v1，v2）=12，W（v1，v3）=7，W（v1，v4）=4，W（v1，v5）=10，W（v2，v3）=4，W（v2，v4）=8，W（v2，v5）=6，W（v3，v4）=5，W（v3，v5）=10，W（v4，v5）=12，试画出连接5个城市的且造价最低的铁路网。

（8分）
解：用Kruskal算法求最小生成树即得连接五个城市且造价最低的铁路网如图：最低造价为：23
q r
s
t u
（百万） 写对思路得2分 画对图得4分
计算出造价2分
3、求叶的权分别为2、
4、6、8、10、12、14的最优二叉树、权及对应的前缀码（8分）
最优二叉树为 权＝148
前缀码为：{01，11，001，100，101，0000，0001}
画对最优树得4分，计算出权得2分，写出前缀码得2分。

四、证明题（共16分）
1、设T 是正则r 叉树，T 有t 片树叶，i 个分支点，证明(r －1)i=t －1。

（8分） 证明：因为T 是正则r 叉树，所以T 的每个分支点的出度均为r.（2分） 由于所有结点入度之和等于所有结点出度之和 （1分）
5 10
4 V1 V3 V4
V5
V2 0 0 0
0 0
1
1
1
1
1 1
T中所有结点出度之和等于（2分）
T中所有结点入度之和等于i+t （2分）
因此ri=i+t-1得(r-1)i=t-1 （1分）
或：T中的边数为ri，结点数为i+t，由边数=结点数-1得
ri，=i+t-1，所以(r－1)i=t－1
2、公安局受理某单位发生的一桩案件，已获取如下事实：
（1）疑犯甲或疑犯乙至少有一人参与作案；
（2）若甲作案，则作案不在上班时间；
（3）若乙的证词正确，则大门还未上锁；
（4）若乙的证词不正确，则作案发生在上班时间；
（5）已证实大门上了锁。

试判断谁是作案人。

要求先将各命题进行符号化，并写出前提、结论及推理证明过程。

（8分）解：作案人是乙
先符号化，设p：甲作案，q:乙作案，r作案发生在上班时间，s：乙的证词正确，t：大门上锁前提：p∨q，p→┐r，s→┐t,┐s→r,t
结论：q
证明：1）t 前提引入
2）s→┐t 前提引入
3）┐s 1）2）拒取式
4）┐s→r 前提引入
5） r 3）4）假言推理
6）p→┐r 前提引入
7）┐p 5）6）拒取式
8）p∨q 前提引入
9）q 7）8）析取三段论
判断出谁作案：2分，写出前提结论：2分，证明4分，每步0.5分。