下载文档原格式
离散数学形考二标记题目信息文本单项选择题题目1正确获得5.00分中的5.00分标记题目题干已知无向图G的邻接矩阵为，则G有（）．选择一项：A. 5点，8边B. 6点，7边C. 5点，7边D. 6点，8边反馈你的回答正确正确答案是：5点，7边题目2正确获得5.00分中的5.00分标记题目题干设图G＝<V, E>，v V，则下列结论成立的是( ) ．选择一项：A. deg(v)=| E |B.C. deg(v)=2| E |D.反馈你的回答正确正确答案是：题目3正确获得5.00分中的5.00分标记题目题干图G如图三所示，以下说法正确的是( )．选择一项：A. a是割点B. {b, d}是点割集C. {b,c}是点割集D. {c}是点割集反馈你的回答正确正确答案是：{b,c}是点割集题目4正确获得5.00分中的5.00分标记题目题干如图一所示，以下说法正确的是( ) ．选择一项：A. {(a, e)}是边割集B. {(a, e) ,(b, c)}是边割集C. {(d, e)}是边割集D. {(a, e)}是割边反馈你的回答正确正确答案是：{(d, e)}是边割集题目5不正确获得5.00分中的0.00分标记题目题干无向图G存在欧拉回路，当且仅当（）．选择一项：A. G连通且所有结点的度数全为偶数B. G连通且至多有两个奇数度结点C. G中所有结点的度数全为偶数D. G中至多有两个奇数度结点反馈你的回答不正确正确答案是：G连通且所有结点的度数全为偶数题目6正确获得5.00分中的5.00分标记题目题干无向完全图K4是（）．选择一项：A. 树B. 汉密尔顿图C. 欧拉图D. 非平面图反馈你的回答正确正确答案是：汉密尔顿图题目7正确获得5.00分中的5.00分标记题目题干设无向图G的邻接矩阵为，则G的边数为( )．选择一项：A. 1B. 6C. 7D. 14反馈你的回答正确正确答案是：7题目8正确获得5.00分中的5.00分标记题目题干若G是一个汉密尔顿图，则G一定是( )．选择一项：A. 平面图B. 对偶图C. 欧拉图D. 连通图反馈你的回答正确正确答案是：连通图题目9正确获得5.00分中的5.00分标记题目题干设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．图五选择一项：A. （b）是强连通的B. （d）是强连通的C. （c）是强连通的D. （a）是强连通的反馈你的回答正确正确答案是：（a）是强连通的题目10正确获得5.00分中的5.00分标记题目题干设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．选择一项：A. e－v＋2B. e＋v＋2C. e－v－2D. v＋e－2反馈你的回答正确正确答案是：e－v＋2标记题目信息文本判断题题目11正确获得5.00分中的5.00分标记题目题干设图G如图七所示，则图G的点割集是{f}．( )选择一项：对错反馈正确的答案是“错”。
一、选择题1设图G= <V, E >, v V,则下列结论成立的是(C ). A . deg(v )=2 E B . deg(v )二 EC.deg(v) 2 E [PPT 23]D.deg(v) Ev Vv V定理1 图G=(V, E )中，所有点的次之和为边数的两倍 2. 设无向图G 的邻接矩阵为0 10 0 1 0 10 10则G 的边数为(B ). A . 6B. 53、设完全图K n 有n 个结点(n 2) , m 条边，当(C )时，K n中存在 欧拉回路.解释：K n 每个结点的度都为n — 1所以若存在欧拉回路则n —1必为偶数。
n 必 为奇数。
4. 欧拉回路是(B )A.路径B.简单回路[PPT 40]C.既是基本回路也是简单回路D.既非基本回路也非简单回路 5 .哈密尔顿回路是(C ) A.路径 B.简单回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路A. m 为奇数 B . n 为偶数 C. n 为奇数 D . m 为偶数0 1 1 01 0 1 0[PPT 40] ：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。
6. 设G是简单有向图，可达矩阵P（G）刻划下列关系中的是（C ）A、点与边B、边与点C、点与点D、边与边7. 下列哪一种图不一定是树（C）。
A.无简单回路的连通图B. 有n个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图8. 在有n 个结点的连通图中，其边数（B）A. 最多有n-1 条B. 至少有n-1 条C. 最多有n 条D. 至少有n9. 下列图为树的是（C）。
A、G1{a,b,c,d},{a,a ,a,b ,c,d B、G2{a,b,c,d},{a,b ,b,d, c,d C、G3{a,b,c,d}, {a,b ,a,d, c,a D、G4{a,b,c,d},{a,b ,a,c ,d,d } } } }10、面的图7-22 是（C）。
离散数学（本）一、单项选择题1.集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, yA}，则R的性质为（）．A.自反的B.对称的C.传递且对称的D.反自反且传递的正确答案: B2.如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A.0B.2C.1D.3正确答案: B3.设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )．A.{1, 2, 3, 4}B.{1, 2, 3, 5}C.{2, 3, 4, 5}D.{4, 5, 6, 7}正确答案: A4.若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是（）．A.{a，{a}}AB.{1，2}AC.{a}AD.A正确答案: C5.若集合A的元素个数为10，则其幂集的元素个数为（）．A.1024B.10C.100D.1正确答案: A6.设函数f：N→N，f(n)=n+1，下列表述正确的是（）．A.f存在反函数B.f是双射的C.f是满射的D.f是单射函数正确答案: D7.设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）．A.下界B.最小上界C.最大下界D.最小元正确答案: B8.设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．A.最大元B.最小元C.极大元D.极小元正确答案: C9.设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1,1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．A.自反B.传递C.对称D.自反和传递正确答案: C10.集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, yA}，则R的性质为（）．A.不是自反的B.不是对称的C.传递的D.反自反正确答案: C11.图G如图三所示，以下说法正确的是 ( )．A.a是割点B.{b,c}是点割集C.{b, d}是点割集D.{c}是点割集正确答案: B12.设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A.e－v＋2B.v＋e－2C.e－v－2D.e＋v＋2正确答案: A13.图G如图四所示，以下说法正确的是 ( ) ．A.{(a, d)}是割边B.{(a, d)}是边割集C.{(a, d) ,(b, d)}是边割集D.{(b, d)}是边割集正确答案: C14.设无向图G的邻接矩阵为，则G的边数为( )．A.6B.5C.4D.3正确答案: B15.无向图G存在欧拉回路，当且仅当（）．A.G中所有结点的度数全为偶数B.G中至多有两个奇数度结点C.G连通且所有结点的度数全为偶数D.G连通且至多有两个奇数度结点正确答案: C16.无向完全图K4是（）．A.欧拉图B.汉密尔顿图C.非平面图D.树正确答案: B17.无向树T有8个结点，则T的边数为( )．A.6B.7C.8D.9正确答案: B18.若G是一个汉密尔顿图，则G一定是( )．A.平面图B.对偶图C.欧拉图D.连通图正确答案: D19.若G是一个欧拉图，则G一定是( )．A.平面图B.汉密尔顿图C.连通图D.对偶图正确答案: C20.设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．图五A.（a）是强连通的B.（b）是强连通的C.（c）是强连通的D.（d）是强连通的正确答案: A21.命题公式为( )A.矛盾式B.可满足式C.重言式D.合取范式正确答案: B22.设个体域为整数集，则公式的解释可为( )．A.存在一整数x有整数y满足x+y=0B.任一整数x对任意整数y满足x+y=0C.对任一整数x存在整数y满足x+y=0D.存在一整数x对任意整数y满足x+y=0正确答案: C23.设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别是 ( )．A.0, 0, 0B.0, 0, 1C.0, 1, 0D.1, 0, 0正确答案: D24.设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．A.B.C.D.正确答案: D25.下列公式 ( )为重言式．A.┐P∧┐Q↔P∨QB.(Q→(P∨Q)) ↔(┐Q∧(P∨Q))C.Q→(P∨(P∧Q))↔Q →PD.(┐P∨(P∧Q)) ↔Q正确答案: C26.下列等价公式成立的为( )．A.┐P∧P┐Q∧QB.┐Q→P P→QC.P∧Q P∨QD.┐P∨P Q正确答案: A27.谓词公式(x)(A(x)→B(x)∨C(x，y))中的（）。
图论复习题（二）图论复习题一、选择题1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( C ) ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B )．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点(n ≥2)，m 条边，当（ C ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。
n 必为奇数。
4．欧拉回路是（ B ）A. 路径B. 简单回路[PPT 40]C. 既是基本回路也是简单回路D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。
6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C ）。
A.无简单回路的连通图B. 有n 个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图8．在有n 个结点的连通图中，其边数（B ）A.最多有n-1条B.至少有n-1条C.最多有n 条D.至少有n 条9．下列图为树的是（C ）。
A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7-22是（C ）。
离散数学图论部分期末复习辅导一、单项选择题 1．设图G ＝<V , E >，v V ，则下列结论成立的是 ( ) ．A ．deg(v )=2EB ．deg(v )=EC ．deg()2||v Vv E ∈=∑ D ．deg()||v Vv E ∈=∑解 根据握手定理（图中所有结点的度数之和等于边数的两倍）知，答案C 成立。
答 C2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110， 则G 的边数为( )．A ．6B ．5C ．4D ．3解 由邻接矩阵的定义知，无向图的邻接矩阵是对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有10个1，故有102=5条边。
答 B3．已知无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111110101110001000111010，则G 有（ ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边解 由邻接矩阵的定义知，矩阵是5阶方阵，所以图G 有5个结点，矩阵元素有14个1，14÷2=7，图G 有7条边。
答 D4．如图一所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d, e)}是边割集定义3.2.9 设无向图G =<V ,E >为连通图，若有边集E 1ÌE ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图仍是连通图，则称E 1是G 的一个边割集．若边割集为单元集{e }，则称边e 为割边（或桥）．解 割边首先是一条边，因为答案A 中的是边集，不可能是割边，因此答案A 是错误的．删除答案B 或C 中的边后，得到的图是还是连通图，因此答案B 、C 也是错误的．在图一中，删去(d , e )边，图就不连通了，所以答案D 正确． 答 D注：如果该题只给出图的结点和边，没有图示，大家也应该会做．如：若图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ) , (a , e ) , (b , c ) , (b , e ) , (c , e ) , (e , d )}，则该图中的割边是什么？5．图G 如图二所示，以下说法正确的是 ( )． A ．a 是割点 B ．{b, c}是点割集 C ．{b , d }是点割集 D ．{c }是点割集定义3.2.7 设无向图G =<V ,E >为连通图，若有点集V 1ÌV ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图仍是连通图，则称V 1是G 的一个点割集．若点割集为单元集{v }，则称结点v 为割点．οοο ο a bc d图一 οe ο οο a b c d图二ο解 在图二中，删去结点a 或删去结点c 或删去结点b 和d 图还是连通的，所以答案A 、C 、D 是错误的．在图二中删除结点b 和c ，得到的子图是不连通图，而只删除结点b 或结点c ，得到的子图仍然是连通的，由定义可以知道，{b, c }是点割集．所以答案B 是正确的． 答 B6．图G 如图三所示，以下说法正确的是 ( ) ． A ．{(a, d )}是割边 B ．{(a, d )}是边割集C ．{(a, d) ,(b, d)}是边割集D ．{(b , d )}是边割集解 割边首先是一条边，{(a, d )}是边集，不可能是割边．在图三中，删除答案B 或D 中的边后，得到的图是还是连通图．因此答案A 、B 、D 是错误的．在图三中，删去(a,d )边和(b, d )边，图就不连通了，而只是删除(a, d )边或(b, d )边，图还是连通的，所以答案C 正确．7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是( )．图四A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的复习：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；若图G 的底图，即在图G 中略去边的方向，得到的无向图是连通的，则称图G 是弱连ο ο ο a bcd图三ο通的．显然，强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不真．定理3.2.1一个有向图是强连通的，当且仅当G中有一个回路，其至少包含每个结点一次．单侧连通图判别法：若有向图G中存在一条经过每个结点至少一次的路，则G是单侧连通的。
05 图【单选题】1. 设无向图G 中有五个顶点，各顶点的度分别为2、4、3、1、2，则G 中边数为（C ）。
Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定2. 含n 个顶点的无向完全图有（D ）条边；含n 个顶点的有向图最多有（C ）条弧；含n 个顶点的有向强连通图最多有（C ）条弧；含n 个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n 个顶点，则要接通全部顶点至少需（G ）条边。
A 、n 2B 、n(n+1)C 、n(n-1)D 、n(n-1)/2E 、n+1F 、nG 、n-13. 对下图从顶点a 出发进行深度优先遍历，则（A ）是可能得到的遍历序列。
A 、acfgdebB 、abcdefgC 、acdgbefD 、abefgcd对下图从顶点a 出发进行广度优先遍历，则（D ）是不可能得到的遍历序列。
A 、abcdefgB 、acdbfgeC 、abdcegfD 、adcbgef4. 设图G 的邻接矩阵A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010101010，则G 中共有（C ）个顶点；若G 为有向图，则G 中共有（D ）条弧；若G 为无向图，则G 中共有（B ）条边。
A 、1B 、2C 、3D 、4E 、5F 、9G 、以上答案都不对5. 含n 个顶点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A 、0B 、1C 、n-1D 、n6. 用邻接表存储图所用的空间大小（A ）。
A 、与图的顶点数和边数都有关B 、只与图的边数有关C 、只与图的顶点数有关D 、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B ）个表结点。
A 、n 2B 、n(n-1)C 、n(n+1)D 、n(n-1)/28. 无向图G=(V ,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。
国家开放大学电大本科《离散数学》网络课形考任务2作业及答案此任务2 g选择题题目1 无向完全图K4是()、选择一项：A、树 B、欧拉图 C、汉密尔顿图 D、非平面图题目2 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为()、选择一项： A、4 B、8 C、3 D、5 题目3 设无向图G的邻接矩阵为 011111 0 0111 0 0 0 011 0 011 01 0 则G 的边数为( 选择一项： A、7 B、14 C、6 D、1 题目4 如图一所示，以下说法正确的是()、选择一项： A、 ((a, e), (b, c)｝是边割集 B、｛(a, e)｝是边割集 C、｛（d, e）｝是边割集 D、（（a, e）｝是割边题目5 以下结论正确的是（）、选择一项： A、有n个结点n-l条边的无向图都是树B、无向完全图都是平面图 C、树的每条边都是割边 D、无向完全图都是欧拉图题目6 若G是一个欧拉图，则G一定是（）、选择一项： A、汉密尔顿图 B、连通图 C、平面图 D、对偶图题目7 设图G=, vGV,则下列结论成立的是（）、选择一项：A、云 d做、）=2|% B、2>“ = |司 w C、 deg（v）=2|S| D、deg（v）=|E| 题目8 图G如图三所示，以下说法正确的是（）、选择一项： A、（b, d｝是点割集 B、｛c｝是点割集 C、｛b, c｝是点割集 D、 a是割点题目9 设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是（）、选择一项： (a)是费连通的 B、 (d)是强连通的 C、 (c)是强连通的D、 (b)是强连通的题目10 设有向图(a)、(b)、(c)与(d)如图六所示，则下列结论成立的是()、选择一项： A、 (b)只是弱连通的 B、 (c)只是弱连通的 C、 (a)只是弱连通的 D、 (d)只是弱连通的判断逝题目11 设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去4条边后使之变成树、()选择一项：对错题目12 汉密尔顿图一定是欧拉图、()选择一项：对错题目13 设连通平面图G的结点数为5,边数为6,则面数为4、()选择一项：对错题目14 设G是一个有7个结点16条边的连通图，则G为平面图、()选择一项：对错题目15 如图八所示的图G存在一条欧拉回路、()选择一项：对错题目16 设图G如图七所示，则图G的点割集是{f}、()选择一项：对错题目172>瞒)=2圜设G是一个图，结点集合为V,边集合为E,则代衫()选择一项：对错题目18 设图G是有5个结点的连通图，结点度数总和为10,则可从G中删去6条边后使之变成树、()选择一项：对错题目19 如图九所示的图G不是欧拉图而是汉密尔顿图、()选择一项：对错题目20 若图 G=,其中 V=( a, b, c, d }, E={ (a, b), (a, d), (b, c), (b, d)},则该图中的割边为(b, c)、()选择一项：对。
第一章测试1.若P：天下雨；Q：他来了；则“虽然天下雨，他还是来了”，可符号化为( )A:P∧QB:P→QC:P∨┐QD:P∨Q答案:A2.以下命题公式中，为永真式的是( )A:(Q∨┐P)→(P∧┐P)B:(P→┐P)→┐PC:┐(Q→Q∧P)D:P∧(P∨Q∨R)答案:B3.命题公式的能成真赋值的P,Q的值为（）A:11B:01C:10D:00答案:ABD4.命题公式的能成假赋值的P,Q的值为（）A:10B:00C:11D:01答案:ABD5.G=P→(P∧(Q→P))主析取范式中所含的极大极小项有（）A:P∧QB:¬P∧¬QC:¬P∨QD:P∨QE:P∧¬QF:¬P∨¬QG:P∨¬QH:¬P∧QI:无答案:ABEH6.G=P→(P∧(Q→P))主合取范式中所含的极大极小项有（）。
A:P∧QB:无C:¬P∧QD:此项必选E:P∨¬QF:P∧¬QG:¬P∨¬QH:¬P∨QI:P∨QJ:¬P∧¬Q答案:BD7.(P→Q)∧Q的主合取范式中所含的极大极小项有（）。
A:¬P∧QB:P∨QC:P∧¬QD:¬P∨QE:无F:P∧QG:¬P∧¬QH:¬P∨¬QI:P∨¬Q答案:BD8.(P→Q)∧Q的主析取范式中所含的极大极小项有（）。
A:P∨¬QB:¬P∧QC:¬P∨¬QD:P∧QE:P∧¬QF:无G:¬P∨QH:¬P∧¬QI:P∨Q答案:BD9.设前提集合Γ={P∨Q, R∧S, ┐Q},公式G=P∧S,，证明Γ=＞G。
证明：（1）┐Q P（2）P∨Q P（3） T,1),2),I （4）R∧S P（5） T,4），I（6）P∧S T,3),5),I 按顺序选出(3）和(5）处应该填的内容（）A:¬PB:SC:RD:P答案:BD10.使用演绎法构造下列推理的证明。
国家开放大学电大本科《离散数学》网络课形考网考作业及答案100%通过考试说明：2020年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有5个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。
做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。
本文库还有其他网核及教学考一体化答案，敬请查看。
课程总成绩 = 形成性考核×30% + 终结性考试×70%形考任务1单项选择题题目1若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是（）．选择一项：题目2若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．选择一项：题目3设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．选择一项：A. 传递B. 对称C. 自反和传递D. 自反题目4设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )．选择一项：A. {1, 2, 3, 5}B. {4, 5, 6, 7}C. {2, 3, 4, 5}D. {1, 2, 3, 4}题目5如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．选择一项：A. 1B. 3C. 2D. 0题目6集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y∈A}，则R的性质为（）．选择一项：A. 不是对称的B. 反自反C. 不是自反的D. 传递的题目7若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．选择一项：题目8设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．选择一项：A. 3B. 2C. 8D. 6题目9设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次。
2、设无向图G的邻接矩阵为，则G的边数为( )A 5B 6C 4D 3隐藏答案正确答案：A知识点：形考63、若集合A的元素个数为10，则其幂集的元素个数为（）A 1B 10C 1024D 100隐藏答案正确答案：C知识点：形考24、如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个A 2B 0C 1D 3隐藏答案正确答案：A知识点：形考55、设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树ABCD隐藏答案正确答案：D知识点：形考66、设G是连通平面图，有v个结点，e条边，r个面，则r= ( )A e－v＋2B v＋e－2C e＋v＋2D e－v－2隐藏答案正确答案：A知识点：形考67、如图一所示，以下说法正确的是( )A {(a, e) ,(b, c)}是边割集B {(a, e)}是割边C {(a, e)}是边割集D {(d, e)}是边割集隐藏答案正确答案：D知识点：形考69、若G是一个汉密尔顿图，则G一定是( )A 欧拉图B 对偶图C 平面图D 连通图隐藏答案正确答案：D知识点：形考610、A 最小元B 极大元C 最大元D 极小元隐藏答案正确答案：B知识点：形考411、如图二所示，以下说法正确的是( )A {a, e}是点割集B {d}是点割集C e是割点D {b, e}是点割集隐藏答案正确答案：C知识点：形考612、设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）A 2B 3C 8D 6隐藏答案正确答案：C知识点：形考113、设集合A = {1, a }，则P(A) = ( )A {Φ，{1}, {a}, {1, a }}B {Φ,{1}, {a}}C {{1}, {a}}D {Φ,{1}, {a}, {1, a }}隐藏答案正确答案：D知识点：形考514、设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是( )A （b）只是弱连通的B （d）只是弱连通的C （a）只是弱连通的D （c）只是弱连通的隐藏答案正确答案：B知识点：形考615、设函数f：N→N，f(n)=n+1，下列表述正确的是（）A f是单射函数B f是满射的C f存在反函数D f是双射的隐藏答案正确答案：A知识点：形考416、已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )A 3B 4C 5D 8隐藏答案正确答案：C知识点：形考617、设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )A 无、2、无、2B 8、1、6、1C 6、2、6、2D 8、2、8、2隐藏答案正确答案：A知识点：形考318、设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={<a，1>, <b，2>}，从B到C的函数g={<1，5>, <2，4>}，则下列表述正确的是（）AB g° f ={<5，a >, <4，b >}C f°g ={<5，a >, <4，b >}D隐藏答案正确答案：D知识点：形考519、图G如图三所示，以下说法正确的是( )A a是割点B {c}是点割集C {b, d}是点割集D {b, c}是点割集隐藏答案正确答案：D知识点：形考620、设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={<a，1>, <b，2>}，从B到C的函数g={<1，5>, <2，4>}，则下列表述正确的是（）A g° f ={<5，a >, <4，b >}BC f°g ={<5，a >, <4，b >}D隐藏答案正确答案：B知识点：形考421、设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )A {1, 2, 3, 5}B {4, 5, 6, 7}C {2, 3, 4, 5}D {1, 2, 3, 4}隐藏答案正确答案：D知识点：形考422、设函数f：N→N，f(n)=n+1，下列表述正确的是（）A f是双射的B f存在反函数C f是满射的D f是单射函数隐藏答案正确答案：D形考123、设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）A 6B 2C 8D 3隐藏答案正确答案：C知识点：形考424、设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）A 2B 3C 8D 6隐藏答案正确答案：C知识点：形考225、设函数f：N→N，f(n)=n+1，下列表述正确的是（）．A f是双射的B f存在反函数C f是满射的D f是单射函数隐藏答案正确答案：D形考226、设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )A （c）是强连通的B （a）是强连通的C （b）是强连通的D （d）是强连通的隐藏答案正确答案：B知识点：形考627、设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={<a，1>, <b，2>}，从B到C的函数g={<1，5>, <2，4>}，则下列表述正确的是（）AB f°g ={<5，a >, <4，b >}C g° f ={<5，a >, <4，b >}D隐藏答案正确答案：D知识点：形考328、设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的关系R={<x, y>| y = x +1｝，则R= ( )A {<2, 1>, <4, 3>, <6, 5>}B {<2, 3>, <4, 5>, <6, 7>}C {<2, 2>, <3, 3>, <4, 6>}D {<2, 1>, <3, 2>, <4, 3>}隐藏答案正确答案：B知识点：形考129、设集合A={a}，则A的幂集为( )A {a，{a}}B {{a}}C {Φ，a}D {Φ，{a}}隐藏答案正确答案：D知识点：形考230、设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包A 传递B 自反C 自反和传递D 对称隐藏答案正确答案：D知识点：形考431、若G是一个欧拉图，则G一定是( )A 平面图B 汉密尔顿图C 连通图D 对偶图隐藏答案正确答案：C知识点：形考632、设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）A 3B 6C 8D 2隐藏答案正确答案：C知识点：形考533、集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y属于集合A}，则R 的性质为（）A 对称的B 传递且对称的C 反自反且传递的D 自反的隐藏答案正确答案：A知识点：形考334、设无向图G的邻接矩阵为，则G的边数为( )A 6B 7C 14D 1隐藏答案正确答案：B知识点：形考635、设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )A {2, 3, 4, 5}B {1, 2, 3, 5}C {4, 5, 6, 7}D {1, 2, 3, 4}隐藏答案正确答案：D知识点：形考236、图G如图四所示，以下说法正确的是( )A {(a, d)}是边割集B {(a, d) ,(b, d)}是边割集C {(b, d)}是边割集D {(a, d)}是割边隐藏答案正确答案：B知识点：形考638、若集合A的元素个数为10，则其幂集的元素个数为（）A 1B 10C 1024D 100隐藏答案正确答案：C知识点：形考140、设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的关系R={<x, y>| y = x +1｝，则R= ( )A {<2, 1>, <4, 3>, <6, 5>}B {<2, 3>, <4, 5>, <6, 7>}C {<2, 2>, <3, 3>, <4, 6>}D {<2, 1>, <3, 2>, <4, 3>}正确答案：B知识点：形考241、设集合A = {1, a }，则P(A) = ( )A {Φ，{1}, {a}, {1, a }}B {Φ,{1}, {a}}C {{1}, {a}, {1, a }}D {{1}, {a}}隐藏答案正确答案：A知识点：形考242、设集合A = {1, a }，则P(A) = ( )A {Φ，{1}, {a}, {1, a }}B {Φ,{1}, {a}}C {{1}, {a}, {1, a }}D {{1}, {a}}隐藏答案正确答案：A知识点：形考143、无向树T有8个结点，则T的边数为( )A 6B 7C 9D 8正确答案：B知识点：形考645、设A={1, 2, 3, 4, 5, 6,7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )A 无、2、无、2B 8、2、8、2C 6、2、6、2D 8、1、6、1隐藏答案正确答案：A知识点：形考446、如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个A 2B 3C 0D 1隐藏答案正确答案：A知识点：形考347、下列公式( )为重言式A Q→(P∨(P∧Q))↔Q →PB (Q→(P∨Q)) ↔(┐Q∧(P∨Q))C (┐P∨(P∧Q)) ↔QD ┐P∧┐Q↔P∨Q隐藏答案正确答案：A知识点：形考748、设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )A {2, 3, 4, 5}B {1, 2, 3, 5}C {4, 5, 6, 7}D {1, 2, 3, 4}隐藏答案正确答案：D知识点：形考149、设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）A g◦fB f◦gC f◦fD g◦g隐藏答案正确答案：B知识点：形考450、命题公式(P∨Q) 的合取范式是( )A (P∨Q)B (P∧Q)∨(P∨Q)C (P∧Q)D ┐(┐P∧┐Q)隐藏答案正确答案：A知识点：形考751、设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）A 最小元B 最小上界C 最大下界D 下界隐藏答案正确答案：B知识点：形考352、设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）A g◦fB f◦fC g◦gD f◦g正确答案：D知识点：形考3判断题1、设A={1，2}，B={ a, b, c }，则A×B的元素个数为8．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考52、如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考63、设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∩(C-B )= {1, 2, 3, 5}．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考54、设G是一个有7个结点16条边的连通图，则G为平面图．( )A 正确B 错误正确答案：错误知识点：形考65、设G=<V,E>是具有n个结点的简单图，若在G中每一对结点度数之和小于n-1，则在G中存在一条汉密尔顿路．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考66、设集合A={1, 2, 3}，B={1, 2}，则A×B={<1,1>, <1,2>, <2,1>, <2,2>, <3,1>,<3,2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考27、命题公式P→(Q∨P)的真值是T．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考78、设图G如图七所示，则图G的点割集是{f}．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考69、设集合A={1, 2, 3}，B={1, 2}，则A×B={<1,1>, <1,2>, <2,1>, <2,2>, <3,1>,<3,2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考210、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有反自反性质．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考311、已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考612、汉密尔顿图一定是欧拉图．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考613、空集的幂集是空集．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考114、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c, b>，<d, c>，则新得到的关系就具有反自反性质．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考315、如图八所示的图G存在一条欧拉回路．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考616、设A={1，2，3 }，R={<1，1 >, <1，2 >，<2，1 >, <3，3 >}，则R是等价关系．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考317、A 正确B 错误隐藏答案正确答案：正确知识点：形考518、设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g° f) ={2，3}．（）A 正确隐藏答案正确答案：正确知识点：形考419、设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>，<2, 2>，<3, 3> 等元素．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考120、命题公式┐(P→Q)的主析取范式是P∨┐Q．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考721、设A={1，2，3 }，R={<1，1 >, <1，2 >，<2，1 >, <3，3 >}，则R是等价关系．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考4上一题23、下面的推理是否正确．( ) (1) (∀x)A(x)→B(x) 前提引入(2) A(y)→B(y) US (1)B 错误隐藏答案正确答案：错误知识点：形考724、设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={<a, 1>, <b, 2>}，从B到C的函数g={<1, b>, <2, a >}，则g° f ={<1，2 >, <2，1 >}．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考225、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有反自反性质．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考426、设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g° f) ={2，3}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考227、结点数v与边数e满足e=v的无向连通图就是树．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考628、设G是一个连通平面图，且有6个结点11条边，则G有7个面．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考629、设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>，<2, 2>，<3, 3> 等元素．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考530、若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G 中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W≤|S|．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考631、A 正确B 错误隐藏答案正确答案：正确知识点：形考332、若集合A = {1，2，3}上的二元关系R={<1, 1>，<1, 2>，<3, 3>}，则R是对称的关系．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考533、设集合A={1, 2, 3}，B={1, 2}，则A×B={<1,1>, <1,2>, <2,1>, <2,2>, <3,1>,<3,2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考34、设A={1，2}，B={ a, b, c }，则A×B的元素个数为8．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考335、空集的幂集是空集．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考236、A 正确B 错误隐藏答案正确答案：正确知识点：形考337、谓词命题公式(∀x)((A(x)∧B(x))∨C(y))中的自由变元为x．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考738、设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>，<2, 2>，<3, 3> 等元素．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考39、如果R1和R2是A上的自反关系，则R1∪R2、R1∩R2是自反的．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考240、空集的幂集是空集．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考441、设A={1, 2}上的二元关系为R={<x, y>|x 属于集合A，y属于集合A, x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考342、如果R1和R2是A上的自反关系，则R1∪R2、R1∩R2是自反的．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考143、设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={<a, 1>, <b, 2>}，从B到C的函数g={<1, b>, <2, a >}，则g° f ={<1，2 >, <2，1 >}．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考444、设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考645、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有反自反性质．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考46、设个体域D＝{a, b},那么谓词公式(∃x)A(x)∨(∀y)B(y)消去量词后的等值式为A(a)∨B(b)．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考747、设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={<a, 1>, <b, 2>}，从B到C的函数g={<1, b>, <2, a >}，则g° f ={<1，2 >, <2，1 >}．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考148、设P：昨天下雨，Q：今天下雨．那么命题“昨天下雨，今天仍然下雨”符号化的结果为P∧Q．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考7上一题50、设个体域D＝{a, b}，则谓词公式(∀x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(a))∧(A(b)∧B(b))．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考751、设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，下列关系f = {<1, 4>, <2, 2,>, <4, 6>, <1, 8>}可以构成函数f：．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考552、设集合A={1, 2, 3}，B={1, 2}，则P(A)-P(B )= {{3},{1,3},{2,3},{1,2,3}}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考453、两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相等．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考654、A 正确B 错误隐藏答案正确答案：正确知识点：形考455、设A={1, 2}上的二元关系为R={<x, y>| x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考256、设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包含<1, 1>，<2, 2>，<3, 3> 等元素．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考457、设P(x)：x是人，Q(x)：x去上课，那么命题“有人去上课．”为(∃x)(P(x)→Q(x))．( )B 错误隐藏答案正确答案：错误知识点：形考758、若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，极小元不存在．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考359、设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g° f) ={2，3}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考560、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c, b>，<d, c>，则新得到的关系就具有反自反性质．（）A 正确隐藏答案正确答案：错误知识点：形考561、设G是一个图，结点集合为V，边集合为E，则．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考662、设A={1, 2}上的二元关系为R={<x, y>| x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考163、空集的幂集是空集．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考564、设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∩(C-B )= {1, 2, 3, 5}．（）B 错误隐藏答案正确答案：错误知识点：形考165、A 正确B 错误隐藏答案正确答案：正确知识点：形考366、设个体域D＝{1, 2, 3}，A(x)为“x小于3”，则谓词公式(∃x)A(x) 的真值为T．( )A 正确B 错误隐藏答案正确答案：正确知识点：形考767、设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∩(C-B )= {1, 2, 3, 5}．（）A 正确B 错误隐藏答案正确答案：错误知识点：形考268、设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有反自反性质．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考169、设P(x)：x是人，Q(x)：x学习努力，那么命题“所有的人都学习努力．”为(∀x)(P(x)∧Q(x))．( )A 正确B 错误隐藏答案正确答案：错误知识点：形考770、设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g° f) ={2，3}．（）A 正确B 错误隐藏答案正确答案：正确知识点：形考1。
2016年秋国家开放大学《离散数学》形考4试题及答案（答案全部正确）04任务_0001试卷总分：100 测试时间：0单项选择题一、单项选择题（共 10 道试题，共 100 分。
）1. 无向树T有8个结点，则T的边数为( )．A. 6B. 7C. 8D. 92. 图G如图三所示，以下说法正确的是( ) ．A. {(a, d)}是割边B. {(a, d)}是边割集C. {(a, d) ,(b, d)}是边割集D. {(b, d)}是边割集3. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )．A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的4. 如图一所示，以下说法正确的是( ) ．A. {(a, e)}是割边B. {(a, e)}是边割集C. {(a, e) ,(b, c)}是边割集D. {(d, e)}是边割集5. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．A. m-n+1B. m-nC. m+n+1D. n-m+16. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A. e－v＋2B. v＋e－2C. e－v－2D. e＋v＋27. 设无向图G的邻接矩阵为，则G的边数为( )．A. 6B. 5C. 4D. 38. 如图所示，以下说法正确的是( )．A. e是割点B. {a,e}是点割集C. {b, e}是点割集D. {d}是点割集9. 无向简单图G是棵树，当且仅当( )．A. G连通且边数比结点数少1B. G连通且结点数比边数少1C. G的边数比结点数少1D. G中没有回路．10. 以下结论正确的是( )．A. 无向完全图都是欧拉图B. 有n个结点n－1条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边04任务_0002试卷总分：100 测试时间：0单项选择题一、单项选择题（共 10 道试题，共 100 分。
(二）图论复习题一、选择题1．设图G ＝〈V ， E 〉，v ∈V ，则下列结论成立的是 ( C ） ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B ）．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点（n ≥2）,m 条边，当（ C )时,K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。
n 必为奇数。
4．欧拉回路是（ B ）A 。
路径 B. 简单回路[PPT 40] C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ) A. 路径 B. 简单回路 C 。
既是基本回路也是简单回路 D.既非基本回路也非简单回路［PPT 40］：哈密尔顿回路要求走遍所有的点,即是基本回路的点不重复，也可以是简单回路的边不重复。
6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C )。
A 。
无简单回路的连通图B 。
有n 个顶点n-1条边的连通图C 。
每对顶点间都有通路的图D 。
连通但删去一条边便不连通的图8．在有n 个结点的连通图中,其边数(B ）A 。
最多有n-1条B 。
至少有n-1条 C.最多有n 条 D 。
至少有n 条9．下列图为树的是(C ）。
A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7—22是（C ）.A.完全图；B 。
最新国家开放大学电大《离散数学(本)》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。
该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。
做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。
本文库还有其他网核及教学考一体化答案，敬请查看。
《离散数学》题库及答案一一、单项选择题（每小题3分，本题共15分）1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．A．A⊂B，且A∈B B．A∈B，但A⊄BC．A⊂B，但A∉B D．A⊄B，且A∉B2．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y∈A}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．34．如图一所示，以下说法正确的是( ) ．A．{(a, e)}是割边B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图一5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（）．A．(∀x)(A(x)∧B(x)) B．┐(∃x)(A(x)∧B(x))C．┐(∀x)(A(x) →B(x)) D．┐(∃x)(A(x)∧┐B(x))二、填空题（每小题3分，本题共15分）6．若集合A的元素个数为10，则其幂集的元素个数为．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为．8．若A={1,2}，R={<x, y>|x∈A, y∈A, x+y=10}，则R的自反闭包为．9．结点数v与边数e满足关系的无向连通图就是树．10．设个体域D＝{a, b, c}，则谓词公式(∀x)A(x)消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．12．将语句“今天没有下雨．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1) （∀x）F（x）→G（x）前提引入(2) F（y）→G（y）US（1）．14．若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．图二五．计算题（每小题12分，本题共36分）15．求（P∨Q）→（R∨Q）的合取范式．16．设A={0，1，2，3，4}，R={<x，y>|x∈A，y∈A且x+y<0}，S={<x，y>|x∈A，y∈A且x+y≤3}，试求R，S，R•S，R-1，S-1，r(R)．17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．六、证明题（本题共8分）18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G 是G的补图)．试题解答一、单项选择题（每小题3分，本题共15分） 1．A 2．B 3．B 4．D 5．C 二、填空题（每小题3分，本题共15分） 6．1024 7．88．{<1,1>,<2,2>} 9．e=v -110．A (a ) ∧A (b )∧A （c ）三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：他接受了这个任务，Q ：他完成好了这个任务， （2分）P ∧⌝ Q ． （6分）12．设P ：今天下雨， （2分）⌝ P ． （6分）四、判断说明题（每小题7分，本题共14分）13．错误． （3分） （2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分） 14．错误． （3分） 集合A 的最大元不存在，a 是极大元． （7分） 五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔⌝（P ∨Q ）∨（R ∨Q ） （4分） ⇔(⌝P ∧⌝Q )∨（R ∨Q ）⇔(⌝P ∨R ∨Q )∧(⌝Q ∨R ∨Q )⇔(⌝P ∨R ∨Q ) ∧R 合取范式 （12分） 16．R =∅, （2分） S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分） R •S =∅， （6分）R -1=∅， （8分） S -1= S ， （10分） r (R )=I A ． （12分） 17．（10分）权为1⨯3+2⨯3+2⨯2+3⨯2+4⨯2=27 （12分）六、证明题（本题共8分）18．证明：因为n 是奇数，所以n 阶完全图每个顶点度数为偶数， （3分） 因此，若G 中顶点v 的度数为奇数，则在G 中v 的度数一定也是奇数， （6分）ο οο ο ο ο ο ο ο 1 2 23 34 75 12所以G 与G 中的奇数度顶点个数相等． （8分）《离散数学》题库及答案二一、单项选择题（每小题3分，本题共15分）1．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( )． A ．2⊂A B ．{1}⊂AC ．1∉AD ．2 ∈ A2．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )． A ．6 B ．4 C ．3 D ．53．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110 则G 的边数为( )． A ．1 B ．7 C ．6 D ．144．设集合A ={a }，则A 的幂集为( )．A ．{{a }}B ．{a ，{a }}C ．{∅，{a }}D ．{∅，a }5．下列公式中 ( )为永真式．A ．⌝A ∧⌝B ↔ ⌝A ∨⌝B B ．⌝A ∧⌝B ↔ ⌝(A ∨B )C ．⌝A ∧⌝B ↔ A ∨BD ．⌝A ∧⌝B ↔ ⌝(A ∧B )二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∧的真值是 ． 7．若无向树T 有5个结点，则T 的边数为 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 ，就可使新得到的关系为对称的．10．(∀x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．14．设G是一个有4个结点10条边的连通图，则G为平面图．五．计算题（每小题12分，本题共36分）15．试求出（P∨Q）→（R∨Q）的析取范式．16．设A={{1}, 1, 2}，B={1, {2}}，试计算（1）（A∩B）（2）（A∪B）（3）A （A∩B）．17．图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．试题解答一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 5．B二、填空题（每小题3分，本题共15分）6．假（或F，或0）7．48．t-19．<2, 1>10．z，y三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：今天上课， （2分） 则命题公式为：P ． （6分） 12．设 P ：他去操场锻炼，Q ：他有时间， （2分） 则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分） 因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数． （7分） 14．错误． （3分） 不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．” （7分）五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔ ┐(P ∨Q )∨（R ∨Q ） （4分）⇔ (┐P ∧┐Q )∨（R ∨Q ） （8分）⇔ (┐P ∧┐Q )∨R ∨Q （析取范式） （12分）16．（1）（A ∩B ）={1} （4分）（2）（A ∪B ）={1, 2, {1}, {2}} （8分） （3） A -（A ∩B ）={{1}, 1, 2} （12分）17．（1）G 的图形表示如图一所示：（3分）（2）邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110 （6分） （3）最小的生成树如图二中的粗线所示：图一 ο ο ο ο a b c d1 124 53 图二ο ο ο ο a b cd1 1 2453（10分）权为：1+1+3=5 （12分）六、证明题（本题共8分）18．证明：设∀x∈A，因为R自反，所以x R x，即< x, x>∈R；又因为S自反，所以x R x，即< x, x >∈S．（4分）即< x, x>∈R∩S （6分）故R∩S自反．（8分）《离散数学》题库及答案三一、单项选择题（每小题3分，本题共15分）1．若集合A＝{ a，{a}}，则下列表述正确的是( )．A．{a}⊆A B．{{{a}}}⊆AC．{a，{a}}∈A D．∅∈A2．命题公式（P∨Q）的合取范式是( )A．（P∧Q）B．（P∧Q）∨（P∨Q）C．（P∨Q）D．⌝（⌝P∧⌝Q）3．无向树T有8个结点，则T的边数为( )．A．6 B．7 C．8 D．9 4．图G如图一所示，以下说法正确的是( )．A．a是割点B．{b,c}是点割集C．{b, d}是点割集D．{c}是点割集图一5．下列公式成立的为( )．A．⌝P∧⌝Q ⇔P∨Q B．P→⌝Q⇔⌝P→QC．Q→P⇒ P D．⌝P∧(P∨Q)⇒Q二、填空题（每小题3分，本题共15分）6．设集合A ={2, 3, 4}，B ={1, 2, 3, 4}，R 是A 到B 的二元关系，},{y x B y A x y x R ≤∈∈><=且且则R 的有序对集合为 ．7．如果R 是非空集合A 上的等价关系，a ∈A ，b ∈A ，则可推知R 中至少包含 等元素． 8．设G ＝<V , E >是有4个结点，8条边的无向连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．9．设G 是具有n 个结点m 条边k 个面的连通平面图，则m 等于 10．设个体域D ＝{1, 2}，A (x )为“x 大于1”，则谓词公式()()x A x ∃的真值为 三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“今天考试，明天放假．”翻译成命题公式． 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式． 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．14．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二五．计算题（每小题12分，本题共36分）15．设谓词公式)),,()(),()((z x y B z y x A x ∀→∃，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． 16．设集合A ={{1},1,2}，B ={1,{1,2}}，试计算（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．17．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4 }，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4) }，试 （1）给出G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形． 六、证明题（本题共8分）18．设A ，B 是任意集合，试证明：若A ⨯A=B ⨯B ，则A=B ．试题解答(供参考)一、单项选择题（每小题3分，本题共15分） 1．A 2．C 3．B 4．B 5．D 二、填空题（每小题3分，本题共15分）6．{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>} 7．<a , a >，< b , b > 8．5 9．n +k -210．真（或T ，或1）三、逻辑公式翻译（每小题4分，本题共12分）11．设P ：今天考试，Q ：明天放假． （2分） 则命题公式为：P ∧Q ． （6分）12．设P ：我去旅游，Q ：我有时间， （2分）则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分） 14．错误． （3分） 集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，． （7分） 五．计算题（每小题12分，本题共36分）15．（1）∃x 量词的辖域为)),,()(),((z x y B z y x A ∀→， （3分）∀z 量词的辖域为),,(z x y B , （6分） （2）自由变元为)),,()(),((z x y B z y x A ∀→中的y ， （9分）约束变元为x 与z ． （12分）16．（1）A -B ={{1},2} （4分）（2）A ∩B ={1} （8分） （3）A ×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分） 17．（1）G 的图形表示为(如图三)：（3分）图三 （2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110101111000100（6分） （3）v 1，v 2，v 3，v 4结点的度数依次为1，2，3，2 （9分） （4）补图如图四所示：（12分）图四六、证明题（本题共8分）18．证明：设x ∈A ，则<x ，x >∈A ⨯A ， （1分） 因为A ⨯A=B ⨯B ，故<x ，x >∈B ⨯B ，则有x ∈B ， （3分） 所以A ⊆B ． （5分） 设x ∈B ，则<x ，x >∈B ⨯B ， （6分） 因为A ⨯A=B ⨯B ，故<x ，x >∈A ⨯A ，则有x ∈A ，所以B ⊆A ． （7分） 故得A=B ． （8分）《离散数学》题库及答案四一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果他掌握了计算机的用法，那么他就能完成这项工作．”翻译成命题公式．12．将语句“前天下雨，昨天还是下雨．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案《离散数学》题库及答案五一、单项选择题（每小题3分，本题共15分）试题及答案《离散数学》题库及答案六一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“昨天下雨”翻译成命题公式．12．将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案及评分标准（供参考）。
无向树T有8个结点，则T的边数为( )．选择一项：A. 7B. 9C. 8D. 6反馈你的回答不正确正确答案是：7题目2不正确获得5.00分中的0.00分标记题目题干设图G＝<V, E>，v V，则下列结论成立的是( ) ．选择一项：A.B. deg(v)=2| E |C. deg(v)=| E |D.反馈你的回答不正确正确答案是：题目3不正确获得5.00分中的0.00分标记题目题干设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．图五选择一项：A. （b）是强连通的B. （c）是强连通的C. （d）是强连通的D. （a）是强连通的反馈你的回答不正确正确答案是：（a）是强连通的题目4不正确获得5.00分中的0.00分标记题目题干设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．选择一项：A.B.C.D.反馈你的回答不正确正确答案是：题目5不正确获得5.00分中的0.00分标记题目题干无向完全图K4是（）．选择一项：A. 树B. 非平面图C. 欧拉图D. 汉密尔顿图反馈你的回答不正确正确答案是：汉密尔顿图题目6不正确获得5.00分中的0.00分标记题目题干已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．选择一项：A. 8B. 3C. 4D. 5反馈你的回答不正确正确答案是：5题目7未回答满分5.00标记题目题干图G如图四所示，以下说法正确的是( ) ．选择一项：A. {(a, d)}是边割集B. {(b, d)}是边割集C. {(a, d)}是割边D. {(a, d) ,(b, d)}是边割集反馈你的回答不正确正确答案是：{(a, d) ,(b, d)}是边割集题目8不正确获得5.00分中的0.00分标记题目题干以下结论正确的是( )．选择一项：A. 无向完全图都是平面图B. 无向完全图都是欧拉图C. 树的每条边都是割边D. 有n个结点n－1条边的无向图都是树反馈你的回答不正确正确答案是：树的每条边都是割边题目9不正确获得5.00分中的0.00分标记题目题干如图二所示，以下说法正确的是( )．图二选择一项：A. {d}是点割集B. e是割点C. {b, e}是点割集D. {a,e}是点割集反馈你的回答不正确正确答案是：e是割点题目10不正确获得5.00分中的0.00分标记题目题干若G是一个汉密尔顿图，则G一定是( )．选择一项：A. 欧拉图B. 连通图C. 平面图D. 对偶图你的回答不正确正确答案是：连通图标记题目信息文本判断题题目11正确获得5.00分中的5.00分标记题目题干设G是一个连通平面图，且有6个结点11条边，则G有7个面．( ) 选择一项：对错反馈正确的答案是“对”。
江苏技术师范学院20 —20 学年第 学期 《离散数学》试卷（27）参考答案与评分标准 一、单项选择题（本大题共5道小题，每小题2分，共10分） 1. 设A 、B 均为非空集合，则下列命题正确的是（ D ）。
A.B A A ∈ B.A B A ∈ C.A B A ⊆ D.A B A ⊆ 2. 实数集R 关于下列二元运算 结合律、交换律都满足的有（ B ）。
A ．a b=a+2b B ．a b=b C ．a b=a+b-2ab D ．a b=b a + 3. 图G=<V,E>，其中顶点集{}n v v v V ,,,21 =，E =m ，则∑==n i i v 1)deg(（ C ）。
A.22-m B.12-m C.m 2 D.12+m 4. 设A={1,2,3}，R 为A 上关系，关系图如下，则R 具有性质（ D ）。
A.自反性 B.反自反性 C.对称性 D.传递性 5. 下面4个推理定律中，不正确的为（ D ）。
A.A=>(A ∨B) (附加律) B.(A ∨B)∧⌝A=>B (析取三段论) C.(A→B)∧A=>B (假言推理) D.(A→B)∧⌝B=>A (拒取式) 二、填空题（本大题共10空，每空2分，共20分） 1. 从公式分类角度来看，(P ∨⌝P)→((Q ∧⌝Q)∧R)为___矛盾/永假 _式。
2. 设p ：我们拼搏，q ：我们刻苦，r ：我们取得好结果。
命题“只要拼搏刻苦，我们就能取得好结果”符号化为 r q p →∧ 。
3. 令Z(x):x 是整数，N(x):x 是自然数。
则命题“并非每个整数都是自然数”的符号化表示为： ))()((x N x Z →⌝∀ 。
4. 集合A={1,2,…,100}上的关系R={<x,y>|x+y=100,x,y ∈A}，则R 的性质为 对装订线班级：姓名：学号：称性 。
5. Q 是有理数集合，代数系统<Q ，+>,任一有理数x 的逆元x -1 = -x 。
离散数学作业2离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。
本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。
并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100，则G 的边数为( )．A ．5B ．6C ．3D ．4答 D2．设图G ＝<V , E >，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(答 C （握手定理）3．设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的 答 A （有一条经过每个结点的回路）4．给定无向图G 如右图所示，下面给出的结 点集子集中，不是点割集的为（ ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e } 答 B5．图G 如右图所示，以下说法正确的是( )． A ．{(a , c )}是割边 B ．{(a , c )}是边割集 C ．{(b , c )}是边割集 D ．{(a, c ) ,(b, c )}是边割集 答 D6．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 答 D7．若G 是一个欧拉图，则G 一定是( )．A ．平面图B ．汉密尔顿图C ．连通图D ．对偶图答 C8．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 答 A （欧拉公式：v -e +r = 2）9．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 答 A （n 个结点的连通图的生成树有1n -条边，必须删去(1)m n --条边） 10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（ ）．A ．8B ．5C ．4D ．3 解 这棵无向树T 有7条边，所有结点的度数之和为14，而4度、3度、2度的分支点各一个共3个结点占用了9度，所以剩下的5个结点占用5度，故有5片树叶．答 Bο a οο οο b c de 5题图 a b dc eο ο ο ο ο 4题图二、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．解设G有x条边，则由握手定理，112233442x⨯+⨯+⨯+⨯=，15x=答152．设给定图G(如右由图所示)，则图G的点割集是．答{f}、{c,e}3．设G是一个图，结点集合为V，边集合为E，则G的结点等于边数的两倍．答的度数之和4．设有向图D为欧拉图，则图D中每个结点的入度．答等于出度5．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路．答n-16．设无向图G＝<V，E>是汉密尔顿图，则V的任意非空子集V1，都有≤∣V1∣．答W(G-V1)7．设完全图Kn 有n个结点(n≥2)，m条边，当时，Kn中存在欧拉回路．答n为奇数8．设图G=<V,E>，其中|V|=n，|E|=m．则图G是树当且仅当G是连通的，且m=．答n-19．连通无向图G有6个顶点9条边，从G中删去条边才有可能得到G的一棵生成树T．答 410．设正则5叉树的树叶数为17，则分支数为i = ．答4（定理5.2.1：(m-1)i=t-1）三、判断说明题（判断下列各题，并说明理由．）1．(1) 如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．解错误．只有当G是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路．(2) 图G1，(如下图所示) 是欧拉图．解正确．图G1是连通图，有4个2度结点，2个4度结点，即图G1的结点全是偶数度结点，所以是欧拉图．2．图G2（如下图所示）不是欧拉图而是汉密尔顿图．解正确．图G2有4个3度结点a，b，d，f，所以图G2不是欧拉图．图G2有汉密尔顿回路abefgdca，所以图G2是汉密尔顿图．3．(1) 设G是一个有7个结点16条边的连通简单图，则G为平面图．(2) 设G是一个连通平面图，且有6个结点11条边，则G有7个面．解（1）错误．由定理4.3.3知，若G有v个结点e条边，且v≥3，则e≤3v-6．但本题中，16≤3×7-6不成立．（2）正确．由欧拉定理，连通平面图G的结点数为v，边数为e，面数为r，则v-e+r=2．于是有r=2-v+e=2-6+11=7．4．下图给出的树是否同构的．解图(a)有一个4度结点，图(b)、(c)没有4度结点，所以图(a)不与图(b)、(c)同构；在图(b)、(c)中标上结点标号，如下图，建立从图(b)结点到图(c)结点的映射() (1,2,3,4,5)i i f b c i ==，则f 是同构双射，所以图(b )与图(c )同构．四、计算题1．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试(1) 给出G 的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形． 解 （1）G 的图形为：（2）图G 的邻接矩阵为：0010000110110110110100110A ⎛⎫ ⎪ ⎪ ⎪= ⎪ ⎪ ⎪⎝⎭（3）图G 的每个结点的度数为：1deg()1v =，2deg()2v =，3deg()4v =，4deg()3v =，5deg()2v =．（4）图G 的补图为：2．图G =<V , E >，其中V ={a , b , c , d , e , f }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (d , e ), (d , f ), (e , f ) }，对应边的权值依次为5，2，1，2，6，1，9，3及8．(1) 画出G 的图形； (2) 写出G 的邻接矩阵； (3) 求出G 权最小的生成树及其权值． 解 （1）G 的图形如左下图：（2）G 的邻接矩阵为：011010100110100010010011111101000110A ⎛⎫⎪⎪ ⎪=⎪ ⎪ ⎪⎪⎪⎝⎭（3）图G 有6个结点，其生成树有5条边，用Kruskal 算法求其权最小的生成树T ：第1步，取具最小权1的边(a ,e )； 第2步，取剩余边中具最小权1的边(c ,e )；第3步，取剩余边中不与前2条边构成回路的具最小权2的边(b ,d )； 第4步，取剩余边中不与前3条边构成回路的具最小权3的边(d ,f )； 第5步，取剩余边中不与前4条边构成回路的具最小权5的边(a ,b )． 所求最小生成树T 如右下图，其权为()1123512W T =++++=．3．已知带权图G 如右图所示．(1) 求图G 的最小生成树； (2)计算该生成树的权值． 解 （1）图G 有6个结点，其生成树有5条边，用Kruskal算法求其权最小的生成树T ：第1步，取具最小权1的边； 第2步，取剩余边中具最小权2的边；第3步，取剩余边中不与前2条边构成回路的具最小权3的边； 第4步，取剩余边中不与前3条边构成回路的具最小权5的边； 第5步，取剩余边中不与前4条边构成回路的具最小权7的边．所求最小生成树T 如右图．（2）该最小生成树的权为()1235718W T =++++=．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解 所求最优二叉树T 如下图：所求最优二叉树T 的权为：()(23)55473172311131w T =+⨯+⨯+⨯+⨯+⨯=五、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明 设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明 由定理3.1.2知，k 必为偶数．要使这k 个奇数度结点变成偶数度结点，从而使图G 变成欧拉图，可在每两个结点间添加一条边．故在图G 中至少要添加2k条边才能使其成为欧拉图．。
