PDF《离散数学 2017 年10 月真题及答案解析》

1 离散数学

2017 年10 月真题及答案解析 单项选择题:本大题共

10 小题,每小题

3 分,共30 分.

1. 令P:他怕困难,q:他战胜困难,命题"他战胜困难是因为他不怕困难"的符号化形式为 (). A. B. C. D. 答案:A 解析:"他不怕困难"是"他怕困难"的否定式,命题"他战胜困难是因为他不怕困难"化成基本结 构为"因为他不怕困难,所以他战胜困难",典型的蕴涵式.因此,符号化形式为 ,选A. 2. 令F(x):x 为苹果,H(x,y):x 与y完全相同,L(x,y):x=y,则命题"没有完全相同的苹果"的符 号化形式为(). A. B. C. D. 答案:B 解析:本题命题"没有完全相同的苹果"中,没有指明个体域,因而采用全总个体域.其中"相 同的苹果"需要任意两个苹果进行比较,即是"两个苹果"同时"非同一个苹果"且"完全相同",符 号化为" ";

"没有"为否定词;

则"没有完全相同的苹 果"符号化为" ",因此选 B.

2 3. 一棵树有

2 个4度结点,3 个3度结点,其余为树叶,则该树中树叶个数是(). A.

7 B.

8 C.

9 D.

10 答案:C 解析:根据无向树的定义,2 个4度结点可以组成"艹"树状,3 个3度节点可以通过"艹"6 个结 点中选择任意

3 个结点上分别悬挂

2 片树叶即可.这样树叶总个数为 9.故选 C. 4. 设集合 A={a,b,c,d},现有 A 上的二元关系 R={,,

,,

},则A是(). A. 自反的 B. 对称的 C. 反对称的 D. 传递的 答案:B 解析:二元关系 R 中典型满足 即满足对称的关 系的定义.故选 B. 5. 下图中为欧拉图的是(). A. A. B. B. C. C.

3 D. D. 答案:C 解析:根据欧拉图的定义,具有欧拉回路的图为欧拉图,其充分必要条件是连通的且不含有奇 度顶点.而ABD 三个选项中均有奇度顶点,故选 C. 6. 下列谓词公式中,不是前束范式的为(). A. B. C. D. 答案:D 解析:根据一阶逻辑前束范式的定义,所有约束量词只能在公式最前面,后面公式不能出现量 词,排除选项 ABC,故选 D. 7. 表示集合之间关系的图是(). A. 文氏图 B. 哈斯图 C. 欧拉图 D. 树 答案:A 解析:根据集合代数理论,表示集合之间关系与运算的图为文氏图,故选 A. 8. 无向完全图 的边的条数为(). A.

10 B.

15 C.

20 4 D.

30 答案:B 解析:根据无向完全图的定义,可以

6 结点中每一个都与其余

5 个相邻接,其边数计算公式 为n(n-1)/2,带入 n=6,则为 15,故选 B. 9. 设T是n阶树(n≥2),则T不具有的性质是(). A. 连通图 B. 哈密顿图 C. 有n-1 条边 D. 至少有两片树叶 答案:B 解析:根据树的定义及等价命题,n 阶树一定是连通的,且有 n-1 条边,至少有两片树叶,但 不会有回路,因此不是哈密顿图(具有哈密顿回路的图),故选 B. 10. 设R、S 均为集合 A 上的二元关系,下面命题正确的是(). A. 若R与S是自反的,则 也是自反的 B. 若R与S是反自反的,则 也是反自反的 C. 若R与S是对称的,则 也是对称的 D. 若R与S是传递的,则 也是传递的 答案:A 解析:根据二元关系的运算规律,两个二元关系的右复合只有自反性保持不变,故选 A. 11. 以下关于图的矩阵的描述,正确的是(). A. 邻接矩阵即关系矩阵 B. 可达矩阵是针对无向图的 C. 无向图有邻接矩阵 D. 可达矩阵是针对有向图的 答案:C

5 解析:根据图的矩阵的描述理论,邻接矩阵与关系矩阵是不同的,无向图与有向图都有关系矩 阵,邻接矩阵仅应用于有向图,故选 C. 12. 一个

6 阶连通图的边数至少为(). A.