2023年7月19日发(作者：)

西安交通大学课程考试复习资料

单选题

1.若R和S是集合A上的两个关系,则下述结论正确的是( )

A.B.C.D.答案: A

2.具有如下定义的代数系统(G,*)，哪个不构成群？（）

A.B.C.D.答案: D

3.设集合A={a,b,c}，R是A上的二元关系，R={＜a,a＞,＜a,b＞,＜a,c＞,＜c,a＞} ，那么R是( )

A.反自反的

B.反对称的

C.可传递的

D.不可传递的

答案: D

4. ( ) A.=

B.∈

C.

D.

答案: D

5.A.B.

( )

C.

D.

答案: C

6. ( )

A.相同或者其中一个通过行与列变换能转换成另一个

B.一定相同

C.行列式相同

D.没什么关系

答案: A

7.设是无向图G=(V,E),则奇结点的个数为( )

A.奇数

B.偶数

C.大于2的自然数

D.1－100之间的自然数

答案: B

8.A.存在且唯一

B.不存在

C.存在但不唯一

D.可能存在

答案: A

元素的补元 ( )

9.设R和S是集合A上的任意关系,则下列命题为真的是( ) A.若R和S是自反的，则B.若R和S是反自反的，则C.若R和S是对称的，则D.若R和S是传递的，则答案: A

也是自反的

也是反自反的

也是对称的

也是传递的

10.A.映射

B.单射

C.满射

D.双射

答案: C

( )

11.A.f必是满射

B.f必是单射

C.g必是满射

D.g必是单射

答案: A

( )

12.函数的复合满足( )

A.交换率

B.结合率

C.幂等率

D.分配率

答案: B

13.在代数系统中,整环和域的关系为( )

A.整环一定是域

B.域不一定是整环

C.域一定是整环

D.域一定不是整环

答案: C 14.A.自反的、反对称的、传递的

B.自反的、对称的、传递的

C.反自反的、对称的、传递的

D.反自反的、对称的、非传递的

答案: A

( )

15.对意集合A、B、C,下述论断正确的是( )

A.B.C.D.答案: A

16.N是自然数集,≤是小于等于关系,则(N,≤)是( )

A.有界格

B.有补格

C.分配格

D.有补分配格

答案: C

17.

A.A

B.B

C.C

D.D

答案: D

18. A.A

B.B

C.C

D.D

答案: D

19.

A.A

B.B

C.C

D.D

答案: D

20.

A.A

B.B

C.C

D.D

答案: D

21.

A.A

B.B

C.C

D.D

答案: D

. 22.

A.A

B.B

C.C

D.D

答案: C

23.

A.A

B.B

C.C

D.D

答案: A

24.

A.恒真的

B.恒假的 C.可满足的

D.前束范式

答案: C

25.

A.A

B.B

C.C

D.D

答案: C

26.

A.A

B.B

C.C

D.D

答案: D

27.量词的约束范围称为量词的（ ）。

A.定义域

B.个体域

C.辖域

D.值域 答案: C

28.任何一个有限群在同构的意义下可以看作是（）。

A.循环群

B.置换群

C.变换群

D.阿贝尔群

答案: B

29.在任意n阶连通图中，其边数（）。

A.至多n-1条

B.至少n-1条

C.至多n条

D.至少n条

答案: B

30.设集合A={a,b,c},2A上的包含关系是（）。

A.自反的、反对称的、传递的

B.自反的、对称的、传递的

C.反自反的、对称的、传递的

D.反自反的、对称的、非传递的

答案: A

31.图的构成要素是（）。

A.结点

B.边

C.结点与边

D.结点、变和面

答案: C

32.设R和S是集合A上的任意关系，则下列命题为真的是（）。

A.若R和S是自反的，则R。S也是自反的

B.若R和S是反自反的，则R。S也是反自反的

C.若R和S是对称的，则R。S也是对称的

D.若R和S是传递的，则R。S也是传递的 答案: A

33.函数的复合运算“ο”满足（）。

A.交换律

B.结合律

C.幂等律

D.消去律

答案: B

34.下列各命题中。哪个是真命题？（）

A.若一个有向图是强连通图，则是有向欧拉图

B.n（n≥1）阶无向完全图Kn都是欧拉图

C.n（n≥1）阶有向完全图都是有向欧拉图

D.二分图G=〈V1,V2,E〉必不是欧拉图

答案: C

35.函数的复合满足（）。

A.交换率

B.结合率

C.幂等率

D.分配率

答案: B

36.域和整环的关系为（）。

A.整环是域

B.域是整环

C.整环不是域

D.域不是整环

答案: B

37.设集合A中有4个元素，则A上的不同的等价关系的个数为（）。

A.11个

B.14个

C.15个

D.17个 答案: C

38.在代数系统中，整环和域的关系为（）。

A.整环一定是域

B.域不一定是整环

C.域一定是整环

D.域一定不是整环

答案: C

39.任何无向图中结点间的连通关系是（）。

A.偏序关系

B.等价关系

C.相容关系

D.逆序关系

答案: B

40.设是6阶群，H是G的非平凡子群，则的阶数可能是（）。

A.1

B.3

C.4

D.5

答案: B

41.下列关系中哪一个能构成函数，其中N是自然数集，R是实数集。（ ）

A.{| x, yB.{| x, yC.{| x, yD.{| x, y答案: B

N, x+y< 10 }

R, y= x2 }

R, x= y2 }

N, x=小于y的素数个数}

42.

A.A

B.B

C.C

D.D

答案: D

43.下列各命题中。哪个是真命题？ （ ）

A.若一个有向图是强连通图，则是有向欧拉图。

B.n（n ≥ 1）阶无向完全图Kn都是欧拉图。

C.n（n ≥ 1）阶有向完全图都是有向欧拉图。

D.二分图G=〈V1, V2, E〉必不是欧拉图。

答案: C

44.下列公式中，可满足式是（ ）。

A.A

B.B

C.C

D.D

答案: D

45.设p，q的真值为0，r的真值为1，下列各公式中，真值为0的是（ ）

A.A

B.B

C.C

D.D

答案: A

46.在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。

A.1

B.2

C.3

D.4

答案: A

47.

A.A

B.B

C.C

D.D

答案: A

48.若是一个群，则运算“*”一定满足（ ）。

A.交换律

B.消去律

C.幂等律

D.分配律

答案: B

49.设全集E＝{0, 1，2，3，…，9, 10}，A={2，4}，B={4, 5, 6, 7}，则（A∪B）∩～A=（ ）

A.{5，6，7}

B.{2，5，6，7} C.{2，4，5}

D.{6，7，8}

答案: A

50.图的构成要素是（）。

A.结点

B.边

C.结点与边

D.结点、变和面

答案: C

51.

下列公式中，（）是析取范式。

A.A

B.B

C.C

D.D

答案: D

52.全体小项合取式为（ ）。

A.可满足式

B.矛盾式

C.永真式

D.A、B、C都有可能

答案: B

53.

设Φ是一个空集，则下列之一哪一个不成立（ ）。

A.A

B.B

C.C

D.D

答案: A

54.域和整环的关系为（ ）

A.整环是域

B.域是整环

C.整环不是域

D.域不是整环

答案: B

55.下述论断不正确的是（ ）

A.A

B.B

C.C

D.D

答案: B

56.对以下定义的集合和运算，哪个不构成代数系统？（A.实数集R和数的加法运算“＋”

B.自然数集N和数的减法运算“-”

C.集合A的幂集P(A)和集合的并、交运算

D.n×n实矩阵的全体组成的集合和矩阵的加法运算“＋”

答案: B

57.下列无向图中，哪个是欧拉图或半欧拉图？（ ） ）

A.A

B.B

C.C

D.D

答案: B

58.短程线的长度叫做从u到v的( )

A.短程线

B.长程线

C.距离

D.中程线

答案: C

59.

—4群

B.循环群

C.置换群

D.半群，不是群

答案: B

60.设G是一个12阶循环群，则该群一定有（A.2

B.4

C.6

D.8

答案: C

）个不变子群。 61.如下哈斯图所对应的偏序集中，哪个不是格？（ ）

A.A

B.B

C.C

D.D

答案: C

62.每个无限循环群有（A.1

B.2

C.3

D.4

答案: B

）个生成元。

63.

。

A.A

B.B

C.C

D.D

答案: A 64.

A.A

B.B

C.C

D.D

答案: B

65.

下列图中，（）是平面图。

A.A

B.B

C.C

D.D

答案: C

66.

A.自由变元

B.约束变元

C.既是自由变元，又是约束变元

D.既不是自由变元，又不是约束变元

答案: C

67.整数集合Z关于数的加法“+”和乘法“·” 构成的代数系统是（ ） A.域

B.域和整环

C.整环

D.有零因子环

答案: C

68.设G是一个12阶循环群，则该群一定有（A.2

B.4

C.6

D.8

答案: C

）个不变子群。

69.设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},

则R具有( )。

A.自反性

B.传递性

C.对称性

D.其他答案都不对

答案: B

70.图的构成要素是（A.结点

B.边

C.结点与边

D.结点、变和面

答案: C

）。

71.量词的约束范围称为量词的（A.定义域

B.个体域

C.辖域

D.值域

答案: C

）。 72.设集合A={1, 2, 3, 4, 5}上的关系R={| x, yA且 x+y=6}，则R的性质是（ ）

A.自反的

B.对称的

C.对称的、传递的

D.反自反的、传递的

答案: B

73.下列公式中，（ ）是可满足式。

A.A

B.B

C.C

D.D

答案: D

74.

A.A

B.B

C.C

D.D

答案: C 75.设A, B, C是集合，则下述论断正确的是（ ）

A.A

B.B

C.C

D.D

答案: C

76.无向图G有6条边，各有一个3度和5度顶点，其余均为2度顶点，则G的阶数是（ ）。

A.2

B.3

C.4

D.5

答案: C

77.量词的约束范围称为量词的（A.定义域

B.个体域

C.辖域

D.值域

答案: C

）。

78.每个非平凡的无向树至少有（A.1

B.2

C.3

D.4

答案: B

）片树叶。 多选题

1.设集合A = {1,2,3,4}, A上的关系R={(1,1),(2,3),(2,4),(3,4)},

则R具有( )

注：本题只有一个选项为正确答案

A.自反性

B.传递性

C.对称性

D.其他答案都不对

答案: B

2.下列语句中,( )不是命题。

A.请把门关上

B.地球外的星球上也有人

C.x + 5 > 6

D.下午有会吗？

答案: A, C, D

3.设集合A={1,2,3},A上的关系R={(1,1),(2,2),(2,3),(3,2),(3,3)},则R具备( )

A.自反性

B.传递性

C.对称性

D.反对称性

答案: A, B, C

4.若供选择答案中的数值表示一个简单图中各个顶点的度,不能画出图的是 ( )

A.(1,2,2,3,4,5)

B.(1,2,3,4,5,5)

C.(1,1,1,2,3)

D.2,3,3,4,5,6) 答案: A, B, D

5.下列语句中，()不是命题。

A.请把门关上

B.地球外的星球上也有人

C.x+5>6

D.下午有会吗？

答案: A, C, D

6.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R具备( ).

A.自反性

B.传递性

C.对称性

D.反对称性

答案: A, B, C

7.

设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题不正确的是( )。

A.A

B.B

C.C

D.D

答案: A, B, D

8.若供选择答案中的数值表示一个简单图中各个顶点的度，不能画出图的是( ).

A.(1,2,2,3,4,5)

B.(1,2,3,4,5,5)

C.(1,1,1,2,3)

D.(2,3,3,4,5,6) 答案: A, B, D

9.下列语句中，( )不是命题。

A.请把门关上

B.地球外的星球上也有人

C.x + 5 > 6

D.下午有会吗？

答案: A, C, D

判断题

1.任何无向树都是二部图。( )

T.对

F.错

答案: T

2.任何树T都至少有两片叶子。 ( )

T.对

F.错

答案: F

3.哈密尔顿图是平面图。 ( )

T.对

F.错

答案: F

4.无向完全图Kn (n>=3) 都是欧拉图。 ( )

T.对

F.错

答案: F

5.仅由一个孤立点构成的图称为平凡图。( ) T.对

F.错

答案: T

6.P(A)是非空集合A的幂集,则P(A)上的包含关系R是P(A)上的偏序关系。 ( )

T.对

F.错

答案: T

7.A.对

B.错

答案: A

则R是传递的 ( )

8.设A、B、C为任意的三个集合,则笛卡尔积:A×(B×C)=A×(B×C)。

( )

A.对

B.错

答案: B

9.A,B是集合,A⊕B=φ,当且仅当A=B。( )

A.对

B.错

答案: A

10.A.对

B.错

答案: B

( ) 11.设P1,P2,…,Pn是不同的命题变元,关于P1,P2,…,Pn的极大项是简单析取式,但简单析取式不一定是极大项。( )

A.对

B.错

答案: A

12.是一个合式命题公式,其中P、Q、R是命题变元。(

A.对

B.错

答案: B

13.

A.错误

B.正确

答案: B

14.邻接矩阵的主对角线上的元素不为零。

A.错误

B.正确

答案: A

15.无向完全图Kn(n>=3)都是欧拉图。

A.错误

B.正确

答案: A

16.图中的初级回路均是简单回路。

A.错误

B.正确

)

答案: B

17.n阶无向完全图Kn（n≥1）都是哈密顿图。

A.错误

B.正确

答案: A

18.p∧┐(q→p)是永假式。

A.错误

B.正确

答案: B

19.设P1，P2，…，Pn是不同的命题变元，关于P1，P2，…，Pn的极大项是简单析取式，但简单析取式不一定是极大项。

A.错误

B.正确

答案: B

20.2n元格都是布尔格。

A.错误

B.正确

答案: A

21.度数为奇数的结点个数为0个或2个的连通的无向图G可一笔画出。

A.错误

B.正确

答案: B

22.在n(n≥2)个人中，不认识另外奇数个人的有偶数个人。

A.错误

B.正确

答案: B 23.函数f：R→R，f(x)=x+1是双射函数。

A.错误

B.正确

答案: B

24.设A、B、C为任意的三个集合，则笛卡尔积：A×(B×C)=A×(B×C)。

A.错误

B.正确

答案: A

25.否定消去规则通常视为反证法。

A.错误

B.正确

答案: B

26.设集合A={1，2，3}的任何关系R都不可能既是对称的，又是反对称的。

A.错误

B.正确

答案: A

27.在简单有向图中，每一个结点恰在一个强连通支中。

A.错误

B.正确

答案: B

28.n(n≥2)阶无向树都是二分图。

A.错误

B.正确

答案: B

29.设A,B是集合，若A-B=B-A,则A=B。 A.错误

B.正确

答案: B

30.初始函数不是原始递归函数。

A.错误

B.正确

答案: A

31.任何代数系统都存在子代数。（ ）

A.错误

B.正确

答案: B

32.有向图G=(V，E)，其中V={a，b，c，d}，E={，，}，则图G为强连通图。

A.错误

B.正确

答案: A

33.存在以序列5,4,4,3,3,2,2为度数列的无向图。

A.错误

B.正确

答案: A

34.

A.错误

B.正确

答案: B

35.命题“如果1+2=3，那么雪是黑的”是真命题。 ( ) A.错误

B.正确

答案: A

36.符号串集合{00，001，011}是二元前缀码。（ ）

A.错误

B.正确

答案: A

37.在n( n ≥2)个人中，不认识另外奇数个人的有偶数个人。（A.错误

B.正确

答案: B

38.整数集Z关于整除关系“|”是格。（ ）

A.错误

B.正确

答案: A

39.如果一个有向图是单向连通图，则必为弱连通图。（ ）

A.错误

B.正确

答案: B

40.如下关系图所对应的关系是对称和传递的。（ ）

A.错误

B.正确

） 答案: A

41.n(n ≥2) 阶无向树都是二分图。（ ）

A.错误

B.正确

答案: B

42.任何无向图G都至少有一棵生成树。（ ）

A.错误

B.正确

答案: A

43.图G中的初级回路（基本回路）都是简单的回路。A.错误

B.正确

答案: B

44.设A, B是集合，若A- B = B- A, 则A=B。（ ）A.错误

B.正确

答案: B

45.根树中最长初级通路的端点都是树叶。（ ）

A.错误

B.正确

答案: A

46.

设A={φ}，B = P（P（A）），则有{φ}B，且{φ}B

A.错误

B.正确

答案: B

)

)

(

( 47.n阶无向完全图Kn（n ≥ 1）都是哈密顿图。（ ）

A.错误

B.正确

答案: A

48.2元格都是布尔格。（ ）

A.错误

B.正确

答案: A

n49.陈述句“x+y>4”是个命题。 ( )

A.错误

B.正确

答案: A

50.命题公式 ┐P∨(Q→R)的成假赋值是110。( )

A.错误

B.正确

答案: B

51.如果一个有向图是强连通图，则必为单向连通图和弱连通图（ ）

A.错误

B.正确

答案: B

52.

设A≠，A上的恒等关系IA既是A上的等价关系也是A上的偏序关系。( )

A.错误

B.正确

答案: B

53. A.错误

B.正确

答案: B

54.图（意指离散数学中的图这一概念）中的基本（初级）回路均是简单回路。

A.错误

B.正确

答案: B

55.

A.错误

B.正确

答案: B

56.

A.错误

B.正确

答案: B

简答题

1.

证明题：

答案: 解: A×B={({a},{b}), ({a},a), (a, {b}), (a, a), (b, {b}), (b,

a)} AÅB=(A-B) ∪(B-A)={{a}, b, {b}} P(A)={Ø, {a}, a, b,

{{a}, a}, {{a},b}, {a,b}, A}.

2.

证明题

证明: G或者G有一个是连通图。

答案: 证明: G或者G有一个是连通图。证明：因为G不连通，则G可以分为若干连通子图: G1=（V1，E1），--- ，Gn=（Vn，En） 根据G的补图的构造过程知V1中每个顶点与其它顶点集V2，--- ，Vn中顶点有边相连。 这样，

在G的补图中，有 分别属于两个顶点子集Vi与Vj中的任意两个顶点之间有边直接相连， 属于同一个顶点子集Vi的任意两个顶点借助顶点子集Vj的任意一个顶点连通。所以，根据连通的定义知：G的补图一定连通 。

3.

证明题：

答案: 证明: 不妨记 A={a1, a2,

a3, …,an, …} B={b1, b2, b3, …,

bm} 作映射 φ:

A→A∪B φ(ai)=bi

(i=1,…,m) φ(ai)=ai-m

(i=m+1,m+2,…) 则可以说明φ为A→A∪B的双射， 故结论得证。

4.

求下图的最小生成树，并求出该最小生成树的权值之和。

答案: 略

5.证明题

证明: 多于一个顶点的树，至少有两片树叶。

答案: 证明: 多于一个顶点的树，至少有两片树叶。证明：设 T=(V,E)是一棵树，若T中最多只有一片树叶，则有 ∑d(v)

≥1+2(|V|-1)=2|E|+1, 这与结论 ∑ d(v) =2|E| 矛盾! 矛盾说明 T

不止一片树叶。

6.给定一个偏序的哈斯图如下，试求集合B={a,b,c,d}的八种特殊元素（如果有的话）。

答案: 略

7.

。

答案: 略

8.

答案: 略

9.

下图是二分图吗？为什么？ 答案: 略

10.若R是集合A上的对称关系和传递关系，则R一定是A上的自反关系吗？为什么？

答案: 略

11.

证明题：

答案: 解: 一般地, R1∘R2≠ R1∘R2. 反例: R1={(1,3),

(3,1)} 对称! R2={(3,2), (2,3)} 对称! R1∘R2 ={(1,2)} 不对称!

名词解释

1.试述函数中单射函数的定义。

答案: 略

2.

试述代数系统中子代数的定义。

答案: 代数系统，且若对运算都是封闭的，且和含有相同的代数常数，则称为的子代数系统，简称子代数。

其他题 1.推理题:

答案: 略

2.

。

答案: 略

3.

符号化下列语句，并用演绎法加以证明。

每个计算机专业的学生都要学习离散数学；有些大学生没有学习离散数学。所以有的大学生不是计算机专业的学生。

答案: 略

4.推理题:

画出5个顶点的自互补图。证明当n=4k 或4k+1时才有. 若一个图和它的补图同构，说它是自互补图。

答案: 略

5.推理题

答案: 略

6.推理题:

答案: 略

7.推理题:

答案: 略

8.推理题：

G是一个群,H,K是G正规子群。

证明: H∩K是G正规子群。

答案: 略

9.

。

答案: 略