中央电大离散数学(本科)考试试题

1中央电大离散数学（本科）考试试题一、单项选择题（每小题3分，本题共15分）1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(a)．A．AB，且ABB．BA，且ABC．AB，且ABD．AB，且AB2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是(d)．图一A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的3．设图G的邻接矩阵为0101010010000011100100110则G的边数为(b)．A．6B．5C．4D．34．无向简单图G是棵树，当且仅当(a)．A．G连通且边数比结点数少1B．G连通且结点数比边数少1C．G的边数比结点数少1D．G中没有回路．5．下列公式(c)为重言式．A．PQPQB．(Q(PQ))(Q(PQ))C．(P(QP))(P(PQ))D．(P(PQ))Q1．若集合A={a，b}，B={a，b，{a，b}}，则（a）．A．AB，且ABB．AB，但ABC．AB，但ABD．AB，且AB2．集合A={1,2,3,4,5,6,7,8}上的关系R={x，y|x+y=10且x,yA}，则R的性质为（b）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（b）个．A．0B．2C．1D．34．如图一所示，以下说法正确的是(d)．A．{(a,e)}是割边B．{(a,e)}是边割集C．{(a,e),(b,c)}是边割集D．{(d,e)}是边割集图一5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（c）．A．(x)(A(x)∧B(x))B．┐(x)(A(x)∧B(x))C．┐(x)(A(x)→B(x))D．┐(x)(A(x)∧┐B(x))1．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={a，2,b，2}，R2={a，1,a，2,b，1}，R3={a，1,b，2}，则（b）不是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R32．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为(b)．A．8、2、8、2B．无、2、无、2C．6、2、6、2D．8、1、6、13．若集合A的元素个数为10，则其幂集的元素个数为（a）．A．1024B．10C．100D．14．设完全图Kn有n个结点(n≥2)，m条边，当（c）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数5．已知图G的邻接矩阵为2，则G有（d）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边1．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是(c)．A．{a，{a}}AB．{2}AC．{a}AD．A2．设图G＝V,E，vV，则下列结论成立的是(c)．A．deg(v)=2EB．deg(v)=EC．EvVv2)deg(D．EvVv)deg(3．命题公式（P∨Q）→R的析取范式是(d)A．（P∨Q）∨RB．（P∧Q）∨RC．（P∨Q）∨RD．（P∧Q）∨R4．如图一所示，以下说法正确的是(a)．A．e是割点B．{a,e}是点割集C．{b,e}是点割集D．{d}是点割集5．下列等价公式成立的为(b)．A．PQPQB．P(QP)P(PQ)C．Q(PQ)Q(PQ)D．P(PQ)Q1．若G是一个汉密尔顿图，则G一定是(d)．A．平面图B．对偶图C．欧拉图D．连通图2．集合A={1,2,3,4}上的关系R={x，y|x=y且x,yA}，则R的性质为（c）．A．不是自反的B．不是对称的C．传递的D．反自反3．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集A，上的元素5是集合A的（b）．A．最大元B．极大元C．最小元D．极小元4．图G如图一所示，以下说法正确的是(c)．A．{(a,d)}是割边B．{(a,d)}是边割集C．{(a,d),(b,d)}是边割集D．{(b,d)}是边割集图一5．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（a）．A．(x)(A(x)∧B(x))B．(x)(A(x)∧B(x))C．┐(x)(A(x)→B(x))D．┐(x)(A(x)∧┐B(x))1．若集合A＝{a，{a}}，则下列表述正确的是(a)．A．{a}AB．{{{a}}}AC．{a，{a}}AD．A2．命题公式（P∨Q）的合取范式是(c)A．（P∧Q）B．（P∧Q）∨（P∨Q）C．（P∨Q）D．（P∧Q）3．无向树T有8个结点，则T的边数为(b)．A．6B．7C．8D．94．图G如图一所示，以下说法正确的是(b)．A．a是割点B．{b,c}是点割集C．{b,d}是点割集D．{c}是点割集图一5．下列公式成立的为(d)．A．P∧QP∨QB．PQPQC．QPPD．P∧(P∨Q)Q1．“小于5的非负整数集合”采用描述法表示为___a___．3A．{xxN,x5}B．{xxR,x5}C．{xxZ,x5}D．{xxQ,x5}2．设R1，R2是集合A={a,b,c,d}上的两个关系，其中R1={(a,a),(b,b),(b,c),(d,d)}，R2={(a,a),(b,b),(b,c),(c,b),(d,d)}，则R2是R1的__b____闭包．A．自反B．对称C．传递D．以上答案都不对3．设函数f：R→R，f(a)=2a+1；g：R→R，g(a)=a2，则___c___有反函数．A．fgB．gfC．fD．g4．已知图G的邻接矩阵为0111110101110001000111010，则图G有___d___．A．5点，8边B．6点，7边C．6点，8边D．5点7边5．无向完全图K4是___a___．A．汉密尔顿图B．欧拉图C．非平面图D．树6．在5个结点的完全二叉树中，若有4条边，则有___b___片树叶．A．2B．3C．4D．57．无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有__c___个4度结点．A．3B．2C．1D．08．与命题公式P（QR）等值的公式是___a___．A．(PQ)RB．(PQ)RC．(PQ)RD．P(QR)9．谓词公式)())()((xQyyRxPx中量词x的辖域是___b___．A．))()((yyRxPxB．)()(yyRxPC．P(x)D．)(xQ10．谓词公式))()(()(xxQxQxxxP的类型是___c___．A．蕴涵式B．永假式C．永真式D．非永真的可满足式1．设A={1,2,3,4}，B={1,3}，C={-1,0,1,2}，则___a___．A．ABB．CBC．ABD．CB2．若集合A的元素个数为10，则其幂集的元素个数为___b___．A．1000B．1024C．1D．103．设集合A={1,2}，B={a,b}，C={}，则CBA)(__c____．A．{1,a,,1,b,,2,a,,2,b,}B．{1,a,,1,b,,2,a,,2,b,}C．{1,a,,1,b,,2,a,,2,b,}D．{{1,2},{a,b},{}}4．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为___d___．A．8、1、6、1B．8、2、8、2C．6、2、6、2D．无、2、无、25．有5个结点的无向完全图K5的边数为___a___．A．10B．20C．5D．256．设完全图Kn有n个结点(n≥2)，m条边，当___b___时，Kn中存在欧拉回路．A．n为偶数B．n为奇数C．m为偶数D．m为奇数7．一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有__c___个顶点．A．3B．8C．11D．138．命题公式（P∨Q）→R的析取范式是___b___．A．（P∧Q）∨RB．（P∨Q）∨RC．（P∧Q）∨RD．（P∨Q）∨R9．下列等价公式成立的是___b___．A．PQPQB．P(QP)P(PQ)C．P(PQ)QD．Q(PQ)Q(PQ)10．谓词公式))()(()(xxQxQxxxP的类型是__c____．A．蕴涵式B．永假式C．永真式D．非永真的可满足式二、填空题（每小题3分，本题共15分）6．命题公式)(PQP的真值是T（或1）．7．若图G=V,E中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前4缀码．9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．10．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y)中的y6．若集合A的元素个数为10，则其幂集的元素个数为1024．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为8．8．若A={1,2}，R={x,y|xA,yA,x+y=10}，则R的自反闭包为{1,1,2,2}．9．结点数v与边数e满足e=v-1关系的无向连通图就是树．6．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b}}．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2个．8．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．9．设连通平面图G的结点数为5，边数为6，则面数为3．10．设个体域D＝{a,b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为(A(a)∧A(b))∧(B（a）∨B（b）)．6．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，},,{BAyxByAxyxR且且则R的有序对集合为{2,2，2,3，3,2}，3,3．7．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．8．设G＝V,E是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．9．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数10．设个体域D＝{1,2}，则谓词公式)(xxA消去量词后的等值式为A(1)A(2)6．命题公式)(PQP的真值是T（或1）．7．若图G=V,E中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前缀码．9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．10．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y)中的y6．若集合A的元素个数为10，则其幂集的元素个数为1024．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为8．8．若A={1,2}，R={x,