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

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

2、數(shù)的結(jié)點(diǎn)有()個(gè)。答：偶數(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)系為 ,則 R2 = ( )。答：, , , 填空題24.1；4.2312設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= （ ）。答：, IA填空題24.4413樹(shù)是不包含樹(shù)是不包含（ ）的（ ）圖的。答：環(huán);無(wú)向填空題28.1314設(shè)A=1，2，3，則A上既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的關(guān)系R=

3、 ( )。答：R=,填空題24.3315設(shè) f，g是自然數(shù)集N上的函數(shù)，則（ ）。答：2(x+1)填空題25.2316設(shè)A=a，b，c，A上二元關(guān)系R= , , , 則s（R）= （ ）。答：填空題24.4517P，Q真值為0 ；R，S真值為1。則的真值為（ ）。答：1填空題22.2318的主合取范式為（ ）。答：填空題22.3419設(shè) P（x）：x是素?cái)?shù)， E(x)：x 是偶數(shù)，O(x)：x是奇數(shù) N (x,y)：x可以整數(shù)y。則謂詞 的自然語(yǔ)言是（ ）。答：填空題23.1320謂詞的前束范式為（ ）。答：填空題23.2421若P，Q，為二命題，真值為0 當(dāng)且僅當(dāng)（ ） 。答：P真值為1，Q

4、的真值為0填空題22.1322將量詞轄域中出現(xiàn)的（ ） 和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱(chēng)為換名規(guī)則。答：約束變?cè)羁疹}23.1323設(shè)G為9階無(wú)向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有 （ ） 個(gè)5度結(jié)點(diǎn)。答：6填空題26.1324有向圖 中從v1到v2長(zhǎng)度為2的通路有（ ） 條。答：2填空題26.3325設(shè)是代數(shù)系統(tǒng)，則滿足冪等律，即對(duì)有（ ） 。答：填空題28.2426任何(n,m) 圖G = (V,E) , 邊與頂點(diǎn)數(shù)的關(guān)系是（ ）。答：填空題26.4327當(dāng)n為（ ） 時(shí),非平凡無(wú)向完全圖Kn是歐拉圖。答：奇數(shù)填空題26.2328已知一棵無(wú)向樹(shù)T有三個(gè)3

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

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

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

8、通平面圖共有r個(gè)面，其中，則它滿足的Euler公式為( )。答：填空題26.4349樹(shù)T的邊數(shù)e與點(diǎn)數(shù)v有關(guān)系( )。答：填空題27.1；7.2350n 個(gè)命題變?cè)? )個(gè)互不等價(jià)的極小項(xiàng)。答：填空題22.2；2.3351按De-Morgan定理， =( )。答：填空題22.2；2.3352公式的主析取范式為( )。答：填空題22.3453設(shè)P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，則命題“大象比老鼠重”的符號(hào)化為( )。答：填空題23.1354設(shè)，X上的關(guān)系R的關(guān)系矩陣是，則 ( )。答：填空題26.3455在具有n個(gè)結(jié)點(diǎn)的有向圖中，任何基本通路的長(zhǎng)度都不超過(guò)( )

9、。答：n-1填空題26.1356任何圖的點(diǎn)連通度，邊連通度，最小點(diǎn)度的關(guān)系為( )。答：填空題26.1；6.2357結(jié)點(diǎn)數(shù)n（）的簡(jiǎ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)，若對(duì)運(yùn)算“ ”還滿足( )則是整環(huán)。答：含幺元，可交換，無(wú)零因子填空題28.2；8.3560給定命題公式A、B，若（ ），則稱(chēng)A和B是邏輯相等的。答：對(duì)于A，B中原子變?cè)我庖唤M真值指派，A和B的真值相同。填空題22.1361設(shè)考慮下列子集，則A的覆蓋有（ ），A的劃分有（ ）。答：填空題24.4

10、462若為哈密頓圖，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，均有P(G-S)（ ）成立，答：填空題26.4463某班有學(xué)生50人,有26人在第一次考試中得優(yōu),有21人在第二次考試中得優(yōu),有17人兩次考試都沒(méi)有得優(yōu),那么兩次考試都得優(yōu)的學(xué)生人數(shù)是（ ）。答：14填空題21364給命題變?cè)猵、s和r指派真值1,q指派真值0,公式p(sr)q)s)的真值為（ ）。答：1填空題22.1；2.2365設(shè)p：我生病，q：我去上課，命題“我雖然生病但我還是去上課”符號(hào)化為：（ ）。答：填空題22.1；2.2366公式xA(x)xB(x)的前束范式為（ ）。 答：填空題23.2467若1,2,3,4上的二元關(guān)系R=,

11、則R的自反閉包r(R )=（ ）。答：r(R)=,填空題24.1；4.2468有向圖D如下，則D的鄰接矩陣A(D) =（ ）。答：填空題26.33695階的群有（ ）個(gè)不同的子群。答：2填空題28.3470一棵高度為5的二元樹(shù)結(jié)點(diǎn)數(shù)最多為（ ）。答：63 填空題27.1；7.2371一個(gè)連通平面圖G有10條邊，G中度為1的頂點(diǎn)有2個(gè)，其余是度為6的頂點(diǎn)，則G中共有（ ）個(gè)頂點(diǎn)，（ ）個(gè)面。答：5，7填空題26.1；6.2372集合X=0,1,2,3，R是X上的二元關(guān)系，R=,，則R的關(guān)系矩陣MR是（ ）。答：填空題26.2；6.3373無(wú)向圖G中有n個(gè)結(jié)點(diǎn)m條邊，且G中每個(gè)結(jié)點(diǎn)的度數(shù)不是k就是

12、k+1,則G中度數(shù)為k的結(jié)點(diǎn)的個(gè)數(shù)是（ ）。答：(k+1)n-2m填空題26.1；6.2374設(shè)Z+=xxZx0，*表示求兩個(gè)數(shù)的最小公倍數(shù)的運(yùn)算，則*運(yùn)算的幺元是（ ）。答：1填空題28.1；8.2375群總共有（ ）個(gè)不同的子群。答：2填空題28.1；8.2476在個(gè)體域D=a,b中，與公式xA(x)等價(jià)又不含量詞的公式是（ ）。答：A(a) A(b)填空題23.1；3.2377具有4個(gè)結(jié)點(diǎn)的有向完全圖的邊數(shù)為（ ）條。答：24填空題26.1378若p：他聰明；q：他用功；則“他雖聰明，但不用功”，可符號(hào)化為（ ）。答：pq填空題22.1379若集合A=1, 2, 3上的二元關(guān)系R1和R2

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

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

15、與其對(duì)偶圖G*的結(jié)點(diǎn)數(shù)目（ ）相等。答：不一定填空題26.4492設(shè)，定義上的等價(jià)關(guān)系則由 R產(chǎn) 生的上一個(gè)劃分共有（ ）個(gè)分塊。答：4填空題24.3；4.4393設(shè)G，是一個(gè)群，則對(duì)任意的G均有 = （ ）。答：填空題28.3594設(shè)圖D=，V=v1，v2，v3，v4，若D的鄰接矩陣A=，則deg-（v1）=（ ），從v2到v4長(zhǎng)度為2的路有（ ）條。答：2，2填空題26.3495設(shè)A=1，2，B=2，3，則A-A=（ ），A-B=（ ）。答：，1填空題21396兩個(gè)重言式的析取是（ ）式，一個(gè)重言式與一個(gè)矛盾式的析取是（ ）式。答：重言式，重言式填空題22.1；2.2397一個(gè)無(wú)向樹(shù)中有6條邊，則它有（ ）個(gè)結(jié)點(diǎn)。答：5填空題27.1398謂詞公