離散數(shù)學(xué)AB卷2套期末考試卷帶答案-模擬試卷-測試卷-期末考試題

2A第8頁共8頁一、單選題（20小題，每小題2分，共40分）得分1、若集合的基數(shù)為4，則集合上的共有（）個(gè)不同的等價(jià)關(guān)系。A．15B．16C．14D．122、集合上的關(guān)系為一個(gè)偏序關(guān)系，當(dāng)且僅當(dāng)具有（）。A．自反性、對(duì)稱性和傳遞性 B．自反性、反對(duì)稱性和傳遞性C．反自反性、對(duì)稱性和傳遞性 D．反自反性、反對(duì)稱性和傳遞3、設(shè)是集合上的二元運(yùn)算，稱元素為關(guān)于運(yùn)算“”的幺元，如果（）。A．，且對(duì)任意元素，使B．，且對(duì)任意元素，使C．，且存在元素，使D．，且存在元素，使4、設(shè)G=〈V，E〉為（ｎ，ｍ）連通圖，則要確定Ｇ的一棵生成樹，必刪去Ｇ的邊數(shù)是（）。A．ｎ－ｍ－１B．ｎ－ｍ＋１C．ｍ－ｎ＋１D．ｍ－ｎ－１5、設(shè)，為集合上的等價(jià)關(guān)系，的對(duì)應(yīng)于的劃分是，則=()。A． B．C． D．6、設(shè)是一個(gè)格，對(duì)，下列命題中不一定為真的是（）。A．B．C．D．7、n階完全圖的邊數(shù)為（）。A．n(n-1)/2B．n-1C．n+1D．2n(n-1)8、下面推理中，正確的是（）。 A．（1）(x)(F(x)G(x))P（2）F(a)G(b)USB．（1）F(a)G(b)P（2）(x)(F(x)G(x))EGC．（1）F(x)G(b)P（2）(x)(F(x)G(x))EGD．（1）(x)(F(x)G(x))P（2）F(y)G(y)US9、下面四組數(shù)能構(gòu)成無向圖的度數(shù)列的有（）。A．2,3,4,5,6,7B．1,2,2,3,4C．2,1,1,1,2D．3,3,5,6,010、設(shè)A為圖G的鄰接矩陣，的主對(duì)角線元素之和為600，則G上有（）個(gè)三角形。A．100B．200C．300D．60011、下面所示的偏序集中，哪一個(gè)是格？（）。ABCD12、下列各圖是歐拉圖的是（）。A．B．C．D．13、下面哪個(gè)偏序集構(gòu)成有界格（）。A．；B．／，其中／為整除關(guān)系；C．；D．；其中，為的冪集．14、下面哈斯圖所示的有界格中，哪個(gè)不是有補(bǔ)格（）。15、無向圖是歐拉圖，當(dāng)且僅當(dāng)（）。A．連通且所有結(jié)點(diǎn)的度數(shù)為偶數(shù)；B．的所有結(jié)點(diǎn)的度數(shù)為偶數(shù)；C．連通且所有結(jié)點(diǎn)的度數(shù)為奇數(shù)；D．的所有結(jié)點(diǎn)的度數(shù)為奇數(shù)．16、在下述公式中是重言式為（）A．? B．C． D．P（QR）17、設(shè)，以下哪一個(gè)關(guān)系是從到的滿射()。A．B．C．D．18、命題“所有的馬都比某些牛跑得快”的符號(hào)化公式為（）假設(shè)：H（x）：x是馬，C（y）：y是牛，F(xiàn)（x，y）：x跑得比y快。A．(x)(H（x）(y)((C（y）F(x,y)))B．(x)(H（x）(y)((C（y）F(x,y)))C．(x)(H（x）(y)((C（y）F(x,y)))D．(y)(x)(H（x）((C（y）F(x,y)))19、下列各式哪個(gè)是錯(cuò)的（）？A．;B．{};C．;D．{,{}20、下列符號(hào)串是合式公式的是（）A．B．C．D．二、填空題（20小題，每空1分，共20分）得分1、設(shè)〈A，≤〉是一個(gè)偏序集，如果A中任意兩個(gè)元素都有，則稱〈A，≤〉是一個(gè)格。2、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的上確界是。3、完全圖K5的連通分支數(shù)是。4、在下圖所給的偏序集中，集合的下確界是。5、設(shè)，則A的冪集=。6、設(shè)〈A,≤〉是一個(gè)有界格，如果，則稱此格為有補(bǔ)格。7、謂詞公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可滿足式）。8、設(shè)是到的函數(shù)，如果，則稱為。9、如果有一臺(tái)計(jì)算機(jī)，它有一條加法指令，可計(jì)算四個(gè)數(shù)的和。現(xiàn)有28個(gè)數(shù)需要計(jì)算和，它至少要執(zhí)行次這個(gè)加法指令。10、一棵有向樹T，若T恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1，則稱T為根樹。其中稱為樹葉。11、命題公式（PQ）（QP）的主析取范式為。12、公式的真值表中共有種真值指派。13、在任何圖中，=。14、設(shè)S為非空集合，為集合S的冪集。代數(shù)系統(tǒng)〈〉中，關(guān)于“”的零元為。15、設(shè)集合，R和S均為A上的二元關(guān)系，且，則_。16、設(shè)是集合上的二元關(guān)系，則=。17、設(shè)表示“天下雨”，表示“我騎自行車上班”，則命題“除非下雨，否則我騎自行車上班”符號(hào)化為。18、設(shè)S為非空集合，為集合S的冪集。代數(shù)系統(tǒng)〈〉中，關(guān)于“”的零元為。19、設(shè)N為自然數(shù)集合，在N上定義運(yùn)算☆：對(duì)任意a，b∈N，a☆b=a+b+3，則〈N，☆〉不是一個(gè)群，因?yàn)椤?0、設(shè)R是實(shí)數(shù)集合，，，且，則。三、簡答題（4小題，每小題6分，共24分）得分1、對(duì)有向圖，通過鄰接矩陣解下列問題：（1）從到長度為4的路有幾條？（2）中長度為3的回路有幾條？2、以給定權(quán)2，4，5，8，13，15，18，25構(gòu)造一棵最優(yōu)二叉樹。3、設(shè)={2，3，6，12，24，36},”/”為的整除關(guān)系，(1)．說明〈，／〉是否為偏序集，若是，畫出其哈斯圖；(2)．說明〈，／〉是否為格？為什么？4、設(shè)Z是整數(shù)集，是Z上的模3同余關(guān)系，即，試根據(jù)等價(jià)關(guān)系決定Z的一個(gè)劃分。四、證明題（2小題，每小題8分，共16分）得分1、設(shè)為，證明：是雙射。2、符號(hào)化下列命題并推證其結(jié)論。任何人如果違反交通規(guī)則，就要被處罰；總有些人違反了交通規(guī)則。因此有些人被處罰。（使用全總個(gè)體域，設(shè)：是人，：違反交通規(guī)則，：被處罰）。一、單選題（20小題，每小題2分，共40分）1、A2、B3、A4、C5、C6、D7、A8、D9、B10、B11、B12、B13、D14、A15、A16、B17、B18、C19、C20、C二、填空題（20小題，每空1分，共20分）1、最大下界和最小上界2、123、14、5、6、集合A中的每一個(gè)元素都存在補(bǔ)元7、矛盾式8、滿射9、910、出度為0的結(jié)點(diǎn)11、或（PQ）（PQ）（PQ）12、1613、2│E│14、15、{<1,3>,<3,1>}16、17、18、S19、〈N，☆〉中不存在幺元20、三、簡答題（4小題，每小題6分，共24分）1、解：，（1分）（1分）所以，（1）從到長度為4的路有4條。它們是：；；；。（2分）（2）中長度為3的回路有3條。它們是：；；。（2分）2、（根據(jù)樹的完整程度酌情減分）3、解：(1)．〈，／〉是偏序集．其哈斯圖為：（4分）(2)．〈，／〉不是格．因?yàn)?和3無下確界或24和36無上確界（2分）4、答案：由決定的Z的劃分為：，其中：四、證明題（2小題，每小題8分，共16分）1、證明：1）先證明是入射（3分）對(duì)任意的則有，從而有，故是入射。2)再證明是滿射（3分）對(duì)任意的從而是滿射。綜合（1）、（2）知是雙射。（2分）2、命題符號(hào)化為：（2分）證明：(1)P(2)ES(1)（1分）(3)T(2)I（1分）(4)P(5)US(4)（1分）(6)T(2)(5)I（1分）(7)T(3)(6)I（1分）(8)EG(7)（1分）一、單選題（20小題，每小題2分，共40分）得分1、設(shè)是一個(gè)格，對(duì)，下列命題中不一定為真的是（）。A．B．C．D．2、下列各式哪個(gè)是錯(cuò)的（）？A．B．{}C．D．{,{}3、設(shè)是集合上的二元運(yùn)算，稱元素為關(guān)于運(yùn)算“”的幺元，如果（）。A．，且對(duì)任意元素，使B．，且對(duì)任意元素，使C．，且存在元素，使D．，且存在元素，使4、設(shè)G=〈V，E〉為（ｎ，ｍ）連通圖，則要確定Ｇ的一棵生成樹，必刪去Ｇ的邊數(shù)是（）。A．ｎ－ｍ－１B．ｎ－ｍ＋１C．ｍ－ｎ＋１D．ｍ－ｎ－１5、在下述公式中是重言式為（）。A．? B．C． D．P（QR）6、無向圖是歐拉圖，當(dāng)且僅當(dāng)（）。A．連通且所有結(jié)點(diǎn)的度數(shù)為偶數(shù)B．的所有結(jié)點(diǎn)的度數(shù)為偶數(shù)C．連通且所有結(jié)點(diǎn)的度數(shù)為奇數(shù)D．的所有結(jié)點(diǎn)的度數(shù)為奇數(shù)7、下面推理中，正確的是（）。 A．（1）(x)(F(x)G(x))P（2）F(a)G(b)USB．（1）F(a)G(b)P（2）(x)(F(x)G(x))EGC．（1）F(x)G(b)P（2）(x)(F(x)G(x))EGD．（1）(x)(F(x)G(x))P（2）F(y)G(y)US8、下面所示的偏序集中，哪一個(gè)是格？（）。ABCD9、下面哈斯圖所示的有界格中，哪個(gè)不是有補(bǔ)格（）。10、下面哪個(gè)偏序集構(gòu)成有界格（）。A．B．／，其中／為整除關(guān)系C．D．；其中，為的冪集11、命題“所有的馬都比某些牛跑得快”的符號(hào)化公式為（）。假設(shè)：H（x）：x是馬，C（y）：y是牛，F(xiàn)（x，y）：x跑得比y快。A．(x)(H（x）(y)((C（y）F(x,y)))B．(x)(H（x）(y)((C（y）F(x,y)))C．(x)(H（x）(y)((C（y）F(x,y)))D．(y)(x)(H（x）((C（y）F(x,y)))12、設(shè)A為圖G的鄰接矩陣，的主對(duì)角線元素之和為600，則G上有（）個(gè)三角形。A．100B．200C．300D．60013、下列符號(hào)串是合式公式的是（）A、B、C、D、14、集合上的關(guān)系為一個(gè)偏序關(guān)系，當(dāng)且僅當(dāng)具有（）。A．自反性、對(duì)稱性和傳遞性 B．自反性、反對(duì)稱性和傳遞性C．反自反性、對(duì)稱性和傳遞性 D．反自反性、反對(duì)稱性和傳遞15、設(shè)，為集合上的等價(jià)關(guān)系，的對(duì)應(yīng)于的劃分是，則=()。A． B．C． D．16、n階完全圖的邊數(shù)為（）。A．n(n-1)/2B．n-1C．n+1D．2n(n-1)17、下列各圖是歐拉圖的是（）。ABCD18、若集合的基數(shù)為4，則集合上的共有（）個(gè)不同的等價(jià)關(guān)系。A．15B．16C．14D．1219、設(shè)，以下哪一個(gè)關(guān)系是從到的滿射()。A．B．C．D．20、下面四組數(shù)能構(gòu)成無向圖的度數(shù)列的有（）。A．2,3,4,5,6,7B．1,2,2,3,4C．2,1,1,1,2D．3,3,5,6,0二、填空題（20小題，每空1分，共20分）得分1、設(shè)S為非空集合，為集合S的冪集。代數(shù)系統(tǒng)〈〉中，關(guān)于“”的零元為。2、設(shè)〈A,≤〉是一個(gè)有界格，如果，則稱此格為有補(bǔ)格。3、設(shè)R是實(shí)數(shù)集合，，，且，則。4、設(shè)〈A，≤〉是一個(gè)偏序集，如果A中任意兩個(gè)元素都有，則稱〈A，≤〉是一個(gè)格。5、公式的真值表中共有種真值指派。6、命題公式（PQ）（QP）的主析取范式為。7、在下圖所給的偏序集中，集合的下確界是。8、完全圖K5的連通分支數(shù)是。9、設(shè)是集合上的二元關(guān)系，則=。10、設(shè)N為自然數(shù)集合，在N上定義運(yùn)算☆：對(duì)任意a，b∈N，a☆b=a+b+3，則〈N，☆〉不是一個(gè)群，因?yàn)椤?1、設(shè)表示“天下雨”，表示“我騎自行車上班”，則命題“除非下雨，否則我騎自行車上班”符號(hào)化為。12、設(shè)集合，R和S均為A上的二元關(guān)系，且，則_。13、設(shè)是到的函數(shù)，如果，則稱為。14、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除關(guān)系，則集合={2,3,4,6}的上確界是。15、設(shè)S為非空集合，為集合S的冪集。代數(shù)系統(tǒng)〈〉中，關(guān)于“”的零元為。16、在任何圖中，=。17、如果有一臺(tái)計(jì)算機(jī)，它有一條加法指令，可計(jì)算四個(gè)數(shù)的和?，F(xiàn)有28個(gè)數(shù)需要計(jì)算和，它至少要執(zhí)行次這個(gè)加法指令。18、設(shè)，則A的冪集=。19、一棵有向樹T，若T恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1，則稱T為根樹。其中稱為樹葉。20、謂詞公式（F（x,y）R（x,y））R（x,y）是（重言式，矛盾式，可滿足式）。三、簡答題（4小題，每小題6分，共24分）得分1、設(shè)Z是整數(shù)集，是Z上的模3同余關(guān)系，即，試根據(jù)等價(jià)關(guān)系決定Z的一個(gè)劃分。2、以給定權(quán)2，4，5，8，13，15，18，25構(gòu)造一棵最優(yōu)二叉樹。3、對(duì)有向圖，通過鄰接矩陣解下列問題：（1）從到長度為4的路有幾條？（2）中長度為3的回路有幾條？4、設(shè)={2，3，6，12，24，36},”/”為的整除關(guān)系，(1)．說明〈，／〉是否為偏序集，若是，畫出其哈斯圖；(2)．說明〈，／〉是否為格？為什么？四、證明題（2小題，每小題8分，共16分）得分1、符號(hào)化下列命題并推證其結(jié)論．任何人如果違反交通規(guī)則，就要被處罰；總有些人違反了交通規(guī)則。因