《离散模拟题(自己总结版)》由会员分享，可在线阅读，更多相关《离散模拟题(自己总结版)（9页珍藏版）》请在金锄头文库上搜索。
1、一.单项选择题1. 永真命题公式( ) 只存在主析取范式;只存在主合取范式;既存在主析取范式也存在主合取范式;都不对.2. 下列代数系统中消去侓不成立的是( ).群;含幺半群;整环;分配格.3.在 4 个元素的集合上可定义的满射有( )个4;12; 16 244. 在整环和格的定义中对运算都要求满足的性质是( ) 及收律; 幂等律; 交换律; 分配律.5. 下面对于群、环、格中运算都要求的性质是( )结合性; 交换性; 幂等性; 分配性6. 下面说法中正确的是( ) 半群都有幂等元;.剩余类环中没有零因子;.整数加法群 不是循环群;每个群都有正规子群 .7.下面正确的说法是( )5 点格都不是
2、分配格;剩余类环中没有零因子; 数加群 不是循环群;群中一定有等幂元8.Z5 为模 5 剩余类集,定义 f: Z5Z 5 如下:f(x)=2x+1,则 f0f( ).不是函数;不是单射;是置换;不是满射(0:1;1:3;2:0;3:2;4:4)9.下面关于集合基数正确的说法是( ) 没有最大的基数集;.任何集合都存在与它等势的真子集 ; 有最小的基数;有理数集合与实数集合等势10. 下面图中,可以割边的图是( )K 10,10; 欧拉图;平面图;哈密顿图.11. 在 4 个元素的集合上可定义的等价关系有( )个4;8;12 15.12.群没有平凡子群 ,则 G( )没有平凡子群;是循环群;是置
3、换群;不存在.13. 设 R 是 A 上的二元关系,且 R0R=R,则( )r（ R）=R; S( R )=R;t( R )=R;R=I A.14.谓词合适公式同时又是命题合适公式时,公式中必无( )自由变量;约束变量;个体常量;函数.15.设 T 是 G 的生成树,则( )G 的回路必含 T 的边;G 的回路必不含 T 的边;G 的割边必含 T 的边;G 的割边必不含 T 的边.16. 设 18 阶简单连通平面图 G 有 35 条边,则最多能为它增加 ( )条边使其仍能保持是简单平面图. 13;.18;.20;.25.(35+13 3*18-6=48)17.下式中( )是永真的.(PQ) (
4、PQ)；(P Q)(P Q)；(PQ) (P Q)；(PQ)(P Q).18. 下面在集合论和逻辑学中正确的公式有( ) PP PP; 2 AU2B=2AUB; x(A(x) B(x) xA(x) xB(x);AB=A CB=C;19. 下面可由拉格朗日定理推出的结论是( )每个群都有循环子群;素数阶的群是循环群;群中方程有解;群的同态核是群的正规子群.20. 下面能够符合既无割点也无割边的图类是( ).树; 欧拉图;哈密顿图;二部图.21. 设 R 是 A 上的二元关系,且 R0R=R 可以肯定 R 应是( )自反关系;传递关系;反对称关系;等价关系22.一个格中每个元都有补元,则该格必是(
5、 )有限格; 分配格; 有界格; 布尔格23.如果图 G 存在完备匹配 M,下面叙述正确的是( )G 中无割边;G 中无割点;不存在 M 非饱和点 ;存在 M 增广道路24. 下面哪个是有限半群必然具备的? ( )有等幂元; 有零元; 有幺元; 方程有解25.循环群之间的满同态映射( )是单射; 是双射; 把生成元映成生成元; 把零元映成零元二.多项选择题 1.下面各图中必存在生成树的有( )哈密顿图;欧拉图;平面图;平面图的对偶图; K 6,82. 下面可由拉格朗日定理推出的结论是( )每个群都有循环子群;素数阶的群是循环群;群中消去律成立;元素的周期可整除群的阶;子群的阶是群的阶的因子3.
6、下面集合中基数为阿列夫零的有( )100 的倍数集;区间（2，4）;素数集合;偶数集合的幂集合；分子为 5 的真分数所成之集4.下列代数系统中消去律成立的有( )2 A，;2 A，U;置换群Sn，0;环;分配格5.下面含有生成元的群有( )整数加法群; 非零实数乘群 ;置换群;素数阶群剩余类乘群6.如果一个格中消去律成立,那么这个格( )是有补格;是分配格;是有界格;满足吸收律;满足幂等律7.下面各图中边数必不小于结点数的图有( )哈密顿图;欧拉图;平面图;二部图;树三.计算题1.求剩余类环中关于置换子群的全部左陪集。7.决定幂集代数系统2 A，中有无幺元、零元、幂等元，如果有，写出它们。8.
7、当 n 阶 K 度正则图是平面图时，求 n 和 k 满足的关系式。9.写出 5 个元素的集合上可以定义的含 2 个等价类的全部等价关系。10. 设 T 是一个 n 阶的完全 3 叉树，求最少要给它新加多少边才能使它成为欧拉图。11.画出元素个数为 6 的全部有补格对应的 Hasse 图。12.设 a 和 b 是交换群中周期分别为 4 和 6 的两个元素,求 a*b 的周期。13.求一个 20 阶的、非连通的、简单平面图的最大边数。14设 A=a,b,c,计算 A 上可以定义多少个二元关系,等价关系和双射。15. 设 n 阶简单连通图 G 既是自补图又是平面图,求它的面数表达式。16求的全部生成
8、元。四.证明题1.1 设 R 是集 A 上的等价关系，证明：对任何正整数 n,Rn也是等价关系。1.2 设 R 是集 A 上一个自反二元关系，且（a，b）R（a，c）R（b，c ）R。证明： R 是等价关系。1.3 设 R 是集 A 上一个自反、对称二元关系，且 RoR-1=IA，证明：R 是等价关系。2.1 证明：连通图 G 其对偶图是平面二部图当且仅当 G 是平面欧拉图。2.2 证明：如果图 G 中存在两个不同的完备匹配,证明 G 中必有回路。3.1 证明：Q(P R)，(R S)B,A (SB)QP A。3.2 证明：x(P(x)(Q(x)R(x)，xQ(x)y(R(y)S(y)x(P(x)(Q(x)S(x)。3.3 证明：P(QR)，RP，SQ PS。4.1 证明：是交换群,并判它的元素周期分布情况。4.2 证明：循环群同态于自己的子群。4.3 证明：设 H 是群的子群,a,b 是 G 中任意两个元素,证明陪集 aH 和 bH 等势。
