離散數(shù)學(xué)填空題及答案

1、編號題目答案題型分值大綱難度1謂詞公式"x(P(x)Ú $yR(y)Q(x)中量詞"x的轄域是（ ）。答：P(x)Ú $yR(y)填空題23.132令R(x):x是實數(shù)，Q(x):x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”的符號化表示為（ ）。答："x(R(x)Q(x)填空題23.133一棵無向樹的頂點數(shù)n與邊數(shù)m關(guān)系是()。答：m=n-1填空題27.134一個圖的歐拉回路是一條通過圖中( )的回路。答：所有邊一次且恰好一次填空題26.435有n個結(jié)點的樹，其結(jié)點度數(shù)之和是()。答：2n-2填空題26.436設(shè)T是一棵樹，則T是一個連通且(

2、)圖。答：簡單無回路填空題26.237任一有向圖中，度數(shù)為奇數(shù)的結(jié)點有()個。答：偶數(shù)填空題26.138設(shè) （N：自然數(shù)集，E+ 正偶數(shù)） 則 （ ） 。答：0，1，2，3，4，6填空題2129設(shè)P，Q 的真值為0，R，S的真值為1，則的真值= （ ）。答：1填空題22.1310公式的主合取范式為（ ） 。答：填空題22.3411設(shè)A=1，2，3，4，A上關(guān)系為 <1,2>,<2,1>,<2,3>,<3,4>則 R2 = ( )。答：<1,1>, <1,3>, <2,2>, <2,4> 填空題24.

3、1；4.2312設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= （ ）。答：<a.b>,<a,c>,<a,d>,<b,d>,<c,d> IA填空題24.4413樹是不包含樹是不包含（ ）的（ ）圖的。答：環(huán);無向填空題28.1314設(shè)A=1，2，3，則A上既不是對稱的又不是反對稱的關(guān)系R= ( )。答：R=<1,2>,<1,3>,<2,1>填空題24.3315設(shè) f，g是自然數(shù)集N上的函數(shù)，則（ ）。答：2(x+1)填空題25.2316設(shè)A=a，b，c，A上二元關(guān)系R=< a, a &

4、gt; , < a, b >,< a, c >, < c, c> , 則s（R）= （ ）。答：填空題24.4517P，Q真值為0 ；R，S真值為1。則的真值為（ ）。答：1填空題22.2318的主合取范式為（ ）。答：填空題22.3419設(shè) P（x）：x是素數(shù)， E(x)：x 是偶數(shù)，O(x)：x是奇數(shù) N (x,y)：x可以整數(shù)y。則謂詞 的自然語言是（ ）。答：填空題23.1320謂詞的前束范式為（ ）。答：填空題23.2421若P，Q，為二命題，真值為0 當(dāng)且僅當(dāng)（ ） 。答：P真值為1，Q的真值為0填空題22.1322將量詞轄域中出現(xiàn)的（ ） 和指

5、導(dǎo)變元交換為另一變元符號，公式其余的部分不變，這種方法稱為換名規(guī)則。答：約束變元填空題23.1323設(shè)G為9階無向圖，每個結(jié)點度數(shù)不是5就是6，則G中至少有 （ ） 個5度結(jié)點。答：6填空題26.1324有向圖 中從v1到v2長度為2的通路有（ ） 條。答：2填空題26.3325設(shè)是代數(shù)系統(tǒng)，則滿足冪等律，即對有（ ） 。答：填空題28.2426任何(n,m) 圖G = (V,E) , 邊與頂點數(shù)的關(guān)系是（ ）。答：填空題26.4327當(dāng)n為（ ） 時,非平凡無向完全圖Kn是歐拉圖。答：奇數(shù)填空題26.2328已知一棵無向樹T有三個3頂點,一個2度頂點,其余的都是1度頂點,則T中有（ ）個1度

6、頂點。答：5填空題27.1329集合A=,的冪集P(A) =（ ） 。答：填空題21330設(shè)|A|=3，則A上有（ ）個二元關(guān)系。答：29填空題24.1331Q：我將去上海，R：我有時間，公式的自然語言為（ ）。答：我將去上海當(dāng)且僅當(dāng)我有空填空題22.1332公式的主合取范式是（ ） 。答：填空題22.3333若是集合A的一個分劃，則它應(yīng)滿足（ ）。答：填空題24.4334代數(shù)系統(tǒng)<A,*>中，|A|>1，如果分別為<A,*>的幺元和零元，則的關(guān)系為（ ） 。答：填空題28.1335設(shè)，定義A上的二元運算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運

7、算*關(guān)于（ ）運算具有封閉性。答：乘法填空題28.1336設(shè)<G,*>是由元素生成的循環(huán)群，且|G|=n，則G = ( )。答：填空題28.3437一個圖是平面圖的充要條件是 ( )。答：它不包含與K3, 3或K5在2度結(jié)點內(nèi)同構(gòu)的子圖填空題26.4338某人有三個兒子，組成集合A=S1,S2,S3，在A上的兄弟關(guān)系具有 （ ）性質(zhì)。答：反自反性、對稱性、傳遞性填空題24.1339若是函數(shù)，則當(dāng)f是的（ ），是f的逆函數(shù)。答：雙射填空題25.2340設(shè)P：它占據(jù)空間，Q：它有質(zhì)量，R：它不斷運動，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運動的叫做物質(zhì)”的符號化為（ ）。答

8、：填空題22.1341設(shè)A，B是兩命題公式，當(dāng)且僅當(dāng)（ ）。答：填空題22.1；2.2342對謂詞公式的自由變元代入得( )。答：填空題23.1；3.2343對集合X和Y，設(shè)|X|=m ，|Y|=n ，則從X到Y(jié)的函數(shù)有( )個。答：nm填空題25.1344若關(guān)系R是等價關(guān)系,則R滿足( )性質(zhì)。答：自反性、對稱性、傳遞性填空題24.4345關(guān)系R的傳遞閉包t (R) = ( ) 。答：填空題24.3446代數(shù)系統(tǒng)是群，則它滿足( )。 答：運算*在A上封閉，*在A上可結(jié)合，*在A上存在幺元，A中每個元素都有逆元；填空題28.2；8.3347設(shè)是兩代數(shù)系統(tǒng)，f是的同態(tài)映射，則f具有( )性質(zhì)。

9、答：填空題28.2；8.3348若連通平面圖共有r個面，其中，則它滿足的Euler公式為( )。答：填空題26.4349樹T的邊數(shù)e與點數(shù)v有關(guān)系( )。答：填空題27.1；7.2350n 個命題變元有( )個互不等價的極小項。答：填空題22.2；2.3351按De-Morgan定理， =( )。答：填空題22.2；2.3352公式的主析取范式為( )。答：填空題22.3453設(shè)P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，則命題“大象比老鼠重”的符號化為( )。答：填空題23.1354設(shè)，X上的關(guān)系R的關(guān)系矩陣是，則 ( )。答：填空題26.3455在具有n個結(jié)點的有向圖中

10、，任何基本通路的長度都不超過( ) 。答：n-1填空題26.1356任何圖的點連通度，邊連通度，最小點度的關(guān)系為( )。答：填空題26.1；6.2357結(jié)點數(shù)n（）的簡單連通平面圖的邊數(shù)為m，則m與n的關(guān)系為( )。答：填空題26.4458群G的非空子集H是G的子群當(dāng)且僅當(dāng)若x , yH 則( )。答：填空題28.3459代數(shù)系統(tǒng)是環(huán)，若對運算“· ”還滿足( )則是整環(huán)。答：含幺元，可交換，無零因子填空題28.2；8.3560給定命題公式A、B，若（ ），則稱A和B是邏輯相等的。答：對于A，B中原子變元任意一組真值指派，A和B的真值相同。填空題22.1361設(shè)考慮下列子集，則A的覆

11、蓋有（ ），A的劃分有（ ）。答：填空題24.4462若為哈密頓圖，則對于結(jié)點集V的每個非空子集S，均有P(G-S)（ ）成立，答：填空題26.4463某班有學(xué)生50人,有26人在第一次考試中得優(yōu),有21人在第二次考試中得優(yōu),有17人兩次考試都沒有得優(yōu),那么兩次考試都得優(yōu)的學(xué)生人數(shù)是（ ）。答：14填空題21364給命題變元p、s和r指派真值1,q指派真值0,公式p(sr)q)s)的真值為（ ）。答：1填空題22.1；2.2365設(shè)p：我生病，q：我去上課，命題“我雖然生病但我還是去上課”符號化為：（ ）。答：填空題22.1；2.2366公式xA(x)xB(x)的前束范式為（ ）。 答：填空題

12、23.2467若1,2,3,4上的二元關(guān)系R=<1,1>,<1,2>,<2,4>,則R的自反閉包r(R )=（ ）。答：r(R)=<1,1>,<1,2>,<2,4>,<2,2><3,3>,<4,4>填空題24.1；4.2468有向圖D如下，則D的鄰接矩陣A(D) =（ ）。答：填空題26.33695階的群有（ ）個不同的子群。答：2填空題28.3470一棵高度為5的二元樹結(jié)點數(shù)最多為（ ）。答：63 填空題27.1；7.2371一個連通平面圖G有10條邊，G中度為1的頂點有2個，其余是度

13、為6的頂點，則G中共有（ ）個頂點，（ ）個面。答：5，7填空題26.1；6.2372集合X=0,1,2,3，R是X上的二元關(guān)系，R=<0,1>,<0,2>,<1,1>,<1,3>,<2,0>,<2,3>,<3,1,>，則R的關(guān)系矩陣MR是（ ）。答：填空題26.2；6.3373無向圖G中有n個結(jié)點m條邊，且G中每個結(jié)點的度數(shù)不是k就是k+1,則G中度數(shù)為k的結(jié)點的個數(shù)是（ ）。答：(k+1)n-2m填空題26.1；6.2374設(shè)Z+=xxZx>0，*表示求兩個數(shù)的最小公倍數(shù)的運算，則*運算的幺元是（ ）

14、。答：1填空題28.1；8.2375群<N7，7>總共有（ ）個不同的子群。答：2填空題28.1；8.2476在個體域D=a,b中，與公式xA(x)等價又不含量詞的公式是（ ）。答：A(a) A(b)填空題23.1；3.2377具有4個結(jié)點的有向完全圖的邊數(shù)為（ ）條。答：24填空題26.1378若p：他聰明；q：他用功；則“他雖聰明，但不用功”，可符號化為（ ）。答：pq填空題22.1379若集合A=1, 2, 3上的二元關(guān)系R1和R2的關(guān)系圖如下所示， 則R1oR2 =（ ）。答：r(R)=<1,1>,<1,2>,<2,4>,<2,2&

15、gt;<3,3>,<4,4>填空題24.1；4.2380樹是平面圖，它有（ ）個面。答：1填空題26.1；7.1381哈密爾頓回路要求經(jīng)過圖中（ ）一次且僅一次。答：每個頂點填空題26.4382有向圖D如下：D的鄰接矩陣A=(aij)3×3,則a11=（ ）,a32=（ ）。答：1，0填空題26.3383在一棵根樹中，僅有一個結(jié)點的入度為（ ），稱為樹根，其余結(jié)點的入度均為（ ）。答：0，1填空題27.2384合式公式Q(P(PQ)與QP的關(guān)系是_的。（等價或蘊含選一）答：等價填空題22.2；2.3385設(shè)R為非空集合A上的二元關(guān)系，如果R滿足（ ），則稱R為

16、A上的一個偏序關(guān)系。 答：自反、反對稱、傳遞填空題24.3386設(shè)R為A上的關(guān)系，則R的自反閉包r(R)= （ ），對稱閉包s(R)= （ ）。答：RIx, RRc 填空題24.3487一棵高度為3的二叉樹結(jié)點數(shù)最多為（ ） 。答：7填空題27.1；7.2388設(shè)Z是整數(shù)集，在Z上定義二元運算*為a*b=a+b+ab，其中+和是數(shù)的加法和乘法， 則代數(shù)系統(tǒng)<Z,*>的幺元是（ ），零元是（ ）。答：a , 0填空題28.1；8.2389設(shè)T是有n個結(jié)點的完全二叉樹，則T葉子數(shù)為（ ）。答：(n+1)/2 填空題27.1；7.2390設(shè)A=a,b,c,則A×A中的元素有(

17、)。答：9填空題21；4.1391圖G與其對偶圖G*的結(jié)點數(shù)目（ ）相等。答：不一定填空題26.4492設(shè)，定義上的等價關(guān)系則由 R產(chǎn) 生的上一個劃分共有（ ）個分塊。答：4填空題24.3；4.4393設(shè)G，是一個群，則對任意的G均有 = （ ）。答：填空題28.3594設(shè)圖D=<V，E>，V=v1，v2，v3，v4，若D的鄰接矩陣A=，則deg-（v1）=（ ），從v2到v4長度為2的路有（ ）條。答：2，2填空題26.3495設(shè)A=1，2，B=2，3，則A-A=（ ），A-B=（ ）。答：，1填空題21396兩個重言式的析取是（ ）式，一個重言式與一個矛盾式的析取是（ ）式。答：重言式，重言式填空題22.1；2.2397