离散数学(四)_08

--

-- 2016年秋国家开放大学《离散数学》形考4试题及答案(答案全部正确)

０4任务_0001

试卷总分:1００ 测试时间:0

单项选择题

一、单项选择题(共 １0 道试题，共 10０ 分。)

1． 无向树T有8个结点，则T的边数为（ )．

A. ６ Ｂ. 7 C. 8 Ｄ. 9

2． 图G如图三所示，以下说法正确的是 （ ) .

Ａ． {(a， ｄ)}是割边 Ｂ． {(a, d)}是边割集Ｃ. ｛(a, d) ,(b, d）｝是边割集D. {(ｂ,

d）}是边割集

3. 设有向图(a）、(b)、(ｃ)与（ｄ）如图所示,则下列结论成立的是（ )．

A. （ａ)只是弱连通的B. （ｂ)只是弱连通的C. （ｃ）只是弱连通的Ｄ． (d）只是弱连通的

４． 如图一所示，以下说法正确的是 （ ) .

A. {(ａ, e)｝是割边B. ｛(a, e)}是边割集Ｃ. ｛(a, e） ,(b， ｃ)}是边割集D. {(d， e)}是边割集

5. 设G是有ｎ个结点,ｍ条边的连通图，必须删去G的( ）条边,才能确定G的一棵生成树．

Ａ. m－ｎ+1Ｂ． m-nC. m＋n+1D． n-m+1

６. 设G是连通平面图,有v个结点,ｅ条边，r个面，则r= ( ).

A. e－v+2Ｂ. ｖ+ｅ－2C. ｅ-v－2D． e+v＋2

7. 设无向图G的邻接矩阵为，则G的边数为（ ）.

A． ６B. 5Ｃ． ４D. 3

8． 如图所示，以下说法正确的是 ( )． --

--

A.

ｅ是割点B. {a， ｅ}是点割集C． ｛ｂ, e}是点割集D． ｛d}是点割集

9. 无向简单图Ｇ是棵树，当且仅当（ ).

A. Ｇ连通且边数比结点数少１ B. G连通且结点数比边数少1

C. G的边数比结点数少１ D. Ｇ中没有回路．

1 离散数学作业4

图的矩阵表示及计算作业

（单个文件上传形式）

作业内容：

1．已知图G如下图所示．

（1）试给出图G的集合表示；

（2）求图G的邻接矩阵A；

（3）利用矩阵A及其幂，求出从结点v1到v5长度为2和3的路的数目并写出这些路．

解 (1) G=，其中，V={v1，v2，v3，v4，v5，v6}，E={(v1,v2)，(v1,v6)，(v2,v3)，(v2,v5)，(v2,v6)，(v3,v4)，(v3,v5)，(v4,v5)，(v5,v6)}．

(2) 图G的邻接矩阵为

010001101011010110001010011101110010A

(3) 2010001010001211021101011101011141222010110010110113122001010001010021211011101011101222141110010110010122113A

3211021010001263335141222101011668397113122010110374574021211001010335263222141011101397668122113110010574384A 2 由2A的第1行第5列的元素为2可知，从结点v1到v5长度为2有2条，分别是v1(v1, v2)v2(v2, v5)v5，v1(v1, v6)v6(v6, v5)v5；

由3A的第1行第5列的元素为3可知，从结点v1到v5长度为3的路有3条，分别是v1(v1, v2)v2(v2, v3)v3(v3, v5)v5，v1(v1, v2)v2(v2, v6)v6(v6, v5)v5，v1(v1, v6)v6(v6,

信计系 专业 级 班 姓名: 学号:

--------------------------------------装----------------------------------------订---------------------------------------线--------------------------------------

第 - 1 - 页 共 -2- 页

2005-2006学年秋季学期《离散数学》课程期末考试试题(B)

一． 填空题（每小题3分，共24分）

1．设集合,aS，则 S.

2．设3,2,1A，3,2,2,2,3,1R为集合A上的二元关系，则1R 。

3．已知命题公式QPG，则所有使G取真值下的指派是

4．设集合24,12,6,3,2X，设R是X上的整除关系，则X的最大元素是 ， X的极小元素是 ，上界是 。

5． 一个X上的二元关系R，如果R 满足 则称R是偏序关系。

6. 群必含有 ，不可能含有

7．设图EVG,是一无向完全图nVmE,，则m

8．有向图中所有结点的引入度数总和)(ivd与引出度数总和)(ivd的关系为： 。

二．判断命题（每小题2分，共16分）

1. 设集合cbaA,,，则A （ ）

离散数学试卷（四）

24 一、 填空 10% （每小题 2分）

1、 若P，Q，为二命题，QP真值为0 当且仅当 。

2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，yxyxL:),(则命题的逻辑谓词公式为 。

3、 谓词合式公式)()(xxQxxP的前束范式为 。

4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。

5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则

被称为存在量词消去规则，记为ES。

二、 选择 25% （每小题 2.5分）

1、 下列语句是命题的有（ ）。

A、 明年中秋节的晚上是晴天； B、0yx；

C、0xy当且仅当x和y都大于0； D、我正在说谎。

2、 下列各命题中真值为真的命题有（ ）。

A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；

C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数；

3、 下列符号串是合式公式的有（ ）

A、QP ；B、QPP ；C、)()(QPQP；D、)(QP。

4、 下列等价式成立的有（ ）。

A、PQQP ；B、RRPP)( ；

C、 QQPP)(； D、RQPRQP)()(。

5、 若nAAA21,和B为wff，且BAAAn21则（ ）。