离散数学填空题及答案.doc

编号题目答案题型分值大纲难度1谓词公式x(P(x) $yR(y)Q(x)中量词x的辖域是（ ）。答：P(x) $yR(y)填空题23.132令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。答：x(R(x)Q(x)填空题23.133一棵无向树的顶点数n与边数m关系是()。答：m=n-1填空题27.134一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次填空题26.435有n个结点的树，其结点度数之和是()。答：2n-2填空题26.436设T是一棵树，则T是一个连通且( )图。答：简单无回路填空题26.237任一有向图中，度数为奇数的结点有()个。答：偶数填空题26.138设 （N：自然数集，E+ 正偶数） 则 （ ） 。答：0，1，2，3，4，6填空题2129设P，Q 的真值为0，R，S的真值为1，则的真值= （ ）。答：1填空题22.1310公式的主合取范式为（ ） 。答：填空题22.3411设A=1，2，3，4，A上关系为 ,则 R2 = ( )。答：, , , 填空题24.1；4.2312设A=a，b，c，d，其上偏序关系R的哈斯图为则 R= （ ）。答：, IA填空题24.4413树是不包含树是不包含（ ）的（ ）图的。答：环;无向填空题28.1314设A=1，2，3，则A上既不是对称的又不是反对称的关系R= ( )。答：R=,填空题24.3315设 f，g是自然数集N上的函数，则（ ）。答：2(x+1)填空题25.2316设A=a，b，c，A上二元关系R= , , , 则s（R）= （ ）。答：填空题24.4517P，Q真值为0 ；R，S真值为1。则的真值为（ ）。答：1填空题22.2318的主合取范式为（ ）。答：填空题22.3419设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词 的自然语言是（ ）。答：填空题23.1320谓词的前束范式为（ ）。答：填空题23.2421若P，Q，为二命题，真值为0 当且仅当（ ） 。答：P真值为1，Q的真值为0填空题22.1322将量词辖域中出现的（ ） 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。答：约束变元填空题23.1323设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 （ ） 个5度结点。答：6填空题26.1324有向图 中从v1到v2长度为2的通路有（ ） 条。答：2填空题26.3325设是代数系统，则满足幂等律，即对有（ ） 。答：填空题28.2426任何(n,m) 图G = (V,E) , 边与顶点数的关系是（ ）。答：填空题26.4327当n为（ ） 时,非平凡无向完全图Kn是欧拉图。答：奇数填空题26.2328已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有（ ）个1度顶点。答：5填空题27.1329集合A=,的幂集P(A) =（ ） 。答：填空题21330设|A|=3，则A上有（ ）个二元关系。答：29填空题24.1331Q：我将去上海，R：我有时间，公式的自然语言为（ ）。答：我将去上海当且仅当我有空填空题22.1332公式的主合取范式是（ ） 。答：填空题22.3333若是集合A的一个分划，则它应满足（ ）。答：填空题24.4334代数系统中，|A|1，如果分别为的幺元和零元，则的关系为（ ） 。答：填空题28.1335设，定义A上的二元运算为普通乘法、除法和加法，则代数系统中运算*关于（ ）运算具有封闭性。答：乘法填空题28.1336设是由元素生成的循环群，且|G|=n，则G = ( )。答：填空题28.3437一个图是平面图的充要条件是 ( )。答：它不包含与K3, 3或K5在2度结点内同构的子图填空题26.4338某人有三个儿子，组成集合A=S1,S2,S3，在A上的兄弟关系具有 （ ）性质。答：反自反性、对称性、传递性填空题24.1339若是函数，则当f是的（ ），是f的逆函数。答：双射填空题25.2340设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为（ ）。答：填空题22.1341设A，B是两命题公式，当且仅当（ ）。答：填空题22.1；2.2342对谓词公式的自由变元代入得( )。答：填空题23.1；3.2343对集合X和Y，设|X|=m ，|Y|=n ，则从X到Y的函数有( )个。答：nm填空题25.1344若关系R是等价关系,则R满足( )性质。答：自反性、对称性、传递性填空题24.4345关系R的传递闭包t (R) = ( ) 。答：填空题24.3446代数系统是群，则它满足( )。 答：运算*在A上封闭，*在A上可结合，*在A上存在幺元，A中每个元素都有逆元；填空题28.2；8.3347设是两代数系统，f是的同态映射，则f具有( )性质。答：填空题28.2；8.3348若连通平面图共有r个面，其中，则它满足的Euler公式为( )。答：填空题26.4349树T的边数e与点数v有关系( )。答：填空题27.1；7.2350n 个命题变元有( )个互不等价的极小项。答：填空题22.2；2.3351按De-Morgan定理， =( )。答：填空题22.2；2.3352公式的主析取范式为( )。答：填空题22.3453设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为( )。答：填空题23.1354设，X上的关系R的关系矩阵是，则 ( )。答：填空题26.3455在具有n个结点的有向图中，任何基本通路的长度都不超过( ) 。答：n-1填空题26.1356任何图的点连通度，边连通度，最小点度的关系为( )。答：填空题26.1；6.2357结点数n（）的简单连通平面图的边数为m，则m与n的关系为( )。答：填空题26.4458群G的非空子集H是G的子群当且仅当若x , yH 则( )。答：填空题28.3459代数系统是环，若对运算“ ”还满足( )则是整环。答：含幺元，可交换，无零因子填空题28.2；8.3560给定命题公式A、B，若（ ），则称A和B是逻辑相等的。答：对于A，B中原子变元任意一组真值指派，A和B的真值相同。填空题22.1361设考虑下列子集，则A的覆盖有（ ），A的划分有（ ）。答：填空题24.4462若为哈密顿图，则对于结点集V的每个非空子集S，均有P(G-S)（ ）成立，答：填空题26.4463某班有学生50人,有26人在第一次考试中得优,有21人在第二次考试中得优,有17人两次考试都没有得优,那么两次考试都得优的学生人数是（ ）。答：14填空题21364给命题变元p、s和r指派真值1,q指派真值0,公式p(sr)q)s)的真值为（ ）。答：1填空题22.1；2.2365设p：我生病，q：我去上课，命题“我虽然生病但我还是去上课”符号化为：（ ）。答：填空题22.1；2.2366公式xA(x)xB(x)的前束范式为（ ）。 答：填空题23.2467若1,2,3,4上的二元关系R=,则R的自反闭包r(R )=（ ）。答：r(R)=,填空题24.1；4.2468有向图D如下，则D的邻接矩阵A(D) =（ ）。答：填空题26.33695阶的群有（ ）个不同的子群。答：2填空题28.3470一棵高度为5的二元树结点数最多为（ ）。答：63 填空题27.1；7.2371一个连通平面图G有10条边，G中度为1的顶点有2个，其余是度为6的顶点，则G中共有（ ）个顶点，（ ）个面。答：5，7填空题26.1；6.2372集合X=0,1,2,3，R是X上的二元关系，R=,，则R的关系矩阵MR是（ ）。答：填空题26.2；6.3373无向图G中有n个结点m条边，且G中每个结点的度数不是k就是k+1,则G中度数为k的结点的个数是（ ）。答：(k+1)n-2m填空题26.1；6.2374设Z+=xxZx0，*表示求两个数的最小公倍数的运算，则*运算的幺元是（ ）。答：1填空题28.1；8.2375群总共有（ ）个不同的子群。答：2填空题28.1；8.2476在个体域D=a,b中，与公式xA(x)等价又不含量词的公式是（ ）。答：A(a) A(b)填空题23.1；3.2377具有4个结点的有向完全图的边数为（ ）条。答：24填空题26.1378若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为（ ）。答：pq填空题22.1379若集合A=1, 2, 3上的二元关系R1和R2的关系图如下所示， 则R1oR2 =（ ）。答：r(R)=,填空题24.1；4.2380树是平面图，它有（ ）个面。答：1填空题26.1；7.1381哈密尔顿回路要求经过图中（ ）一次且仅一次。答：每个顶点填空题26.4382有向图D如下：D的邻接矩阵A=(aij)33,则a11=（ ）,a32=（ ）。答：1，0填空题26.3383在一棵根树中，仅有一个结点的入度为（ ），称为树根，其余结点的入度均为（ ）。答：0，1填空题27.2384合式公式Q(P(PQ)与QP的关系是_的。（等价或蕴含选一）答：等价填空题22.2；2.3385设R为非空集合A上的二元关系，如果R满足（ ），则称R为A上的一个偏序关系。 答：自反、反对称、传递填空题24.3386设R为A上的关系，则R的自反闭包r(R)= （ ），对称闭包s(R)= （ ）。答：RIx, RRc 填空题24.3487一棵高度为3的二叉树结点数最多为（ ） 。答：7填空题27.1；7.2388设Z是整数集，在Z上定义二元运算*为a*b=a+b+ab，其中+和是数的加法和乘法， 则代数系统的幺元是（ ），零元是（ ）。答：a , 0填空题28.1；8.2389设T是有n个结点的完全二叉树，则T叶子数为（ ）。答：(n+1)/2 填空题27.1；7.2390设A=a,b,c,则AA中的元素有( )。答：9填空题21；4.1391图G与其对偶图G*的结点数目（ ）相等。答：不一定填空题26.4492设，定义上的等价关系则由 R产 生的上一个划分共有（ ）个分块。答：4填空题24.3；4.4393设G，是一个群，则对任意的G均有 = （ ）。答：填空题28.3594设图D=，V=v1，v2，v3，v4，若D的邻接矩阵A=，则deg-（v1）=（ ），从v2到v4长度为2的路有（ ）条。答：2，2填空题26.3495设A=1，2，B=2，3，则A-A=（ ），A-B=（ ）。答：，1填空题21396两个重言式的析取是（ ）式，一个重言式与一个矛盾式的析取是（ ）式。答：重言式，重言式填空题22.1；2.2397一个无向树中有6条边，则它有（ ）个结点。答：5填空题27.1398谓词公式(x)( y)（P(x,y)R(y)Q(y)，则其约束变元是（ ），自由变元是（ ）。答：（P(x,y)R(y)中的x,y; Q(y)中的y填空题22.1；2.2399一个结点为n的无向完全图，其边的数目为（ ）,并且它是 （ ）度正则图。答：n(n-1)/2,n填空题26.1；7.13100设R为非空集合A上的等价关系，其等价类记为xR。x,yA，若x,yR，则xR与yR的关系是（ ），而若x,yR，则xRyR=（ ）。答：xR=yR , 填空题24.44