离散数学期末考试答案题库2024秋

山东大学

1. R是实数集，则＜R-{0}, ×＞不能构成群，原因是单位元不存在。( )

A:错 B:对
答案:错

2. 图G中各顶点之间的连通关系是一个等价关系。( )

A:错 B:对
答案:B:对

3. 若在某一指派下，公式A、B的真值相同，则称A、B等价，记为A=B。（ ）

A:错 B:对
答案:错

4. 利用析取范式，可以判断一个公式是否永真或永假，且对于任意公式都存在唯一一个与之等价的主析取范式。（ ）

A:错 B:对
答案:对

5. 〈L, *, ⊕,’,0,1〉 为布尔代数，其中’称为补运算，即对∀a∈L, ∃!a’∈L,有a⊕a’= 0,a*a’=1。( )

A:对 B:错
答案:A: 对

6. data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAA8AAAANCAYAAAB2HjRBAAAAe0lEQVQ4EcWR0Q3AIAhEby4GYh6mYRmGuUZNLR8YTftREyMxvuM8wA8LZNAEBNJWP5Kc8PN+iInFVqCASboSj9pSpITD5C3sVIAHjTk758BOwPaXCS+BCHoEw72fOYA93MIT66CpMA/hCL7H1oLMDpFtlLUrf4JLO+PyAoDktjbcgsTjAAAAAElFTkSuQmCC

A:错 B:对
答案:对

7. 公式的Skolem范式与原公式是等价的。（ ）

A:错 B:对
答案:错

8. data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAALCAYAAACprHcmAAAAgUlEQVQoFZVQ2w0AIQhjrg7UeZjGZRymFxRfd7kPTYyGltJiujh2wZWpumAmlndblZMiXTUhk77FhhXKXiLdRgIBnpfaB6bnIgLCGJnW4MNA9zEDVofMoMALKeBUDfokt6BNPYgQv4k3skJxeO4TcgnzWcpRGkGx1jWZh429+vN/ADtflr+Z/BYdAAAAAElFTkSuQmCC

A:对 B:错
答案:对

9. 对六个顶点的完全图的边用红蓝二色着色，结果中必有一个同色三角形。（ ）

A:错 B:对
答案:B:对

10. 两个不同的命题公式是等价的则它们的主合取范式是相同。( )

A:错 B:对
内容已经隐藏，点击付费后查看
11. 下列论述正确的有( )

A:设 ＜H,*＞ 是 ＜G,*＞ 的一个子群，群中两个元素的左陪集相同，则两个元素一定具有模H左同余关系。
B:素数阶循环群的每个非单位元都是生成元。（即素数阶的群必为循环群 ）
C:设 是 的一个子群，则对a∈G，都有 aH = H 。
D:9阶群必有3阶子群

内容已经隐藏，点击付费后查看
12. 设有K种明信片，每种张数不限．现在要分别寄给n个朋友，k≥n，以下说法正确的有( )

A:若给每个朋友寄1张明信片，有kn种寄法
B:若给每个朋友寄1张明信片，但每个人得到的明信片都不相同，有P(k,n)种寄法
C:若给每个朋友寄2张不同的明信片（不同的人可以得到相同的明信片），有(C(k,2))n种寄法
D:若给每个朋友寄2张不同的明信片（不同的人可以得到相同的明信片，但组合不可相同），有C(k,2)/P(k,n)种寄法

内容已经隐藏，点击付费后查看
13. 在下列给出的图中，选出所有和图1图2均不同构的简单图( )

A:
B:
C:
D:
E:

内容已经隐藏，点击付费后查看
14. 下列说法正确的有( )

A:完全格一定是有界格
B:有限格一定是完全格
C:有界格一定是有补格
D:有补格一定是有界格

内容已经隐藏，点击付费后查看
15. 全体n阶方阵按矩阵的加法和乘法可以构成的环的类型为( )。

A:有单位元
B:无单位元
C:可交换
D:不可交换

内容已经隐藏，点击付费后查看
16. 关于最短路算法(迪杰斯屈拉算法)，下列论述正确的有( )。

A:算法可以解决有向图中指定两顶点间的最短通路问题。
B:算法结束时的顶点标号就是到达该顶点的最短通路长度。
C:算法的时间复杂度是O（n3）。
D:算法的每次运行可以求出任意顶点对间的最短通路长度。

内容已经隐藏，点击付费后查看
17. 以下是合式公式∀x(P(x,y)→∃yQ(x,y,z))∧R(f(x,z))的原子公式的有( )

A:f(x,z)
B:R(f(x,z))
C:P(x,y)
D:x

内容已经隐藏，点击付费后查看
18. ＜Z4,+4,×4＞是一个环，可以构成的环的类型为( )

A:不可交换
B:无单位元
C:可交换
D:有单位元

内容已经隐藏，点击付费后查看
19. 下列关于Hamilton有向图的说法正确的有( )

A:半Hamilton有向图一定含有至少一个Hamilton有向圈
B:竞赛图必是Hamilton有向图
C:强连通的竞赛图必是Hamilton有向图
D:Hamilton有向图必定是强连通的

内容已经隐藏，点击付费后查看
20. 关于最大项的性质，下列论述正确的有( )

A:n个命题变元可构成2ⁿ个最大项
B:全体最大项的析取式永为F
C:全体最大项的合取式永为F
D:任意两个不同最大项的析取式永为T

内容已经隐藏，点击付费后查看
21. 关于哈密顿图的性质下列论述正确的有( )。

A:设G是有n个顶点的连通图, 则G的哈密顿回路一定是长度为n的回路。
B:哈密顿图中的哈密顿回路并不唯一。
C:每个哈密顿图都一定是连通的且每个顶点的度均等于2。
D:设v是G中度为2的顶点, 若G中有哈密顿回路, 则该回路必经过以v为端点的那两条边。

内容已经隐藏，点击付费后查看
22. 实系数多项式的全体按普通加法和普通乘法可以构成的环的类型为( )

A:可交换
B:有单位元
C:不可交换
D:无单位元

内容已经隐藏，点击付费后查看
23. 假设图G是n个顶点的简单无向图，下列说法正确的有( )

A:若G的边数，则G一定是Hamilton图
B:
C:若G的边数，则G一定是Hamilton图
D:

内容已经隐藏，点击付费后查看
24. 下列关于欧拉回路和哈密顿回路的说法正确的有( )

A:欧拉回路遍历所有的边
B:哈密顿回路遍历所有的边
C:哈密顿回路是路
D:欧拉回路是路

内容已经隐藏，点击付费后查看
25. 以下能构成连通平面图的是(  )。

A: n=7,m=5,r=3 B:n=4,m=6,r=5 C: n=1,m=1,r=2 D:n=4,m=5,r=3
内容已经隐藏，点击付费后查看
26. 设A为任意集合，下式为真的是(    )

A:∅∈P(A)




B:{∅,{∅}}Í P(P(A)) C:∅ÍP(A)




D:{∅}∈P(P(A))




内容已经隐藏，点击付费后查看
27. 以下各式成立的是( )

A:∀x(A(x)∨B(x)),∀x(B(x)→¬C(x)),∃xC(x)⇒∀xA(x)
B:∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))
C:∀x(¬A(x)→B(x)),∀x¬B(x)⇒∃xA(x)
D:∀x(A(x)→B(x)),∀x(C(x)→¬B(x))⇒∀x(C(x)→¬A(x))

内容已经隐藏，点击付费后查看
28. 对任意集合A, B, C, 下列命题为真有( )。

A:{∅}{∅,{∅}}；
B:{∅}∈{∅,{∅}}；
C:{∅} {{∅}}；
D:∅∅；
E:∅{∅};
F:∅∈∅ ；

内容已经隐藏，点击付费后查看
29. 下列说法错误的有( )

A:任何有向树中有且仅有一个入度为0的结点
B:Kruskal算法和Prim算法都需要对边进行排序准备
C:连通图G的每棵生成树都至少包含一条不同的割边
D:高度为3的正则二叉树唯一

内容已经隐藏，点击付费后查看
30. 设A,B,C为两个集合，下列命题为真有( )。

A:
B:
C:
D:

内容已经隐藏，点击付费后查看
31. 以下说法正确的是( )

A:任意有向图中，所有顶点的入度之和与所有顶点出度之和不相等
B:图同构是一种等价关系
C:非负整数序列 (3, 3, 3, 1) 不是可图化的
D:在一个图中，既有有向边的又有无向边，这样的图叫作正则图

内容已经隐藏，点击付费后查看
32. ​四个顶点的非同构简单图有( )个

A:8
B:13
C:10
D:11

内容已经隐藏，点击付费后查看
33. 公式的主合取范式是 ( )。

A:
B:
C:
D:

内容已经隐藏，点击付费后查看
34. 若一棵完全二元（叉）树有2n-1个顶点，则它含有（ ）片树叶。

A:n
B:n-1
C:2
D:2n

内容已经隐藏，点击付费后查看
35. 谓词公式的否定式为（ ）

A:
B:
C:
D:

内容已经隐藏，点击付费后查看
36. 具有6个顶点的无向简单图，当有( )条边时能确保是一个连通图。

A:5
B:3
C:2
D:4

内容已经隐藏，点击付费后查看
37. 在不同构下有（ ）棵含7个顶点的树。

A:13
B:6
C:11
D:8
E:5

内容已经隐藏，点击付费后查看
38. 下列论述正确的是( )

A:任何无限群都与整数加群＜I,+＞同构
B:整数加群＜I,+＞只有一个生成元1
C:整数加群＜I,+＞除单位元0外，其它元素的周期都是无限的
D:整数加群＜I,+＞只有两个生成元1和-1

内容已经隐藏，点击付费后查看
39. data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAwAAAAPCAYAAADQ4S5JAAAAaklEQVQoFd2S0Q2AMAhEby4GYh6mYRmGOYPGFo3E1E+b9K+P414KLh4svud3wBWE+mvgSPgnEDQBxeIioi8dRlGlQlndtUCYMC2nvWq7AXxO3pNmxjPgSgDlCs8qA6jN7mvkekd5X/tLCW4vKYDLcBh59wAAAABJRU5ErkJggg==

A:dom A;
B:ran A;
C:ran= A
D:dom A

内容已经隐藏，点击付费后查看
40. https://image.zhihuishu.com/zhs/doctrans/docx2html/202108/9350f2d81c924fa9b7b4d00eb2a8f185.png

A:GH
B:eH
C:1H
D:H

内容已经隐藏，点击付费后查看
41. 在有6个结点、12条边构成的连通平面图G中，每个面由几条边围成.( )

A:2
B:4
C:5
D:3

内容已经隐藏，点击付费后查看
42. 下列命题公式中为永真式的有( )

A:((P∨Q)→R)→P
B:(P∨R)∨(Q∧R)∨P
C:(P∨R)∨(Q∧R)∨P
D:(P∨R)∨(Q∧R)∨P

内容已经隐藏，点击付费后查看
43. 要使右图成为平面图，至少要去掉几条边（ ）

A:3
B:0
C:1
D:2

内容已经隐藏，点击付费后查看
44. 公式的主析取范式是( )。

A:
B:
C:
D:

内容已经隐藏，点击付费后查看
45. 下列有关分配格的说法正确的是( )

A:分配格中各元素的补元可能存在且不唯一。
B:集合的幂集与其上所定义的并和交运算所组成的格 <,∪,∩>是一个分配格
C:分配格中各元素都存在补元
D:分配格一定存在一个如右图所示的子格

内容已经隐藏，点击付费后查看
46. n对夫妻围圆桌就座，要求每对夫妻不相邻，问有多少种入座方式？( )

A:
B:
C:
D:

内容已经隐藏，点击付费后查看
47. 下列关于域的说法错误的是( )

A:对于任意的p，是域，其中分别是模p加法和乘法
B:域中一定没有零因子
C:阶不小于2有限整环必定是域
D:域中的每一个非零元都有逆元

内容已经隐藏，点击付费后查看
48. 已知一棵无向树T有3个3度结点，1个2度结点，其余的都是1度结点,则T的1度结点个数为( ).

A:5
B:7
C:6
D:4

内容已经隐藏，点击付费后查看
49. 一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点数量为( )

A:8
B:9
C:5
D:7

内容已经隐藏，点击付费后查看
50. 个体域为整数集合时，下列公式( )不是命题。

A:
B:
C:
D:

内容已经隐藏，点击付费后查看