《2022年2022年离散数学试卷二十试题与答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学试卷二十试题与答案 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、试卷二十试题与答案一、填空 20%（每空 2 分）1n 个命题变元有个互不等价的极小项。2 按 De-Morgan 定理，ininAAAA121= 。3公式)(RQP的主析取范式为。4设 P(x)：x 是大象， Q(x)： x 是老鼠， R(x,y) ：x 比 y 重，则命题“大象比老鼠重”的符号化为。5设,cbaX，X 上的关系R 的关系矩阵是111011101RM，则RRM。6 在 具 有n个 结 点 的 有 向 图 中 ， 任 何 基 本 通 路 的 长 度 都 不 超过。7任何图的点连通度)(G，边连通度)(G，最小点度)(G的关系为。8 结 点 数n （3n） 的 简 单 连 通 平
2、 面 图 的 边 数 为m ， 则m与n的 关 系为。9群 G 的非空子集H 是 G 的子群当且仅当若x , yH 则。10代数系统,A是环，若对运算“”还满足则,A是整环。二、选择 10%（每小题 2分）1集合,2NnxxAn对（）运算封闭。A、加法；B、减法；C、乘法；D、yx。2设 I 为整数集合， m 是任意正整数，mZ是由模 m 的同余类组成的同余类集合，在mZ上定 义 运 算m o d)(mjiji， 则 代 数 系 统mmZ,最 确 切 的 性 质 是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -
3、 - - - - - - 第 1 页，共 5 页 - - - - - - - - - （） 。A、封闭的代数系统；B、半群；C、独异点；D、群。3设,N是偏序格，其中N 是自然数集合， “ ”是普通的数间“小于等于”关系，则Nba,有ba（） 。A、a ；B、b ；C、max(a，b) ；D、min(a，b)。4连通非平凡的无向图G 有一条欧拉回路当且仅当图G ( )。A、只有一个奇度结点；B、只有两个奇度结点；C、只有三个奇度结点；D、没有奇度结点。5设无向图EVG,是连通的且mEnV,若（）则 G 是树。A、M=N+1 ；B、n=m+1 ；C、63nm；D、63mn。三、12%逻辑推理：符
4、号化命题“有些病人相信医生， 但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。 （P(x)：x 是病人， D(x)：x 是医生， Q(x)：x 是法轮功练习者，L(x , y)： x 相信 y）四、序关系 8%：设,54321xxxxxA，偏序集RA,的 Hass 图为求 A 中最小元与最大元；,543xxx的上界和上确界，下界和下确界。五、函数 8% 设ZYgYXf:和是映射且使得fg是满射，若 g 是入射，证明 f 是满射。六、图 8% 设 G 是连通简单平面图，结点数为n（3n） ，边数为m，面数为 r，则42nr。七、树的应用12% 设 7 个符号在通讯中使用的频率
5、如下：a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ， g ：5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。八、道路的基本性质10% 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 设 u ，v 是树 T 的两个不同的结点，从u 至 v 的基本通路（结点不同的道路）是T 中最长的基本道路，证明：d(u)=d(v)=1 。九、子群 12% 若
6、H 是 G 的子群，Gba,，则bHaHHab1。答案一、填空 20% 1、n2；2、)(1iniA；3、7,5,4,3,2,1,0)()()()()()()(RQPRQPRQPRQPRQPRQPRQP；4、),()()(yxRyQxPyx；5、111111111；6、n-1 ；7、)()()(GGG；8、63nm；9、Hyx1；10、含幺元，可交换，无零因子。二、选择 10% 题号1 2 3 4 5 答案C B C D B 三、12% 解：前提：)(),()(,),()()(yQyxLyxPxyxLyDyxPx结论：)()(yQyDy演绎推理：（1）),()()(yxLyDyxPxP （2）
7、),()()(yeLyDyePES(1) （3）)(),()(yQyxLyxPxP （4）)(),()(yQyeLyePUS(3) （5）)(ePT(2)I （6）)(),(yQyeLyT(4)(5)I 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - （7）)(),(cQceLUS(6) （8）),()(yeLyDyT(2)I （9）),()(ceLcDUS(8) （10）)()(cQcDT(9)(7)I （11）)()(yQy
8、DyUG(10) 四、解： A 中最大元为1x，最小元不存在；,543xxx上界31,xx，上确界1x；下界无，下确界无。五、解：证：Yy，因g是映射，故必存在Zz使zyg)(，由于zxfg)(即)()(ygzxfg，因g是单射，所以yxf)(说明Yy，必有Xx使得yxf)(，故)( xf是满射。六、解：证：因为G 是结点数3n的简单连通平面图，所以63nm，又由于2m且连通简单平面图的每个面至少有3条边围成，于是)63(223nmr， 所以42nr。七、解：用 100 乘各频率得权数：w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列
9、用Huffman 算法可求得最优树。5 5 10 10 15 20 35 10 10 10 15 20 35 20 10 15 20 35 20 25 20 35 40 25 35 4060 100 最优二叉树为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 编码树为：前缀码： a：11； b：0000；g：0001 八、解：设l为 T 中最长的基本道路且以u 为起点， v 为终点，即vvvuvlk21如果1)(ud， 则 u
10、的邻接点除了1v之外还有一点，不妨设为1u，而1u不在l上，否则T 中存在回路uuvuv121即与 T 为树矛盾。于是得到一条vvvuvulk211是比l更长的基本道路，这与l是最长的道路矛盾，故1)(ud。同理可证1)(vd。九、证：因为HbaabHab1111）（所以，又aHbbaabaab)()(11bHaabbabba)()(11bHhhbhhbhaxaHx)()(111bHaH同理可证aHbH所以bHaH故aHbHaH若bHaH设bHaHx则Hhh21,使21hbhax可得：Hhhab1121。u v1 vk v u v1 u1 vk v名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -