计算机四级-离散数学
(总分67, 做题时间90分钟)
一、选择题
(一)中文题
1. 
在谓词逻辑中，令F(x)表示x是人，G(x)表示x呼吸，命题“没有不呼吸的人”的符号表示中 (    )是正确的。    
A 仅Ⅲ
B Ⅰ和Ⅱ
C Ⅱ和Ⅲ
D Ⅰ、Ⅱ和Ⅲ
2. 
4阶非同构的无向简单图共有(   )个。
A 9
B 13
C 11
D 27
3. 
If graph with d={1,1,1,1,2,2,4} as its degree sequence. What is the number of nonisomorphic spanning trees? (    )
A 2
B 3
C 4
D 5
4. 
设f:Z→Z，其中Z为整数集，且          则下列命题为真的是(    )。
A f是单射的，但不是满射的
B f是满射的，但不是单射的
C f是双射的
D f既不是单射的，也不是满射的
5. 
下面推理中(    )是正确的。    
A Ⅰ与Ⅱ
B Ⅲ与Ⅳ
C Ⅰ、Ⅱ、Ⅲ
D 只有Ⅰ
6. 
已知5阶有向图G的度数列和入度列分别为(3，3，2，3，3)和(2，1，1，1，2)，则有向图G的出度列为(    )。
A (1，2，1，2，1)
B (2，2，2，2，0)
C (2，2，1，2，1)
D (1，2，0，2，1)
7. 
设有命题：对于组成元素为集合的集合C，存在函数为f:C→∪C，使得对每一个S∈C，有f(S)∈S。该命题的否命题是(    )。
A 对于集合C，对每个函数f:C→∪C，对每一个S∈C，都有f(S
B 对于集合C，存在函数f:C→∪C，使对每一个S∈C，有f(S
C 对于集合C，对每一个函数f:C→∪C，存在S∈C，使得f(S
D 对于集合C，不存在函数f:C→∪C，使对某些S∈C，没有f(S
8. 
设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为(    )。
A 10
B 9
C 8
D 7
9. 
if p、q and r are Boolean variables, which of the following formulas is (are) autological? (  )      Ⅰ. (┐P→q)→(p∨q)      Ⅱ. (p→r)∧(┐p→q) ∧┐r
A none
B Ⅰ only
C Ⅱ only
D Ⅰ and Ⅱ
10. 
设R+为正实数集合，＜R+，*＞在下面四种运算下不构成代数系统的是(    )。
A *代表普通加法
B *代表普通乘法
C *代表普通除法
D *代表普通减法
11. 
已知图G有11条边，由1个4度顶点，4个3度顶点，其余顶点的度数均小于等于2，则G中至少有(    )个顶点。
A 7
B 8
C 9
D 10
12. 
设V＝＜S，·＞，其中·为矩阵乘法，    则下面命题成真的为(    )。Ⅰ．V是一个半群Ⅱ．＜T，·＞是V的子独异点Ⅲ．＜T，·＞是V的子半群
A 只有Ⅰ
B 只有Ⅱ
C Ⅰ和Ⅱ
D Ⅰ和Ⅲ
13. 
在谓词逻辑中，令F(x)表示x是瘦人，G(y)表示y是胖人，L(x，y)表示x比y吃的少，命题“并不是所有的瘦人比所有的胖人吃的少”的符号表示中，(    )是正确的。    
A 仅Ⅲ
B Ⅰ和Ⅱ
C Ⅰ和Ⅲ
D 都不对
14. 
P(n) is the predicate if 2 can'nt divides n 4 can'nt divides n then 8 divides n. What is the truth value of P(12)? (    )
A 10
B 0
C 1
D none of the above
15. 
Suppose V1=＜R,+＞,V2=＜R, ·＞,where R is the set of real numbers, +and · are respectively addition and multiplication. Let f: R→R and {(x) = 10x, which of the following propositions is true? (    )
A 
f is an injective homomorphism from V1 to V2
B 
f is a surjective homomorphism from V1 to V2
C 
f is an isomorphism from V1 to V2
D none of the above
16. 
When the adjacency matrix method is used to store a graph, which of the statements is (are) true? (    )
A Ⅰ and Ⅱ
B Ⅰ only
C Ⅱ only
D neither
17. 
18. 
设R是集合A={1，2，3}上的二元关系，且R={＜1，1＞，＜3，3＞}，下列命题中(    )为真。    Ⅰ．R的自反闭包为{＜1，1＞，＜2，2＞，＜3，3＞}    Ⅱ．R的对称闭包为{＜1，1＞，＜3，3＞}    Ⅲ．R的传递闭包为{＜l，1＞，＜3，3＞}
A 只有Ⅰ
B 只有Ⅱ
C Ⅰ和Ⅱ
D Ⅰ、Ⅱ和Ⅲ
19. 
设F(x):x为地球上的东西，G(x):x是静止不动的，命题“地球上所有的东西都不是静止不动的”的符号化形式中，(    )正确。    
A 只有Ⅰ正确
B 只有Ⅱ正确
C Ⅰ和Ⅱ都正确
D Ⅱ和Ⅲ都正确
20. 
对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为(    )。
A 42
B 24
C 216
D 取决于元素是否为数值
21. 
以2，2，3，3，1，1，1，1为顶点度数列的所有非同构的无向树的个数为(    )。
A 4
B 5
C 6
D 7
22. 
集合A1，A2，…，An是集合C的n个子集，n≥2，已知C中的任意一元素都恰好在两个不同的子集中出现一次，即任意两个不同的子集Ai，Aj有|Ai∩Aj|=1，则|C|=(    )。
A n
B n-1
C 2n
D n+1
23. 
公式的前束范式是(    )。
   
A  B  C  D  
24. 
设G为n(n≥2)阶无向连通图，下面(    )命题必为真。    Ⅰ．若G有割点，则G一定有桥    Ⅱ，若G有桥，则G一定有割点
A 仅Ⅰ
B 仅Ⅱ
C 全不一定为真
D 全一定为真
25. 
Which property does R possess? (    )     let A={1,2,3,4} and let R ={＜1,2＞,＜2,2＞,＜3,4＞,＜4,1＞,＜4,2＞}
A symmetry
B antisymmetry
C asymmetry
D reflexivity
26. 
下面集合之间的包含和属于关系中，(    )为真。  
A Ⅰ和Ⅱ
B Ⅰ和Ⅲ
C Ⅰ和Ⅳ
D Ⅱ、Ⅲ和Ⅳ
27. 
设R是集合A={a，b，c，d)上的二元关系，R={＜a，d＞，＜d，a＞，＜a，c＞，＜c，a＞， ＜b，d＞，＜d，b＞}，下面(    )命题为真，    Ⅰ．R·R是对称的    Ⅱ．R·R是自反的    Ⅲ．R·R不是传递的
A 仅Ⅰ
B 仅Ⅱ
C Ⅰ和Ⅱ
D 全真
28. 
If p and q are statements, which of the following formulas is tautological? (    )
A ┐ (p→∧q
B (p∨→p∧q
C (q∧(p→)→p
D ((p→∧→q
29. 
设R，S是非空集合A上的等价关系，则下面是A上的等价关系的是(    )。    A) (A×
A -R
B S∪R
C S-R
D S∩R
30. 
How many subsets does A have? (    )     let A={1,2,3,4,5,6,7)
A 128
B 64
C 32
D 16
31. 
设R是集合A(A≠＞)上的等价关系，x∈A，[x]R为x关于R的等价关系，则下面命题为真的是(    )。      
A 只有Ⅰ
B Ⅰ和Ⅲ
C 只有Ⅱ
D Ⅱ和Ⅲ
32. 
设A为n个元素的集合，则A上有(    )个二元关系。
A 
2n
B 
2n×n
C 2n
D n
33. 
设无向图G=＜V，E＞，其中V={V1，V2，V3，V4，V5}，E={(V1，V4)，(V4，V4)，(V1，V2)， (V2，V3)，(V3，V4)}，下列命题为真的是(    )。
A G是哈密尔顿图
B G是欧拉图
C G是二部图
D G是平面图
34. 
When the adjacency list method is used to store a graph, which of the statements is (are) true? (    )
A None
B Ⅰ only
C Ⅱ only
D Ⅰ and Ⅱ
35. 
设T为n(n≥3)阶无向树，T有几条割边?(    )
A n条
B n-2条
C n-1条
D 没有
36. 
What is the definition of a Path? (    )
A a sequence of vertices and the edges formed by each successive pair of vertices
B a walk with distinct edges
C a walk with distinct vertices
D none of the above
37. 
Which of the following statements is (are) true? (    )      Ⅰ. The number of cyclic subgroups of the additive group of integers is infinite      Ⅱ. The number of cyclic subgroups of the additive group of real numbers is infinite
A Ⅰ and Ⅱ
B Ⅰ only
C Ⅱ only
D neither     Questions 43、44 refer to the space requirements of different methods of storing graph The Choices for these questions are combinations of the following statement      Ⅰ. The space required depends on the number of vertices      Ⅱ. The space required depends on the number of edges
38. 
具有7个结点的所有非同构的树有(    )个。
A 7
B 11
C 12
D 14
39. 
设N为自然数集合，Z为整数集合，Q为有理数集合，R为实数集合，为全体奇数集合，[0，1)和(0，1)为两个区间，下列关系中为假的是(    )。
A (0，1)≈Q
B Z≤R
C Q≈N
D [0，1]≈R
40. 
Which set is a proper subset of E? (    )      E= {0,1,2,3}
A { x|x is a real number and x—3=0}
B 
{ x|x is a real number and x2—9}
C 
{ x|x is a real number and x2+5x+6=0}
D {0,1,2,3)
41. 
下面的图形中不是格的是(    )。
   
A  B  C  D  
42. 
下列命题公式中(    )为重言式?    Ⅰ．(p→(p∨q))∨r    Ⅱ．(p→(q∨r))→((p→q)∧(p→r))    Ⅲ．(p→q)∧(p→r)→(p→r)    Ⅳ．┐(p→q)∧q∧r
A Ⅲ
B Ⅰ和Ⅲ
C Ⅰ和Ⅱ
D Ⅰ、Ⅱ、Ⅲ和Ⅳ
43. 
下面带权为2、3、5、7、8、11的最优树的为(    )。
         
A  B  C  D  
44. 
设f：B→C，g：A→B。若f·g是满射的，则下面命题为真的是(    )。
A f是满射的
B f是单射的
C f是双射的
D g是满射的
45. 
设p、q为两个命题，对于“”的逻辑含义，下面的(    )叙述是正确的。    Ⅰ．如果p，则q    Ⅱ．p当且仅当q    Ⅲ．p与q互为充要条件
A Ⅰ和Ⅱ
B 只有Ⅱ
C Ⅲ
D Ⅱ和Ⅲ
46. 
设无向树T由3个3度顶点，2个2度顶点，其余顶点都是树叶，则T有(    )片树叶。
A 3
B 4
C 5
D 6
47. 
6阶11条边的连通的简单的非同构的非平面图的个数为(    )。
A 3
B 4
C 5
D 6
二、论述题
48. 
所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数也不是无理数．
   (1)将上述命题符号化。
   (2)用演绎法证明其结论是否正确。
49. 
设R是集合上的关系，证明或否定下述论断：
    (1)若R是自反的，则s(R)、t(R)是自反的。
   (2)若R是对称的，则r(R)、t(R)是对称的。
   (3)若R是传递的，则r(R)、s(R)是传递的。
50. 
n个城市由k条公路网连接(一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市)，证明：如果有
   k＞l/2(n-1)(n-2)
则人们总能通过连接城市的公路在任何两个城市之间旅行。
51. 
赵、钱、孙、李、周五位教师，要承担语文、数学，物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周三人都只熟悉数学和物理两门课程。问能否安排他们五人每人只上一门自己所熟悉的课程，使得每门课都有人教，说明理由。
答题卡