离散数学期末考试复习题.pdf

《离散数学期末考试复习题.pdf》由会员分享，可在线阅读，更多相关《离散数学期末考试复习题.pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、、判 断 题（共 5 道 小 题，共 5 0.0分）1.如 果 a 克 A u 6,则。史 或。/8.A.正 确 B.错 误 知 识 点：集 合 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示:2.设 科，为 集 合 不 上 的 等 价 关 系，则 臼 餐=齐 1 百 A.正 确 B.错 误 知 识 点：关 系 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示：3.设 A，凸 为 集 合 三 上 的 等 价 关 系，则 月 C R 也 是 集 合 工 上 的 等 价 关 系 A.正 确 B.错 误 知 识 点：关 系 学 生 答 案：A;得 分：10 试 题

2、分 值：10.0提 示：4,设 冰 集 合/上 的 传 递 关 贰 则 独 身 上 的 传 递 关 某 A.正 确 B.错 误 知 识 点：关 系 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：5.(错 误)设 集 合/=&,%，),8=皿,2 则/X 6=VOJ.A.y.%A)A.正 确 B.错 误 知 识 点：关 系 学 生 答 案：A;得 分：0 试 题 分 值：10.0提 示：二、单 项 选 择 题(共 5 道 小 题，共 5 0.0分)1.设 儿 B,C是 集 合，贝 I J()成 立.A.如 果 B.如 果 匚 CJWAW CC.如 果 D.如 果 Z u 6

3、w C j B U u C知 识 点：集 合 学 生 答 案：B;得 分：10提 示：试 题 分 值：10.02.设=&，。,则 下 列 各 式 中 错 误 的 是 A 1 3B.BG()2MD U 2,知 识 点：集 合 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示：3.(错 误)下 列 各 式 中 不 正 确 的 是 A.嫉 CB.*阑 C.*3D.”依 知 识 点：集 合 学 生 答 案：B;得 分：0 试 题 分 值：10.0提 示：4.设 点 为 实 数 集 合，下 列 集 合 中 哪 一 个 不 是 空 集 A x|x，-1=0.且 x w/?B(x p14-9

4、 0,3 x/$)C x X=X+L&XW 虐 Dx|xa=-t f i j c e知 识 点：集 合 学 生 答 案：A；得 分：10 试 题 分 值：10.0提 示：5.设，=1%,8=I，瓦 乡，则/（J 8 的 恒 等 关 系 为 A,B.)C.D.,I。知 识 点：关 系 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：-、判 断 题（共 5 道 小 题，共 5 0.0分）1.设 是 代 数 系 统 8,0 的 元 素，如 果=,是 该 代 数 系 统 的 单 位 元）,则。T=bA.正 确 B.错 误 知 识 点：代 数 系 统 的 基 本 概 念 学 生 答 案

5、：A;得 分：10 试 题 分 值：10.0提 示：2.集 合 A上 的 任 一 运 算 对 A是 封 闭 的.A.正 确 B.错 误 知 识 点：代 数 系 统 的 基 本 概 念 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：3.设 5 是 群.如 果 对 于 任 意 4 力 W G,有（0 8?=功，则 是 阿 贝 尔 群.A.正 确 B.错 误 知 识 点：群、环 和 域 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：4.设 是 布 尔 代 数，则 对 任 意。A w B,有 内=A.正 确 B.错 误 知 识 点：格 和 布 尔 代 数 学 生

6、 答 案：A;得 分：10 试 题 分 值：10.0提 示：5.设 集 合 则 依-9，肛 3 八 是 格.A.正 确 B.错 误 知 识 点：格 和 布 尔 代 数 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：二、单 项 选 择 题（共 5 道 小 题，共 5 0.0分）1.下 列 哪 个 集 关 于 减 法 运 算 是 封 闭 的 A.”（自 然 数 集）B.3 工 W Z（蛔 婢 C（2X+1|X Z）D 1*1母 甫 切知 识 点：代 数 系 统 的 基 本 概 念 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示：下 列 定 义 的 实 数 集

7、R上 的 运 算*中 可 结 合 的 是 A.。&B.a b=a+2 a-bC.ab=bD.。*=卜/知 识 点：代 数 系 统 的 基 本 概 念 学 生 答 案：c得 分：0 试 题 分 值：10.0提 示：3.在 整 数 集 上，下 列 哪 种 运 算 是 可 结 合 的 A=a-bBC.=a+2bD a9b知 识 点：代 数 系 统 的 基 本 概 念 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示:4.循 环 群 伊 用 的 所 有 生 成 元 为 A.1,0B.-1,2C.1,2D.1,-1知 识 点：群、环 和 域 学 生 答 案：D得 分：0 试 题 分 值：

8、10.0提 示：设 代 数 系 统（4 则 下 面 结 论 成 立 的 是.A.如 果 下 是 群，则 是 阿 贝 尔 群 B.如 果 4 4:是 阿 贝 尔 群，则；4：是 循 环 群 C.如 果（A 是 循 环 群，则 三 A:，是 阿 贝 尔 群 D.如 果:是 阿 贝 尔 群，则 匕 4 必 不 是 循 环 群 知 识 点：群、环 和 域 学 生 答 案：C得 分：0 试 题 分 值：10.0提 示:一、判 断 题（共 5 道 小 题，共 5 0.0分）1.强 连 通 有 向 图 一 定 是 单 向 连 通 的 A.正 确 B.错 误 知 识 点：无 向 图 和 有 向 图 学 生 答

9、 案：A;得 分：10 试 题 分 值：10.0提 示：2.有 生 成 树 的 无 向 图 是 连 通 的 A.正 确B.错 误 知 识 点：树 学 生 答 案：AJ得 分：10提 示：试 题 分 值：10.03.设 尸，0都 是 命 题 公 式，则 y 充 分 必 要 条 件 为 尸 T Q Q LA.正 确 B.错 误 知 识 点：命 题 逻 辑 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：4.设 P Q都 是 命 题 公 式，则 P=Q 也 是 命 题 公 式 A.正 确 B.错 误 知 识 点：命 题 逻 辑 学 生 答 案：B;得 分：10 试 题 分 值：10

10、.0提 示：5.“如 果 8+7 2,则 三 角 形 有 四 条 边”是 命 题 A.正 确 B.错 误 知 识 点：命 题 逻 辑 学 生 答 案：A;得 分：10 试 题 分 值：10.0提 示：二、单 项 选 择 题（共 5 道 小 题，共 5 0.0分）1.设 G=：忆，G=（乙 瓦）都 是 无 向 图，贝 叩 匕 中 心 且#6=#氏 是 G与&司 构 的 A.充 分 必 要 条 件 B.充 分 而 非 必 要 条 件 C.必 要 而 非 充 分 条 件 D.既 非 充 分 乂 非 必 要 条 件 知 识 点：无 向 图 和 有 向 图 学 生 答 案：C得 分：0 试 题 分 值：

11、10.0提 示:有 向 图。=匕 君，其 中,E=.c.,则 有 向 图 G=匕 是 A.强 连 通 图 B.单 向 连 通 图 C.弱 连 通 图 D.不 连 通 图 知 识 点：无 向 图 和 有 向 图 学 生 答 案：C得 分：0 试 题 分 值：10.0提 示：3.是 无 向 图。=的 关 联 矩 阵，”e V 是，了 中 的 孤 立 点，则 A.1对 应 的 一 行 元 素 全 为 0B.0 对 应 的 一 行 元 素 全 为 1C.7 对 应 的 一 列 元 素 全 为 0D.3 对 应 的 一 列 元 素 全 为 1知 识 点：图 的 矩 阵 表 示 学 生 答 案：A;得 分

12、：10 试 题 分 值：10.0提 示：4.由 前 提。得 到 的 有 效 结 论 为 A.-1SB.QC.PD.-5知 识 点：命 题 逻 辑 学 生 答 案：C得 分：0 试 题 分 值：10.0提 示：5.设 个 体 域 4=9,劫，公 式 G*)代 外 八 在 遇 上 消 去 量 词 后 应 为 A.N X)八 次 冷 B.既 M 侬 八 GS(a)vS)c.知 识 点：一 阶 逻 辑 学 生 答 案：B;得 分：10 试 题 分 值：10.0提 示：离 散 数 学 期 末 复 习 题 第 一 章 集 合 论一、判 断 题(1)空 集 是 任 何 集 合 的 真 子 集.(错)(2)研

13、 是 空 集.（错)(3)aea,a（对)(4)设 集 合 A=1,2,1,2,则 1,2 c 2（对)(5)如 果。任 则。任 A 或 a 8.（错)解 a 任 A u B 则 即 Q E A 且 Q E B,所 以。史 A 且 B(6)如 果 A U 6=8,则 A q B.（对)(7)设 集 合 A=4,勺，4，8=仇 力 2/3，则 A x B=,（错)(8)设 集 合 A=0,1,则 夕=,是 2 至！J A 的 关 系.(对)解 2=。,0,1,。,2AX A=,（9）关 系 的 复 合 运 算 满 足 交 换 律.（错）（10）。P=P 是 集 合 A 上 的 关 系 具 有 传

14、 递 性 的 充 分 必 要 条 件.（错）（11）设 夕 是 集 合 A 上 的 传 递 关 系，则 万 也 是 A 上 的 传 递 关 系.（对）（12）集 合 力 上 的 对 称 关 系 必 不 是 反 对 称 的.（错）（13）设 为 集 合 A 上 的 等 价 关 系，则 q c q 也 是 集 合 A 上 的 等 价 关 系（对）（14）设 夕 是 集 合 A 上 的 等 价 关 系，则 当 e p 时，ap=hp（对）（15）设 夕”2为 集 合 A 上 的 等 价 关 系，则 臼。2=瓦。离（错）二、单 项 选 择 题（1）设 R 为 实 数 集 合，下 列 集 合 中 哪 一

15、 个 不 是 空 集（A）A.I x2-1=0,.,x e R B.X I X?+9=0,.且 X G/?C.X I X=X+1,_BJ C W R D.x x2=e R（2）设 A,B为 集 合，若 A B=,则 一 定 有（C）A.B=(/)B.8 W 0(3)下 列 各 式 中 不 正 确 的 是 A.q B.“C.A Q BC.(j)u(f)D.A o B(C)D.他 0(4)设 4=凡 仅,则 下 列 各 式 中 错 误 的 是 B）A.ae 2A B.a2A C.aw2“D.=2（5）设 人=1,2,B=a,b,c,C=c,d,则 A x（B n C）为（B）A.,B.,C.,D.

16、,（6）设 4=0,6,B=1,仇 3,则 A U 8 的 恒 等 关 系 为（A）A.,B.,C.,D.,（7）设 4=,6,0上 的 二 元 关 系 如 下，则 具 有 传 递 性 的 为（D）A.p,=,B.p2=,C.py=,D.pA=（8）设 P 为 集 合 A 上 的 等 价 关 系，对 任 意。e A,其 等 价 类 a。为（B）A.空 集；B.非 空 集；C.是 否 为 空 集 不 能 确 定；D.xlxwA.（9）映 射 的 复 合 运 算 满 足（B）A.交 换 律 B.结 合 律 C.易 等 律 D.分 配 律（10）设 A,B 是 集 合，则 下 列 说 法 中（C）是

17、 正 确 的.A.A 到 B 的 关 系 都 是 A 到 B 的 映 射 B.A 到 8 的 映 射 都 是 可 逆 的 C.A 到 B 的 双 射 都 是 可 逆 的 D.A u 8 时 必 不 存 在 A 到 B 的 双 射（II）设 A 是 集 合，则（B）成 立.A.#2=2#AB.X w 2 X=AC.%e 2AD.Aw2（12）设 A 是 有 限 集（#A=），则 A 上 既 是 又 是 的 关 系 共 有（B）.A.0 个 B.1个 C.2 个 D.个三、填 空 题 1.设 4=1,2,1,2,则 2.=.填 2*=。,2,1,2,1,2,1,1,2,2,1,2,42.设 4=。

18、,。,则 2*=.填 2*=,0,A3.设 集 合 A,8 中 元 素 的 个 数 分 别 为#A=5,#B=7,且#(AuB)=9,则 集 合 A C 8 中 元 素 的 个 数#(Ac 8)=.34.设 集 合 4=%11%4100,%是 4的 倍 数，xeZ),B=11 4 x 4 100,x是 5的 倍 数，x&Z,则 A U B 中 元 素 的 个 数 为.405.设 A=a,b,夕 是 2 A 上 的 包 含 于 关 系，则 有 P=,b,A,)6.设 p、,p2为 集 合 A 上 的 二 元 关 系，则 p、。P=.p-y Pi7.集 合 A 上 的 二 元 关 系 p 为 传

19、递 的 充 分 必 要 条 件 是.p o p p8.设 集 合 A=0,l,2上 的 关 系 q=,及 集 合 A 到 集 合 8=0,2,4的 关 系 q=|e Ax B且 a,e A n 8,贝 Uq 0 Pl=,填,四、解 答 题 1.设 I=a,6,c,d,A上 的 关 系 p=,(1)写 出 P 的 关 系 矩 阵；(2)验 证 是 A 上 的 等 价 关 系；(3)求 出 A 的 各 元 素 的 等 价 类。解(1)0 的 关 系 矩 阵 为 1 1 0 0、1 1 0 0M-0 0 1 1、0 0 1 1?(2)从 P 的 关 系 矩 阵 可 知：夕 是 自 反 的 和 对 称

20、 的。又 由 于 1 1 0 0、1 1 0 0、1 1 0 0、1 1 0 0 1 1 0 0 1 1 0 0Mp、。M p门=O M,0 0 1 1 0 0 1 1 0 0 1 1P、0 0 1 1,、0 0 1 1,、0 0 1 1,或 po P=P 满 足 p o p j p所 以 是 传 递 的。因 为 是 自 反 的、对 称 的 和 传 递 的，所 以 是 A 上 的 等 价 关 系。（3）a=b=a,b,c=d=c,d2.设 集 合 A=1,2,3,6,8,12,24,36,夕 是 A 上 的 整 除 关 系,（1）写 出 P 的 关 系 矩 阵 M。；（2）画 出 偏 序 集

21、的 哈 斯 图；（3）求 出 A 的 子 集 6=2,3,6的 最 小 上 界 和 最 大 下 界。(2)0 1 0 1 1 1 1 10 0 1 1 0 1 1 10 0 0 1 0 1 1 1解：M,=P0 0 0 0 1 0 1 00 0 0 0 0 1 1 10 0 0 0 0 0 1 00 0 0 0 0 0 0 1(3)lubB=6,glbB=l五、证 明 题 1.设 8,0 为 集 合 A 上 的 等 价 关 系，试 证 自 C R 也 是 集 合 A 上 的 等 价 关 系。证 明：由 于 a 是 自 反 的，所 以 对 任 意 a w 4,8，e p2,因 而 e 8 c 0

22、?，即 Pi c q 是 自 反 的。若 e p|C 0 2，则 Pi，e pz,由 于 p,p2 是 对 称 的，所 以 e px,e p2,从 而 e 2 c q，即 0 e g 是 对 称 的。若,b,c w P c 2 2，则,b,c p、,G P？，由 于 Pi，22 是 传 递 的，所 以 a,c eq,e p2,从 而 e q c/，即 q c o；是 传 递 的。由 于 8 C 是 自 反 的、对 称 的 和 传 递 的，所 以 8 c p 2是 等 价 关 系。第 二 章 代 数 系 统 一、判 断 题（1）集 合 A 上 的 任 一 运 算 对 A 是 封 闭 的.（对）（

23、2）代 数 系 统 的 零 元 是 可 逆 元.（错）（3）设 A 是 集 合，:AxA-A,aob=b,则。是 可 结 合 的.（对)(4)设 a,b是 代 数 系 统 4,。的 元 素，(对)(5)设 是 群 G,的 元 素，则(4/广=人(6)设 G,-是 群.如 果 对 于 任 意。力 e G,群.(7)设 L,v,人 是 格,则 运 算 v 满 足 嘉 等 律.(8)设 集 合 A=伍,与，则 Ma,6,A,u,c 是 格.(9)设 8,v,，-是 布 尔 代 数，则 8,v 是 格.二、单 项 选 择 题(1)在 整 数 集 Z 上，下 列 哪 种 运 算 是 可 结 合 的 A.

24、a。b=a-b B.ab=max,bC.a。b=a+2b D.(2)下 列 定 义 的 实 数 集 R 上 的 运 算*中 可 结 合 的 是.A.a*b=a+a bB.a*b=a+2a bC.a*b=bD.Q*/?=|a+W其 中，+，I I分 别 为 实 数 的 加 法、乘 法 和 取 绝 对 值 运 算.(3)设 集 合 A=1,2,3,4,，10,则 a-=b.（错）有（a-b）2 a2-b2,则 6,-是 阿 贝 尔（对）（对）（对）（对）（B）（C）如 果。匕=0oa=e(e是 该 代 数 系 统 的 单 位 元),卜 面 定 义 的 哪 种 运 算 关 于 集 合 A 不 是 封

25、 闭 的(D)A.尤。y=maxx,yB.x。y=minx,yC.xoy=GCDx.y,即 x,y 的 最 大 公 约 数 D.xo y=LCMx,y,即 尤，y 的 最 小 公 倍 数(4)下 列 哪 个 集 关 于 减 法 运 算 是 封 闭 的(B)A.N(自 然 数 集)；B.2xlxeZ(整 数 集)卜 C.2x+11 x e Z；D.xlx是 质 数.(5)设。是 有 理 数 集，在。定 义 运 算*为 a*b=a+b a b,贝 乂。,*)的 单 位 元 为(D)A.a；B.b；C.1；D.0(6)设 代 数 系 统 A,，则 下 面 结 论 成 立 的 是.(C)A.如 果 A

26、,是 群，则 A,是 阿 贝 尔 群B.如 果 A,是 阿 贝 尔 群，贝 式 4,是 循 环 群 C.如 果 A,是 循 环 群，贝 RA,是 阿 贝 尔 群 D.如 果 4,是 阿 贝 尔 群，则 A,必 不 是 循 环 群(7)循 环 群(Z,+)的 所 有 生 成 元 为(D)A.1,0 B.-1,2 C.1,2 D.1,-1三、填 空 题 1.设 A 为 非 空 有 限 集，代 数 系 统 2%U 中，2A对 运 算 U 的 单 位 元 为，零 元 为.填。,A2.代 数 系 统 Z,+中(其 中 Z 为 整 数 集 合，+为 普 通 加 法)，对 任 意 的 x e/,其 x=.填

27、-x3.在 整 数 集 合 Z 上 定 义。运 算 为 aob=a+2+b,则 Z,。的 单 位 元 为.解 设 单 位 元 为 e,a0 e=a+2+e=a,所 以 e=-2,又。(-2)=a+2+(-2)=a,(-2)。a=(-2)+2+a=a,所 以 单 位 元 为 e=-24.在 整 数 集 合 Z 上 定 义。运 算 为 aob=a+b ab,则 Z,。的 单 位 元 为.解 设 单 位 元 为 e,a0e=a+e-ae=a,(l-a)e=O,所 以 e=05.设(G,)是 群，对 任 意 a,b,ceG,如 果 a/=:,则.填 人=c6.设(G,)是 群，e为 单 位 元，若 G

28、 元 素 a满 足/=“，则。=.填 e四、解 答 题 1.设。为 实 数 集 R 上 的 二 元 运 算，其 定 义 为。：A?.R,a0b=a+b+2ab,对 于 任 意 求 运 算。的 单 位 元 和 零 元。解：设 单 位 元 为 e,则 对 任 意 a e R,有 a。e=a+e+2ae=a,即 e(l+2a)=0,由 a 的 任 意 性 知 e=0,又 对 任 意 a w R，4。0=。+0+0=。；0。=0+“+0=。所 以 单 位 元 为 0设 零 元 为。，则 对 任 意 a w R,有 ao6=a+e+2a6=。，即 a(l+26)=0,由。的 任 意 性 知 6=又 对

29、任 意 Q G R,a o(-)=a-a=,(一 工)。=-+a-a-2 2 2 2 2 2所 以 零 元 为-L22.设。为 集 合 人=0,1,2,3,4上 的 二 元 运 算，其 定 义 为 0:/5/5,ab-(a/?)mod5,对 于 任 意 a,6 G 心(1)写 出 运 算。的 运 算 表；(2)说 明 运 算。是 否 满 足 交 换 律、结 合 律，是 否 有 单 位 元 和 零 元、如 果 有 请 指 出;(3)写 出 所 有 可 逆 元 的 逆 元 解：(1)运 算 表 为O0 1 2 3 40 0 0 0 0 01 0 1 2 3 42 0 2 4 1 33 0 3 1

30、4 24 0 4 3 2 1(2)运 算。满 足 交 换 律、结 合 律，有 单 位 元，单 位 元 为 1,有 零 元，零 元 为 0；(3)1 的 逆 元 为 1,2 的 逆 元 为 3,3 的 逆 元 为 2,4 的 逆 元 4,0 没 有 逆 元 五、证 明 题 1.设 G,。是 一 个 群，试 证 G 是 交 换 群 当 且 仅 当 对 任 意 的。，匕 w G，有 a2 b2-(a o h)2.证 明：充 分 性 若 在 群 G,。中，对 任 意 的，有/=(。人 了.则(。)。(6。6)=(。匕)。(。匕)ao(aob)ob=ao(boa)obab-boa从 而 G,。是 一 个

31、 交 换 群。必 要 性 若 G,。是 一 个 交 换 群，对 任 意 的 a,b e G，有 a。/?=/?。a,则 a0(aob)oh-ao(boa)ob(a o a)o(匕 匕)=(a/7)o(a o b)即/=3。勿 2.2.证 明 代 数 系 统 Z,。是 群，其 中 二 元 运 算。定 义 如 下：。：Z,xoy=x+y-3(这 里，+,一 分 别 是 整 数 的 加 法 与 减 法 运 算.)证 明(1)运 算 满 足 交 换 律 对 任 意 x,y,z e Z,由(x y)z=(x+y-3)z=x+y+z-6,x 0(y 0 z)=xo(y+z-3)=x+y+z-6得(x。y)

32、。z=x。(y。z),即。满 足 结 合 律;(2)有 单 位 元 3 是 单 位 元；(3)任 意 元 素 有 逆 元 对 任 意 xez,=6-尤.所 以，Z,。是 群.第 三 章 图 论 一、判 断 题(1)n 阶 完 全 图 的 任 意 两 个 不 同 结 点 的 距 离 都 为 1.(对（2）图 G 的 两 个 不 同 结 点 匕,匕 连 接 时 一 定 邻 接.（错）（3）图 G 中 连 接 结 点 匕，匕 的 初 级 通 路 为 匕，之 间 的 短 程.（错）（4）在 有 向 图 中，结 点 匕 到 结 点 匕 的 有 向 短 程 即 为 匕 到 匕 的 有 向 短 程.（错）（

33、5）强 连 通 有 向 图 一 定 是 单 向 连 通 的.（对）（6）不 论 无 向 图 或 有 向 图，初 级 回 路 一 定 是 简 单 回 路.（对）（7）设 图 G 是 连 通 的，则 任 意 指 定 G 的 各 边 方 向 后 所 得 的 有 向 图 是 弱 连 通 的.（对）（8）有 生 成 树 的 无 向 图 是 连 通 的.（对）（9）下 图 所 示 的 图 是 欧 拉 图.（错）（10）下 图 所 示 的 图 有 哈 密 尔 顿 回 路.（对）二、单 项 选 择 题（1）仅 由 孤 立 点 组 成 的 图 称 为 A.零 图；B.平 凡 图；C.完 全 图；D.多 重 图.

34、（2）仅 由 一 个 孤 立 点 组 成 的 图 称 为 A.零 图；B.平 凡 图；C.多 重 图；D.子 图.（3）在 任 何 图 G 中 必 有 偶 数 个 A.度 数 为 偶 数 的 结 点；B.度 数 为 奇 数 的 结 点；C.入 度 为 奇 数 的 结 点；D.出 度 为 奇 数 的 结 点.（4）设 G 为 有 个 结 点 的 无 向 完 全 图，则 G 的 边 数 为(A)(B)(B)(C)A.n(n-1)B.n(n+1)C.”(-l)/2 D.(n-1)/2（5）在 有 个 结 点 的 连 通 图 G 中，其 边 数 A.最 多-1 条；B.至 少-1 条;C.最 多 条；

35、D.至 少 条.（6）任 何 无 向 图 G 中 结 点 间 的 连 通 关 系 是(B)(B)A.偏 序 关 系；B.等 价 关 系；C.既 是 偏 序 关 系 又 是 等 价 关 系；D.既 不 是 偏 序 关 系 也 不 是 等 价 关 系.（7）对 于 无 向 图，下 列 说 法 中 正 确 的 是.(B)A.不 含 平 行 边 及 环 的 图 称 为 完 全 图 B.任 何 两 个 不 同 结 点 都 有 边 相 连 且 无 平 行 边 及 环 的 图 称 为 完 全 图 C.具 有 经 过 每 条 边 一 次 且 仅 一 次 回 路 的 图 称 为 哈 密 尔 顿 图D.具 有 经

36、 过 每 个 结 点 一 次 且 仅 一 次 回 路 的 图 称 为 欧 拉 图（8）设。是 有 向 图，则。强 连 通 的 充 分 必 要 条 件 为.（C）A.略 去。中 各 边 方 向 后 所 得 到 的 无 向 图 是 连 通 的 B.。是 单 向 连 通 图，且 改 变 它 的 各 边 方 向 后 所 得 到 的 有 向 图 也 是 单 向 连 通 图 C.。的 任 意 两 个 不 同 的 结 点 都 可 以 相 互 到 达 D.。是 完 全 图（9）对 于 无 向 图 G,以 下 结 论 中 不 正 确 的 是.（A）A.如 果 G 的 两 个 不 同 结 点 是 连 接 的，则

37、这 两 个 结 点 之 间 有 初 级 回 路 B.如 果 G 的 两 个 不 同 结 点 是 连 接 的，则 这 两 个 结 点 之 间 至 少 有 一 条 短 程 C.如 果 G 是 树，则 任 何 两 个 不 同 结 点 之 间 有 且 仅 有 一 条 初 级 通 路 D.如 果 G 是 欧 拉 图，则 G 有 欧 拉 回 路 三、填 空 题 1.设 树 T 中 有 7片 树 叶，3 个 3度 结 点，其 余 都 是 4度 结 点，则 T 中 有 一 个 4 度 结 点 解 用 握 手 定 理 和 树 的 性 质 列 出 方 程 求 解，设 有 x 个 4 度 结 点，7+9+4x=2（

38、7+3+x l）,x-12.设 T=为 树，T 中 有 4 度，3度，2度 分 支 点 各 1个，问 T 中 有 一 片 树 叶。解 与 上 题 解 法 相 同，设 有 x 片 树 叶，4+3+2+x=2（3+x 1）,x=53.n 阶 完 全 图 的 任 意 两 个 不 同 结 点 的 距 离 都 为.14.图 G 为 阶 无 向 完 全 图，则 G 共 有 条 边。（一 1）/25.设 G 为（,机）图，则 图 中 结 点 度 数 的 总 和 为。2m6.图 G 为 欧 拉 图 的 充 分 必 要 条 件 是.G 为 无 奇 度 结 点 的 连 通 图 四、解 答 题 1.对 下 图 所

39、示 的 图 G,求（1）G 的 邻 接 矩 阵 A；（2）G 的 结 点 匕,匕 之 间 长 度 为 3 的 通 路;（3）G 的 连 接 矩 阵 C：（4）G 的 关 联 矩 阵 加。匕 乙 匕 以 也 解（1）v(fO 1v2 1 0v3 1 1V4 1 01 1 0、1 0 10 1 11 0 0匕（0 1 1 0 0,（2）因 为所 以，结 点 W，匕 之 间 长 度 为 3 的 通 路 共 有 7 条，它 们 是 3 1 2 1 2、“x x 7 x x1 3 2 2 1 X X X X XA2=2 2 4 1 1 X X X X X1 2 1 2 1 X X X X X 2 1 1

40、 1 2；、x X X X X匕 匕 匕 匕，v,v2v5v3,匕 2 匕 匕，小 冲 3，匕 匕 为 匕，匕 1（3）由 于 图 G 是 连 通 的，所 以 W 彩 匕 打 匕 C=v3 1V4 1以 11 1 1 ri i i ii i i ii i i ii i i i,(4)弓 24q 0 1 1岭 1 1 0 0M=V30 1 1 0匕 0 0 0 1%00 0 00 00 01 11 00 10、100I（1）写 出 图。的 邻 接 矩 阵 A；（2）写 出 结 点 匕 到 结 点 匕 的 长 度 为 3 的 所 有 有 向 通 路;%ek（3）写 出 结 点 匕 到 自 身 的

41、长 度 为 3 的 所 有 有 向 回 路;0 0 0 0 1、1 0 1 0 0解：A=0 0 1 1 00 0 0 0 1、0 1 0 1 0 1 0 1 0、1 0 1 0 1、0 0 1 1 1 0 1 1 2 1(2)A2=0 0 1 1 1 A3=0 1 1 2 10 1 0 1 0 1 0 1 0 10 1 0、0 1 1 2 1,所 以 结 点 匕 到 结 点 匕 的 长 度 为 3 的 所 有 有 向 通 路 只 有 一 条：匕 匕 匕 匕(3)结 点 也 到 自 身 的 长 度 为 3 的 所 有 有 向 回 路 只 有 一 条：匕 匕 匕 匕 3.在 下 面 的 无 向

42、图 G 中，回 答 下 列 问 题(1)写 出 之 间 的 所 有 初 级 通 路；(2)写 出 a,d之 间 的 所 有 短 程，并 求 d(a,d)：(3)判 断 无 向 图 G 是 否 为 欧 拉 图 并 说 明 理 山。解(1)a,d之 间 的 所 有 初 级 通 路 共 有 7条，分 别 为 aed，aecd，aebcd,abed,abed,abecd,abced(2)a,d之 间 的 长 度 最 短 的 通 路 只 有 1条，即 aed,因 而 它 是 a,d之 间 唯 一 的 短 程,d(a,d)=2(3)由 于 无 向 图 G 中 有 两 个 奇 度 顶 点 deg(Z0=3,

43、deg(c)=3,所 以 无 向 图 G 没 有 欧 拉 回 路，因 而 不 是 欧 拉 图。第 四 章 数 理 逻 辑 一、判 断 题(1)“如 果 8+72,则 三 角 形 有 四 条 边”是 命 题.(对)(2)设 P,。都 是 命 题 公 式，则 P O。也 是 命 题 公 式.(错)(3)命 题 公 式 的 真 值 分 别 为 0,1,则 P f Q 的 真 值 为 0(以 上 是 在 对 P,Q 所 包 含 的 命 题 变 元 的 某 个 赋 值 下).(错)(4)设 p:他 生 于 1963年,q:他 生 于 1964年，则 命 题“他 生 于 1963年 或 1964年”可 以

44、 符 号 化 为 pvq.(对)(5)设 P,。都 是 命 题 公 式，则 的 充 分 必 要 条 件 为 尸-。=1.(对)(6)逻 辑 结 论 是 正 确 结 论.(错)（9）设 A,8,C 都 是 命 题 公 式，则（A v B v C）f（A-C）也 是 命 题 公 式.（对）（10）命 题 公 式 P,。的 真 值 分 别 为 0,1,则 P n Q 的 真 值 为 0（以 上 是 在 对 P,。所 包 含 的 命 题 变 元 的 某 个 赋 值 下）.（对）二、单 项 选 择 题（1）下 面 哪 个 联 结 词 不 可 交 换（B）A.A；B.-,C.v；D.（2）命 题 公 式（

45、P A（P/）-q 是（C）A.永 假 式；B.非 永 真 式 的 可 满 足 式；C.永 真 式；D.等 价 式.（3）记 p:他 懂 法 律，q：他 犯 法，则 命 题“他 只 有 懂 法 律，才 不 会 犯 法”可 符 号 化 为（B）.A.p）（jB.-C1-）pC.q pD.p T q（4）下 列 命 题 中 假 命 题 是（B）.A.如 果 雪 不 是 白 的，则 太 阳 从 西 边 出 来 B.如 果 雪 是 白 的，则 太 阳 从 西 边 出 来 C.如 果 雪 不 是 白 的，则 太 阳 从 东 边 出 来 D.只 要 雪 不 是 白 的，太 阳 就 从 西 边 出 来（5）

46、设 A,B 都 是 命 题 公 式，则 A-B 为 可 满 足 式 是 A n 8 的（B）.A.充 分 而 非 必 要 条 件 B.必 要 而 非 充 分 条 件 C.充 分 必 要 条 件 D.既 非 充 分 又 非 必 要 条 件 三、填 空 题 1.设：天 气 很 冷，q:老 王 还 是 来 了，则 命 题“虽 然 天 气 很 冷，但 老 王 还 是 来 了 符 号 化 为.p A q2.设 p：天 下 雨，q-.我 骑 自 行 车 上 班，则 命 题“如 果 天 不 下 雨，我 就 骑 自 行 车 上 班”符 号 化 为.p-73.设 p,q的 真 值 为 0,r,s的 真 值 为

47、1,则 命 题 公 式（p c 厂）人 v s）的 真 值 为.04.设 p,q 的 真 值 为 0,r 的 真 值 为 1,则 命 题 公 式 p v（q 厂）的 真 值 为.0离 散 数 学 综 合 练 习 题 一、判 断 下 列 命 题 是 否 正 确.如 果 正 确，在 题 后 括 号 内 填“/”；否 则，填“X”（1）空 集 是 任 何 集 合 的 真 子 集.（）(2)“是 空 集.()(3)ae a,a()(4)如 果 a e A u B,则“c A 或。任 B.()(5)设 集 合 A=q,%,如，8=4 贝 IAx B-,()(6)设 集 合 A=0,1,则 2=,是 24

48、到 A 的 关 系.()(7)关 系 的 复 合 运 算 满 足 交 换 律.()(8)设 月，0 为 集 合 A 上 的 等 价 关 系，则 8 c p 2也 是 集 合 A 上 的 等 价 关 系()(9)设 夕 是 集 合 A 上 的 等 价 关 系，则 当 a/e P 时，()(10)设 门，金 为 集 合 7 1/匕 的 等 价 关 系，则 q。2 2=万。万 2()(11)集 合 A 上 的 任 一 运 算 对 A 是 封 闭 的.()(12)设 A 是 集 合，。：A x A-A,ab-b,则。是 可 结 合 的.()(13)设 G 是 群.如 果 对 于 任 意。力 e G,有

49、(a-b)2=a2 b则 G,-是 阿 贝 尔 群.()(14)设 a 是 群 6,的 元 素，记“=y I y e G 且 y-a=a-y则”,是 6,-的 子 群.()(15)0,1,2,3,4,max,min 是 格.()(16)设 a,b 是 格 L,v,人 的 任 意 两 个 元 素，则 a/b=b c a/b=a.()(17)设 8,v,，一 是 布 尔 代 数，则 8,v,/是 格.()(18)设 集 合 A=a,。,则。,。,6,4,。,0 是 格.()0=b(19)设 B,v,八，是 布 尔 代 数，则 对 任 意 有 a/b-a/b.()(20)设 B,v,，一 是 布 尔

50、 代 数，则 对 任 意。e B,都 有 e B,使 得 a v b=1,a/b=0.()(21)n 阶 完 全 图 的 任 意 两 个 不 同 结 点 的 距 离 都 为 1.()(22)在 有 向 图 中，结 点 匕 到 结 点 匕 的 有 向 短 程 即 为 匕 到 匕 的 有 向 短 程.()(23)强 连 通 有 向 图 一 定 是 单 向 连 通 的.()(24)不 论 无 向 图 或 有 向 图，初 级 回 路 一 定 是 简 单 回 路.()(25)设 图 G 是 连 通 的，则 任 意 指 定 G 的 各 边 方 向 后 所 得 的 有 向 图 是 弱 连 通 的.()(26