《离散数学模拟试题_中学教育-中考.pdf》由会员分享，可在线阅读，更多相关《离散数学模拟试题_中学教育-中考.pdf（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备 欢迎下载 离散数学模拟试卷一 一、填空 20%（每小题 2 分）1设 7|),5()(|xExxBxNxxA且且（N：自然数集，E+正偶数）则 BA 。2A，B，C 表示三个集合，文图中阴影部分的集合表达式为 。3设 P，Q 的真值为 0，R，S 的真值为 1，则)()(SRPRQP的真值=。4公式PRSRP)()(的主合取范式为 。5若解释 I 的论域 D 仅包含一个元素，则)()(xxPxxP 在 I 下真值为 。6设 A=1，2，3，4，A 上关系图为 则 R2=。7设 A=a，b，c，d，其上偏序关系 R 的哈斯图为 则 R=。8图的补图为 。9设 A=a，b，c，d，A 上
2、二元运算如下：A B C 学习必备 欢迎下载*a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10下图所示的偏序集中，是格的为 。二、选择 20%（每小题 2 分）1、下列是真命题的有（）A aa；B,；C ,；D。2、下列集合中相等的有（）A4，3；B，3，4；C4，3，3；D 3，4。3、设 A=1，2，3，则 A 上的二元关系有（）个。A 23；B 32 ；C 332；D 223。4、设 R，S 是集合 A 上的关系，则下列说法正确的是（）A若 R，S 是自反的，则SR是自反的；
3、B若 R，S 是反自反的，则SR是反自反的；C若 R，S 是对称的，则SR是对称的；D若 R，S 是传递的，则SR是传递的。5、设 A=1，2，3，4，P（A）（A 的幂集）上规定二元系如下|(|)(,|,tsAptstsR则 P（A）/R=（）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定
4、二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 AA；BP(A)；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A 6、设 A=，1，1，3，1，2，3 则 A 上包含关系“”的哈斯图为（）7、下列函数是双射的为（）Af:IE,f(x)=2x；Bf:NNN,f(n)=；Cf:RI,f(x)=x；Df:IN,f(x)=|x|。（注：I整数集，E偶数集，
5、N自然数集，R实数集）8、图 中 从 v1到 v3长度为 3 的通路有（）条。A 0；B 1；C 2；D 3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（）10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该树有（）个 4度结点。A1；B2；C3；D4。三、证明 26%、R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当 和在 R 中有在 R 中。（8 分）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎
6、下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载、f 和 g 都是群到的同态映射，证明是的一个子群。其中 C=)()(|1xgxfGxx 且 (8 分)、G=(|V|=v，|E|=e)是每一个面至
7、少由 k（k3）条边围成的连通平面图，则2)2(kvke，由此证明彼得森图（Peterson）图是非平面图。（11 分）四、逻辑推演 16%用 CP 规则证明下题（每小题 8 分）1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx 五、计算 18%1、设集合 A=a，b，c，d上的关系 R=,用矩阵运算求出 R 的传递闭包 t(R)。（9 分）2、如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素
8、则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 模拟试卷二 一、填空 20%（每小题 2 分）1、P：你
9、努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。2、论域 D=1，2，指定谓词 P P(1,1)P(1,2)P(2,1)P(2,2)T T F F 则公式),(xyyPx真值为 。2、设 S=a1，a2，a8，Bi是 S 的子集，则由 B31所表达的子集是 。3、设 A=2，3，4，5，6 上的二元关系|,是质数xyxyxR，则 R=（列举法）。R 的关系矩阵 MR=。5、设A=1，2，3，则A上 既 不 是 对 称 的 又 不 是 反 对 称 的 关 系R=；A 上既是对称的又是反对称的关系R=。6、设代数系统，其中 A=a，b，c,则 幺
10、 元 是 ；是 否 有 幂 等 性 ；是否有对称性 。7、4 阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n 个结点的无向完全图 Kn的边数为 ，欧拉图的充要条件是*a b c a b c a b c b b c c c b 集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下
11、则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 。10、公式RQPQPP)()(的根树表示为 二、选择 20%（每小题 2 分）1、在下述公式中是重言式为（）A)()(QPQP；B)()()(PQQPQP；CQQP)(；D)(QPP。2、命题公式)()(PQQP 中极小项的个数为（），成真赋值的个数为（）。A0；B1；C2；D3。3、设2,1,1,S，则 S2 有（）个元素。A3；B
12、6；C7；D8。4、设 3 ,2 ,1 S，定义SS上的等价关系,|,cbdaSSdcSSbadcbaR则由 R 产 生的SS 上一个划分共有（）个分块。A4；B5；C6；D9。5、设 3 ,2 ,1 S，S 上关系 R 的关系图为 则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。6、设,为普通加法和乘法，则（）,S是域。A,3|QbabaxxS B,2|ZbanxxS C,12|ZnnxxS D 0|xZxxS=N。7、下面偏序集（）能构成格。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下
13、真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 8、在如下的有向图中，从 V1到 V4长度为 3 的道路有（）
14、条。A1；B2；C3；D4。9、在如下各图中（）欧拉图。10、设 R 是实数集合，“”为普通乘法，则代数系统 是（）。A群；B独异点；C半群。三、证明 46%1、设 R 是 A 上一个二元关系，),(),(|,RbcRcaAcAbabaS且有对于某一个试 证明若 R 是 A 上一个等价关系，则 S 也是 A 上的一个等价关系。（9 分）2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11 分）3、若BAf:是从 A 到 B 的函数，定义一个函数ABg2:对任意Bb有)()(|)(bxfAxxbg，证明：若 f 是 A 到 B 的满射，则 g 是从
15、B 到 A2 的单射。（10 分）4、若无向图 G 中只有两个奇数度结点，则这两个结点一定连通。（8 分）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证
16、是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 5、设 G 是具有 n 个结点的无向简单图，其边数2)2)(1(21nnm，则 G 是Hamilton 图（8 分）四、计算 14%1、设是一个群，这里+6是模 6 加法，Z6=0 ，1，2，3，4，5，试求出的所有子群及其相应左陪集。（7 分）2、权数 1，4，9，16，25，36，49，64，81，100 构造一棵最优二叉树。（7 分）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈
17、斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 模拟试卷三 填空 20%（每空 2 分）1、设 f，g 是自然数集 N 上的函数xxgxxfNx2)
18、(,1)(,，则)(xgf 。2、设 A=a，b，c，A 上二元关系 R=,则 s（R）=。3、A=1，2，3，4，5，6，A 上二元关系|,是素数yxyxT，则用列举法 T=；T 的关系图为 ；T 具有 性质。4、集合2,2,A的幂集 A2=。5、P，Q 真值为 0；R，S 真值为 1。则)()()(SRQPSRPwff的真值为 。6、RRQPwff)(的主合取范式为 。7、设 P（x）：x 是素数，E(x)：x 是偶数，O(x)：x 是奇数 N(x,y)：x 可以整数 y。则谓词),()()(xyNyOyxPxwff的自然语言是 。8、谓词),(),(),(uyxuQzyPzxPzyxwf
19、f的前束范式为 。二、选择 20%（每小题 2 分）1、下述命题公式中，是重言式的为（）。A、)()(qpqp；B、)()()(pqqpqp；C、qqp)(；D、qpp)(。2、rqpwff)(的主析取范式中含极小项的个数为（）。A、2；B、3；C、5；D、0；E、8。3、给定推理)()(xGxFx P)()(yGyF US)(xxF P 集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若
20、是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载)(yF ES)(yG TI)(xxG UG)()()(xxGxGxFx 推理过程中错在（）。A、-;B、-;C、-;D、-;E、-4、设 S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=
21、3，5，在条件31SXSX且下 X 与（）集合相等。A、X=S2或 S5；B、X=S4或 S5；C、X=S1，S2或 S4；D、X 与 S1，S5中任何集合都不等。5、设 R 和 S 是 P 上的关系，P 是所有人的集合，,|,的父亲是yxPyxyxR，,|,的母亲是yxPyxyxS则RS1表示关系（）。A、,|,的丈夫是yxPyxyx；B、,|,的孙子或孙女是yxPyxyx；C、；D、,|,的祖父或祖母是yxPyxyx。6、下面函数（）是单射而非满射。A、12)(,:2xxxfRRf；B、xxfRZfln)(,:；C、的最大整数表示不大于 xxxxfZRf,)(,:；D、12)(,:xxfR
22、Rf。其中 R 为实数集，Z 为整数集，R+，Z+分别表示正实数与正整数集。7、设 S=1，2，3，R 为 S 上的关系，其关系图为 则 R 具有（）的性质。A、自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。8、设2,1,1,S，则有（）S。A、1,2；B、1,2 ；C、1；D、2。9、设 A=1,2,3 ，则 A 上有（）个二元关系。A、23 ；B、32 ；C、322；D、232。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必
23、备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 10、全体小项合取式为（）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C 都有可能。三、用 CP 规则证明 16%（每小题 8 分）
24、1、FAFEDDCBA,2、)()()()(xxQxxPxQxPx 四、（14%）集合 X=,，R=,|x1+y2=x2+y1。1、证明 R 是 X 上的等价关系。（10 分）2、求出 X 关于 R 的商集。（4 分）五、（10%）设集合 A=a,b,c,d 上关系 R=,要求 1、写出 R 的关系矩阵和关系图。（4 分）2、用矩阵运算求出 R 的传递闭包。（6 分）六、（20%）1、（10 分）设 f 和 g 是函数，证明gf 也是函数。2、（10 分）设函数STfTSg:，证明 STf:有一左逆函数当且仅当 f 是入射函数。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论
25、域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 试卷四 1 填空 10%（每小题 2 分
26、）1、若 P，Q，为二命题，QP 真值为 0 当且仅当 。2、命题“对于任意给定的正实数，都存在比它大的实数”令 F(x)：x 为实数，yxyxL:),(则命题的逻辑谓词公式为 。3、谓词合式公式)()(xxQxxP的前束范式为 。4、将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、设 x 是谓词合式公式 A 的一个客体变元，A 的论域为 D，A(x)关于 y 是自由的，则 被称为存在量词消去规则，记为ES。2 选择 25%（每小题 2.5 分）6、下列语句是命题的有（）。A、明年中秋节的晚上是晴天；B、0yx；C、0 xy当且仅当 x 和 y
27、都大于 0；D、我正在说谎。7、下列各命题中真值为真的命题有（）。A、2+2=4 当且仅当 3 是奇数；B、2+2=4 当且仅当 3 不是奇数；C、2+24 当且仅当 3 是奇数；D、2+24 当且仅当 3 不是奇数；8、下列符号串是合式公式的有（）A、QP；B、QPP；C、)()(QPQP；D、)(QP。9、下列等价式成立的有（）。A、PQQP；B、RRPP)(；C、QQPP)(；D、RQPRQP)()(。10、若nAAA21,和 B 为 wff，且BAAAn21则（）。A、称nAAA21为 B 的前件；B、称 B 为nAAA21,的有效结论 C、当且仅当FBAAAn21；D、当且仅当FBA
28、AAn21。11、A，B 为二合式公式，且BA，则（）。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下
29、载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 A、BA为重言式；B、*BA；C、BA；D、*BA；E、BA为重言式。12、“人总是要死的”谓词公式表示为（）。（论域为全总个体域）M(x)：x 是人；Mortal(x)：x 是要死的。A、)()(xMortalxM；B、)()(xMortalxM C、)()(xMortalxMx；D、)()(xMortalxMx 13、公式)()(xQxPxA的解释 I 为：个体域 D=2，P(x)：x3,Q(x)：x=4 则 A的真值为（）。A、1；B、0；C、可满足式；D、无法判定。14、下列等价关系正确的是（）。A、)(
30、)()()(xxQxxPxQxPx；B、)()()()(xxQxxPxQxPx；C、QxxPQxPx)()(；D、QxxPQxPx)()(。15、下列推理步骤错在（）。)()(xGxFx P)()(yGyF US)(xxF P)(yF ES)(yG TI)(xxG EG A、；B、；C、；D、3 逻辑判断 30%16、用等值演算法和真值表法判断公式)()()(QPPQQPA的类型。（10 分）17、下列问题，若成立请证明，若不成立请举出反例：（10 分）（1）已知CBCA，问BA成立吗？（2）已知BA，问BA成立吗？18、如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了
31、厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10 分）集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在
32、中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 四、计算 10%1、设命题 A1，A2的真值为 1，A3，A4真值为 0，求命题)()(421321AAAAAA的真值。（5 分）2、利用主析取范式，求公式RQQP)(的类型。（5 分）五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域 D=a,b,c，求证：)()()()(xBxAxxxBxxA。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上
33、偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 试卷五 一、填空 15%（每空 3 分）1、设 G 为 9 阶无向图，每个结点度数不是
34、5 就是 6，则 G 中至少有 个 5 度结点。2、n 阶完全图，Kn的点数 X(Kn)=。3、有向图 中从 v1到 v2长度为 2 的通路有 条。4、设R，+，是代数系统，如果R，+是交换群 R，是半群 则称R，+，为环。5、设,L是代数系统，则,L满足幂等律，即对La 有 。二、选择 15%（每小题 3 分）1、下面四组数能构成无向简单图的度数列的有（）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。2、下图中是哈密顿图的为（）。3、如果一个有向图 D 是强连通图，则 D 是欧拉图，这个命题的真值为（）A、真；B、假。4、下
35、列偏序集（）能构成格。5、设 4,41,3,31,2,21,1s，*为普通乘法，则S，*是（）。A、代数系统；B、半群；C、群；D、都不是。三、证明 48%1、（10%）在至少有 2 个人的人群中，至少有 2 个人，他们有相同的朋友数。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下
36、则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 2、（8%）若图 G 中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在 6 个结点 12 条边的连通平面简单图中，每个面的面数都是 3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设 1,0,B是布尔代数，定义运算*为)()(*bababa，求证B，*是阿贝尔群。四、计算 22%1、在二叉树中 1）求带权为
37、2，3，5，7，8 的最优二叉树 T。（5 分）2）求 T 对应的二元前缀码。（5 分）2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在 D 点）。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度
38、结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 试卷六 一 填空 15%（每小题 3 分）1、n 阶完全图结点 v 的度数 d(v)=。2、设 n 阶图 G 中有 m 条边，每个结点的度数不是 k 的是 k+1，若 G 中有 Nk个 k 度顶点，Nk+1个 k+1 度顶点，则 N k=。3、算式)*()*)*(fedcba的二叉树表示为 。4、如图 给出格 L，则 e 的补元是 。5、一 组 学 生，用 二 二 扳 腕 子 比 赛 法 来 测 定 臂 力 的
39、大 小，则 幺 元是 。二、选择 15%（每小题 3 分）1、设 S=0,1,2,3,为小于等于关系，则S，是（）。A、群；B、环；C、域；D、格。2、设a,b,c，*为代数系统，*运算如下：*a b c a a b c b b a c c c c c 则零元为（）。A、a；B、b；C、c；D、没有。3、如右图 相对于完全图 K5的补图为（）。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的
40、是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 4、一棵无向树 T 有 7 片树叶，3 个 3 度顶点，其余顶点均为 4 度。则 T 有（）4 度结点。A、1；B、2；C、3；D、4。5、设A，+，是代数系统，其中+，为普通加法和乘法，则 A=（）时，A，+，是整环。A、,2
41、|Znnxx；B、,12|Znnxx；C、,0|Zxxx 且；D、,5|4Rbabaxx。三、证明 50%1、设 G 是（n,m）简单二部图，则42nm。（10 分）2、设 G 为具有 n 个结点的简单图，且)2)(1(21nnm，则 G 是连通图。（10 分）3、记“开”为 1，“关”为 0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 证明它是一个环，并且是一个域。（14 分）4、,L是一代数格，“”为自然偏序，则L，是偏序格。（16 分）四、10%设)()()(),(323221321xxxxxxxxxE是
42、布尔代数,1,0上的一个布尔表达式，试写出),(321xxxE的析取范式和合取范式（10 分）五、10%如下图所示的赋权图表示某七个城市721,vvv及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是
43、传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 试卷七 一、填空 15%（每小题 3 分）1.任何(n,m)图 G=(V,E),边与顶点数的关系是 。2.当 n 为 时,非平凡无向完全图 Kn是欧拉图。3.已知一棵无向树 T有三个 3 顶点,一个 2 度顶点,其余的都是 1 度顶点,则 T中有 个 1 度顶点。4.n 阶完全图 Kn的点色数 X(KN)=
44、。5.一 组 学 生,用 两 两 扳 腕 子 比 赛 来 测 定 臂 力 大 小,则 幺 元是 。二、选择 15%（每小题 3 分）1、下面四组数能构成无向图的度数列的有()。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、图 的邻接矩阵为()。A、0001101110100001；B、1111111111111111；C、0001101111000010；D、0001101110100010。3、下列几个图是简单图的有()。A.G1=(V1,E1),其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de；B.G2=(V2,E
45、2)其中 V2=V1,E2=,；C.G=(V3,E3),其中 V3=V1,E3=ab,be,ed,cc；D.G=(V4,E4),其中 V4=V1,E4=（a,a）,（a,b）,（b,c）,（e,c）,（e,d）。4、下列图中是欧拉图的有()。集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元
46、系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 5、),2(SG，其中 3,2,1S，为集合对称差运算，则方程 3,1 2,1x的解为（）。A、3,2；B、3,2,1；C、3,1；D、。三、证明 34%1、证明：在至少有 2 个人的人群中，至少有 2 个人，他的有相同的朋友数。（8 分）2、若图 G 中恰有两个奇数顶点，则这两个顶点是连通的。（8 分）3、证明：在 6 个结点
47、12 条边的连通平面简单图中，每个面的面度都是 3。（8 分）4、证明循环群的同态像必是循环群。（10 分）四、中国邮递员问题 13%求带权图 G 中的最优投递路线。邮局在 v1点。根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。10%设 B4=e,a,b,ab ，运算*如下表，证明是一个群（称作 Klein 四元群*e a b ab e e a b ab a a e ab b b b ab e a ab ab b a e 集合表达式为设的真值为的真值为则的真值公
48、式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态映射证明是的一个子且群其中分是每一个面至少由学习必备 欢迎下载 试卷八 一、填
49、空 15%（每小题 3 分）1、n 阶完全图 Kn的边数为 。2、右图 的邻接矩阵A=。3、图 的对偶图为：4、完全二叉树中，叶数为 nt，则边数 m=。5、设 为代数系统，*运算如下：则它的幺元为 ；零元为 ；a、b、c 的逆元分别为 。二、选择 15%（每小题 3 分）1、图 相对于完全图的补图为（）。则)(),(),(GGGk分 别 为2、对图G （）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。3、一棵无向树 T 有 8 个顶点，4 度、3 度、2 度的分枝点各 1 个，其余顶点均为树叶，则 T 中有（）片树叶。A、3；B、4；C、5；D、6*a b c a a b
50、 c b b a c c c c c 集合表达式为设的真值为的真值为则的真值公式的主合取范式为若解释的论域仅包含一个元素则在下真值为设上关系图为则设其上偏序关系的哈斯图为则图的补图为设上二元运算如下学习必备欢迎下载那么代数系统的幺元是有逆元设则上的二元关系有个设是集合上的关系则下列说法正确的是若是自反的则是自反的若是反自反的则是反自反的若是对称的则是对称的若是传递的则是传递的设的幂集上规定二元系如下则学习必备欢迎下载设则上包含关系的哈斯图是在一棵树中有片树叶个度结点其余都是度结点则该树有个度结点三证明是集合上的一个自反关系求证是对称和传递的当且仅当和在中有在中分学习必备欢迎下载和都是群到的同态